
Keywords: microcontroller microprocessor LFSR random


Pseudo Random Number Generation Using Linear Feedback Shift Registers
© Jun 30, 2010, Maxim Integrated Products, Inc.


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.
Introduction
LFSRs (
linear feedback shift registers) provide a simple means for generating nonsequential lists of numbers quickly on microcontrollers. Generating the pseudorandom numbers only requires a rightshift operation and an XOR operation.
Figure 1 shows a 5bit LFSR.
Figure 2 shows an LFSR implementation in C, and
Figure 3 shows a 16bit LFSR implementation in 8051 assembly.
LFSRs and Polynomials
A LFSR is specified entirely by its polynomial. 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. There are 2
^{(6  1)} = 32 different possible polynomials of this size. Just as with numbers, some polynomials are prime or primitive. We are interested in primitive polynomials because they will give us maximum length periods when shifting. A maximum length polynomial of degree n will have 2
^{n}  1 different states. A new state is transitioned to after each shift. Consequently, a 6
^{th}degree polynomial will have 31 different states. Every number between 1 and 31 will occur in the
shift register before it repeats. In the case of primitive 6
^{th}degree polynomials, there are only six.
Table 1 lists all the primitive 6
^{th}degree polynomials and their respective polynomial masks. The polynomial mask is created by taking the binary representation of the polynomial and truncating the rightmost bit. The mask is used in the code that implements the polynomial. It takes n bits to implement the polynomial mask for an n
^{th}degree polynomial.
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
^{th}degree polynomial, x
^{6} + x + 1, its dual is x
^{66} + x
^{61} + x
^{60}, which is equal to x
^{6} + x
^{5} + 1. In Table 1, polynomials 1 and 2, 3 and 4, 5 and 6 are the duals of each other.
Table 2 lists the period of each different size polynomial and the number of primitive polynomials that exist for each size.
Table 3 lists one polynomial mask for each polynomial of a different size. It also shows the first four values that the LFSR will hold after consecutive shifts when the LFSR is initialized to one. This table should help to ensure that the implementation is correct.
The Structure of a LFSR
LFSRs can never have the value of zero, since every shift of a zeroed LFSR will leave it as zero. The LFSR must be initialized, i.e., seeded, to a nonzero value. When the LFSR holds 1 and is shifted once, its value will always be the value of the polynomial mask. When the register is all zeros except the most significant bit, then the next several shifts will show the high bit shift to the low bit with zero fill. For example, any 8bit shift register with a primitive polynomial will eventually generate the sequence 0x80, 0x40, 0x20, 0x10, 8, 4, 2, 1 and then the polynomial mask.
Generating PseudoRandom Numbers with LFSR
In general, a basic LFSR does not produce very good random numbers. A better sequence of numbers can be improved by picking a larger LFSR and using the lower bits for the random number. For example, if you have a 10bit LFSR and want an 8bit number, you can take the bottom 8 bits of the register for your number. With this method you will see each 8bit number four times and zero, three times, before the LFSR finishes one period and repeats. This solves the problem of getting zeros, but still the numbers do not exhibit very good statistical properties. Instead you can use a subset of the LFSR for a random number to increase the permutations of the numbers and improve the random properties of the LFSR output.
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 4bit and a primitive 6bit 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 6bit LFSRs, no more than the bottom 4 bits should be used. In Figure 2, the bottom 16 bits are used from 32 and 31bit 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,
The Art of Computer Programming, Volume 2, Section 3.3. More extensive testing can be done using
NIST's Statistical Test Suite. NIST also has several publications describing random number testing and references to other test software.
Figure 1. Simplified drawing of a LFSR.
Figure 2. C code implementing a LFSR.
Figure 3. 8051 assembly code to implement a 16bit LFSR with mask 0D295h.
Table 1. All 6^{th}Degree Primitive Polynomials

