Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 3K / Solution

A binary linear-feedback shift register of degree $d$ has a state
$(s_n,\dots ,s_{n+d-1})\in {\mathbb{F}}_2^d$ and recurrenceIts feedback polynomial is

There are $2^d$ states, and the zero state is fixed. A nonzero periodic orbit therefore visits at most the other $2^d-1$ states, proving the period bound for a linear-feedback shift register.

For a maximal orbit with $d>1$, the all-one state cannot itself be fixed. From that state the incoming bit is $a_0+\cdots +a_{d-1}$ in ${\mathbb{F}}_2$. If an odd number of the $a_i$ were one, the incoming bit would be one and the all-one state would be fixed. Hence an even number of the $a_i$ are one; including the leading coefficient, the feedback polynomial has an odd number of nonzero coefficients. This is the feedback-polynomial parity condition for maximal period.

The given prefix has seven consecutive zeros followed by a one. Any register of degree at most seven would therefore enter the all-zero state before producing the final one, which is impossible. Degree eight is attained bywith initial state $10000000$. It produces the next bit $1$ and has feedback polynomialThus this is the minimal linear-feedback shift register for the prefix 100000001.

Solved by gpt-5.6-sol high.