Linear Feedback Shift Register Calculator - Fibonacci and Galois LFSR Step Generator

A linear feedback shift register calculator generates the bit-by-bit output stream of an LFSR given a register length, an initial seed, and a feedback tap set, and reports the detected period so you can tell whether the tap set is primitive and therefore produces a maximal-length sequence.

• • Generate a deterministic pseudo-random bit stream: Step a maximal-length LFSR forward N cycles to get a reproducible sequence of bits that looks statistically random.
• • Validate a chosen feedback polynomial: Try different tap sets for a given register length and immediately see whether the detected period reaches 2^n - 1, confirming the polynomial is primitive.
• • Compare Fibonacci and Galois configurations: Run the same seed and tap set in both modes to see the offset output stream and confirm that the reciprocal tap set produces the same period.
• • Study cyclic redundancy check (CRC) math: Use the step table to trace how a serial CRC divider works in hardware, since CRCs are mathematically equivalent to Galois-form LFSRs.

The calculator treats the register as a fixed-width integer and applies the same recurrence that hardware LFSRs implement with XOR gates and flip-flops.

Switching between Fibonacci and Galois modes does not change the polynomial; it only changes whether the XOR gates sit outside the shift register or inside it.

Because LFSRs work on raw binary words, pair this calculator with our Binary Converter when you need to translate the resulting bit stream into decimal, hex, or octal for documentation or testing.

Each clock cycle the register drops its least significant bit (the output bit), shifts every other bit one position toward the LSB, and computes a new MSB from the XOR of the bits at the user-supplied tap positions. The tap positions, together with the implicit output tap at position 1, define a feedback polynomial over GF(2); when that polynomial is primitive, the resulting bit stream is a maximal-length m-sequence.

• n: Register length in bits. Period grows as 2^n - 1 for primitive polynomials (n in [2, 16]).
• seed: Initial non-zero state (decimal). Must satisfy 1 <= seed <= 2^n - 1, otherwise the register locks up at 0.
• taps: Comma-separated 1-indexed positions from the LSB. Position 1 is always an implicit tap and position n is required.
• lfsrMode: Either Fibonacci (external XOR chain) or Galois (internal XOR chain). Both produce identical periods for reciprocal tap sets.
• feedback_bit: Single-bit XOR of state[t-1] for every tap position t. Placed at the new MSB after the shift.
• period: Detected cycle length, equal to 2^n - 1 for maximal-length (primitive) polynomials and shorter otherwise.

For the Fibonacci configuration the XOR happens before the shift: compute the feedback bit, shift the register right by one, then insert the feedback bit at the new MSB.

For the Galois configuration the shift happens first, then a mask is XORed into the shifted register when the dropped LSB was 1.

According to Wikipedia, a linear-feedback shift register is a shift register whose input bit is a linear function of its previous state, and a maximal-length LFSR is one whose feedback polynomial is primitive over GF(2).

Each clock cycle shifts the register right by one bit, which is the exact operation our Bit Shift Calculator analyzes for arbitrary shift counts and widths.

Four concepts come up every time you design or analyze an LFSR. Understanding them makes this linear feedback shift register calculator's output - period, maximal-length flag, bit stream - easy to interpret.

These four concepts are enough to predict the period and lockup behavior of any LFSR you build with this calculator.

The feedback taps are coefficients of a polynomial over GF(2), and Polynomial Division Calculator applies the same modular-arithmetic view to general polynomial long division.

Pick a register length, seed, and tap set, choose Fibonacci or Galois, then read the bit stream, detected period, and maximal-length flag from the results panel.

1. 1 Choose a register length n: Pick n from 2 to 16 bits. The maximum period (2^n - 1) and maximum seed both grow with n; start with n = 8 for an initial exploration.
2. 2 Enter a non-zero seed: Type the seed as a decimal integer. The calculator rejects 0 because XOR LFSRs lock up at zero, and rejects seeds larger than 2^n - 1.
3. 3 Specify tap positions: List the interior tap positions as 1-indexed numbers from the LSB, comma-separated. Position 1 is implicit; position n is required. Try [3,4,8] for n = 8.
4. 4 Pick the configuration: Use Fibonacci for textbook external XOR chains, or Galois when you plan to implement the LFSR in software. Both produce the same period when their tap sets are reciprocals.
5. 5 Set the step count: Decide how many clock cycles to advance. The calculator prints that many output bits and reports the full detected period separately.
6. 6 Read the results: The output bit stream, initial and final states, detected period, and maximal-length flag appear at once. If the flag is false, try a different tap set and re-run.

For a quick sanity check, leave the defaults (n = 8, seed = 225, taps = [3,4,8], Fibonacci, 16 steps) and confirm that the maximal-length flag turns on and the period reaches 255.

Six concrete ways to use this linear feedback shift register calculator when you are designing, validating, or learning about shift-register-based circuits.

• • Detect maximal-length polynomials quickly: Try a tap set, read the period, and immediately see whether the polynomial is primitive. No need to factor polynomials by hand.
• • Generate reproducible pseudo-random streams: Step a maximal-length LFSR forward N cycles to get a deterministic bit stream that looks statistically random.
• • Compare Fibonacci and Galois outputs: Run the same seed and reciprocal tap sets in both modes to confirm the offset output streams and verify that both configurations produce identical maximal periods.
• • Trace CRC divider behavior: Use the step table to follow how a serial CRC divider processes each input bit, since CRCs are equivalent to Galois-form LFSRs.
• • Validate register length and lockup behavior: Confirm experimentally that an XOR LFSR with seed = 0 stays locked at zero, and that a non-primitive tap set produces a period shorter than 2^n - 1.
• • Plan test-pattern generators for digital circuits: Use the output stream as a deterministic pattern generator for built-in self-test (BIST) or signature analysis.

For users who need ready-to-use pseudo-random numbers rather than a bit stream they have to seed themselves, the Random Number Generator wraps an LFSR-style generator in a simpler interface.

Five factors that decide how useful a linear feedback shift register calculator output will be for your task, plus two important limitations to keep in mind.

• • This calculator only supports XOR-based feedback. XNOR feedback inverts the lockup state to all-ones; invert the output bits after each step if you need XNOR behavior.
• • LFSR bit streams are deterministic and statistically biased. Do not use them directly for cryptographic keys without a non-linear combiner.

Combined, these factors decide whether your LFSR is suitable for testing, simulation, CRC computation, or only for classroom demonstrations.

According to Xilinx Application Note XAPP052, LFSR counters with primitive feedback polynomials can replace natural binary counters for high-speed applications because the feedback logic uses only XOR gates, eliminating long carry chains.

When the maximal-length flag is false, you can use the Characteristic Polynomial Calculator to inspect the actual characteristic polynomial of the matrix and confirm why the period falls short of 2^n - 1.