Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 4 / 4H / Solution

A general feedback shift register of length $d$ over an alphabet $A$ stores $(s_n,\dots ,s_{n+d-1})$, outputs $s_n$, and shifts to $(s_{n+1},\dots ,s_{n+d-1},F(s_n,\dots ,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}_j{s}_{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 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.