Berlekamp–Massey algorithm: Difference between revisions

Revision as of 04:55, 27 February 2025

Revision as of 04:21, 5 March 2025

Line 1:

{{Short description|Algorithm on linear-feedback shift registers}}

{{distinguish|Berlekamp's algorithm}}

[[File:Berlekamp–Massey_algorithmBerlekamp–Massey algorithm.png | thumb | right | Berlekamp–Massey algorithm]]

The '''Berlekamp–Massey algorithm''' is an [[algorithm]] that will find the shortest [[linear-feedback shift register]] (LFSR) for a given binary output sequence. The algorithm will also find the [[Minimal polynomial (field theory)|minimal polynomial]] of a linearly [[Recurrence relation|recurrent sequence]] in an arbitrary [[field (mathematics)|field]]. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse.<ref>{{Harvnb|Reeds|Sloane|1985|p=2}}</ref> Reeds and Sloane offer an extension to handle a [[ring (mathematics)|ring]].<ref>{{Citation |last1=Reeds |first1=J. A. |last2=Sloane |first2=N. J. A. |author-link2=N. J. A. Sloane |journal=SIAM Journal on Computing |volume=14 |issue=3 |pages=505–513 |year=1985 |title=Shift-Register Synthesis (Modulo n) |url=http://neilsloane.com/doc/Me111.pdf |doi=10.1137/0214038 |citeseerx=10.1.1.48.4652 }}</ref>

Line 127:

polynomial(field K) T(x) = C(x);

C(x) = C(x) - d b^-1−1 x^m B(x);

L = n + 1 - L;

B(x) = T(x);

Line 134:

} else {

/* step 4. */

C(x) = C(x) - d b^-1−1 x^m B(x);

m = m + 1;

}