Feedback turns a shift register into a sequence generator

A linear-feedback shift register shifts every clock. Its input bit is the XOR of selected tap bits.

For this XOR-feedback topology, a primitive polynomial selects taps that make every nonzero seed visit all 2ⁿ − 1 nonzero states before repeating. That maximal period is the useful behavior to check; an arbitrary tap choice need not achieve it. Hardware uses n flops and an XOR feedback network.

Here x⁷ + x⁶ + 1 is implemented as a left-shifting Fibonacci register: keep s[5:0], append s[6] ^ s[5] as the new LSB. The tap positions 7 and 6 use one-based numbering. A right-shifting or Galois implementation needs its own topology mapping; do not copy indices without checking direction, numbering and XOR/XNOR convention. AMD/Xilinx XAPP052 provides maximum-length tap tables and discusses feedback conventions.

Read the row as the register: every clock each bit moves one box to the left, s[6] leaves as the output bit, and the XOR of the two highlighted taps becomes the new s[0].

• Taps: s[6] and s[5] are polynomial terms x⁷ and x⁶ in one-based numbering.

• Seed 01: s[6] and s[5] are both 0, so the new s[0] is 0 and the register becomes 02, as in slot 1 of the trace below.

• State 20: s[5] is 1, so the feedback is 1 and the next state is 41.

The state row steps through the first twelve states after reset.

• Slot 1: state 02.

• Slot 2: state 04.

• Slot 3: state 08.

• Slot 4: state 10.

• Slot 5: state 20.

• Slot 6: state 41.

• Slot 7: state 03.

• Slot 8: state 06.

• Slot 9: state 0c.

• Slot 10: state 18.

• Slot 11: state 30.

• Slot 12: state 61.

From state to a serial bit stream

Define prbs = s[6]. A receiver samples this bit just before each rising-edge update, so the emitted bit belongs to the old state, while the waveform displays the new state. Starting from seed 01, the first twelve emitted bits are 000000100000. Predict the next state and emitted bit for 20 and 41, then compare the retained bits and XOR below.

The plus signs in that table mean concatenation, not arithmetic addition. A different output tap, seed or pre/post-edge sampling convention changes the stream phase; agree on these before connecting a checker or receiver.

Try it: step the register

The stepper starts on this page's PRBS7 register: taps 7 and 6, seed 0000001, Fibonacci structure, shifting left with the old s[6] as the output bit.

• Press Step twelve times: the states run 02, 04, 08, 10, 20, 41, 03, 06, 0c, 18, 30, 61 and the output so far is 000000100000, as in the trace above. Run carries on until the seed returns after 127 steps.

• Untap x⁶ and tap x⁵ (taps 7,5): the period drops to 93, because x⁷ + x⁵ + 1 is not primitive. Taps 7,4 give the full 127 again.

• Switch to Galois with taps 7,6: the period is still 127, but the states differ (02, 04, 08, 10, 20, 40, 41), so the two structures are not interchangeable in a checker.

The rules that make it work

Standard PRBS polynomials

What it is used for

• Built-in self-test (BIST): an LFSR drives test patterns into logic and a second LFSR-like register compresses the responses into a signature.

• Scramblers: XORing data with an LFSR sequence whitens the data, which usually gives enough transitions for clock recovery. It gives no guaranteed run length (data matching the sequence still gives all zeros), and the receiver must align its matching sequence to recover the data.

• CRC generators: a CRC is a division by a polynomial, computed with a similar feedback shift register.

• Pseudo-random stimulus in hardware testbenches and traffic generators.

Common mistakes

An LFSR is not cryptographically secure: given a few outputs, the taps and state can be recovered. It suits testing and scrambling, never secrets.

Testbench

The bounded test checks the defined pre-edge serial output, the twelve worked bits and an integer next-state reference, then checks return to seed after 127 steps and coverage of every nonzero state. Unknown state is diagnosed before indexing the coverage array. The 300-step bound catches failure to return; diagnostics identify the step and failed expectation.

1
2
3
4
5
6
7
8
9
10

module lfsr7 (
  input  logic       clk, rst_n,
  output logic [6:0] s,
  output logic       prbs
);
  assign prbs = s[6];                              // sample old MSB at each rising edge
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) s <= 7'h01;                         // seed must be non-zero
    else        s <= {s[5:0], s[6] ^ s[5]};          // x^7 + x^6 + 1
endmodule

Related topics

• DFT and scan (BIST)