Irreducible Polynomial 
In Binary Form 
Binary Mask 
Mask 
1 
x^{6} + x + 1 
1000011b 
100001b 
0x21 
2 
x^{6} + x^{5} + 1 
1100001b 
110000b 
0x30 
3 
x^{6} + x^{5} + x^{2} + x + 1 
1100111b 
110011b 
0x33 
4 
x^{6} + x^{5} + x^{4} + x + 1 
1110011b 
111001b 
0x39 
5 
x^{6} + x^{5} + x^{3} + x^{2} + 1 
1101101b 
110110b 
0x36 
6 
x^{6} + x^{4} + x^{3} + x + 1 
1011011b 
101101b 
0x2D 
Table 2. Polynomial Information
Degree 
Period 
Factors of Period 
No. of Primitive Polynomials of This Degree 
3 
7 
7 
2 
4 
15 
3, 5 
2 
5 
31 
31 
6 
6 
63 
3, 3, 7 
6 
7 
127 
127 
18 
8 
255 
3, 5, 17 
16 
9 
511 
7, 73 
48 
10 
1,023 
3, 11, 31 
60 
11 
2,047 
23, 89 
176 
12 
4,095 
3, 3, 5, 7, 13 
144 
13 
8,191 
8191 
630 
14 
16,383 
3, 43, 127 
756 
15 
32,767 
7, 31, 151 
1,800 
16 
65,535 
3, 5, 17, 257 
2,048 
17 
131,071 
131071 
7,710 
18 
262,143 
3, 3, 3, 7, 19, 73 
7,776 
19 
524,287 
524287 
27,594 
20 
1,048,575 
3, 5, 5, 11, 31, 41 
24,000 
21 
2,097,151 
7, 7, 127, 337 
84,672 
22 
4,194,303 
3, 23, 89, 683 
120,032 
23 
8,388,607 
47, 178481 
356,960 
24 
16,777,215 
3, 3, 5, 7, 13, 17, 241 
276,480 
25 
33,554,431 
31, 601, 1801 
1,296,000 
26 
67,108,863 
3, 2731, 8191 
1,719,900 
27 
134,217,727 
7, 73, 262657 
4,202,496 
28 
268,435,455 
3, 5 29, 43, 113, 127 
4,741,632 
29 
536,870,911 
233, 1103, 2089 
18,407,808 
30 
1,073,741,823 
3, 3, 7, 11, 31, 151, 331 
17,820,000 
31 
2,147,483,647 
2147483647 
69,273,666 
32 
4,294,967,295 
3, 5, 17, 257, 65537 
Not Available 
Table 3. Sample Masks and First Four Values Output after Initializing LFSR with One
Degree 
Typical Mask 
First Four Values in LFSR After Consecutive Shifts 
3 
0x5 
0x5 
0x7 
0x6 
0x3 
4 
0x9 
0x9 
0xD 
0xF 
0xE 
5 
0x1D 
0x1D 
0x13 
0x14 
0xA 
6 
0x36 
0x36 
0x1B 
0x3B 
0x2B 
7 
0x69 
0x69 
0x5D 
0x47 
0x4A 
8 
0xA6 
0xA6 
0x53 
0x8F 
0xE1 
9 
0x17C 
0x17C 
0xBE 
0x5F 
0x153 
10 
0x32D 
0x32D 
0x2BB 
0x270 
0x138 
11 
0x4F2 
0x4F2 
0x279 
0x5CE 
0x2E7 
12 
0xD34 
0xD34 
0x69A 
0x34D 
0xC92 
13 
0x1349 
0x1349 
0x1AED 
0x1E3F 
0x1C56 
14 
0x2532 
0x2532 
0x1299 
0x2C7E 
0x163F 
15 
0x6699 
0x6699 
0x55D5 
0x4C73 
0x40A0 
16 
0xD295 
0xD295 
0xBBDF 
0x8F7A 
0x47BD 
17 
0x12933 
0x12933 
0x1BDAA 
0xDED5 
0x14659 
18 
0x2C93E 
0x2C93E 
0x1649F 
0x27B71 
0x3F486 
19 
0x593CA 
0x593CA 
0x2C9E5 
0x4F738 
0x27B9C 
20 
0xAFF95 
0xAFF95 
0xF805F 
0xD3FBA 
0x69FDD 
21 
0x12B6BC 
0x12B6BC 
0x95B5E 
0x4ADAF 
0x10E06B 
22 
0x2E652E 
0x2E652E 
0x173297 
0x25FC65 
0x3C9B1C 
23 
0x5373D6 
0x5373D6 
0x29B9EB 
0x47AF23 
0x70A447 
24 
0x9CCDAE 
0x9CCDAE 
0x4E66D7 
0xBBFEC5 
0xC132CC 
25 
0x12BA74D 
0x12BA74D 
0x1BE74EB 
0x1F49D38 
0xFA4E9C 
26 
0x36CD5A7 
0x36CD5A7 
0x2DABF74 
0x16D5FBA 
0xB6AFDD 
27 
0x4E5D793 
0x4E5D793 
0x6973C5A 
0x34B9E2D 
0x5401885 
28 
0xF5CDE95 
0xF5CDE95 
0x8F2B1DF 
0xB25867A 
0x592C33D 
29

0x1A4E6FF2 
0x1A4E6FF2 
0xD2737F9 
0x1CDDF40E 
0xE6EFA07 
30 
0x29D1E9EB 
0x29D1E9EB 
0x3D391D1E 
0x1E9C8E8F 
0x269FAEAC 
31 
0x7A5BC2E3 
0x7A5BC2E3 
0x47762392 
0x23BB11C9 
0x6B864A07 
32 
0xB4BCD35C 
0xB4BCD35C 
0x5A5E69AE 
0x2D2F34D7 
0xA22B4937 
The content on this webpage is protected by copyright laws of the United States and of foreign countries. For requests to copy this content, contact us.
APP 4400: Jun 30, 2010
APPLICATION NOTE 4400,
AN4400,
AN 4400,
APP4400,
Appnote4400,
Appnote 4400
