Linear feedback shift registers
A LFSR (linear feedback shift register) is a shift register where the input is a linear function of two or more bits (taps). There are many possible configurations, the one presented here is very simple and has the property that it will start from an input of all 0's and is very easy to implement in software and hardware. A LFSR of this type will never contain only 1's and would stall if loaded with that value. Only some combinations of taps and lengths will generate a sequence with a period of 2n-1 cycles.
If you need a counter and it does not have to count in a linear way then a LFSR is faster and requires less hardware resources.
Some possible uses:
- Pseudo random number generator
- Head and tail pointers in a FIFO
- Program counter in a simple CPU
The math involved in analyzing the properties of a LFSR uses Galois fields:
A simple simulation of a LFSR with two taps: lfsrsim.zip
A complete list of all dual tap LSFRs up to 42 bit in length and their periods: lfsrperiods.txt
Contents
Optimal implementations (Your compiler may think differently)
VHDL
signal lfsr : std_logic_vector(14 downto 0); lfsr <= lfsr(13 downto 0) & (lfsr(14) xnor lfsr(0));
Verilog
reg [14:0] lfsr; lfsr <= {lfsr[13:0], lfsr[14] ~^ lfsr[0]};
ARM
Consecutive taps:
MOVS r0,r0,lsl #1 EORCC r0,r0,#1<<31-14 EORMI r0,r0,#1<<31-14
Non-consecutive taps:
MOVS r0,r0,lsr #1 EORCC r0,r0,#1<<14 TST r0,#1 EORNE r0,r0,#1<<14
MMX
MOVQ mm6,mm5 //lfsr PSRLQ mm6,mm3 //Tap1 MOVQ mm7,mm5 PSRLQ mm7,mm4 //Tap2 PSLLQ mm5,1 PXOR mm6,mm1 //1 PXOR mm6,mm7 PAND mm6,mm1 //1 POR mm5,mm6
C++
n2 = (lfsr >> 14) xor (lfsr >> 13); n2 &= 1; lfsr <<= 1; lfsr &= mask; lfsr += n2 ^ 1;
BASIC
tmp = 1 If (lfsr And t1) Then tmp = 0 If (lfsr And t2) Then tmp = tmp Xor 1 lfsr = (lfsr + lfsr) + tmp
Maximum periods
Length | Taps giving maximum period | Maximum Period | Type |
---|---|---|---|
2 | 1 | 3 | 2n-1, Prime |
3 | 1, 2 | 7 | 2n-1, Prime |
4 | 1, 3 | 15 | 2n-1 |
5 | 2, 3 | 31 | 2n-1, Prime |
6 | 1, 5 | 63 | 2n-1 |
7 | 1, 3, 4, 6 | 127 | 2n-1, Prime |
8 | 3, 5 | 217 | - |
9 | 4, 5 | 511 | 2n-1 |
10 | 3, 7 | 1023 | 2n-1 |
11 | 2, 9 | 2047 | 2n-1 |
12 | 1, 11 | 3255 | - |
13 | 3, 10 | 8001 | - |
14 | 1, 13 | 11 811 | - |
15 | 1, 4, 7, 8, 11, 14 | 32 767 | 2n-1 |
16 | 7, 9 | 63 457 | - |
17 | 3, 5, 6, 11, 12, 14 | 131 071 | 2n-1, Prime |
18 | 7, 11 | 262 143 | 2n-1 |
19 | 5, 6, 12, 13 | 520 065 | - |
20 | 3, 17 | 1 048 575 | 2n-1 |
21 | 2, 19 | 2 097 151 | 2n-1 |
22 | 1, 21 | 4 194 303 | 2n-1 |
23 | 5, 9, 14, 18 | 8 388 607 | 2n-1 |
24 | 5, 19 | 16 766 977 | - |
25 | 3, 7, 18, 22 | 33 554 431 | 2n-1 |
26 | 5, 21 | 67 074 049 | - |
27 | 8, 19 | 133 693 185 | - |
28 | 3, 9, 13, 15, 19, 25 | 268 435 455 | 2n-1 |
29 | 2, 27 | 536 870 911 | 2n-1 |
30 | 7, 23 | 1 073 215 489 | - |
31 | 3, 6, 7, 13, 18, 24, 25, 28 | 2 147 483 647 | 2n-1, Prime |
32 | 15, 17 | 4 292 868 097 | - |
33 | 13, 20 | 8 589 934 591 | 2n-1 |
34 | 13, 21 | 17 179 312 129 | - |
35 | 2, 33 | 34 359 738 367 | 2n-1 |
36 | 11, 25 | 68 71 94 76 735 | 2n-1 |
37 | 1, 36 | 137 438 167 041 | - |
38 | 15, 23 | 240 518 168 569 | - |
39 | 4, 8, 14, 25, 31, 35 | 549 755 813 887 | 2n-1 |
40 | 19, 21 | 1 090 921 693 057 | - |
41 | 3, 20, 21, 38 | 2 199 023 255 551 | 2n-1 |
42 | 11, 31 | 4 123 042 283 535 | - |