Content deleted Content added
added Category:Articles with example code using HotCat |
Citation bot (talk | contribs) Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with example code | #UCB_Category 75/101 |
||
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 |
[[Elwyn Berlekamp]] invented an algorithm for decoding [[BCH code|Bose–Chaudhuri–Hocquenghem (BCH) codes]].<ref>{{Citation
Line 32:
|doi= 10.1109/TIT.1969.1054260
}}</ref><ref>{{Citation
|
|
|last2= Diaz-Toca
|first2= Gema M.
Line 44:
|url= http://hlombardi.free.fr/publis/ABMAvar.html
|doi= 10.1007/s00200-005-0190-z
|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.
==Description of algorithm==
| |||