= Solution
A general <feedback shift register> of length $d$ over an alphabet $A$ stores $(s_n,\ldots,s_{n+d-1})$, outputs $s_n$, and shifts to $(s_{n+1},\ldots,s_{n+d-1},F(s_n,\ldots,s_{n+d-1}))$ for a fixed function $F:A^d\to A$. When the alphabet is a field $K$, it is a <linear-feedback shift register> if $F$ is linear over $K$, equivalently $s_{n+d}=\sum_{j=0}^{d-1}a_js_{n+j}$ for fixed coefficients in $K$. The binary case uses the <finite field> $K=\mathbb F_2$; the examples and counterexamples below are binary.
For a genuinely nonlinear example take length three and $F(a,b,c)=a+bc$. Its values at $(0,1,0)$ and $(0,0,1)$ are both zero, but its value at their sum $(0,1,1)$ is one, violating additivity. Thus \b[this general register is not linear]. It even has an invertible state update: from $(b,c,d)$ the old leading bit is $a=d+bc$, so the counterexample does not rely on allowing singular registers.
Back to article page
