Linear Feedback Shift Register (LFSR) Calculator
Enter a binary seed, the tap (feedback) positions, and the number of clock steps to run. The calculator simulates a Fibonacci or Galois Linear Feedback Shift Register with XOR or XNOR feedback, outputs the generated bit sequence and detected period, and shows every register state in the step-by-step panel.
What is a Linear Feedback Shift Register?
A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is the XOR (or XNOR) of specific bits from the register, called tap positions. At each clock cycle, the register shifts one place, the output bit falls off the end, and the feedback bit enters the other end. Because the next state depends only on a linear combination of the current bits, the sequence repeats after at most 2^n - 1 steps for an n-bit register (avoiding the all-zeros lock-up state). When the tap positions correspond to a primitive polynomial over GF(2), the LFSR achieves this maximum period and the output is called a maximal-length sequence or m-sequence. LFSRs are used in stream ciphers, digital communication, CRC error detection, test pattern generation, and anywhere that a fast, repeatable pseudo-random bit stream is needed.
Fibonacci vs. Galois LFSRs
The two main LFSR architectures produce the same period length for the same primitive polynomial, but they differ in hardware structure and bit ordering. In a Fibonacci (external feedback) LFSR, the selected tap bits are XORed together to form a single feedback bit that is shifted into the MSB while the register contents shift one position toward the LSB. The output bit is the value that falls off the LSB end. This is the textbook arrangement and the simplest to analyze. In a Galois (internal feedback) LFSR, the output bit from the LSB is instead fed back in parallel to each tap position within the register during the same clock cycle, while the register shifts right. The MSB is filled with the output bit. Galois LFSRs have shorter critical paths in hardware because all XOR operations happen in parallel rather than being chained. Both architectures produce sequences with the same period, but the bit order differs by a constant rotation.
How the feedback polynomial determines the period
The feedback polynomial is a polynomial over the two-element field GF(2) whose exponents correspond to the tap positions plus the implicit x^0 = 1 constant term. For a 4-bit LFSR with taps at positions 4 and 3, the polynomial is x^4 + x^3 + 1. If this polynomial is primitive over GF(2), meaning it cannot be factored into lower-degree polynomials with coefficients in GF(2), the LFSR achieves its maximum period of 2^n - 1 = 15 for n = 4. If the polynomial is not primitive, the period divides 2^n - 1 but is shorter. For example, using only tap 4 gives the polynomial x^4 + 1 = (x + 1)^4, which is not primitive, and the period is only 1 for any non-zero seed. The reference table above lists primitive polynomials for common register sizes up to 16 bits.
Applications and practical notes
LFSRs are used in many practical systems. In wireless communications, CDMA spreading codes are generated by LFSRs, and GSM uses the A5/1 stream cipher, which combines three LFSRs. CRC (cyclic redundancy check) algorithms are efficiently implemented as Galois LFSRs whose divisor polynomial matches the CRC polynomial. Test pattern generators in VLSI design use LFSRs because they cover a large fraction of possible input patterns in 2^n - 1 steps. For cryptographic applications, a single LFSR is not secure because the Berlekamp-Massey algorithm can recover the full state from just 2n output bits. Secure designs combine multiple LFSRs nonlinearly (e.g. the Geffe generator) or filter the output through a nonlinear function. In simulation and games, LFSRs are popular because they are extremely fast in both hardware and software while still passing basic statistical randomness tests.
Primitive polynomials for maximal-length LFSRs
| Bits (n) | Tap positions | Max period (2^n - 1) | Polynomial |
|---|---|---|---|
| 2 | 2, 1 | 3 | x^2 + x + 1 |
| 3 | 3, 2 | 7 | x^3 + x^2 + 1 |
| 4 | 4, 3 | 15 | x^4 + x^3 + 1 |
| 5 | 5, 3 | 31 | x^5 + x^3 + 1 |
| 6 | 6, 5 | 63 | x^6 + x^5 + 1 |
| 7 | 7, 6 | 127 | x^7 + x^6 + 1 |
| 8 | 8, 6, 5, 4 | 255 | x^8 + x^6 + x^5 + x^4 + 1 |
| 10 | 10, 7 | 1023 | x^10 + x^7 + 1 |
| 12 | 12, 11, 10, 4 | 4095 | x^12 + x^11 + x^10 + x^4 + 1 |
| 16 | 16, 15, 13, 4 | 65535 | x^16 + x^15 + x^13 + x^4 + 1 |
Tap positions (1-indexed from MSB) for common register sizes. These produce a period of 2^n - 1, visiting every non-zero state exactly once.
Frequently asked questions
What tap positions should I use for a maximal-length LFSR?
Choose tap positions that correspond to a primitive polynomial over GF(2) for your register size. The reference table in this calculator lists standard primitive polynomials for register sizes from 2 to 16 bits. For a 4-bit LFSR, use taps 4 and 3. For an 8-bit LFSR, use taps 8, 6, 5, and 4. These selections produce a period of 2^n - 1, visiting every non-zero state exactly once.
Why does my LFSR get stuck at all zeros?
An XOR-feedback LFSR locks permanently when every bit in the register is 0, because XOR of zeros is always zero, so the feedback bit is always zero and the register never changes. Avoid seeding with all-zeros. Alternatively, switch to XNOR feedback: XNOR of all-zeros produces a 1, so XNOR LFSRs include the all-zeros state in their sequence but exclude the all-ones state instead.
What is the difference between XOR and XNOR feedback?
XOR feedback is the standard choice. It cycles through 2^n - 1 states, skipping the all-zeros state. XNOR feedback inverts the feedback bit, which shifts the excluded state: an XNOR LFSR cycles through 2^n - 1 states and skips the all-ones state instead. Both produce the same period length with a primitive polynomial. XNOR is occasionally preferred in hardware when an active-low logic convention makes inversion free.
What does the period tell me?
The period is the number of clock steps before the register returns to exactly the same state it started in. After that point the output bit sequence repeats. For a maximal-length LFSR the period is 2^n - 1, so a 16-bit LFSR has a period of 65,535 steps. If the period is shorter, the tap positions do not form a primitive polynomial, and you should consult the reference table to find a maximal tap set.
Is an LFSR suitable for cryptographic use?
A single LFSR is not cryptographically secure. Given just 2n consecutive output bits, the Berlekamp-Massey algorithm can reconstruct the full internal state and predict all future and past outputs. Secure stream ciphers use several LFSRs combined by a nonlinear function, or pass the output through a nonlinear filter. Examples include the Geffe generator, the shrinking generator, and the A5/1 cipher used in GSM. For security-critical applications, use an established CSPRNG or stream cipher library.
How do I convert tap positions to a feedback polynomial?
Each tap position k corresponds to the term x^k in the polynomial, and the constant term 1 (= x^0) is always present. So taps at positions 4 and 3 give x^4 + x^3 + 1. The highest exponent equals the register length. To check whether a polynomial is primitive over GF(2), verify that it has no roots in GF(2^n) other than a primitive element, which is most easily done by consulting published tables or using a computer algebra system.
What is the difference between Fibonacci and Galois LFSRs?
Both produce the same period for the same primitive polynomial, but their hardware implementations differ. A Fibonacci LFSR XORs the tapped bits together externally and feeds one result bit into the MSB each cycle; the XOR chain can be long. A Galois LFSR applies feedback in parallel at each tap position during the shift, which shortens the critical timing path and makes it faster at high clock frequencies. The output sequences of the two types are identical up to a constant time shift.
Sources
- Golomb, S. W. (1967). Shift Register Sequences. Holden-Day. (Foundational text on LFSR theory and primitive polynomials.)
- National Institute of Standards and Technology (NIST). Random Bit Generation - NIST SP 800-90A.
- Schneier, B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. Wiley, 1996. (Section on LFSR-based stream ciphers.)