벌러캠프-매시 알고리즘

벌러캠프-매시 알고리즘은 주어진 수열을 만들 수 있는 가장 작은 선형 귀환 시프트 레지스터를 찾는 알고리즘이다. 다시 말해, 선형 점화식의 최소 다항식을 구하는 알고리즘이다.

역사

엘윈 랠프 벌러캠프(영어: Elwin Berlekamp)가 1968년에 고안했으며, 제임스 리 매시(영어: James Lee Massey)가 이듬해에 이것이 선형 부호와 연관이 있다는 사실을 발견했다. 오늘날에 널리 쓰이는 리드 솔로몬 부호를 실용화하는데 중요한 구실을 했다.

외부 링크

• 온라인 구현 //서버에 없는 페이지
• [https://web.archive.org/web/20120716181541/http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html Archived 2012년 7월 16일 - 웨이백 머신 PlanetMath의 알고리즘 설명] //페이지 낫 파운드