LFSRs (Galois and Fibonacci)
A shift register that feeds back the XOR of a few of its bits can step through every nonzero state.
You Will Be Able To
- Build a Fibonacci LFSR and find its period by simulation.
- Write an LFSR's taps as a polynomial and tell a maximal-length set from a short one.
- Explain the all-zeros lock and how to avoid it.
- Relate the Galois form to the Fibonacci form with the same output sequence.
- Lesson
- G6.9
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A link test sends a pattern that looks random but repeats exactly, so the receiver can check every bit. A 4-bit counter needs an adder. A 4-bit LFSR makes a 15-bit pattern with one XOR gate.
- Cycle 1
q3 XOR q2 is 0, so a 0 enters at q0 while the 1 moves up: 0010.
- Cycle 3
From 0100, q3 = 0 and q2 = 1. Their XOR is 1, and a 1 enters: 1001.
- Cycle 15
After 15 edges the state is 0001 again. All 15 nonzero values appeared once.
Measured: the values are the states the lab prints.
A Shift Register That Feeds Itself
A linear-feedback shift register (LFSR) shifts at every edge. The bit that enters is the XOR of a few chosen bits, the taps. In this Fibonacci form, the XOR sits outside the chain.
- Storage
- Datapath
- Data
- Shift
Each edge moves every bit up one stage, like any shift register.
- Feed back
q3 XOR q2 becomes the new q0. Which bits are tapped decides the sequence.
Read the diagram as text
- q0: stage 0
- q1: stage 1
- q2: stage 2
- q3: stage 3, the output
- XOR: the taps
- q0 → q1
- q1 → q2
- q2 → q3
- q2 → XOR
- q3 → XOR
- XOR → q0: new bit
Four flip-flops and one XOR gate. Press Synthesize in the lab: 5 cells.
The output is usually the bit that leaves the top, q3. Because the rest is a plain shift register, q2, q1 and q0 are the next three output bits.
Taps and Maximal Length
An N-bit register has 2^N values. The LFSR can never reach 0000 from a nonzero state, so its longest loop has 2^N - 1 states. A tap set that reaches it is maximal length.
Taps are written as a polynomial. For N bits it starts with x^N and ends with 1. Each other tap on q[k-1] adds the term x^k. Taps q3 and q2 give x^4 + x^3 + 1.
| Taps | Polynomial | Period from 0001 | Maximal? |
|---|---|---|---|
| q3, q2 | x^4 + x^3 + 1 | 15 | yes |
| q3, q0 | x^4 + x + 1 | 15 | yes |
| q3, q1 | x^4 + x^2 + 1 | 6 | no |
| q3, q2, q1, q0 | x^4 + x^3 + x^2 + x + 1 | 5 | no |
| q3, q2, q1 | x^4 + x^3 + x^2 + 1 | 7 | no |
| q3, q1, q0 | x^4 + x^2 + x + 1 | 7 | no |
| q3, q2, q0 | x^4 + x^3 + x + 1 | 6 | no |
Measured: every 4-bit tap set that uses q3, run on Icarus until the state returned to 0001.
Only a primitive polynomial gives the maximal length. Textbooks and FPGA application notes list one for each N. Without a table, simulate and count: the period tells you.
The All-Zeros Lock
The XOR of zeros is 0. So from 0000 the LFSR shifts in a 0 and stays at 0000 forever. That state sits outside the loop.
Two ways out. Reset to a nonzero seed, so 0000 is never reached. Or detect 0000 and push a 1 in, so even a glitch cannot lock it.
Some designs use XNOR feedback instead. Then all zeros is in the loop, and all ones becomes the locked state.
The Galois Form
A Galois LFSR moves the XOR gates into the chain. The top bit is fed back to q0 and also XORed into the tapped stages. Each path holds at most one XOR. With more than two taps that makes it faster. On our pinned Yosys flow, an 8-bit LFSR with four taps has 2 logic levels as Fibonacci and 1 as Galois.
Both presets use the same middle tap, q1. Fibonacci reads it; Galois XORs the feedback in right after it. Then the Galois output runs backwards. To get the same sequence, mirror the middle taps.
| Edge | Fibonacci q (taps q3, q2) | Galois q (q3 XORed into q1) | Fibonacci q3 | Galois q3 |
|---|---|---|---|---|
| 0 | 0001 | 0001 | 0 | 0 |
| 1 | 0010 | 0010 | 0 | 0 |
| 2 | 0100 | 0100 | 0 | 0 |
| 3 | 1001 | 1000 | 1 | 1 |
| 4 | 0011 | 0011 | 0 | 0 |
| 5 | 0110 | 0110 | 0 | 0 |
| 6 | 1101 | 1100 | 1 | 1 |
| 7 | 1010 | 1011 | 1 | 1 |
Measured from 0001. The states differ, but the output bit q3 matches at every edge.
Same polynomial, same period. A Galois state and a Fibonacci state that give the same stream are different words. Moving a seed from one form to the other needs a mapping: G6.9.2 asks for it.
Where LFSRs Are Used
| Use | What the LFSR does |
|---|---|
| Pseudo-random bit sequence (PRBS) | Its output is a test pattern that a receiver can predict and check bit by bit. |
| Scrambler | Its output is XORed with the data, to break up long runs of 0s or 1s. In this additive kind the receiver XORs again with the same sequence. G6.10 shows the self-synchronizing kind. |
| Built-in self-test (BIST) | One LFSR makes test inputs; another folds the outputs into a signature to compare. |
| CRC | An LFSR with the data XORed into the feedback. G1.10 builds one. |
| Cheap counter | It steps through 2^N - 1 states with no adder. Decode one state as the terminal count. |
Each use relies on one property: the sequence looks random, yet it is fixed by the taps and the seed.
Asked in interviews
Why is the longest period of an N-bit LFSR 2^N - 1 and not 2^N?
With XOR feedback, all zeros goes to all zeros. That state forms its own loop, so at most the 2^N - 1 nonzero states share the other.
What is the difference between Fibonacci and Galois LFSRs?
Fibonacci XORs the taps outside the chain into the first stage. Galois puts the XORs between stages. With mirrored taps they give the same sequence; Galois has at most one XOR per path.
How do you pick taps for a maximal-length LFSR?
Use a primitive polynomial from a table, mapping x^k to the tap on q[k-1]. Then simulate and check that the period is 2^N - 1.
Try It
The LFSR visits all 15 nonzero states and returns to 0001 after 15 edges.
Press Synthesize: four flip-flops and one XOR gate, 5 cells.
Change the taps to q[3] ^ q[1] and run again. The state returns to 0001 after only 6 edges.
Synthesize the design to measure its cells and inspect the mapped gates.
reset: 0001 edges 1- 5: 0010 0100 1001 0011 0110 edges 6-10: 1101 1010 0101 1011 0111 edges 11-15: 1111 1110 1100 1000 0001 back to 0001 after 15 edgesOriginal design · 5 cells · 4 flip-flops · 0 latches · 1 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the state after each edge until it returns to the reset value (read-only).
`timescale 1ns/1ns
module tb;
logic clk = 0, rst = 1;
wire [3:0] q;
int n = 0;
string s = "";
lfsr4 dut (.clk(clk), .rst(rst), .q(q));
initial begin
#5 clk = 1; #5 clk = 0; rst = 0;
$display("reset: %b", q);
do begin
#5 clk = 1; #5 clk = 0; n++;
s = {s, $sformatf(" %b", q)};
if (n % 5 == 0) begin $display("edges %2d-%2d:%s", n - 4, n, s); s = ""; end
end while (q != 4'b0001 && n < 40);
if (s != "") $display("edges %2d-%2d:%s", n - n % 5 + 1, n, s);
$display("back to 0001 after %0d edges", n);
end
endmodule
Check Yourself
Common Mistakes
Wrong Reset an LFSR to all zeros.
With XOR feedback, 0000 goes to 0000. The register never leaves it.
Fix Reset to any nonzero value, or detect the all-zeros state and force a 1 in.
Wrong Expect 2^N states from an N-bit LFSR.
The all-zeros state is not in the loop, so the best is 2^N - 1. Many tap sets give far fewer: taps q3 and q1 give 6.
Fix Use a tap set from a primitive polynomial, and check the period in simulation.
Wrong Read the term x^k of a polynomial as the tap on q[k].
In x^5 + x^3 + 1 the term x^3 is the tap on q2. Taps q4 and q2 give 31 states; q4 and q3 give only 21.
Fix Term x^k is the tap on q[k-1]. Then simulate and confirm the period.
Wrong Copy the Fibonacci tap positions into a Galois LFSR and expect the same sequence.
With the same positions, the Galois form produces the output sequence backwards.
Fix Mirror the middle taps: Fibonacci taps q3 and q2 match a Galois XOR into q1.
Remember
- An LFSR shifts and feeds back the XOR of its taps: N flip-flops and a few XOR gates.
- A primitive polynomial gives the maximal length 2^N - 1; other taps give shorter loops.
- With XOR feedback, all zeros locks: reset to a nonzero seed or detect zero and push a 1 in.
- The Galois form puts the XORs between stages; with mirrored taps it gives the same sequence from a different state.