Berlekamp–Massey algorithm: Difference between revisions

Revision as of 17:43, 8 March 2005

Revision as of 18:30, 22 July 2005

Line 1:

The '''Berlekamp-Massey algorithm''' is an [[algorithm]] for finding the shortest [[linear feedback shift register]] (LFSR) for a given output sequence. Equivalently, it is an algorithm for finding the [[minimal polynomial]] of a [[Recurrence relation|linearly recurrent sequence]].

The algorithm was invented by [[Elwyn Berlekamp]] in 1968. Its connection to linear codes was observed by [[J.L. Massey]] the following year. It became the key to practical application of the now ubiquitous [[Reed-Solomon error correction|Reed-Solomon code]].

==External links==

* [http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html Berlekamp-Massey algorithm] at [[PlanetMath]].

* [http://www.paulisageek.com/school/ some related papers]

* [http://www.paulisageek.com/school/pmat519/berlekamp-massey.php An online implementation]

<!--(both of these links appear to be dead, keep googling)-->

{{crypto-stub}}