Difference between revisions of "Linear feedback shift registers"
From ScienceZero
(New page: 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 ...) |
|||
| Line 21: | Line 21: | ||
==Language Optimal implementation (Your compiler may think differently)== | ==Language Optimal implementation (Your compiler may think differently)== | ||
| − | ==VHDL== | + | ===VHDL=== |
signal lfsr : std_logic_vector(14 downto 0); | signal lfsr : std_logic_vector(14 downto 0); | ||
lfsr <= lfsr(13 downto 0) & (lfsr(14) xnor lfsr(0)); | lfsr <= lfsr(13 downto 0) & (lfsr(14) xnor lfsr(0)); | ||
| − | ==ARM== | + | ===ARM=== |
| − | Consecutive taps: | + | ====Consecutive taps:==== |
MOVS r0,r0,lsl #1 | MOVS r0,r0,lsl #1 | ||
EORCC r0,r0,#1<<31-14 | EORCC r0,r0,#1<<31-14 | ||
EORMI r0,r0,#1<<31-14 | EORMI r0,r0,#1<<31-14 | ||
| − | Non-consecutive taps: | + | ====Non-consecutive taps:==== |
MOVS r0,r0,lsr #1 | MOVS r0,r0,lsr #1 | ||
EORCC r0,r0,#1<<14 | EORCC r0,r0,#1<<14 | ||
| Line 37: | Line 37: | ||
EORNE r0,r0,#1<<14 | EORNE r0,r0,#1<<14 | ||
| − | ==MMX== | + | ===MMX=== |
MOVQ mm6,mm5 //lfsr | MOVQ mm6,mm5 //lfsr | ||
PSRLQ mm6,mm3 //Tap1 | PSRLQ mm6,mm3 //Tap1 | ||
| Line 48: | Line 48: | ||
POR mm5,mm6 | POR mm5,mm6 | ||
| − | ==C++== | + | ===C++=== |
n2=(lfsr>>14) xor (lfsr>>13); | n2=(lfsr>>14) xor (lfsr>>13); | ||
n2&=1; | n2&=1; | ||
| Line 55: | Line 55: | ||
lfsr+=n2^1; | lfsr+=n2^1; | ||
| − | == BASIC == | + | === BASIC === |
tmp = 1 | tmp = 1 | ||
If (lfsr And t1) Then tmp = 0 | If (lfsr And t1) Then tmp = 0 | ||
Revision as of 11:56, 30 January 2007
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:
- A simple simulation of a LFSR with two taps: lfsrsim.zip
Contents
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
