LFSR Period Calculator

Find the period of a linear-feedback shift register from its length and taps: tests whether the polynomial is primitive, simulates the register from your seed in Fibonacci or Galois form, shows the lock-up state, the first output bits and the balance and run counts of the sequence.

Calculator Electronics Updated Oct 15, 2026
How to Use
  1. Enter the register length n, from 2 to 32 stages.
  2. Give the taps as stage positions (16,15,13,4), as a hex tap mask (0xD008, bit i − 1 for stage i) or as a CRC-style polynomial (0xA011, x16 implied). Pick the format with the buttons above the field.
  3. Choose Fibonacci (taps XORed together and fed into stage 1) or Galois (the output XORed into the tapped stages), and XOR or XNOR feedback.
  4. Optionally change the seed (decimal, hex or binary) and add a clock frequency to get the time before the sequence repeats.
  5. Read the period, whether the polynomial is primitive, and the lock-up state. The diagram shows the register with its taps and the first 48 output bits; Show Work has the primitive test, the balance and the run counts.
Register
stages, 2 to 32
stage numbers, e.g. 16,15,13,4bit i − 1 = stage i, e.g. 0xD008xn implied, e.g. 0xA011
dec, 0x, 0b
Hz, kHz, MHz
Presets
Register & output
Period
—
Maximum
—
Primitive
—
Lock-up state
—
Polynomial
—
Repeat time
—

Worked Example

16-bit register, taps 16, 15, 13, 4 (the 16-bit entry in Xilinx XAPP052). The feedback polynomial is p(x) = x16 + x15 + x13 + x4 + 1, tap mask 0xD008. The largest possible period is 216 − 1 = 65,535 = 3 × 5 × 17 × 257. Reducing x65,535 modulo p(x) gives 1, and x65,535/3, x65,535/5, x65,535/17 and x65,535/257 do not, so p(x) is primitive and the register is maximal length. Simulating from seed 0x0001 confirms it: the state first comes back after 65,535 clocks, the output has 32,768 ones and 32,767 zeros, and the longest run is 16 ones. At 100 MHz the sequence repeats every 655 µs.

4-bit register, taps 4, 2. p(x) = x4 + x2 + 1 = (x2 + x + 1)2, so it is not even irreducible. From seed 0x1 the states run 1 → 2 → 5 → A → 4 → 8 and back to 1: a period of 6 out of a possible 15. With a reducible polynomial the period depends on the seed; seed 0x6 sits on a 3-state cycle (6 → D → B). The maximal 4-bit taps are 4,3 (or the mirror pair 4,1).

The common mistake: using a CRC polynomial as an LFSR. CRC-16 (0x8005) is x16 + x15 + x2 + 1, taps 16, 15, 2. Three taps means an even number of terms, so p(1) = 0 and x + 1 divides the polynomial; it cannot be primitive, and from seed 1 the register repeats after 32,767 states, half the maximum. CRC-CCITT 0x1021 (taps 16, 12, 5) does the same. CRC polynomials are chosen for error detection, where the x + 1 factor is a feature; LFSR polynomials must be primitive.

Show Work

Enter the register length and taps to see the working.

Formulas

Maximum period
Pmax = 2n − 1
All 2n states except the lock-up state; reached only by a primitive polynomial
Feedback polynomial
p(x) = xn + Σ xti + 1
One term per tap ti; tap n is always present
Fibonacci step
Q1′ = ⊕ Qti, Qi+1′ = Qi
Output = Qn; XNOR adds a NOT to the feedback
Galois step
Qi′ = Qi+1 ⊕ (out · [i is a tap])
out = Q1, Qn+1 = 0; in software: s >>= 1, then s ^= mask when out = 1
Primitive test
xN ≡ 1, xN/q ≠ 1 (mod p)
N = 2n − 1, for every prime q dividing N
Balance of an m-sequence
ones = 2n−1, zeros = 2n−1 − 1
Golomb’s first postulate; swapped when the output is inverted
Runs of an m-sequence
runs = 2n−1, half of length 1
A quarter of length 2, an eighth of length 3; one run of n ones and one of n − 1 zeros
Repeat time
T = P / fclk
65,535 / 100 MHz = 655 µs; 232 − 1 at 1 MHz = 71.6 min

Why Some Taps Run the Full Length

A shift register with linear feedback is a state machine whose next state is a fixed linear function of the current one. Written as a polynomial over GF(2), the register multiplies its state by x modulo p(x) on every clock, so the period of any state divides the order of x in that ring. When p(x) is primitive, the order of x is 2n − 1 and every non-zero state lies on one long cycle: an m-sequence (maximal-length sequence). When p(x) is irreducible but not primitive, every non-zero state has the same shorter period (x6 + x3 + 1 gives 9, not 63). When p(x) factors, the register splits into cycles of different lengths and the period depends on where you start.

Solomon Golomb’s Shift Register Sequences (1967) set out the three randomness postulates that m-sequences satisfy: balance (one more 1 than 0 over a period), the run distribution (half the runs have length 1, a quarter length 2, and so on) and a two-valued autocorrelation. Those properties are why m-sequences serve as test patterns, spreading codes and noise sources, and why they are useless as cryptographic keystreams: 2n consecutive output bits determine the taps through the Berlekamp–Massey algorithm.

Peter Alfke’s Xilinx application note XAPP052 (1996) gave FPGA designers a table of maximal-length taps for 3 to 168 stages, drawn with XNOR feedback so that a register that powers up at all zeros starts running; its lock-up state is all ones instead. Its 4-, 8- and 16-bit entries are the first three presets above. The ITU-T O.150 recommendation fixes the pseudo-random test sequences used in telecom bit-error-rate testers by the number of stages and the two stages that are added modulo two:

