APPLICATION NOTE 4400

Abstract: Linear feedback shift registers are introduced along with the polynomials that completely describe them. The application note describes how they can be implemented and techniques that can be used to improve the statistical properties of the numbers generated.

Every 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. Every primitive polynomial also defines a second primitive polynomial, its dual. The dual can be found by subtracting the exponent from the degree of the polynomial for each term. For example, given the 6

Shifting the LFSR more than once before getting a random number also improves its statistical properties. Shifting the LFSR by a factor of its period will reduce the total period length by that factor. Table 2 has the factors of the periods.

The relatively short periods of the LFSRs can be solved by XORing the values of two or more different sized LFSRs together. The new period of these XORed LFSRs will be the LCM (least common multiple) of the periods. For example, the LCM of a primitive 4-bit and a primitive 6-bit LFSR is the LCM(15, 63), which is 315. When joining LFSRs in this way, be sure to use only the minimum number of bits of the LFSRs; it is a better practice to use less than that. With the 4- and 6-bit LFSRs, no more than the bottom 4 bits should be used. In Figure 2, the bottom 16 bits are used from 32- and 31-bit LFSRs. Note that XORing two LFSRs of the same size will not increase the period.

The unpredictability of the LFSRs can be increased by XORing a bit of "entropy" with the feedback term. Some care should be taken when doing this—there is a small chance that the LFSR will go to all zeros with the addition of the entropy bit. The zeroing of the LFSR will correct itself if entropy is added periodically. This method of XORing a bit with the feedback term is how CRCs (cyclic redundancy checks) are calculated.

Polynomials are not created equal. Some polynomials will definitely be better than others. Table 2 lists the number of primitive polynomials available for bit sizes up to 31 bits. Try different polynomials until you find one that meets your needs. The masks given in Table 3 were randomly selected.

All the basic statistical tests used for testing random number generators can be found in Donald Knuths,

Irreducible Polynomial | In Binary Form | Binary Mask | Mask | |

^{6} + x + 1 |
||||

^{6} + x^{5} + 1 |
||||

^{6} + x^{5} + x^{2} + x + 1 |
||||

^{6} + x^{5} + x^{4} + x + 1 |
||||

^{6} + x^{5} + x^{3} + x^{2} + 1 |
||||

^{6} + x^{4} + x^{3} + x + 1 |

Degree | Period | Factors of Period | No. of Primitive Polynomials of This Degree |

Degree | Typical Mask | First Four Values in LFSR After Consecutive Shifts | |||