How this instrument works
A linear-feedback shift register generates a long, pseudo-random-looking sequence of bits from a deceptively simple rule: every step, shift every bit one place to the right (the rightmost bit drops off and is discarded), and feed a brand-new bit in at the left — computed by XOR-ing two fixed 'tap' positions from the register's state BEFORE the shift. This page runs exactly one such step on a 4-bit register, with taps fixed at bit 3 and bit 2.
The XOR itself reuses this site's own truth-table identity for disagreement between two 0/1 values, applied here to the two tap bits: the feedback bit is 1 exactly when those two tap bits disagree, and 0 when they match. That single feedback bit becomes the new leftmost bit, while every other bit simply shifts one position to the right of where it started.
Real LFSRs are used in stream ciphers, error-detection codes, and pseudo-random number generators — a well-chosen set of tap positions can make the register cycle through every possible non-zero state before ever repeating, a property called being 'maximal length,' though verifying that property in general needs more than a single step.
- Enter the register's current four bits, from bit 3 (leftmost) down to bit 0 (rightmost, about to be dropped).
- Read New bit 3: the feedback value, found by XOR-ing the old bit 3 and bit 2.
- Read New bit 2 and New bit 1: the old bit 3 and old bit 2, each shifted one place to the right.
- Run the result back through as a new starting register to see the next step in the sequence.
Worked example — one step from register 1011
Starting from register 1011 (bit3=1, bit2=0, bit1=1, bit0=1): the feedback bit is bit3 XOR bit2 = 1 XOR 0 = 1, and the register shifts right, with the old bit0 (1) dropping off entirely. The new register reads new bit3=1 (the feedback), new bit2=1 (the old bit3), and new bit1=0 (the old bit2).
Starting from 0001, the feedback is 0 XOR 0=0, so the register shifts toward an all-zero leading state — which is exactly why a genuine LFSR is never started with all its tap-related bits already at 0, since it would then stay stuck producing no new information. Starting from 1100, the feedback is 1 XOR 1=0, since matching taps always cancel out under XOR.
Questions
What is a linear-feedback shift register?
A digital circuit that shifts its own bits one place every step, feeding a new bit in from a simple XOR combination of specific fixed 'tap' positions — a mechanism that can generate long, pseudo-random-looking sequences from very simple hardware.
Why are the tap positions fixed at bit 3 and bit 2?
This page demonstrates a single, specific 4-bit tap arrangement to keep the calculation concrete — different tap choices produce different sequences, and only specific tap combinations produce the longest possible 'maximal length' sequence before repeating.
What happens to the bit that falls off the right side?
It's discarded entirely — an LFSR only ever tracks a fixed number of bits, so the oldest bit disappears from the register the moment a new one is fed in at the left.
What are LFSRs actually used for?
Stream ciphers, error-detection codes, and pseudo-random number generation — their simple hardware requirements make them attractive wherever a long, evenly-spread sequence of bits is needed without heavy computation.
Why shouldn't an LFSR start with both tap bits at 0?
The feedback bit would then also be 0, and depending on the rest of the register's state, the sequence can get stuck producing no new variation — a well-chosen LFSR design avoids ever reaching that stuck condition during normal operation.