A memory of four bits

The two constructions below this rung both hold the whole sequence in mind while building it — a graph with $2^{n-1}$ vertices, or a list of necklaces in alphabetical order. Neither is a machine. This one is: four flip-flops, one exclusive-or gate, and a clock.

The register holds $n$ bits. At each tick it shifts them along by one, drops the bit at the end, and puts a new bit in at the start: the sum, modulo two, of the bits at a chosen few positions. The chosen positions are the taps, and everything about the machine’s behaviour is decided by them.

What the taps decide #

There are $2^n$ possible states and the all-zero state is a trap — every tap sums to zero there, so the register stays put forever. The best a register can do is visit the other $2^n - 1$ states in one cycle, and a register that does is called maximum-length.

Most tap choices do far worse. A four-bit register has fifteen useful tap sets and only two of them are maximum-length; the rest split the fifteen nonzero states into shorter cycles, and a register that has fallen into a cycle of length three produces a sequence with a period of three.

The rule for which taps work is not about the register at all. Write the taps as a polynomial: taps at positions $n$ and $j$ become $x^n + x^j + 1$. The recurrence is then multiplication by $x$ in the ring of polynomials modulo that polynomial, and the state cycles through every nonzero element exactly when $x$ generates the multiplicative group — which is what primitive means, and which requires the polynomial to be irreducible first.

The register is running arithmetic in a field of $2^n$ elements, and the state is a field element being multiplied by $x$ over and over.

That the multiplicative group of a finite field is cyclic is the theorem doing all the work, and it is the same theorem that makes every nonzero residue a power of a single one. A generator exists; the question is only whether $x$ happens to be one, and for each degree there are $\varphi(2^n-1)/n$ primitive polynomials to choose from.

Every window but one #

Run the register and read the bit that falls off the end at each step. That output has period $2^n - 1$, and its windows are the states themselves: the window of $n$ consecutive output bits starting at step $t$ is the state at step $t$, read off.

So the output contains every nonzero window of width $n$ exactly once and the all-zero window never. That is a de Bruijn sequence with exactly one word missing, and the missing word is the one the machine cannot represent.

The repair is a single character. In the output there is exactly one run of $n-1$ zeros — it is the state $000\ldots01$ passing through — and writing one more zero into it produces a cyclic sequence of length $2^n$ in which the all-zero window now appears once and nothing else has changed. Every other window is untouched, because the only windows that see the edit are the ones overlapping the run, and those were the ones spelling $0^{n-1}1$ and $10^{n-1}$, which shift by one place each.

The result is a de Bruijn sequence produced by $n$ bits of memory and a handful of gates. Nothing is stored, nothing is searched, and the sequence can be generated indefinitely from any point in it — which is the property that makes the construction useful rather than merely elegant.

The sequence looks random and is not #

A maximum-length sequence passes the tests one would apply to a coin.

Balance. In each period there are $2^{n-1}$ ones and $2^{n-1}-1$ zeros — as close to equal as an odd-length sequence can be, and the imbalance is exactly the missing all-zero state.

Runs. The runs of consecutive equal bits are distributed as they would be for a fair coin: half the runs have length one, a quarter have length two, and so on down to the single run of $n-1$ zeros and the single run of $n$ ones.

Autocorrelation. Comparing the sequence with any nontrivial shift of itself gives agreement in exactly $2^{n-1}-1$ places and disagreement in $2^{n-1}$ — a correlation of $-1/(2^n-1)$, the same for every shift. This is the sharpest of the three: the sequence is uncorrelated with every shift of itself by the same tiny amount, which is a stronger and more uniform property than a random sequence would have.

The autocorrelation property is worth a sentence more, because it is the one that gets these sequences used. A signal correlating sharply with itself at zero shift and almost not at all at every other shift is exactly what a ranging system needs: transmit the sequence, correlate the echo against every shift, and the shift that spikes is the delay. The sequence is doing the work a single sharp pulse would do, spread over a long interval, so the transmitter never needs high peak power. That is why maximum-length sequences are in satellite navigation, in radar, and in the impulse-response measurement of a room.

Golomb collected these as the postulates a pseudorandom sequence ought to satisfy, and maximum-length sequences satisfy them exactly rather than on average. That is the tell.

And a sequence that satisfies them exactly is predictable. Given any $2n$ consecutive output bits, the taps can be recovered by solving $n$ linear equations, after which the entire past and future of the sequence is determined. The linear complexity of a maximum-length sequence is $n$ — the smallest register that can produce it is the one that did — and the Berlekamp–Massey algorithm finds it from $2n$ bits in time $O(n^2)$.

This is the same lesson the planes a recurrence cannot leave teaches about linear congruential generators, in a different disguise. A generator whose next value is a linear function of the previous ones has a structure that shows up as soon as the right question is asked, and passing statistical tests is not evidence of the absence of structure. It is evidence about which tests were run.

There is a second structural fact the tests cannot see, and it is the reason the linear complexity is exactly $n$. The sequence satisfies a linear recurrence of order $n$ — that is what the register is — so any $n$ consecutive bits determine the next one, and a recurrence with a short description is compressible however random its output looks. Kolmogorov’s notion of randomness is the absence of a short description, and by that standard a maximum-length sequence of length four billion is not random at all: it is thirty-two bits of state and two tap positions.

