How the LFSR Calculator Works
A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function — here, an XOR — of some of its previous bits, called taps. This calculator implements the standard Fibonacci (external-XOR) LFSR: on each clock cycle, the tapped bits are XORed together to form a feedback bit, every bit shifts one position toward the output end, the bit that shifts out becomes the next bit of the output sequence, and the feedback bit is loaded into the newly empty position at the other end.
The feedback and shift rule
Number the register's bits 1 through n from left (most significant, entry point) to right (least significant, output point). A tap set T ⊆ {1, …, n} — which must include position n — defines the feedback bit as f = b₍t₁₎ ⊕ b₍t₂₎ ⊕ … for every tap position in T. Each clock cycle, the rightmost bit (position n) is read off as the next output bit, every other bit shifts one place to the right, and f is written into position 1. This is exactly the update rule implemented by the calculator above. The tap set corresponds to a characteristic polynomial over GF(2); taps at positions 4 and 3, for example, correspond to x⁴ + x³ + 1.
Period and maximal-length sequences
Because the feedback function is linear and always includes position n, the state transition is a bijection on the register's 2ⁿ possible values, with the all-zero state fixed in place. A nonzero seed therefore cycles indefinitely through nonzero states only, and the cycle length (period) always divides evenly into the register's state space, topping out at 2ⁿ − 1. When the tap set corresponds to a primitive polynomial over GF(2), every nonzero seed produces a single cycle of the maximum possible length 2ⁿ − 1 — this is called a maximal-length sequence or m-sequence, and it is the configuration used in most pseudo-noise (PN) generators, CRC circuits, and stream ciphers. Other tap sets split the 2ⁿ − 1 nonzero states into several shorter cycles instead of one long one.
Practical notes
- Seed must be nonzero: an all-zero state is a fixed point — its feedback is always 0, so the register never changes. This calculator rejects an all-zero seed.
- Position n must be tapped: the rightmost (highest-numbered) position must be included in the tap set for the transition to be invertible; leaving it out can make bits collide onto the same next state instead of forming a clean cycle.
- Known maximal tap sets: commonly cited primitive tap sets (numbered 1 = leftmost, n = rightmost, as used here) include {3,2} for n = 3, {4,3} for n = 4, {5,3} for n = 5, and {7,6} for n = 7 — each gives the full 2ⁿ − 1 period for any nonzero seed.
- Applications: LFSRs generate pseudo-random bit streams, scramble/whiten data in communications links, drive built-in self-test (BIST) circuits, compute CRC checksums, and form building blocks inside stream ciphers.