Linear-feedback shift register (LFSR)

This page draws the Fibonacci form of the LFSR, whose stages are a plain shift register and whose XOR sits outside them, feeding the first stage. The other common form, Galois, puts the XOR between two stages instead.

How it works, edge by edge

The flops print no names. From left to right they are q3, q2, q1 and q0, and each prints the bit it holds; a lamp on the wire after each flop shows its q, as on the shift register page. Where that page had si, a wire comes back along the top: the XOR at the top right reads q1 and q0, and its output, fb, is what q3 takes at every edge while rst is low. The waveform's rows are in the same order, with fb last.

From tick 0 to tick 3 every row but clk and rst is X. rst is high, but the reset is synchronous and waits for an edge like any other input. fb, the XOR of two unknowns, is unknown too. At the first edge, tick 4, the four stages load the seed: q0 resets to 1 and the other three to 0, so the register reads 0001 and fb leaves X for 1. rst falls in the same tick, after that edge has sampled it high.

At the second edge, tick 12, rst is low and the register shifts: q2, q1 and q0 take what q3, q2 and q1 held, and q3 takes fb, which was 1. The register reads 1000. Now q1 and q0 are both 0 and fb falls. The third edge, tick 20, shifts that 0 in: 0100. At the fourth edge, tick 28, the 1 reaches q1, so q1 and q0 differ and fb rises again: 0010, with a 1 waiting to enter q3.

So far a single 1 has gone round the register as it would round a ring. All fifteen runs on, and its fifth edge, tick 36, is where the XOR starts to matter: a ring would put q0's 0 into q3 and read 0001, but fb is 1, and the register reads 1001. The table has one row per edge, with the values just after it. q is the four bits read as one number, q3 the most significant, and fb is the bit the next edge shifts into q3:

From tick 4 to tick 116 every number from 1 to 15 appears once. At tick 124, fifteen edges after the seed, the register reads 0001 again, and from there it repeats the same fifteen in the same order. The one value missing is 0000: from it fb would be 0, and the first pitfall below says what follows. A register whose taps make it visit every value but 0000 is called maximal-length. Fifteen is as many values as a 4-bit LFSR can visit.

The taps, the stages the XOR reads, decide the sequence. Tables of maximal-length taps usually number the stages from 1 at the input to 4 at the output, so this register's taps are 4 and 3, and its feedback polynomial is $x^4 + x^3 + 1$. Its reciprocal, $x^4 + x + 1$, is the characteristic polynomial of the sequence every stage runs through, and some texts name a register by that one instead. A polynomial is primitive exactly when its reciprocal is, so either name marks this register as maximal-length.

No reset holds rst low from tick 0, and every row but clk and rst stays X to the end. At each edge q3 takes fb, the XOR of two unknowns, and the other three take the X of the stage before them. On the shift register page the X leaves after four edges, because si brings a known bit in at every edge. With rst low, an LFSR has no input but its own bits, and fb reads q0: the edge that shifts an X out of q0 shifts an X from fb into q3, so an unknown it starts with never leaves.

Where only the number of edges matters and not the order of the values, an LFSR can stand in for a counter: its next value takes one XOR, where the decade counter has to add one across all four bits.

The code

// A 4-bit Fibonacci LFSR, a linear-feedback shift register: four flip-flops in
// a row, q3 nearest the input, and one XOR that feeds q1 ^ q0 back into q3.
// From any value but 0000 it visits all fifteen nonzero values, then repeats.
//
// Reset style for this module: synchronous, active high. The reset loads the
// seed 0001. Any value but 0000 would do; 0000 is the one it could never leave.
module lfsr (
    input  logic       clk,
    input  logic       rst,
    output logic [3:0] q
);

  // One flip-flop a bit, named as the drawing names them, q3 nearest fb.
  logic q3, q2, q1, q0;

  // The bit shifted in: the last two stages, XORed.
  logic fb;
  assign fb = q1 ^ q0;

  always_ff @(posedge clk) begin
    if (rst) begin
      q3 <= 1'b0;
      q2 <= 1'b0;
      q1 <= 1'b0;
      q0 <= 1'b1;
    end else begin
      q3 <= fb;
      q2 <= q3;
      q1 <= q2;
      q0 <= q1;
    end
  end

  // The state as one number, q3 the most significant bit.
  assign q = {q3, q2, q1, q0};

endmodule

The reset style is stated at the top of the file and used once: synchronous, active high. It is also what loads the seed. The shift register can leave its reset out; this one cannot, as No reset shows. The four lines under else are the four flops, in the drawing's order. The four above them are the same flops' reset values, 1 for q0 and 0 for the rest, and each flop lights both of its lines. assign fb = q1 ^ q0; is the XOR at the top right, and the fb that q3 <= fb; reads is the wire that runs back along the top of the drawing into the first flop.

The register could be one line on a vector, {q3, q2, q1, q0} <= {fb, q3, q2, q1};. As on the shift register page, the four stages are named instead, so that each is a flop in the drawing and a row the replay below can compare by name.

Synthesis result

Yosys's generic synthesis turns lfsr.sv into 5 cells, 4 of them flip-flops. The cells are Yosys's own gate library, not an FPGA's or a standard-cell library's: the count measures the logic, not the area of any chip.

Lint by Verilator 5.052, the testbench by Icarus Verilog 13.0, synthesis by Yosys 0.66.

Icarus replayed this page's three scenarios on this code, and all 1,400 values the waveform draws match.

Pitfalls

The all-zeros lock-up. From 0000, fb is 0 and every edge loads 0000 again: the register stops. None of the fifteen values in All fifteen is 0000, and none of them leads to it. So 0000 is the one seed a reset must never load, and a register that powers up there stays there until a reset loads a nonzero seed. No scenario can show it, because a flop's reset value is part of the model rather than an input. In Icarus, a copy of this code whose reset loads 0000 was still at 0000 after 32 edges.

What the reset has to load. From the seed and No reset are the same register, with rst high at the first edge and with rst never high. With rst never high, a simulator that models X, as this figure and Icarus do, shows X for as long as it runs. Silicon has no X: a register that is never reset runs from whatever its flops power up holding, and if that is 0000 it never runs at all. On an ASIC it can be any of the sixteen. On most FPGAs, configuration loads each flip-flop's initial value, 0 unless the code sets one, and if all four of this register's flops start at 0, it starts in the lock-up. A reset that loads a nonzero seed is what makes the register start, not only what makes the simulation readable.

The wrong taps. Only some pairs of taps make the register visit all fifteen values. Move one tap, fb = q2 ^ q0, and from 0001 the register runs 0001, 1000, 0100, 1010, 0101, 0010 and is back at 0001 after six edges. The sixteen values then fall into cycles of 6, 6, 3 and 1, the 1 being 0000. Which cycle the register runs depends on its seed. On a waveform the mistake is easy to miss, since the first values are all new; count the edges back to the seed instead. This page's testbench does: from the seed, each of the next fourteen edges has to bring a value not yet held and the fifteenth the seed again, and a copy with q2 ^ q0 fails it.