Berlekamp–Massey algorithm: Difference between revisions

Revision as of 10:22, 28 September 2009

Revision as of 22:13, 12 December 2009

Line 2:

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]].

==The algorithm==

#Let <math>s_0, s_1, s_2 ... s_n</math> be the [[bit]]s of the stream.

#Initialise three arrays <math>b</math>, <math>c</math> and <math>t</math> each of length <math>n</math> to be zeroes, except <math>b_0 \leftarrow 1, c_0 \leftarrow 1</math>; [[Assignment (computer science)|assign]] <math>N \leftarrow 0, L \leftarrow 0, m \leftarrow -1</math>.

Line 121 ⟶ 120:

==See also==

* [[Reeds-Sloane algorithm]], an extension for sequences over integers mod ''n''

==References==

{{ref-list}}

==External links==