Berlekamp-Massey algorithm
From Free net encyclopedia
Revision as of 16:59, 18 March 2006; view current revision
←Older revision | Newer revision→
←Older revision | Newer revision→
The Berlekamp-Massey algorithm is an algorithm for finding the shortest linear feedback shift register (LFSR) for a given output sequence. Equivalently, it is an algorithm for finding the minimal polynomial of a linearly recurrent sequence.
The algorithm was invented by Elwyn Berlekamp in 1968. Its connection to linear codes was observed by J. L. Massey the following year. It became the key to practical application of the now ubiquitous Reed-Solomon code.
[edit]