LFSR Applications

An LFSR's sequence looks random but is fixed by its taps and seed. That one property tests chips, checks links, scrambles data and counts.

You Will Be Able To

  • Build a self-test from a pattern LFSR and a signature register, and explain aliasing.
  • Check a PRBS stream and say how many errors a checker counts for one wrong bit.
  • Tell an additive scrambler from a self-synchronizing one.
  • Use an LFSR as a counter that decodes one state as its terminal count.
Lesson
G6.10
Time
30 min
Runs on
Your browser
Check
5 questions

A chip cannot be probed inside. So it tests itself: an LFSR feeds patterns in, and a second LFSR folds the answers into one word. The run below is the lab, edge by edge.

Self-Test of a 2-bit Multiplier, No FaultFrom the lab: the pattern pat and the signature sig after each edge.
0123456789101112131415clkpat0001001001001001001101101101101001011011011111111110110010000001sig000000100100101101001101101100011011000100100100
Scroll horizontally ↔
  1. Cycle 0

    After reset the pattern LFSR holds 0001 and the signature is 0000.

  2. Cycle 1

    pat[3:2] times pat[1:0] is 0 times 1 = 0. The signature register steps, and nothing is XORed in.

  3. Cycle 15

    After all 15 patterns the signature is 0100. A tester compares it with the expected word.

Measured: the last signature is the lab's first line.

Built-In Self-Test: Patterns in, a Signature Out

A built-in self-test (BIST) needs no tester for every output. A pattern LFSR drives the circuit. A multiple-input signature register (MISR) takes all its outputs at every edge.

The Lab's Self-TestArrows carry bits at every clock edge.
  • Storage
  • DUT
  • Datapath
  • Data
The lab's self-testArrows carry bits at every clock edge. storage Pattern LFSR lfsr4: 15 patterns dut Circuit undertest a 2-bit multiplier storage MISR an LFSR with theoutputs XORed in datapath Compare with the expectedsignature patysig
  1. storage Pattern LFSRlfsr4: 15 patterns
    • pat → Circuit under test
  2. dut Circuit under testa 2-bit multiplier
    • y → MISR
  3. storage MISRan LFSR with the outputs XORed in
    • sig → Compare
  4. datapath Comparewith the expected signature
  1. Patterns

    The LFSR steps through all 15 nonzero patterns with one XOR gate.

  2. Signature

    At each edge the MISR steps like an LFSR and XORs in the 4 outputs. 60 output bits become one 4-bit word.

  3. Pass or fail

    Only the final word is compared. One comparison checks the whole run.

Read the diagram as text
  • Pattern LFSR: lfsr4: 15 patterns
  • Circuit under test: a 2-bit multiplier
  • MISR: an LFSR with the outputs XORed in
  • Compare: with the expected signature
  • Pattern LFSR → Circuit under test: pat
  • Circuit under test → MISR: y
  • MISR → Compare: sig

The same idea with longer registers is how chips test their logic and memories after manufacture.

The lab runs the test three times: with no fault, and with two stuck-at faults. One fault changes the signature. The other gives 0100, the good signature: aliasing.

A 4-bit signature can take 16 values, so about 1 in 16 faulty runs alias. Real BIST uses 16- to 32-bit signature registers.

A CRC is the same register with the data bits XORed into the feedback. The receiver recomputes it to catch transmission errors. G1.10 builds one.

PRBS Test Patterns and Their Checkers

A pseudo-random bit sequence (PRBS) is an LFSR's output bit sent on a link. PRBS7 uses x^7 + x^6 + 1: each bit is the XOR of the bits 6 and 7 places back. For 10G Ethernet, IEEE 802.3 cl. 49.2.8 offers an optional PRBS31 test pattern.

The receiver knows the rule, so it can predict every bit and count the wrong ones. It needs no copy of the transmitter's seed.

Two Ways to Predict the Next BitBoth keep the last 7 bits in a shift register and XOR two of them.
  • I/O
  • Storage
  • Datapath
  • Control / FSM
  • Data
Two ways to predict the next bitBoth keep the last 7 bits in a shift register and XOR two of them. io Received bit one per edge storage Shift register the last 7 bits datapath Prediction XOR of two taps control Error flag received XORpredicted self-synchronizingfree-running
  1. io Received bitone per edge
    • self-synchronizing → Shift register
    • Error flag
  2. storage Shift registerthe last 7 bits
    • Prediction
  3. datapath PredictionXOR of two taps
    • Error flag
    • free-running → Shift register
  4. control Error flagreceived XOR predicted
  1. Self-synchronizing

    The received bits fill the register. It locks after 7 bits from any start. But a wrong bit enters the register too.

  2. The error flag

    A bit that differs from the prediction raises the flag.

  3. Free-running

    Once locked, the register can take its own prediction instead. A wrong bit then never enters it.

Read the diagram as text
  • Received bit: one per edge
  • Shift register: the last 7 bits
  • Prediction: XOR of two taps
  • Error flag: received XOR predicted
  • Received bit → Shift register: self-synchronizing
  • Shift register → Prediction
  • Prediction → Error flag
  • Received bit → Error flag
  • Prediction → Shift register: free-running

Test equipment that reports a bit error rate needs each wrong bit counted once.

Additive and Self-Synchronizing Scramblers

A scrambler XORs the data with a pseudo-random stream, so long runs of 0s or 1s cannot reach the wire.

Feed a scrambler all-zero data and its line output is a PRBS. The two predicts below do exactly that, so they also run a PRBS generator and a self-synchronizing checker. There are two kinds of scrambler.

Additive (G6.9)

line = data ^ lfsr_bit;
// the LFSR steps on its own

