Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 4 / 4G (Coding and Cryptography)

A binary linear-feedback shift register stores $L$ bits, shifts them at each clock step, and inserts a fixed linear combination over ${\mathbb{F}}_2$ of the stored bits. Its output obeys a recurrence $s_n+c_1{s}_{n-1}+\cdots +c_L{s}_{n-L}=0$. Write its connection polynomial as $C(D)=1+c_{1}D+\cdots +c_L{D}^L$; the corresponding monic feedback polynomial is $z^{L}C(z^{-1})$.

The Berlekamp-Massey algorithm maintains the shortest recurrence fitting the observed prefix. Initialize $C=B=1$, length $L=0$, displacement $m=1$, and previous nonzero discrepancy $b=1$. At symbol $n$, calculate $d=s_n+{\sum }_{j=1}^L{c}_j{s}_{n-j}$. If $d=0$, increase $m$. If $d\ne 0$, save $T=C$ and replace $C$ by $C-(d/b)D^{m}B$. If $2L\le n$, replace $L$ by $n+1-L$, $B$ by $T$, $b$ by $d$, and $m$ by $1$; otherwise only increase $m$. In the binary field subtraction equals addition. The shifted previous discrepancy polynomial cancels the current discrepancy while preserving earlier equations. A failed recurrence of length $L$ at position $n$ requires a corrected length at least $n+1-L$ when this exceeds $L$, explaining the length update. Thus the algorithm recovers the shortest compatible register; a known bound $L$ and at least $2L$ output symbols suffice to identify its minimal recurrence.

For the printed twelve-bit prefix, the nonzero discrepancies occur at positions $n=0,1,2,5,6,7$ (indexing from zero). The successive updated pairs $(L,C)$ areAll remaining discrepancies vanish. ThereforeThe first four observed bits are the fill. Length four is necessary: a length-three recurrence would need to hold already at $n=3$ and no such recurrence fits the prefix. Indeed the equations at $n=3,4,5$ force $c_2=1$, $c_1+c_3=0$, $c_1+c_3=1$, a contradiction. Finite observations cannot rule out longer nonminimal registers.