Berlekamp–Massey algorithm: Difference between revisions

Revision as of 21:19, 22 March 2008

Revision as of 16:02, 5 June 2008

Line 1:

The '''Berlekamp-MasseyBerlekamp–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 [[James Massey]] the following year. It became the key to practical application of the now ubiquitous [[Reed-SolomonReed–Solomon error correction|Reed-SolomonReed–Solomon code]].

==External links==

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

* {{MathWorld|urlname=Berlekamp-MasseyAlgorithm|title=Berlekamp-MasseyBerlekamp–Massey Algorithm}}

* [http://modp.com/release/mma_lfsr/ Implementation in Mathematica]

* [http://www.informationsuebertragung.ch/indexAlgorithmen.html Applet Berlekamp-MasseyBerlekamp–Massey algorithm]

{{Comp-sci-stub}}