= Minimum recurrence length after a new discrepancy
{title2=$L'\geq r+1-L$}
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'$ successfully explains the prefix through $r$ and $L+L'\leq 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.
Back to article page
