Why are a primitive polynomial equations used in linear feedback shift registers?

Question

A real-world shift register uses lets say 4 bits, and it shifts each bit +1 from least significant to most significant. Its a simple formula. When reading up on these, why do they use or are defined by confusing equations such as 1+x+x^4?

Answer 1

The choice of which taps to use in Linear Feedback Shift Registers (LFSR) determines how many delayed registers, N are included in a sequence of pseudorandom generator (PRG) values before the sequence is repeated. Each binary delay register can be expressed as power of 2 in the formula and may used for feedback with/without inversion or feed-forward, using XOR gates combined to create the mathematical algorithm.

Only certain tap settings yield the maximal length sequences (MLS) of (2N-1). Depending on the valid initial condition (Seed) and parity (even, odd) there will always be one invalid condition of all zeros or all ones.

Thus MLS LFSR's are the design of choice for PRG or PRSG's. (these acronyms may help in further searches)

Applications include;

Data Encryption/Decryption
Digital Signal Processing
Wireless Communications
Built-in Self Test (BIST)
Data Integrity Checksums
Data Compression
Pseudo-random Number Generation (PN)
Direct Sequence Spread Spectrum
Scrambler/Descrambler
Optimized Counters

Answer 2

You refer to LFSRs in your question title but talk about the simplicity of shift registers in the question detail. Dealing with LFSRs...

Linear Feedback Shift Registers are a marvellous demonstration of the simplicity and power inherent in mathematics. An LFSR will count in an through every possible value it can hold for its bit size, except one value, in a seemingly random order that's actually fixed and repeatable. The skipped value is all-1's or all-0's, depending on the type of LFSR it is. The fact that it can do that with a shift register and maybe 4 or 5 XOR gates, depending on the LFSR length, can at first sight look incredible.

It's therefore hardly surprising that the underlying maths behind this remarkably simple and useful circuit has some depth to it. The polynomials describing their behaviour are only confusing if we're unfamiliar with the maths or unable to grasp it. That doesn't stop us appreciating it, though.

Translating the polynomial into a feedback term is quite straightforward. There's plenty of text showing this on the Internet.

Answer 3

Providing specific examples from the text may be easier to address.

But something similar is done for CRCs. Polynomials are occasionally used to express the values in certain bit positions. In your example, \$x^4+x+1\$ would be 10011.

If you fill in the zeros for the polynomial this makes more sense:

$$1x^4+0x^3+0x^2+1x^1+1x^0$$

The coefficients are the bit value and the rest is the value position. This can sometimes save a some writing and confusion if you had a large binary number like:

$$10000000000000001000000000000000 $$

This would simply be written in polynomial form with: $$x^{31}+x^{15}$$

For the LSFRs it's defining which bit positions are being used to generate the next value of the register. It's much easier to provide the polynomial defining the bit positions than it is to provide a binary number where the 1s are the bit positions.