Understanding Shift Registers and LFSRs
A shift register is a chain of memory elements (flip-flops) that moves data one position per clock cycle. In its simplest form, bits cascade from left to right or right to left, with new input appearing at one end and output exiting the other.
An LFSR adds feedback: instead of shifting in a static 0 or 1, the new input bit is computed from a linear combination of tapped positions. The taps are specified as a binary coefficient vector, where 1 marks positions whose bits participate in the feedback logic, and 0 marks positions that do not.
The key insight is linearity. The feedback operation uses only XOR (addition modulo 2), never multiplication or other nonlinear gates. This constraint makes LFSRs mathematically tractable yet capable of generating sequences that appear random for many practical applications.
Fibonacci versus Galois Topology
LFSRs come in two main flavours, distinguished by where feedback is injected and how taps are processed:
- Fibonacci LFSR: Tap positions are XORed together to produce a single feedback bit, which enters the shift register at one end (usually the left). The bit exiting the opposite end (usually right) becomes the output. This configuration resembles a classic feedback loop.
- Galois LFSR: Also called serial or internal-feedback configuration. When the output bit is 0, a simple right shift occurs with 0 fed in. When the output bit is 1, the shift still happens rightward, but each tapped position is inverted (XORed with 1). The output is always the rightmost bit.
Both topologies can produce identical output sequences for appropriately chosen tap patterns, though their internal state sequences differ. Galois tends to be faster in hardware since all shifts happen in parallel.
LFSR Core Equations
The fundamental calculation in an LFSR involves counting the number of bits in the seed (initial state) and the tap coefficient vector. These lengths must match for the register to function correctly.
Message length = number of bits in initial state (seed)
Coefficients length = number of bits in tap vector
Constraint: Message length = Coefficients length
Fibonacci feedback bit = XOR of all (bit[i] AND coefficient[i]) for i = 0 to n−1
Galois: if output bit = 1, XOR each tapped position with feedback; else, shift with 0
Message length— The bit-width of the initial state or seedCoefficients length— The bit-width of the tap pattern vectorFeedback bit (Fibonacci)— Result of XORing all tapped bit positions together
Common Pitfalls and Considerations
Using an LFSR effectively requires attention to several design and operational details.
- All-Zero Seed is a Dead End — If the initial state is all zeros, all subsequent states will remain zero and produce no useful output. Always initialize with at least one '1' bit. This null state is absorbing and will never transition to any other state.
- Tap Pattern Determines Period Length — Not every tap configuration yields a maximal-length sequence. A given register width has at most 2^n − 1 distinct non-zero states, but poor tap choices produce much shorter cycles. Primitive polynomials (in GF(2)) guarantee maximal length, but discovering them requires careful mathematical study or lookup tables.
- Identical Taps and Message Length — The tap coefficient vector must have exactly the same bit-width as your seed. Mismatched lengths break the feedback logic. If you have a 16-bit register, provide exactly 16 tap bits, using 0 for non-tapped positions and 1 for active feedback taps.
- XOR vs XNOR Affects Behavior — Some LFSR designs use XNOR (complement of XOR) for feedback instead of pure XOR. This inverts the logic and can change the output sequence significantly. Verify which operation your application or standard specifies before running simulations.
Practical Applications of LFSRs
Cryptography: Stream ciphers like A5/1 (used in GSM) and E0 (Bluetooth) combine multiple LFSRs to generate keystreams. Solo LFSRs are cryptographically weak (predictable from short output), but their speed makes them attractive in hardware-constrained environments.
Test and Diagnostics: Built-in self-test (BIST) circuits use LFSRs to generate exhaustive test patterns. A maximal-length LFSR produces every possible n-bit state (except all-zero) exactly once, ensuring comprehensive coverage of circuit logic.
Error Detection and Correction: Cyclic redundancy checks (CRCs) are implemented using polynomial division over GF(2), mathematically equivalent to LFSR operation. The remainder detects transmission errors in data.
Noise Simulation: The pseudo-random output of an LFSR approximates white noise, useful for modelling interference, jitter, and signal degradation in communication system simulations.