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 taps will generate a maximal sequence with a period of 2ⁿ-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:

• http://en.wikipedia.org/wiki/Galois_field
• http://mathworld.wolfram.com/FiniteField.html

A simple simulation of a LFSR with two taps: lfsrsim.zip

A complete list of all LSFRs up to 42 bit in length and their periods: lfsrperiods.txt

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));  

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