Editing Berlekamp–Massey algorithm (section)

{{Short description|Algorithm on linear-feedback shift registers}}
{{distinguish|Berlekamp's algorithm}}
[[File:Berlekamp–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>

[[Elwyn Berlekamp]] invented an algorithm for decoding [[BCH code|Bose–Chaudhuri–Hocquenghem (BCH) codes]].<ref>{{Citation
 |last= Berlekamp
 |first= Elwyn R.
 |author-link= Elwyn Berlekamp
 |title= Nonbinary BCH decoding
 |year= 1967
 |series= International Symposium on Information Theory
 |place= San Remo, Italy}}</ref><ref>{{Citation
 |last= Berlekamp
 |first= Elwyn R.
 |author-link= Elwyn Berlekamp
 |title=Algebraic Coding Theory
 |place=Laguna Hills, CA
 |orig-year=1968
 |year=1984
 |edition= Revised
 |publisher=Aegean Park Press
 |isbn= 978-0-89412-063-3}}. 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
 |author-link= James Massey
 |title= Shift-register synthesis and BCH decoding
 |journal= IEEE Transactions on Information Theory
 |volume= IT-15
 |issue= 1
 |date= January 1969
 |pages= 122–127
 |url= http://crypto.stanford.edu/~mironov/cs359/massey.pdf
 |doi= 10.1109/TIT.1969.1054260
 |s2cid= 9003708
 }}</ref><ref>{{Citation
 |last1= Ben Atti
 |first1= Nadia
 |last2= Diaz-Toca
 |first2= Gema M.
 |last3= Lombardi
 |first3= Henri
 |title= The Berlekamp–Massey Algorithm revisited
 |journal= Applicable Algebra in Engineering, Communication and Computing
 |date=April 2006 |volume=17 |issue=1 |pages=75–82 
 |citeseerx=10.1.1.96.2743
 |url= http://hlombardi.free.fr/publis/ABMAvar.html
 |doi= 10.1007/s00200-005-0190-z
|arxiv= 2211.11721
 |s2cid= 14944277
 }}</ref> Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm),<ref>{{Harvnb|Massey|1969|p=124}}</ref> but it is now known as the Berlekamp–Massey algorithm.