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.
- Cycle 0
After reset the pattern LFSR holds 0001 and the signature is 0000.
- Cycle 1
pat[3:2] times pat[1:0] is 0 times 1 = 0. The signature register steps, and nothing is XORed in.
- 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.
- Storage
- DUT
- Datapath
- Data
- Patterns
The LFSR steps through all 15 nonzero patterns with one XOR gate.
- Signature
At each edge the MISR steps like an LFSR and XORs in the 4 outputs. 60 output bits become one 4-bit word.
- 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.
- I/O
- Storage
- Datapath
- Control / FSM
- Data
- Self-synchronizing
The received bits fill the register. It locks after 7 bits from any start. But a wrong bit enters the register too.
- The error flag
A bit that differs from the prediction raises the flag.
- 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 count | Flip-flops | Cells | Levels |
|---|---|---|---|
| Divide by 15, binary counter | 4 | 14 | 3 |
| Divide by 15, 4-bit LFSR | 4 | 8 | 2 |
| Divide by 65535, binary counter | 16 | 62 | 8 |
| Divide by 65535, 16-bit LFSR | 16 | 34 | 4 |
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
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.
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.
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?
no fault: signature 0100 bit 1 stuck at 0: signature 0100 bit 3 stuck at 1: signature 0000Read 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
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.