Linear Feedback Shift Register Calculator

Understanding Linear Feedback Shift Registers (LFSR)

A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function of its previous state. In digital logic, the only available linear functions of single bits are exclusive-OR (XOR) and exclusive-NOR (XNOR). LFSRs are widely used in telecommunications, cryptography, spread-spectrum systems (such as GPS and CDMA), digital circuit testing via Built-In Self-Test (BIST), and pseudo-random number generation (PRNG).

LFSR Topologies: Fibonacci vs Galois

There are two primary architectures for implementing an LFSR in hardware and software:

• Fibonacci LFSR (External Feedback): The feedback bit is computed by XORing several tap bits across the register. The entire register shifts by one position, and the feedback bit is fed into the newly vacated end of the register.
• Galois LFSR (Internal / Modular Feedback): When the output bit is 1, the register shifts and simultaneously applies XOR masks to internal state bits in parallel. Galois LFSRs typically execute faster in hardware because XOR gates do not form a deep cascade.

Characteristic Polynomials and Maximal Length (m-sequences)

An LFSR of length \(n\) bits can produce at most \(2^n - 1\) distinct non-zero states before repeating. The all-zero state is a trap state in XOR-based LFSRs because XORing zeros always yields zero.

When the feedback polynomial is a primitive polynomial over the Galois Field \(\text{GF}(2)\), the sequence generated is called a maximal length sequence or m-sequence, achieving the theoretical maximum period of:

$$T_{\text{max}} = 2^n - 1$$

For example, a 4-bit maximal LFSR with polynomial \(P(x) = x^4 + x + 1\) generates all 15 non-zero 4-bit permutations in a deterministic pseudo-random order.

Properties of Maximal Length Sequences

M-sequences possess ideal pseudo-noise properties:

• Balance Property: The number of ones in a full period is \(2^{n-1}\), while the number of zeros is \(2^{n-1} - 1\) (exactly one more one than zero).
• Run Property: Half the runs have length 1, one quarter have length 2, one eighth have length 3, mimicking true statistical randomness.
• Autocorrelation Property: The circular autocorrelation of an m-sequence has a sharp delta peak at zero shift and constant low value elsewhere, making it ideal for radar and spread-spectrum synchronization.