Free Linear Feedback Shift Register Calculator

Computers, being deterministic machines, cannot generate truly random numbers without external physical processes. Linear‑feedback shift registers (LFSR) offer an elegant solution by producing pseudo‑random binary sequences using simple XOR operations and a shift register structure. This Linear Feedback Shift Register calculator—supporting both Fibonacci and Galois configurations—lets you explore how seeds and taps influence the output of an LFSR, making it an ideal tool for studying shift registers, pseudo‑random number generators, and binary sequence generation.

What Are Shift Registers and How Do They Lead to LFSR?

A shift register is a chain of flip‑flops, each storing one bit. At each clock cycle, the contents move one position to the right (or left), with a new bit entering at one end and the last bit being discarded or forming the output. If the new input bit is computed as a linear function (XOR or NXOR) of some of the current bits, the circuit becomes a linear‑feedback shift register. The positions that participate in the feedback are called taps, and the initial configuration is known as the seed.

The XOR gate performs modulo‑2 addition and is the fundamental linear operation in LFSR designs. Its truth table is:

Input A	Input B	Output (A⊕B)
0	0	0
0	1	1
1	0	1
1	1	0

An NXOR gate can also be used (it is simply the complement of XOR). Because the operation is linear, the entire register constitutes a linear system over the Galois field GF(2).

The output sequence of an LFSR is periodic, with a maximum period of $2^n - 1$ (where $n$ is the register length), provided the seed is not all zeros (which would lock the register into a trivial all‑zero state). The period depends heavily on the tap selection; special sets of taps that yield the maximal period are called maximal‑length taps and correspond to the coefficients of a primitive polynomial.

Fibonacci LFSR vs Galois LFSR

There are two canonical architectures for linear‑feedback shift registers: Fibonacci and Galois. They use the same taps and seed but differ in how the feedback is applied.

Fibonacci LFSR

In a Fibonacci LFSR, all tapped bits are XORed together to form a single feedback value, which becomes the new input bit. The register then shifts to the right, discarding the rightmost bit as output. Mathematically, if $\vec{X} = (X_1,\dots,X_n)$ is the current state (with $X_1$ the leftmost) and $\vec{c} = (c_1,\dots,c_n)$ the tap vector (1 indicates a tap), the next state is:

\begin{aligned} X_i(t+1) &= X_{i+1}(t) \quad\text{for } i = 1,\dots,n-1,\$$2pt] X_1(t+1) &= \bigoplus_{j=1}^{n} \bigl(c_j \cdot X_j(t)\bigr). \end{aligned}

The symbol $\oplus$ denotes XOR. The output of the LFSR is the sequence of rightmost bits $X_n(t)$ over successive steps.

Galois LFSR

In a Galois LFSR, the feedback is applied during the shift. The output bit (the rightmost bit of the current state) directly influences the tap positions. A common implementation can be described as:

\begin{aligned} \text{Let } y &= X_n(t).\$$2pt] X_1(t+1) &= y,\\ X_i(t+1) &= X_{i-1}(t) \oplus \bigl(c_{i-1} \cdot y\bigr),\quad i=2,\dots,n, \end{aligned}

where $c_i$ (for $i=1,\dots,n-1$) indicates whether the $i$-th cell from the left is a tap. If $y=0$, the bits simply shift right and no tap flipping occurs; if $y=1$, the bits at tap positions are inverted before moving right.

Relationship Between the Two Types

For a given set of taps that produces a maximal‑length sequence, the outputs of the Fibonacci and Galois LFSRs are essentially the same sequence, but one is reversed and possibly shifted in phase relative to the other. The tap vectors that produce this dual behavior are reciprocals of each other. For example, a Fibonacci LFSR with taps at positions 1, 4, 6, and 12 (binary tap vector $100100000001$) yields a maximal‑length sequence. The corresponding Galois LFSR requires taps at positions 1, 7, 9, and 12 ($100000101001$) to generate the same cycle (after reversal and alignment).

Worked Example: 12‑Bit LFSR

Let’s illustrate with a concrete 12‑bit scenario: seed = $100110011001$ and taps = $110111011101$.

• Fibonacci mode: The XOR sum of the bits where the tap vector has a 1 is taken; this sum becomes the new leftmost bit. The rightmost bit of each state is recorded as output. After seven steps the register returns to the original state, producing the output stream starting with $10010111\ldots$ (period = 7).
• Galois mode: Using the same seed and taps, the register follows the Galois rule. The resulting output begins with $10100111\ldots$. Reversing this sequence and shifting it a few positions yields exactly the Fibonacci output, confirming the duality described above.

This example also shows that the period is only 7, far less than the maximal possible period $2^{12}-1 = 4095$. The short period occurs because the chosen taps do not form a maximal‑length set.

Practical Applications of LFSR

Linear‑feedback shift registers are ubiquitous in digital systems:

• Pseudo‑random number generators (PRNGs) for simulation, games, and cryptography.
• Built‑in self‑test (BIST) circuits that apply all possible input patterns to a digital block.
• Scramblers and descramblers in communication links to reduce signal correlation.
• Stream ciphers where a pseudo‑random key stream is XORed with plaintext.
• Noise generation for signal testing and interference simulation.

Because LFSRs are lightweight in hardware and can produce long cycles with little overhead, they remain a cornerstone of digital design.

How to Use the LFSR Calculator

The calculator on this page provides a hands‑on way to experiment with LFSR behavior:

1. Enter the seed and tap vectors as binary strings of equal length.
2. Select the LFSR type: Fibonacci (default) or Galois.
3. Choose the output mode:
   • Output – displays the generated bit sequence (grouped in 8‑bit blocks).
   • Steps – shows the full register state at each clock cycle.
   • Period – returns only the cycle length.
4. Optionally specify the number of bits to generate; if left blank, the calculator stops after one full period.
5. Expand “Additional setup” to:
   • Switch the linear gate from XOR to NXOR.
   • Enable “Dangerous calculations” if you want to allow sequences exceeding 10,000 steps (helpful for longer registers, e.g., 16‑bit with maximal period 65,535).

The calculator automatically detects maximal‑length LFSRs (period = $2^n-1$) and notifies you. It also halts if the register becomes all zeros, as such a state is not usable for LFSR operation.

Conclusion

Linear‑feedback shift registers are a classic digital building block for generating pseudo‑random binary sequences. With both Fibonacci and Galois architectures, a few lines of binary code can produce cycles of nearly any length. The Linear Feedback Shift Register calculator on this page makes it easy to explore how seed and tap choices affect the output, providing insight into shift registers, pseudo‑random number generation, and binary sequence generators. Try different configurations to see which taps yield the longest cycles and how the two LFSR types relate to each other.