Linear-feedback shift register

A binary linear-feedback shift register of degree $d$ updates a $d$-bit state by shifting and inserting a fixed linear combination over ${\mathbb{F}}_2$. With recurrenceits feedback polynomial is $x^d+a_{d-1}{x}^{d-1}+\cdots +a_0$.

Under the convention that a register emits each shifted-out symbol, its first $d$ output symbols are exactly its initial fill. Thus a binary register of length $d$ has $2^d-1$ distinct outputs from nonzero fills. For lengths $r<s$, at least one longer-register output is absent from the shorter register, guaranteeing a pair of unequal nonzero outputs. The two sets need not be disjoint: recurrences $s_{n+1}=s_n$ and $s_{n+2}=s_n$ both generate constant ones. Nor must they intersect: the length-one recurrence and $s_{n+2}=s_{n+1}+s_n$ have no common nonzero output, since constant ones fail the second recurrence.

The feedback polynomial records the coefficients of an LFSR recurrence. With the conventionit is $x^d+a_{d-1}{x}^{d-1}+\cdots +a_0$.

A feedback shift register updates a finite state by shifting its stored symbols and inserting the value of a feedback function of the previous state. The feedback function need not be linear.

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

A degree-$d$ binary register has $2^d$ states. The zero state is fixed, so a nonzero periodic orbit has length at most $2^d-1$.

A maximal-period feedback polynomial cannot have $1$ as a root. Over ${\mathbb{F}}_2$, this saysso an even number of the coefficients $a_i$ equal one and the full monic polynomial has an odd number of nonzero coefficients.

If an output prefix contains $d$ consecutive zeros followed by a one, no register of degree at most $d$ can generate it: the all-zero state would have been reached and would remain zero forever.

The seven consecutive zeros followed by one force degree at least eight. Degree eight is attained by $s_{n+8}=s_n$, with initial state $10000000$ and feedback polynomial $x^8+1$.

Let $K={\mathbb{F}}_{2^d}$, let $\alpha$ generate $K^{\times }$, and let $T:K\to {\mathbb{F}}_2$ be nonzero linear with nondegenerate bilinear form $(x,y)\mapsto T(xy)$. If the minimal polynomial of $\alpha$ is $P(X)=X^d+{\sum }_{j<d}{c}_j{X}^j$, then $x_n=T({\alpha }^n)$ satisfiesso it is produced by an LFSR of length at most $d$. Its period is exactly $2^d-1$: any period $r$ would imply $T(({\alpha }^r-1)y)=0$ for every $y\in K$, hence ${\alpha }^r=1$ by nondegeneracy.