Berlekamp-Massey algorithm

The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.

Suppose a connection polynomial $C$ of degree at most $L$, with recurrence span $L$ gives zero recurrence discrepancies through index $r-1$ but a nonzero discrepancy at $r$. If a polynomial $D$ of span $L^{\prime }$ successfully explains the prefix through $r$ and $L+L^{\prime }\le r$, evaluate the coefficient at $r$ in the convolution $(CD)x$. Applying $D$ first makes it zero. Applying $C$ first leaves its nonzero discrepancy at $r$, because the earlier discrepancies vanish and $D$ 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 $11001011$ has length three:Its connection polynomial is $1+D^2+D^3$.