The Berlekamp-Massey algorithm finds a shortest linear recurrence consistent with a finite sequence over a field. It returns a register length and a connection polynomial such thatMissing coefficients are zero; for a finite prefix the polynomial degree of can be less than . The output describes the shortest recurrence for the observed prefix, rather than proving how an unknown infinite sequence continues.
Initialize , , , and . At index , compute the discrepancy . If , increase by one. Otherwise save and replace by . If , also set , , , and ; if , only increase . The saved discrepancy cancels the current failure of the linear recurrence, while the update of accounts for the extra memory it requires.[ref]
Shift-Register Synthesis and BCH Decoding by James L. Massey. Sections II–III: register length, discrepancy, and synthesis algorithm
For the binary prefix , the result is and , corresponding to over the field with two elements. This is useful both in analyzing a linear-feedback shift register and in constructing a BCH code error-locator polynomial.
Suppose a connection polynomial of degree at most , with recurrence span gives zero recurrence discrepancies through index but a nonzero discrepancy at . If a polynomial of span successfully explains the prefix through and , evaluate the coefficient at in the convolution . Applying first makes it zero. Applying first leaves its nonzero discrepancy at , because the earlier discrepancies vanish and has constant coefficient one. This contradiction gives the displayed lower bound. It is the minimality step used by the Berlekamp-Massey algorithm; the algorithm cancels the new discrepancy with a shifted earlier failed polynomial.
The shortest binary linear recurrence producing the prefix has length three:Its connection polynomial is .
Articles by others on the same topic
The Berlekamp–Massey algorithm is a fundamental algorithm in coding theory and information theory used to find the shortest linear feedback shift register (LFSR) that can generate a given finite sequence of output. It is particularly useful for determining the linear recurrence relations for a sequence, which is essential in applications such as error correction coding, cryptography, and sequence analysis.