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.

The 4-bit LFSR After Each EdgeFrom the lab: the state q and its top bit q3, the output bit.
0123456789101112131415clkq0001001001001001001101101101101001011011011111111110110010000001q3
Scroll horizontally ↔
  1. Cycle 1

    q3 XOR q2 is 0, so a 0 enters at q0 while the 1 moves up: 0010.

  2. Cycle 3

    From 0100, q3 = 0 and q2 = 1. Their XOR is 1, and a 1 enters: 1001.

  3. 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.

A 4-bit Fibonacci LFSR with Taps q3 and q2Arrows carry bits. The XOR output enters stage q0 at each edge.
  • Storage
  • Datapath
  • Data
A 4-bit Fibonacci LFSR with taps q3 and q2Arrows carry bits. The XOR output enters stage q0 at each edge. storage q0 stage 0 storage q1 stage 1 storage q2 stage 2 storage q3 stage 3, the output datapath XOR the taps new bit
  1. storage q0stage 0
    • q1
  2. storage q1stage 1
    • q2
  3. storage q2stage 2
    • q3
    • XOR
  4. storage q3stage 3, the output
    • XOR
  5. datapath XORthe taps
    • new bit → q0
  1. Shift

    Each edge moves every bit up one stage, like any shift register.

  2. 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.

TapsPolynomialPeriod from 0001Maximal?
q3, q2x^4 + x^3 + 115yes
q3, q0x^4 + x + 115yes
q3, q1x^4 + x^2 + 16no
q3, q2, q1, q0x^4 + x^3 + x^2 + x + 15no
q3, q2, q1x^4 + x^3 + x^2 + 17no
q3, q1, q0x^4 + x^2 + x + 17no
q3, q2, q0x^4 + x^3 + x + 16no

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.

All 16 States of the 4-Bit LFSR
All 16 States of the 4-Bit LFSR01010101010101010101010101010101S00010001resetS00100010step 1S01000100step 2S10011001step 3S00110011step 4S01100110step 5S11011101step 6S10101010step 7S01010101step 8S10111011step 9S01110111step 10S11111111step 11S11101110step 12S11001100step 13S10001000step 14S00000000locked
  1. reset · S00010001
    • ↓0 → S0001
    • ↓1 → S0010
  2. step 1 · S00100010
    • ↓0 → S0010
    • ↓1 → S0100
  3. step 2 · S01000100
    • ↓0 → S0100
    • ↓1 → S1001
  4. step 3 · S10011001
    • ↓0 → S1001
    • ↓1 → S0011
  5. step 4 · S00110011
    • ↓0 → S0011
    • ↓1 → S0110
  6. step 5 · S01100110
    • ↓0 → S0110
    • ↓1 → S1101
  7. step 6 · S11011101
    • ↓0 → S1101
    • ↓1 → S1010
  8. step 7 · S10101010
    • ↓0 → S1010
    • ↓1 → S0101
  9. step 8 · S01010101
    • ↓0 → S0101
    • ↓1 → S1011
  10. step 9 · S10111011
    • ↓0 → S1011
    • ↓1 → S0111
  11. step 10 · S01110111
    • ↓0 → S0111
    • ↓1 → S1111
  12. step 11 · S11111111
    • ↓0 → S1111
    • ↓1 → S1110
  13. step 12 · S11101110
    • ↓0 → S1110
    • ↓1 → S1100
  14. step 13 · S11001100
    • ↓0 → S1100
    • ↓1 → S1000
  15. step 14 · S10001000
    • ↓0 → S1000
    • ↓1 → S0001
  16. locked · S00000000
    • ↓0 → S0000
    • ↓1 → S0000
StateInputNextOutput in state
S00010S00010001
S00011S00100001
S00100S00100010
S00101S01000010
S01000S01000100
S01001S10010100
S10010S10011001
S10011S00111001
S00110S00110011
S00111S01100011
S01100S01100110
S01101S11010110
S11010S11011101
S11011S10101101
S10100S10101010
S10101S01011010
S01010S01010101
S01011S10110101
S10110S10111011
S10111S01111011
S01110S01110111
S01111S11110111
S11110S11111111
S11111S11101111
S11100S11101110
S11101S11001110
S11000S11001100
S11001S10001100
S10000S10001000
S10001S00011000
S00000S00000000
S00001S00000000

Current state: S0001 · Output: 0001

Sampled input, state and output waveformStepState0S00011S00102S01003S10014S00115S01106S11017S10108S01019S101110S011111S111112S111013S110014S100015S0001en—111111111111111q30001001101011110q20010011010111100q10100110101111000q01001101011110001
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step0123456789101112131415
Input—111111111111111
StateS0001S0010S0100S1001S0011S0110S1101S1010S0101S1011S0111S1111S1110S1100S1000S0001
Output0001001001001001001101101101101001011011011111111110110010000001

  1. Step 15. Fifteen edges visit all 15 nonzero states and return to 0001.

