A shift register that feeds itself

An ordinary shift register needs an external serial input. A linear-feedback shift register (LFSR) instead computes that input itself, by XORing together a fixed subset of the register's own bits (its "taps") and feeding the result back into the first stage.

Why XOR feedback produces long sequences

Because XOR feedback is linear, the register cycles through a long sequence of distinct states before repeating — for a well-chosen set of taps, an N-bit LFSR visits all 2^N−1 nonzero states exactly once before returning to its starting value, a so-called maximum-length sequence. The output looks statistically noise-like even though the whole thing is entirely deterministic sequential logic.

Building one from Boolflow's SHIFT4

Take a SHIFT4 block, XOR two of its output bits (the two highest stages, Q2 and Q3, are a tap pair known to give a maximum-length 4-bit sequence), and feed that XOR's output into the shift register's serial input instead of an external signal. There is one catch: the registers in Boolflow power up at 0000, and a plain XOR LFSR would stay there forever, since XORing zeros always gives zero. Use an XNOR gate instead — the lock-up state moves to 1111, 0000 becomes an ordinary state, and the register walks through 15 of its 16 values.

Where it's used

The exact same structure that generates pseudo-random test patterns for chip self-test also computes CRC checksums for detecting transmission errors — a CRC is just an LFSR run over the message bits instead of its own free-running feedback. Build one in the circuit editor, toggle the CLOCK, and watch the 4-bit output cycle through 15 different values before repeating.