Linear feedback shift registers

From ScienceZero
Jump to: navigation, search
Lfsr15bit.gif

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


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 -