See it move
The idea
A linear feedback is a shift register whose input is an XOR of some of its own bits. With the right bits, called taps, it steps through a long sequence that looks random, at a cost of just one or a few XOR gates. It is completely repeatable, so it is called pseudo-random.
// 4-bit maximal LFSR: taps at bits 3 and 2
always_ff @(posedge clk)
if (rst) q <= 4'b0001;
else q <= {q[2:0], q[3] ^ q[2]};Period
With N bits there are 2^N states, and a good choice of taps visits 2^N - 1 of them before repeating. This is a maximal-length sequence. The one state it skips is all zeros: XOR of zeros is zero, so if the register ever reached that state it would stay there.
The choice of taps matters. Most sets give shorter cycles, so people use published tables of maximal taps rather than guessing. You can see the sequences in the animation above.
Common uses
- Test patterns in built-in self-test
- Generating random stimulus cheaply
- Scrambling data so that long runs of the same bit don't appear on a link
- Very fast counters, where only a sequence is needed, since an LFSR has no carry chain
- Checksums: CRC uses the same structure
Reset is mandatory
An XOR-based LFSR needs a non-zero seed. Reset it to all zeros and it stays locked there. An XNOR version instead locks up at all ones. If a design might see a bit upset, add logic to detect and leave the lock-up state.
Common mistake
Treating an LFSR as truly random. Its output is deterministic and correlated between adjacent bits, so it suits testing and scrambling, but not security.
Key ideas
- Feedback XOR taps set the sequence.
- A maximal N-bit LFSR cycles through 2^N-1 states.
- An XOR-based LFSR locks up at all-zeros.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
if (rst) q <= 4'b0001;
Why it failed
This LFSR feeds back an XOR of its bits. If all bits are 0, the XOR is 0, so a 0 shifts in and the register stays at 0 forever. It is the one state outside the sequence, and this reset goes straight to it. Any non-zero seed works.
Interview questions
coreWhat state must an XOR LFSR avoid?
All zeros: it would stay there forever.
basicHow many states does a maximal-length 8-bit LFSR step through before repeating, and which state does it never reach?
It visits 2^8 - 1 = 255 states. The all-zeros state is the one missing, because in an XOR-based LFSR the feedback from all zeros is zero, so it would never leave that state.
basicAn LFSR uses XNOR feedback instead of XOR. Which state does it lock up in?
All ones. XNOR of two ones is 1, so from 1111... the feedback bit is 1 and the register shifts in another 1, staying at all ones forever. All zeros, which is the problem state for XOR, is fine for the XNOR form.
coreThis 4-bit LFSR is reset to 4'b0001. What is its state after three clocks, and what is its period?
always @(posedge clk)
if (rst) q <= 4'b0001;
else q <= {q[2:0], q[3] ^ q[2]};The feedback is q[3] ^ q[2], shifted in at the bottom. From 0001: the feedback is 0, giving 0010, then 0100, then from 0100 the feedback is 0 ^ 1 = 1, giving 1001 after three clocks. The taps are maximal, so it runs through all 15 non-zero states and returns to 0001 after 15 clocks.
coreAn LFSR is written without a reset. What do you see in simulation, and what could happen in silicon?
In simulation the register starts as x, and XOR with x gives x, so the whole sequence stays x forever. In silicon the flops power up to some value, and if that value happens to be all zeros the XOR LFSR stays there and never runs. An LFSR needs a reset to a non-zero seed.
coreWhy is an LFSR useful as a very fast counter, and what do you give up compared with a binary counter?
Its next state needs only a shift and one or a few XOR gates, with no carry chain, so it can run at very high clock rates. If you only need to know when N steps have passed, you can decode the specific state the LFSR reaches after N steps from its seed. You lose the ability to read the count as a number or compare it easily, so arithmetic on it is impractical.
coreGive three places where LFSRs are used in chips, and say why the property they rely on fits each one.
Built-in self-test uses them to generate long test patterns with very little hardware. Link scramblers use them to break up long runs of identical bits, because the sequence is spread over many values. CRC checksums use the same shift-and-XOR structure to compress a data stream into a short check value. In each case the key properties are low cost and a sequence that is repeatable at both ends.
advancedA 4-bit LFSR is written with taps at bits 3 and 1 instead of 3 and 2. What is wrong with its sequence?
q <= {q[2:0], q[3] ^ q[1]};These taps are not maximal, so the 15 non-zero states split into separate shorter loops instead of one loop of 15. Simulating every start state shows loops of 6, 6 and 3 states; for example, starting from 0001 the register returns to 0001 after only 6 clocks. Tap choices should come from a table of known maximal taps, not guesswork.
advancedWhy is an LFSR unsuitable for generating secret keys, even though its output looks random?
Its output is fully determined by its taps and current state. In this shifting form, the bits that leave the register are its own state bits, so once someone knows the taps, N consecutive output bits from an N-bit LFSR give the whole state, and every future bit follows. Neighbouring outputs are also correlated. It suits testing and scrambling, but secrets need a cryptographic generator.