PatternStagesTapsLengthLongest run of zeros
29 − 199, 55118 (non-inverted)
211 − 11111, 92,04710 (non-inverted)
215 − 11515, 1432,76715 (inverted)
220 − 12020, 3 or 20, 171,048,57519 (non-inverted; zero-suppressed variant for 20, 17)
223 − 12323, 188,388,60723 (inverted)
229 − 12929, 27536,870,91129 (inverted)

From ITU-T O.150 (05/96), clause 5. Inverting the output turns the single run of n ones into n zeros, which is the harder case for clock recovery and is why the longer patterns are specified inverted. Any tap set that works also works mirrored: if p(x) is primitive so is its reciprocal, which turns taps 16, 15, 13, 4 into 16, 12, 3, 1 and produces the same sequence backwards.

About This Calculator

This calculator takes a register length up to 32 and its taps in any of the three common notations, decides whether the polynomial is primitive with the exact order test rather than a lookup table, and then simulates the register you described, Fibonacci or Galois, XOR or XNOR, from your own seed. Up to 24 stages the period is measured by running the register until the state repeats, which also yields the balance and run counts of the sequence; above that, a primitive polynomial is reported as 2n − 1 without simulation and a non-primitive one is simulated for 16,777,216 steps before giving up. The lock-up state is found as the fixed point of the step function, so it is right for XNOR and Galois variants too.

The preset tap sets come from the Xilinx XAPP052 table and ITU-T O.150, and each preset period was re-derived with a separate simulation before publishing. All calculations run in your browser; nothing you enter is sent anywhere.

It is for FPGA and ASIC designers choosing a counter or scrambler, firmware developers writing a small pseudo-random generator, and students checking a homework polynomial.

Related calculators: CRC Calculator (the same shift registers used for error detection), Barker Code Calculator and Hamming Code Calculator.

Frequently Asked Questions

What is the maximum period of an LFSR?

An n-stage register has 2n states, and one of them (all zeros for XOR feedback, all ones for XNOR) never changes, so the longest possible cycle is 2n − 1. A 16-bit LFSR can run at most 65,535 states and a 32-bit one 4,294,967,295. Only taps whose polynomial is primitive reach that length; 16-bit taps 16,15,13,4 do, 16-bit taps 16,15,2 (the CRC-16 polynomial) only run 32,767.

What is the difference between a Fibonacci and a Galois LFSR?

A Fibonacci LFSR XORs the tapped stages together and shifts the result into stage 1; a Galois LFSR takes the output bit and XORs it into each tapped stage as the register shifts. Both implement the same polynomial and have the same period, but the Galois form has one XOR gate per tap in parallel instead of a chain, so it is faster in hardware and in software (shift, then XOR a constant when the output bit is 1). The state sequences differ, so the same seed gives a different starting point.

Why does my LFSR get stuck at zero?

With XOR feedback a register full of zeros feeds back 0 ⊕ 0 = 0 forever, so it never leaves that state. Seed the register with any non-zero value, or use XNOR feedback (as the Xilinx XAPP052 designs do), which locks up at all ones instead; a power-on reset to all zeros then starts it safely.

How do I tell if a tap set gives maximal length without simulating it?

Check that the feedback polynomial is primitive: xN ≡ 1 modulo p(x) for N = 2n − 1 but xN/q ≢ 1 for every prime factor q of N. Two quick rejections: an odd number of taps (an even number of polynomial terms) means x + 1 divides p(x), and a tap set in which n and every tap share a common factor (6 and 3, say) is never primitive. This calculator runs the full test for any n up to 32.

Which taps are used for PRBS-7, PRBS-9, PRBS-15, PRBS-23 and PRBS-31?

The ITU-T O.150 test patterns are PRBS-9 (stages 9 and 5, 511 bits), PRBS-11 (11 and 9, 2,047 bits), PRBS-15 (15 and 14, 32,767 bits, inverted), PRBS-20 (20 and 3, or 20 and 17), PRBS-23 (23 and 18, 8,388,607 bits, inverted) and PRBS-29 (29 and 27). PRBS-7 (7 and 6, 127 bits) and PRBS-31 (31 and 28, 2,147,483,647 bits) follow the same two-tap pattern and come from the XAPP052 table; all of them are primitive, as the calculator confirms.

How do I use the LFSR Period Calculator?

Just type your numbers. The answer shows up right away — there is no button to press. Change anything and it updates by itself.

Is it free? Does it work without internet?

Yes to both. It is free with no sign-up, and once the page has loaded it keeps working even with no internet.

Where does my data go?

Nowhere — every calculation runs on your own device. Nothing you enter is uploaded, logged, or stored.

Common Use Cases

FPGA counter replacement

A 16-bit LFSR with taps 16,15,13,4 cycles through 65,535 states with two XOR gates, where a binary counter needs a 16-bit carry chain. At 100 MHz it repeats every 655 µs.

PRBS-7 serial link test

Taps 7,6 give a 127-bit pattern with 64 ones and 63 zeros and runs no longer than 7, the standard quick eye-diagram stimulus for SerDes links.

Checking a tap set before building it

Taps 4,2 look plausible but x4 + x2 + 1 = (x2 + x + 1)2: from seed 1 the register repeats after 6 states instead of 15.

Noise and dither generators

A 23-bit register with taps 23,18 produces 8,388,607 bits before repeating; clocked at 44.1 kHz that is 190 s of noise with a flat spectrum.

Scramblers and spread spectrum

GPS C/A codes combine two 10-stage registers (taps 10,3 and 10,9,8,6,3,2) whose 1,023-chip m-sequences are XORed into Gold codes; the period of each half is checked here.

Last updated: