linear feedback shift register truth table

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.

Linear feedback shift register truth table