LFSR: Deterministic Randomness

A computer is an honest machine: the same program on the same inputs gives the same answer. Where does the "random" dice-roll number in a processor come from, then? In this course the answer is the LFSR — a Linear Feedback Shift Register. The trick is that its numbers only look random. This kind of randomness is called pseudorandomness, and it has an exact formula.

A shift with one added bit

Eight flip-flops form the state byte. On every clock tick the whole byte shifts by one position: the top bit leaves, the rest move left, and a new bit takes the vacant spot. That is where all the cleverness lives: several bits of the register (in our LFSR — bits 7, 5, 4 and 3) are picked off and combined with XOR, gate by gate. The result is appended to the tail.

From the outside the behavior looks unsystematic: the register jumps between values with no visible order. Yet every step is strictly determined by the current state — there is no chance inside.

Check it by hand

The starting state of the course LFSR is 156 (0x9C, bits 10011100). Compute the new bit: among the taps, bits 7, 4 and 3 are ones and bit 5 is zero; 1⊕0⊕1⊕1 = 1. Shift left and append 1 — you get 57 (0x39). The next steps: 115, then 230, 204, 152… The sequence defies the eye — and yet it reproduces to the last bit: rebuild the circuit with the same seed, and the very same numbers come out.

Period 255 and the forbidden zero

Our polynomial x⁸ + x⁶ + x⁵ + x⁴ + 1 is the maximal-length one for 8 bits: the register walks through all 255 non-zero states one by one and only then returns to the seed. The period is 255 — that is where the "randomness" comes from: more than two hundred ticks pass before the first repeat.

One state out of 256 is unreachable — zero. From an all-zero register the new bit is always zero, and the circuit sticks forever. That is why an LFSR is never initialized to zero: the seed 156 is guaranteed to work.

Where it appears in the course

On level 26 the LFSR joins the data bus as a third device: it is read via port 250 (0xFA, 0x1A on the address bus). In the final Snake game the same register places the food. A useful property for a game: the sequence is the same on every run — the behavior is reproducible and debuggable, even though the player will not notice the determinism.

In real hardware the LFSR shows up wherever a fast pseudorandom stream is needed: checksums, communication scramblers, counters, built-in self-test generators. Where randomness must be genuine — encryption keys — physical noise sources are used instead. An LFSR is honestly named for what it is: a deterministic generator that only looks random.