When the LFSR holds 1 and is shifted once, its value will always be the value of the polynomial mask. The LFSR must be initialized, i.e., seeded, to a nonzero value. LFSRs can never have the value of zero, since every shift of a zeroed LFSR will leave it as zero. This table should help to ensure that the implementation is correct. It also shows the first four values that the LFSR will hold after consecutive shifts when the LFSR is initialized to one. Table 3 lists one polynomial mask for each polynomial of a different size. Table 2 lists the period of each different size polynomial and the number of primitive polynomials that exist for each size. In Table 1, polynomials 1 and 2, 3 and 4, 5 and 6 are the duals of each other. For example, given the 6 th-degree polynomial, x 6 + x + 1, its dual is x 6-6 + x 6-1 + x 6-0, which is equal to x 6 + x 5 + 1.

The dual can be found by subtracting the exponent from the degree of the polynomial for each term. Every primitive polynomial also defines a second primitive polynomial, its dual. It takes n bits to implement the polynomial mask for an n th-degree polynomial.Įvery primitive polynomial will have an odd number of terms, which means that every mask for a primitive polynomial will have an even number of 1 bit. The mask is used in the code that implements the polynomial. The polynomial mask is created by taking the binary representation of the polynomial and truncating the right-most bit. Table 1 lists all the primitive 6 th-degree polynomials and their respective polynomial masks. In the case of primitive 6 th-degree polynomials, there are only six. Every number between 1 and 31 will occur in the shift register before it repeats. Consequently, a 6 th-degree polynomial will have 31 different states. A new state is transitioned to after each shift. A maximum length polynomial of degree n will have 2 n - 1 different states. We are interested in primitive polynomials because they will give us maximum length periods when shifting.

Just as with numbers, some polynomials are prime or primitive. There are 2 (6 - 1) = 32 different possible polynomials of this size. For example, a 6 th-degree polynomial with every term present is represented with the equation x 6 + x 5 + x 4 + x 3 + x 2 + x + 1. LFSRs and PolynomialsĪ LFSR is specified entirely by its polynomial. Figure 2 shows an LFSR implementation in C, and Figure 3 shows a 16-bit LFSR implementation in 8051 assembly. Generating the pseudo-random numbers only requires a right-shift operation and an XOR operation. LFSRs (linear feedback shift registers) provide a simple means for generating nonsequential lists of numbers quickly on microcontrollers. The application note describes how they can be implemented and techniques that can be used to improve the statistical properties of the numbers generated. Linear feedback shift registers are introduced along with the polynomials that completely describe them.