Where each construction is the right one #

Three constructions now produce the same kind of object, and they are good at different things.

The Eulerian walk produces any of them and needs the whole graph. It is the existence proof, and it is what shows the object exists for every alphabet and every order.

The necklace list produces the alphabetically first, in constant time per letter and $O(n)$ space, for any alphabet. It is what to use when the sequence is wanted as data.

The shift register produces one particular sequence, from $n$ bits of state, and can be started anywhere in it and run forward or backward. It is what to use when the sequence is wanted as a process, and it is the only one of the three that a circuit can be.

The register’s other distinguishing property is the one the rung below flagged: locating a window. In a maximum-length sequence the window at step $t$ is the field element $x^t$, so finding where a given window sits means solving $x^t = w$ for $t$ — a discrete logarithm in a field of $2^n$ elements. For small $n$ that is a table lookup; for large $n$ it is a problem believed to be hard, and the whole of a branch of cryptography rests on it being so.

So the same sequence is cheap to generate and expensive to index, and which of those is the feature depends entirely on the application. A position-encoding strip wants both: cheap to print, and indexable by the reader — which is why such strips use small $n$ and a stored table rather than the arithmetic.

What a wrong tap set does #

It is worth seeing the failure, because it is quiet.

Take a four-bit register and tap positions four and two instead of four and one. The polynomial is $x^4 + x^2 + 1$, which factors as $(x^2+x+1)^2$ — reducible, so certainly not primitive. Started at 0001 the register visits six states and returns; started elsewhere it visits three, or one. The fifteen nonzero states break into cycles of six, six and three.

Nothing about the register announces this. It clocks, it produces bits, the bits are not obviously patterned, and the failure shows only when the output is watched for long enough to repeat — six bits, in a machine whose designer expected fifteen. A register of width thirty-two with badly chosen taps can have a period of a few thousand while the designer expects four billion, and the difference is invisible in any short sample.

That is the practical reason primitivity is checked by arithmetic rather than by running the machine. Running it settles the question only after a full period, which is exactly the quantity in doubt, and a short period is discovered by the thing that goes wrong rather than by the test.

The same shape of error appears wherever a recurrence is trusted for its period: a modulus and multiplier that fail one of the conditions in the criterion for full period give a generator that works and repeats early, and the symptom arrives long after the decision that caused it.

What the taps cost to find #

A last practical note, because it is a good example of a search that looks harder than it is.

To find a maximum-length register of width $n$, one needs a primitive polynomial of degree $n$ over the two-element field. There are $\varphi(2^n - 1)/n$ of them, which for $n = 32$ is about 67 million out of $2^{32}$ candidate polynomials — roughly one in sixty. So random search finds one quickly, provided each candidate can be tested quickly.

Testing is where the work is, and it needs the factorisation of $2^n - 1$: a polynomial is primitive when $x$ has order exactly $2^n-1$, which is checked by verifying that $x^{(2^n-1)/p} \ne 1$ for each prime $p$ dividing $2^n-1$. So the difficulty of finding a good register of width $n$ is the difficulty of factoring one specific number — and for the widths where $2^n - 1$ is a Mersenne prime, there is nothing to factor and every irreducible polynomial of that degree is primitive.

That is a pleasing inversion. The primes that are one less than a power of two are a subject with no obvious application, and they turn out to be exactly the register widths for which the design problem disappears.

What the pictures cannot show #

The register is drawn as a table of states, not as a circuit. What a circuit would add is the gate count and the propagation delay, which are the reasons the construction is used and are facts about hardware rather than about the sequence.

The statistical properties are described and not measured. The balance, run and correlation statements are theorems about maximum-length sequences; the figures here show one register at four bits and one at five, where the statistics are visible but the sample is far too small to be evidence.

The tap search is not run. The claim that about one polynomial in sixty is primitive at degree thirty-two is arithmetic, and generating sixty-seven million polynomials is not something a figure does.

And the field picture is a different notation for the same object. The powers of a primitive element and the states of the register are the same fifteen things written two ways; the figure showing both does not prove they correspond, it displays the correspondence the text argues for.

Where the ladder goes next #

The rung above takes the property into two dimensions. An array can be printed so that every small rectangular patch of it appears exactly once — a de Bruijn torus — and a reader that sees a patch knows where on the page it is. The one-dimensional constructions do not simply lift: the counting is tighter, the existence conditions are more delicate, and a row of a torus is generally not a de Bruijn sequence at all.

Above that: which other families of objects admit such a cycle. Words are the easy case because the transition structure is a graph with equal degrees; subsets and permutations are not, and the question of which admit a universal cycle has a counting obstruction and a good deal of open ground.

What is worth carrying away #

A machine that produces a sequence and a description of that sequence are different objects, and knowing which one is in hand decides what questions are easy.

The register makes the sequence cheap to produce and cheap to continue from anywhere, and it makes the sequence’s position hard to determine. The necklace list makes the position obvious and continuation from the middle awkward. Both produce de Bruijn sequences and neither is a better construction than the other. The useful question about a construction is not whether it works but which of the object’s properties it makes visible — and here the answer is decided, both times, by what has to be held in memory while it runs.