Science Zero
[ Science ] [ Electronics ] [ Experiments ] [ Computing ] [ About us ] [ Links ]

 

lfsr15bit.gif (2050 bytes)

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^n-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

 

Language Optimal implementation (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

 

Length Taps giving maximum period

Maximum Period

 Type
2 1  3 2^n-1, Prime
3 1, 2 7 2^n-1, Prime
4 1, 3 15 2^n-1
5 2, 3 31 2^n-1, Prime
6 1, 5 63 2^n-1
7 1, 3, 4, 6 127 2^n-1, Prime
8 3, 5 217  
9 4, 5 511 2^n-1
10 3, 7 1023 2^n-1
11 2, 9 2047 2^n-1
12 1, 11 3255  
13 3, 10 8001  
14 1, 13 11 811  
15 1, 4, 7, 8, 11, 14 32 767 2^n-1
16 7, 9 63 457  
17 3, 5, 6, 11, 12, 14 131 071 2^n-1, Prime
18 7, 11 262 143 2^n-1
19 5, 6, 12, 13 520 065  
20 3, 17 1 048 575 2^n-1
21 2, 19 2 097 151 2^n-1
22 1, 21 4 194 303 2^n-1
23 5, 9, 14, 18 8 388 607 2^n-1
24 5, 19 16 766 977  
25 3, 7, 18, 22 33 554 431 2^n-1
26 5, 21 67 074 049  
27 8, 19 133 693 185  
28 3, 9, 13, 15, 19, 25 268 435 455 2^n-1
29 2, 27 536 870 911 2^n-1
30 7, 23 1 073 215 489  
31 3, 6, 7, 13, 18, 24, 25, 28 2 147 483 647 2^n-1, Prime
32 15, 17 4 292 868 097  
33 13, 20 8 589 934 591 2^n-1
34 13, 21 17 179 312 129  
35 2, 33 34 359 738 367 2^n-1
36 11, 25 68 71 94 76 735 2^n-1
37   137 438 167 041  
38 15, 23 240 518 168 569  
39 4, 8, 14, 25, 31, 35 549 755 813 887 2^n-1
40 19, 21 1 090 921 693 057  
41 3, 20, 21, 38 2 199 023 255 551 2^n-1
42 11, 31 4 123 042 283 535  

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