Berlekamp–Massey algorithm: Difference between revisions

Revision as of 03:25, 17 December 2009

Revision as of 14:40, 21 December 2009

Line 1:

{{distinguish|Berlekamp's algorithm}}

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 linearly [[Recurrence relation| recurrent sequence]].

The algorithm was invented by [[Elwyn Berlekamp]] in 1968.<ref>''Algebraic Coding Theory'', [[New York City|New York]]: [[McGraw-Hill]], 1968. Revised ed., Aegean Park Press, 1984, ISBN 0894120638.</ref> Its connection to linear codes was observed by [[James Massey]] the following year.<ref>J. L. Massey, [http://www.google.com/url?sa=t&source=web&ct=res&cd=1&ved=0CAcQFjAA&url=http%3A%2F%2Fcrypto.stanford.edu%2F~mironov%2Fcs359%2Fmassey.pdf&ei=GBIkS56YBpOMMqauleMJ&usg=AFQjCNEXiuUFcZNbLHE0kFtRLC2cSssvHQ&sig2=U3lCCnFjuYeuWorbXQ_Lyg Shift-register synthesis and BCH decoding], IEEE Trans. Information Theory, IT-15 (1969), 122-127.</ref> It became the key to practical application of the now ubiquitous [[Reed–Solomon error correction|Reed–Solomon code]].

Line 124:

==External links==

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

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

Line 130 ⟶ 129:

* {{de icon}} [http://www.informationsuebertragung.ch/indexAlgorithmen.html Applet Berlekamp–Massey algorithm]

{{Expand|date=December 2009}}

{{expand}}

[[Category:Error detection and correction]]