Theory: how an LFSR works

An LFSR costs a handful of flip-flops and a few XOR gates, which is why you find one in almost every serial link, built-in self-test and stream cipher. There is no multiplier and no lookup table — the whole generator is shifting and XOR.

The recurrence

An LSFR has some fixed length denote L. In this lab, we will take the value L=16. For a given L, the LFSR has a state of exactly L bits, b0, b1, ..., b{L-1}. The LFSR then generates pseudorandom bits iterativesly in steps. In each step, it shifts the left by one (b{i+1} <- b{i}), and the bit shifted in at the right b0 is the XOR of four tap positions:

The shaded cells are the four taps. Their values are XORed together on the way around the top and fed back into b0, while every bit slides one place toward b15 and the old b15 drops off the right-hand end:

new_bit = b15 ^ b14 ^ b12 ^ b3
state   = (state << 1) | new_bit          keeping 16 bits

The diagram puts b0 on the left, so the bits travel left to right — the value in b0 moves to b1, b1 to b2, and so on. That is a left shift: every bit moves to the next higher position. It only looks like a right shift because a binary number is normally written with b15 on the left.

Why these taps

The XOR combination describing the update for b0 is sometimes described by a polynomial. In the L=16 case above, the polynomial is x¹⁶ + x¹⁵ + x¹³ + x⁴ + 1, which is primitive: the state visits all 65535 nonzero values before it repeats.

That is not a property you get for free. Most tap sets give much shorter periods, and some give dramatically shorter ones — a generator that cycles after a few hundred values will still look plausible in a histogram while being useless. Tap sets for each width are tabulated rather than derived by hand; this one is a standard choice for 16 bits.

Zero is a fixed point

Shift zero left and XOR it with nothing, and it is still zero. A seed of 0 therefore produces an infinite stream of zeros, forever.

This is why the seed is nonzero, and it is the first thing to check if your generator produces nothing but 0. It is also why the maximum period is 65535 rather than 65536: the all-zero state is not part of the cycle, because nothing can ever enter or leave it.

Getting multi-bit samples

Each step above produces exactly one new bit. So, if you want samples that are NBITS bits, you need to run the LFSR NBITS times. In this lab, we will take NBITS=8, so each sample is an 8-bit number. You can then think of the pseudo-random number generator (PRNG) as producing a sequence of random values from 0 to 2^{NBITS}-1=255. We often scale the values by 2^{NBITS} so the value is between 0 and 1.

Note that taking a sample after every single step instead would leave consecutive samples sharing seven of their eight bits. The histogram would still look flat — every value would still occur about equally often — and the numbers would be nothing like independent. That failure is invisible to the eye and obvious to a correlation measurement, which is the subject of Evaluating before you build.

You write that eight-step loop twice: once in Python as prng_sample, and once in SystemVerilog inside the testbench. It is the same loop both times, and writing it in two languages that look nothing alike is much of the point of the lab.

A closing note on “random”

Your generator will pass every check in this lab, and it is still not secure. An LFSR is completely linear: given 32 consecutive output bits, anyone can solve for the state and predict the entire rest of the sequence, forwards and backwards.

That is fine for the jobs LFSRs actually do — test patterns, scrambling, dithering — and fatal for anything protecting a secret. That gap is where stream ciphers begin, and it is worth remembering the next time something is described as “random”.

---

Go to the Python model