Berlekamp–Massey algorithm: Difference between revisions

Revision as of 20:44, 5 February 2019

Revision as of 22:44, 10 February 2019

Line 1:

{{distinguish|Berlekamp's 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 |last=Reeds |first=J. A. |last2=Sloane |first2=N. J. A. |authorlink2=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>

[[Elwyn Berlekamp]] invented an algorithm for decoding [[BCH code|Bose–Chaudhuri–Hocquenghem (BCH) codes]].<ref>{{Citation

Line 19:

|edition= Revised

|publisher=Aegean Park Press

|isbn= 978-0-89412-063-83}}. Previous publisher McGraw-Hill, New York, NY.</ref> [[James Massey]] recognized its application to linear feedback shift registers and simplified the algorithm.<ref>{{Citation

|first= J. L.

|last= Massey

Line 29:

|year= 1969

|pages= 122–127

|url= http://crypto.stanford.edu/~mironov/cs359/massey.pdf|doi= 10.1109/TIT.1969.1054260
}}</ref><ref>{{Citation

|last= Ben Atti

|first= Nadia