Taps q3 and q2. The outer loop holds every nonzero state. 0000 goes to 0000: the XOR of zeros is 0. en = 1 is a clock edge.

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.

A 3-Bit Fibonacci LFSR
A 3-Bit Fibonacci LFSRg0 · XORfb=1DQg1 · DFFq0=0DQg2 · DFFq1=1DQg3 · DFFq2=0clk=0
clk=0
g0 · XORq2=0, q1=1 → fb=1
g1 · DFFfb=1, clk=0 → q0=0
g2 · DFFq0=0, clk=0 → q1=1
g3 · DFFq1=1, clk=0 → q2=0
Read the connections
GateKindInputsOutput
g0XORq2, q1fb
g1DFFfb, clkq0
g2DFFq0, clkq1
g3DFFq1, clkq2

Outputs: q2, q1, q0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 48. Settled after 48 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748q20000000000111111000000111111111111111111000000000q10000111111000000111111111111111111000000000000111q01111000000111111111111111111000000000000111111000
Scroll horizontally ↔
Every computed frame
Timeq2q1q0
0001
1001
2001
3001
4010
5010
6010
7010
8010
9010
10101
11101
12101
13101
14101
15101
16011
17011
18011
19011
20011
21011
22111
23111
24111
25111
26111
27111
28110
29110
30110
31110
32110
33110
34100
35100
36100
37100
38100
39100
40001
41001
42001
43001
44001
45001
46010
47010
48010

  1. Step 4. First edge: q2 XOR q1 = 0 enters q0, and 001 becomes 010.
  2. Step 40. After seven edges it is back at 001: all seven nonzero states.

The lfsr-fibonacci preset: taps q2 and q1 (x^3 + x^2 + 1), seed 001. The XOR sits outside the chain.

A 3-Bit Galois LFSR
A 3-Bit Galois LFSRg0 · XORx2=1DQg1 · DFFq0=0DQg2 · DFFq1=1DQg3 · DFFq2=0clk=0
clk=0
g0 · XORq1=1, q2=0 → x2=1
g1 · DFFq2=0, clk=0 → q0=0
g2 · DFFq0=0, clk=0 → q1=1
g3 · DFFx2=1, clk=0 → q2=0
Read the connections
GateKindInputsOutput
g0XORq1, q2x2
g1DFFq2, clkq0
g2DFFq0, clkq1
g3DFFx2, clkq2

Outputs: q2, q1, q0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 48. Settled after 48 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748q20000000000111111111111111111000000111111000000000q10000111111000000000000111111111111111111000000111q01111000000000000111111111111111111000000111111000
Scroll horizontally ↔
Every computed frame
Timeq2q1q0
0001
1001
2001
3001
4010
5010
6010
7010
8010
9010
10100
11100
12100
13100
14100
15100
16101
17101
18101
19101
20101
21101
22111
23111
24111
25111
26111
27111
28011
29011
30011
31011
32011
33011
34110
35110
36110
37110
38110
39110
40001
41001
42001
43001
44001
45001
46010
47010
48010

  1. Step 10. Second edge: q2 = 0 goes to q0 and into the XOR, so q2 takes q1: 100.
  2. Step 40. Also back at 001 after seven edges. Its q2 sequence is the Fibonacci one backwards.

The lfsr-galois preset: q2 goes back to q0, and q1 XOR q2 enters q2. Seed 001.

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.

EdgeFibonacci q (taps q3, q2)Galois q (q3 XORed into q1)Fibonacci q3Galois q3
00001000100
10010001000
20100010000
31001100011
40011001100
50110011000
61101110011
71010101111

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

UseWhat the LFSR does
Pseudo-random bit sequence (PRBS)Its output is a test pattern that a receiver can predict and check bit by bit.
ScramblerIts 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.
CRCAn LFSR with the data XORed into the feedback. G1.10 builds one.
Cheap counterIt 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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 edges

Original 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

ConceptA 4-bit LFSR with XOR feedback is reset to 0000. What does it do?
ConceptWhich taps does the polynomial x^5 + x^3 + 1 give for a 5-bit LFSR with bits q4 to q0?
Predict the outputThe lab's LFSR starts at 0110. Predict the exact line after two edges.
module tb;
  logic       clk = 0;
  logic [3:0] q = 4'b0110;
  always @(posedge clk) q <= {q[2:0], q[3] ^ q[2]};
  initial begin
    repeat (2) begin #1 clk = 1; #1 clk = 0; end
    $display("q=%b", q);
  end
endmodule
ConceptWhy can a Galois LFSR run at a higher clock rate than a Fibonacci LFSR with many taps?
ConceptA 16-bit LFSR uses a primitive polynomial. How many edges until the sequence repeats?

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.

Practice

Report a problem with this page