How to use the lfsr sequence generator
- Enter the register length n and the taps as a list of exponents, such as 4, 3.
- Enter a seed from 1 to 2 to the power n minus 1, and choose Fibonacci or Galois style.
- Enter the number of output bits to show.
- Read the period and the bit sequence, and compare it with the maximal length.
Formula
Fibonacci style: the new bit is the XOR of the register bits at the tap positions, and the register shifts by one
Galois style: the bit shifted out is XORed into the register at the tap positions
A register of n bits has at most 2 to the power n minus 1 states, because the all-zero state never changes
Taps that follow a primitive polynomial give the maximal period 2 to the power n minus 1.
A 4 bit register with taps 4 and 3
For x to the 4 plus x to the 3 plus 1, with seed 1, the period is 15, which is the maximum for 4 bits. The first 32 output bits in Fibonacci style are 10001001101011110001001101011110, and in Galois style they are 10011010111100010011010111100010. Both repeat every 15 bits.
An 8 bit register with taps 8, 6, 5 and 4 and seed 1 has a period of 255. The preset with taps 4 and 2 does not follow a primitive polynomial, so its period is shorter than the maximum and the tool says so.
Shift registers in practice
A linear feedback shift register is a row of bits that shifts one place on each step. The bit that enters is a XOR of a few chosen positions, called taps. It needs very little hardware, so LFSRs are used for scrambling signals, test patterns, error check codes and simple noise. The two styles give different bit orders from the same polynomial, though both have the same period.
The outputs of a single register are completely predictable from 2n bits of output, so a plain LFSR is not secure as a cipher on its own.
Choosing taps
Tables of primitive polynomials list tap sets that give the maximal period for each length. Enter the exponents with the highest one equal to the register length. If the period shown is smaller than the maximum, the taps are not primitive. See the CRC Calculator for Multiple Algorithms for the related error check codes, the CRC32 Checksum Calculator for a common one and the Noncryptographic Hash Calculator for other fast mixes. The Binary Calculator helps read the states in base 2.
Assumptions and limits
- The register holds 2 to 32 bits, and the seed cannot be zero.
- Taps are the exponents of the feedback polynomial. The highest must equal the register length.
- The settings shown are examples. Use the taps that suit your design.
- Up to 256 output bits are shown. The period is found for the whole register.
Frequently asked questions
Why can the seed not be zero?
A register of all zeros produces only zeros, because the XOR of zeros is zero. It would never leave that state.
What is the difference between the two styles?
They arrange the XOR gates differently. Both give the same period, but the bit order and the register contents differ.
How do I know the taps are maximal?
If the period shown equals 2 to the power n minus 1, the taps give a maximal length sequence.
Can I use it to encrypt data?
Not safely. Anyone with enough output bits can solve for the taps and predict the rest of the sequence.