How to build an LFSR (linear feedback shift register)

A linear feedback shift register (LFSR) is a shift register whose new input bit is the XOR or XNOR of some of its own bits, so it steps through a long, fixed sequence of states that looks random. This live 4-bit one feeds Q3 XNOR Q2 back into Q0 and visits 15 different states before it repeats.

Every clock the bits move one place along, Q0 to Q1 to Q2 to Q3, and the feedback gate computes the bit that enters at Q0. The flip-flops it reads are the taps, and the choice of taps decides how long the sequence is. Taps 4 and 3 (the polynomial x⁴ + x³ + 1) give the longest run possible, 2⁴ - 1 = 15 states. One state is always left out: with XOR feedback 0000 would shift in 0 forever, and with XNOR, as here, 1111 would shift in 1 forever. XNOR is handy because the clear input then gives a valid starting state, 0000. The register has only four flip-flops and one gate, whatever the sequence, which is why LFSRs generate test patterns for chips, scramble data on serial links, compute CRCs (the same shift and XOR, with the message fed in) and serve as very cheap counters. Two laps of the 15 states are checked, all four bits after every clock, before the page is built.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

4× D flip-flop with clear: the shift register Q0 to Q3, on one clock CLK and one clear CLR
1× XNOR: the feedback Q3 XNOR Q2 into D of Q0 (taps 4 and 3)

Step by step

Place a clock CLK, an input CLR, four D flip-flops with clear, and probes Q0 to Q3 on their outputs.
Chain them into a shift register: Q0 drives D of the second flip-flop, Q1 the third and Q2 the fourth. All four share CLK and CLR.
Add the feedback: an XNOR of Q3 and Q2 drives D of the first flip-flop.
Pulse CLR to start from 0000, then run the clock. The state walks through 15 different values and comes back to 0000; Q3 is the pseudo-random output bit stream.

The 15 states, clock by clock

Clocks since CLR	Q0 Q1 Q2 Q3	Next Q0 = Q3 XNOR Q2
0	0 0 0 0	1
1	1 0 0 0	1
2	1 1 0 0	1
3	1 1 1 0	0
4	0 1 1 1	1
5	1 0 1 1	1
6	1 1 0 1	0
7	0 1 1 0	0
8	0 0 1 1	1
9	1 0 0 1	0
10	0 1 0 0	1
11	1 0 1 0	0
12	0 1 0 1	0
13	0 0 1 0	0
14	0 0 0 1	0
15	0 0 0 0	1

After 15 clocks the register is back at 0000, so the period is 15 = 2⁴ - 1, and 1111 never appears. Reading Q3 down the table gives the output stream 000011101100101, which then repeats. Longer registers with the right taps run much longer: 2¹⁶ - 1 = 65,535 states from 16 flip-flops and a few XNOR gates.

You can also read the full theory in the lesson on shift registers. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter Hamming (7,4) code encoder and corrector traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder full adder using 4:1 multiplexers edge detector serial adder 4-bit carry-select adder 4-bit Kogge-Stone adder 4-bit carry-skip adder 4x4 Wallace tree multiplier 8-bit adder frequency divider (by 2, 4 and 3)switch debouncer (SR latch)3-bit Gray code counter Mealy machine (1011 detector)master-slave JK flip-flop (NAND)half subtractor from NOR gates 1-to-8 demultiplexer excess-3 to BCD code converter vending machine FSM 4-bit carry-save adder 3-bit synchronous counter (JK)CMOS transmission gate tri-state buffer (CMOS)2-to-1 mux from transmission gates mod-5 counter flip-flop conversion (JK to D)8-bit ALU decimal to BCD encoder BCD to decimal decoder 4-to-1 mux from 2-to-1 muxes XOR gate from NOR gates 74LS138 decoder BCD subtractor

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the 4-bit LFSR in the lab →

Frequently asked

What is an LFSR?

A linear feedback shift register: a shift register whose input bit is the XOR (or XNOR) of some of its own outputs, called taps. Each clock shifts the register and feeds that bit back in, so it steps through a fixed sequence of states that looks random.

Why does an n-bit LFSR have 2^n - 1 states and not 2^n?

Because one state maps to itself. With XOR feedback, all zeros shifts in another 0 forever; with XNOR, all ones shifts in another 1. A maximal-length LFSR visits every other state, 2^n - 1 of them, before it repeats.

Which taps give a maximal-length LFSR?

For feedback into the first stage of an n-bit register, these tap sets give all 2^n - 1 states, with XOR or XNOR alike: 3 bits (3, 2), 4 bits (4, 3), 5 bits (5, 3), 6 bits (6, 5), 7 bits (7, 6), 8 bits (8, 6, 5, 4) and 16 bits (16, 15, 13, 4). Each was checked here by running the register through its whole period.

What is the difference between an XOR and an XNOR LFSR?

Only the stuck state and the sequence. An XOR LFSR locks up at all zeros, so it must be seeded with something else; an XNOR LFSR locks up at all ones, so a plain reset to zeros is a valid start. With the same taps both have the same period.

What are LFSRs used for?

Pseudo-random test patterns for chips, scrambling and whitening data on serial links, CRC error detection, spreading codes such as the GPS C/A code (built from two 10-bit LFSRs), and counters that need very little logic.

Is an LFSR a secure random number generator?

No. Its output is completely predictable: the Berlekamp-Massey algorithm recovers the shortest LFSR that produces a sequence from just 2n of its bits. LFSRs are fine for testing and noise-like signals, not for cryptography.