One wrong line bit gives one wrong data bit. The receiver's LFSR must start in step with the transmitter's.

Self-synchronizing

line = data ^ s[4] ^ s[2];
s    = {s[3:0], line};   // the line bit

The receiver locks after 5 bits from any state. One wrong line bit gives three wrong data bits.

10G Ethernet's 64B/66B coding scrambles each block payload with a self-synchronizing scrambler, x^58 + x^39 + 1 (IEEE 802.3 cl. 49.2.6). Its 2-bit sync header bypasses the scrambler.

An LFSR as a Counter

An N-bit LFSR passes through 2^N - 1 states in a fixed order. Decode one of them as the terminal count, and it divides the clock by 2^N - 1 with no adder.

Counter with a terminal countFlip-flopsCellsLevels
Divide by 15, binary counter4143
Divide by 15, 4-bit LFSR482
Divide by 65535, binary counter16628
Divide by 65535, 16-bit LFSR16344

Measured on the pinned Yosys flow. The binary counter needs an adder and a compare against N - 1; the LFSR needs a few XOR gates and one compare.

The price: the count is not a binary number. The length is fixed at 2^N - 1 unless extra logic skips states. Use it where only the terminal count matters.

Asked in interviews
  1. What is a MISR and why can BIST miss a fault?

    A multiple-input signature register is an LFSR that XORs in many outputs at every edge. A fault can leave the same final word: aliasing, about 1 in 2^N for N bits.

  2. Why do 10G Ethernet links use a self-synchronizing scrambler?

    The receiver locks after enough line bits from any state, so no seed has to be sent. The cost is that one line error becomes three data errors.

  3. Why would you build a counter from an LFSR?

    It needs only XOR gates for the next state, so it is small and fast. It suits dividers and timeouts where only the terminal count matters.

Try It

Each line is one 15-pattern test. With no fault the signature is 0100.

Product bit 3 stuck at 1 changes the signature to 0000: the test catches it. Product bit 1 stuck at 0 also gives 0100: an alias.

Change the stuck-at-0 mask to 4'b1110 (bit 0) and run again. Does the test catch that fault?

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: no fault: signature 0100 bit 1 stuck at 0: signature 0100 bit 3 stuck at 1: signature 0000
Read included file: tb.sv
// tb.sv: one 15-pattern test per fault setting; prints each signature (read-only).
`timescale 1ns/1ns
module tb;
  logic       clk = 0, rst = 1;
  logic [1:0] fault = 0;
  wire  [3:0] sig;
  bist4 dut (.clk(clk), .rst(rst), .fault(fault), .sig(sig));
  task automatic test(input logic [1:0] f, input string name);
    fault = f; rst = 1;
    #5 clk = 1; #5 clk = 0; rst = 0;
    repeat (15) begin #5 clk = 1; #5 clk = 0; end
    $display("%s: signature %b", name, sig);
  endtask
  initial begin
    test(2'd0, "no fault");
    test(2'd1, "bit 1 stuck at 0");
    test(2'd2, "bit 3 stuck at 1");
  end
endmodule

Check Yourself

ConceptWhat does the signature register in a self-test do?
ConceptAn additive descrambler starts one bit out of step with the scrambler. What happens?
Predict the outputThe same self-synchronizing pair, in step, with the line bit at i == 5 flipped. Predict the exact line.
module tb;
  logic [4:0]  tx = 5'b10110, rx = 5'b10110;     // both start from the same state
  logic [15:0] data = 16'h0000, line, back;
  initial begin
    for (int i = 15; i >= 0; i--) begin
      line[i] = data[i] ^ tx[4] ^ tx[2];
      tx      = {tx[3:0], line[i]};
      if (i == 5) line[i] = ~line[i];             // one bit flipped on the wire
      back[i] = line[i] ^ rx[4] ^ rx[2];
      rx      = {rx[3:0], line[i]};
    end
    $display("back %b", back);
  end
endmodule
ConceptWhich clause of IEEE 802.3 gives the 64B/66B self-synchronizing scrambler?
ConceptA 5-bit maximal LFSR counter decodes one state as its terminal count. How often is tc 1?

Common Mistakes

Wrong Trust a matching signature to mean the circuit has no fault.

A 4-bit signature has only 16 values. In the lab, a stuck-at fault gives the same signature as the good circuit.

Fix Use a longer signature register and more patterns, and measure which faults the test misses.

Wrong Count the error flags of a self-synchronizing checker as the number of wrong bits.

A wrong bit is flagged when it arrives and again at each tap it passes. With two taps one wrong bit gives three flags.

Fix Let the checker run its own LFSR once it has locked. Dividing by taps plus one works only for isolated errors.

Wrong Expect an additive descrambler to recover from any starting state.

Its LFSR runs on its own. If it starts out of step with the transmitter, it never recovers: about half the bits stay wrong for good.

Fix Align the seeds with a known frame start, or use a self-synchronizing scrambler.

Wrong Decode the LFSR counter's terminal count as the all-ones state.

Any nonzero state works, but the state must be in the loop. With XNOR feedback all ones is the lock-up state.

Fix Pick a state from the measured loop, and check the period in simulation.

Remember

  • BIST: a pattern LFSR drives the circuit and a MISR folds its outputs into one signature; short signatures alias.
  • A PRBS checker predicts each bit from earlier ones; a self-synchronizing one counts a wrong bit once per tap plus once.
  • An additive scrambler needs aligned seeds; a self-synchronizing one locks by itself but multiplies line errors.
  • An LFSR with one decoded state divides by 2^N - 1 with fewer cells and levels than a binary counter.

Practice

Report a problem with this page