Berlekamp–Massey algorithm: Difference between revisions

Revision as of 21:22, 9 January 2021

Revision as of 20:25, 29 January 2021

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

|authorlinkauthor-link= Elwyn Berlekamp

|title= Nonbinary BCH decoding

|year= 1967

Line 12:

|last= Berlekamp

|first= Elwyn R.

|authorlinkauthor-link= Elwyn Berlekamp

|title=Algebraic Coding Theory

|place=Laguna Hills, CA

|origyearorig-year=1968

|year=1984

|edition= Revised

Line 22:

|first= J. L.

|last= Massey

|authorlinkauthor-link= James Massey

|title= Shift-register synthesis and BCH decoding

|journal= IEEE Transactions on Information Theory