LFSR ќ Linear Feedback Shift Register

LFSR logic is commonly used in hardware and software to generate pseudo-random data. An n-bit LFSR cycles between as many as 2^n - 1 unique, non-zero states.

In some contexts, the output of the LFSR is considered a single bit, the state of the right-most register in these examples. In other situations, the output is the state of all of the registers.

Two configurations are possible: Galois (also known as type 2), and Fibonacci (also known as type 1). The single bit output at the right-most register is identical for both configurations. The output at the other bit positions differ, but only by a time delay. The time delay for each bit position can be found by inspection for the Fibonacci configuration, and with a calculation for the Galois configuration, as shown below.

Both Galois and Fibonacci configurations can be drawn with left shifting registers or right shifting registers. But the choice of shift direction is not important. Because no inherently directional operation such as carry propagation is involved, the operation of the two mirror each other. The shift direction used here has been chosen to accommodate comparing the Galois and Fibonacci configurations.

Galois configuration for polynomial x^10 + x^3 + 1

The state of the LFSR at time t can be written in terms of the previous state. The equations are found by inspection of the circuit:

 g0 (t) = g9 (t-1)            (1)
 g1 (t) = g0 (t-1)           
 g2 (t) = g1 (t-1)           
 g3 (t) = g2 (t-1) ^ g9(t-1) 
 g4 (t) = g3 (t-1)           
 g5 (t) = g4 (t-1)           
 g6 (t) = g5 (t-1)           
 g7 (t) = g6 (t-1)           
 g8 (t) = g7 (t-1)           
 g9 (t) = g8 (t-1)           

In matrix form, the current state is multiplied by the matrix to give the next state. Each bit in the current state selects a row in the matrix. The selected rows are exclusive ored together to produce the next state.

  0000000010
  0000000100
  0000001000
  0000010000
  0000100000
  0001000000
  0010000000
  0100000000
  1000000000
  0000001001

Fibonacci configuration for polynomial x^10 + x^3 + 1

The state of the LFSR at time t can be written in terms of the previous state. The equations are found by inspection of the circuit:

 f0 (t) = f1 (t-1)              (2)
 f1 (t) = f2 (t-1)             
 f2 (t) = f3 (t-1)             
 f3 (t) = f4 (t-1)             
 f4 (t) = f5 (t-1)             
 f5 (t) = f6 (t-1)             
 f6 (t) = f7 (t-1)             
 f7 (t) = f8 (t-1)             
 f8 (t) = f9 (t-1)             
 f9 (t) = f0 (t-1)  ^ f3 (t-1) 

The next state matrix for the Fibonacci configuration:

  1000000000
  0000000001
  0000000010
  1000000100
  0000001000
  0000010000
  0000100000
  0001000000
  0010000000
  0100000000

The next state matrix of one LFSR configuration is the transpose of the next state matrix of the other configuration.

The LFSRs cycle through the following states when the registers are initially loaded with 0000000001:

      Galois       Fibonacci
t     g9ииииииg0   f9ииииииf0
0     0000000001   0000000001
1     0000000010   1000000000
2     0000000100   0100000000
3     0000001000   0010000000
4     0000010000   0001000000
5     0000100000   0000100000
6     0001000000   0000010000
7     0010000000   0000001000
8     0100000000   1000000100
9     1000000000   0100000010
10    0000001001   0010000001
11    0000010010   1001000000
12    0000100100   0100100000
13    0001001000   0010010000
14    0010010000   0001001000
15    0100100000   1000100100

        (complete listing)
1007  1001011101   0011010011
1008  0010110011   1001101001
1009  0101100110   0100110100
1010  1011001100   0010011010
1011  0110010001   1001001101
1012  1100100010   0100100110
1013  1001001101   0010010011
1014  0010010011   1001001001
1015  0100100110   0100100100
1016  1001001100   0010010010
1017  0010010001   0001001001
1018  0100100010   0000100100
1019  1001000100   0000010010
1020  0010000001   0000001001
1021  0100000010   0000000100
1022  1000000100   0000000010
<cycle repeats starting here>
Equivalence of Galois and Fibonacci configurations for polynomial x^10 + x^3 + 1

Notice that the output, when taken as the single right-most register, is the same for both configurations. This is true in general, and can be demonstrated by writing the output equations for the right-most register of both configurations in terms of previous values of the register. For the Fibonacci configuration, start with equations (2) and solve for f0 (t) as a function of f0 at times t-1 through t-10:

f0 (t) = f1 (t-1)
f0 (t) = f2 (t-2)
f0 (t) = f3 (t-3)
f0 (t) = f4 (t-4)
f0 (t) = f5 (t-5)
f0 (t) = f6 (t-6)
f0 (t) = f7 (t-7)
f0 (t) = f8 (t-8)
f0 (t) = f9 (t-9)
f0 (t) = f0 (t-10) ^ f3 (t-10)
f0 (t) = f0 (t-10) ^ f0 (t-7)

f1 (t) = f0 (t+1)
       = f0 (t-9) ^ f0 (t-6)

f2 (t) = f0 (t+2)
       = f0 (t-8) ^ f0 (t-5)

f3 (t) = f0 (t+3)
       = f0 (t-7) ^ f0 (t-4)

f4 (t) = f0 (t+4)
       = f0 (t-6) ^ f0 (t-3)

f5 (t) = f0 (t+5)
       = f0 (t-5) ^ f0 (t-2)

f6 (t) = f0 (t+6)
       = f0 (t-4) ^ f0 (t-1)

f7 (t) = f0 (t+7)
       = f0 (t-3) ^ f0 (t-0)
       = f0 (t-3) ^ f0 (t-10) ^ f0 (t-7)

f8 (t) = f0 (t+8)
       = f0 (t-2) ^ f0 (t+1)
       = f0 (t-2) ^ f0 (t-9) ^ f0 (t-6)

f9 (t) = f0 (t+9)
       = f0 (t-1) ^ f0 (t+2)
       = f0 (t-1) ^ f0 (t-8) ^ f0 (t5)

 f0 (t) = f0 (t-10) ^ f0 (t-7)             (3)
 f1 (t) = f0 (t-9)  ^ f0 (t-6)            
 f2 (t) = f0 (t-8)  ^ f0 (t-5)            
 f3 (t) = f0 (t-7)  ^ f0 (t-4)            
 f4 (t) = f0 (t-6)  ^ f0 (t-3)            
 f5 (t) = f0 (t-5)  ^ f0 (t-2)            
 f6 (t) = f0 (t-4)  ^ f0 (t-1)            
 f7 (t) = f0 (t-10) ^ f0 (t-7) ^ f0 (t-3) 
 f8 (t) = f0 (t-9)  ^ f0 (t-6) ^ f0 (t-2) 
 f9 (t) = f0 (t-8)  ^ f0 (t-5) ^ f0 (t-1) 

The coefficients for the terms in the above 
equations can also be found with a calculation:
    t-1иииt-10        calculation    p10ииииииp0 p9ииииииp0
f0  0000001001        gf2util modmul,10000001001,0000001001,1
f1  0000010010        gf2util modmul,10000001001,0000001001,10
f2  0000100100        gf2util modmul,10000001001,0000001001,100
f3  0001001000        gf2util modmul,10000001001,0000001001,1000
f4  0010010000        gf2util modmul,10000001001,0000001001,10000
f5  0100100000        gf2util modmul,10000001001,0000001001,100000
f6  1001000000        gf2util modmul,10000001001,0000001001,1000000
f7  0010001001        gf2util modmul,10000001001,0000001001,10000000
f8  0100010010        gf2util modmul,10000001001,0000001001,100000000
f9  1000100100        gf2util modmul,10000001001,0000001001,1000000000

For the Galois configuration, start with equations (1) and solve for g0 (t) as a function of g0 at times t-1 through t-10:
g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g1 (t-1)
g3 (t) = g2 (t-1) ^ g9 (t-1)
g4 (t) = g3 (t-1)
g5 (t) = g4 (t-1)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g2 (t-1) ^ g9 (t-1)
g4 (t) = g3 (t-1)
g5 (t) = g4 (t-1)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g2 (t-1) ^ g0 (t)
g4 (t) = g3 (t-1)
g5 (t) = g4 (t-1)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g3 (t-1)
g5 (t) = g4 (t-1)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g4 (t-1)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g5 (t-1)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g6 (t-1)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g0 (t-7) ^ g0 (t-4)
g8 (t) = g7 (t-1)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g0 (t-7) ^ g0 (t-4)
g8 (t) = g0 (t-8) ^ g0 (t-5)
g9 (t) = g8 (t-1)

g0 (t) = g9 (t-1)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g0 (t-7) ^ g0 (t-4)
g8 (t) = g0 (t-8) ^ g0 (t-5)
g9 (t) = g0 (t-9) ^ g0 (t-6)

g0 (t) = g0 (t-10) ^ g0 (t-7)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g0 (t-7) ^ g0 (t-4)
g8 (t) = g0 (t-8) ^ g0 (t-5)
g9 (t) = g0 (t-9) ^ g0 (t-6)

g0 (t) = g0 (t-10) ^ g0 (t-7)
g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-3) ^ g0 (t-10) ^ g0 (t-7)
g4 (t) = g0 (t-4) ^ g0 (t-1)
g5 (t) = g0 (t-5) ^ g0 (t-2)
g6 (t) = g0 (t-6) ^ g0 (t-3)
g7 (t) = g0 (t-7) ^ g0 (t-4)
g8 (t) = g0 (t-8) ^ g0 (t-5)
g9 (t) = g0 (t-9) ^ g0 (t-6)

 g0 (t) = g0 (t-10) ^ g0 (t-7)             (4)
 g1 (t) = g0 (t-1)                        
 g2 (t) = g0 (t-2)                        
 g3 (t) = g0 (t-10) ^ g0 (t-7) ^ g0 (t-3) 
 g4 (t) = g0 (t-4)  ^ g0 (t-1)            
 g5 (t) = g0 (t-5)  ^ g0 (t-2)            
 g6 (t) = g0 (t-6)  ^ g0 (t-3)            
 g7 (t) = g0 (t-7)  ^ g0 (t-4)            
 g8 (t) = g0 (t-8)  ^ g0 (t-5)            
 g9 (t) = g0 (t-9)  ^ g0 (t-6)            

The coefficients for the terms in the above equations can also be found with a calculation:

    t-1иииt-10                      p10ииииииp0
g1  1000000000       gf2util modmul,10000001001,01000000000,1
g2  0100000000       gf2util modmul,10000001001,00100000000,1
g3  0010001001       gf2util modmul,10000001001,10010000000,1
g4  1001000000       gf2util modmul,10000001001,01001000000,1
g5  0100100000       gf2util modmul,10000001001,00100100000,1
g6  0010010000       gf2util modmul,10000001001,00010010000,1
g7  0001001000       gf2util modmul,10000001001,00001001000,1
g8  0000100100       gf2util modmul,10000001001,00000100100,1
g9  0000010010       gf2util modmul,10000001001,00000010010,1
g0  0000001001       gf2util modmul,10000001001,00000001001,1

The above shows that for the LFSR using polynomial x^10 + x^3 + 1, the output of the right-most register is the same for both the Galois and Fibonacci configurations.


Converting a Fibonacci state to the corresponding Galois state

To convert a Fibonacci state into the corresponding Galois state, the equations for the Galois state must be written in terms of the current Fibonacci state, f0 (t) through f6(t).

The current Fibonacci state holds future register zero states:
f0 (t) = f0 (t+0)
f1 (t) = f0 (t+1)
f2 (t) = f0 (t+2)
f3 (t) = f0 (t+3)
f4 (t) = f0 (t+4)
f5 (t) = f0 (t+5)
f6 (t) = f0 (t+6)
f7 (t) = f0 (t+7)
f8 (t) = f0 (t+8)
f9 (t) = f0 (t+9)

Start with equations (4) and write the Galois state in terms of future register zero states
 g0 (t) = g0 (t-10) ^ g0 (t-7)
 g1 (t) = g0 (t-1)
 g2 (t) = g0 (t-2)
 g3 (t) = g0 (t-10) ^ g0 (t-7) ^ g0 (t-3)
 g4 (t) = g0 (t-4)  ^ g0 (t-1)
 g5 (t) = g0 (t-5)  ^ g0 (t-2)
 g6 (t) = g0 (t-6)  ^ g0 (t-3)
 g7 (t) = g0 (t-7)  ^ g0 (t-4)
 g8 (t) = g0 (t-8)  ^ g0 (t-5)
 g9 (t) = g0 (t-9)  ^ g0 (t-6)

Equations used to shift t-10 through t-1 references to t+0 through t+9:
0 = g0 (t-10) ^ g0 (t-7) ^ g0 (t+0)
0 = g0 (t-9)  ^ g0 (t-6) ^ g0 (t+1)
0 = g0 (t-8)  ^ g0 (t-5) ^ g0 (t+2)
0 = g0 (t-7)  ^ g0 (t-4) ^ g0 (t+3)
0 = g0 (t-6)  ^ g0 (t-3) ^ g0 (t+4)
0 = g0 (t-5)  ^ g0 (t-2) ^ g0 (t+5)
0 = g0 (t-4)  ^ g0 (t-1) ^ g0 (t+6)
0 = g0 (t-3)  ^ g0 (t+0) ^ g0 (t+7)
0 = g0 (t-2)  ^ g0 (t+1) ^ g0 (t+8)
0 = g0 (t-1)  ^ g0 (t+2) ^ g0 (t+9)

g1 (t) = g0 (t-1)
       = g0 (t-1)  ^ g0 (t-1) ^ g0 (t+2) ^ g0 (t+9)
       = g0 (t+2)  ^ g0 (t+9)

g2 (t) = g0 (t-2)
       = g0 (t-2)  ^ g0 (t-2)  ^ g0 (t+1) ^ g0 (t+8)
       = g0 (t+1)  ^ g0 (t+8)

g3 (t) = g0 (t-10) ^ g0 (t-7) ^ g0 (t-3)
       = g0 (t-10) ^ g0 (t-7) ^ g0 (t-3) ^ g0 (t-10) ^ g0 (t-7) ^ g0 (t+0)
       = g0 (t-3)  ^ g0 (t+0)
       = g0 (t-3)  ^ g0 (t+0) ^ g0 (t-3)  ^ g0 (t+0) ^ g0 (t+7)
       = g0 (t+7)

g4 (t) = g0 (t-4)  ^ g0 (t-1)
       = g0 (t-4)  ^ g0 (t-1) ^ g0 (t-4)  ^ g0 (t-1) ^ g0 (t+6)
       = g0 (t+6)

g5 (t) = g0 (t-5)  ^ g0 (t-2)
       = g0 (t-5)  ^ g0 (t-2) ^ g0 (t-5)  ^ g0 (t-2) ^ g0 (t+5)
       = g0 (t+5)

g6 (t) = g0 (t-6)  ^ g0 (t-3)
       = g0 (t-6)  ^ g0 (t-3) ^ g0 (t-6)  ^ g0 (t-3) ^ g0 (t+4)
       = g0 (t+4)

g7 (t) = g0 (t-7)  ^ g0 (t-4)
       = g0 (t-7)  ^ g0 (t-4) ^ g0 (t-7)  ^ g0 (t-4) ^ g0 (t+3)
       = g0 (t+3)

g8 (t) = g0 (t-8)  ^ g0 (t-5)
       = g0 (t-8)  ^ g0 (t-5) ^ g0 (t-8)  ^ g0 (t-5) ^ g0 (t+2)
       = g0 (t+2)

g9 (t) = g0 (t-9)  ^ g0 (t-6)
       = g0 (t-9)  ^ g0 (t-6) ^ g0 (t-9)  ^ g0 (t-6) ^ g0 (t+1)
       = g0 (t+1)

g0 (t) = g0 (t)
g1 (t) = g0 (t+2)  ^ g0 (t+9)
g2 (t) = g0 (t+1)  ^ g0 (t+8)
g3 (t) = g0 (t+7)
g4 (t) = g0 (t+6)
g5 (t) = g0 (t+5)
g6 (t) = g0 (t+4)
g7 (t) = g0 (t+3)
g8 (t) = g0 (t+2)
g9 (t) = g0 (t+1)

g0 (t) = f0 (t)
g1 (t) = f0 (t+2)  ^ f0 (t+9)
g2 (t) = f0 (t+1)  ^ f0 (t+8)
g3 (t) = f0 (t+7)
g4 (t) = f0 (t+6)
g5 (t) = f0 (t+5)
g6 (t) = f0 (t+4)
g7 (t) = f0 (t+3)
g8 (t) = f0 (t+2)
g9 (t) = f0 (t+1)

g0 (t) = f0 (t)            (5)
g1 (t) = f2 (t)  ^ f9 (t) 
g2 (t) = f1 (t)  ^ f8 (t) 
g3 (t) = f7 (t)           
g4 (t) = f6 (t)           
g5 (t) = f5 (t)           
g6 (t) = f4 (t)           
g7 (t) = f3 (t)           
g8 (t) = f2 (t)           
g9 (t) = f1 (t)           
The coefficients for the terms in the above equations can also be found with a calculation involving the polynomial and coefficients from equations (4):
    f0ииииииf9                      p0ииииииp10 t-10иииt-1
g0  1000000000       gf2util modmul,10010000001,1001000000,10000000000
g1  0010000001       gf2util modmul,10010000001,0000000001,10000000000
g2  0100000010       gf2util modmul,10010000001,0000000010,10000000000
g3  0000000100       gf2util modmul,10010000001,1001000100,10000000000
g4  0000001000       gf2util modmul,10010000001,0000001001,10000000000
g5  0000010000       gf2util modmul,10010000001,0000010010,10000000000
g6  0000100000       gf2util modmul,10010000001,0000100100,10000000000
g7  0001000000       gf2util modmul,10010000001,0001001000,10000000000
g8  0010000000       gf2util modmul,10010000001,0010010000,10000000000
g9  0100000000       gf2util modmul,10010000001,0100100000,10000000000
Converting a Galois state to the corresponding Fibonacci state

To convert a Galois state into the corresponding Fibonacci state, stare with equations (5) and solve for f0 (t) - f9 (t) in terms of g0 (t) - g9 (t):
 
g0 (t) = f0 (t)
g1 (t) = f2 (t) ^ f9 (t) 
g2 (t) = f1 (t) ^ f8 (t) 
g3 (t) = f7 (t) 
g4 (t) = f6 (t) 
g5 (t) = f5 (t) 
g6 (t) = f4 (t) 
g7 (t) = f3 (t) 
g8 (t) = f2 (t) 
g9 (t) = f1 (t) 
f0 (t) = g0 (t)
f1 (t) = g9 (t)
f2 (t) = g8 (t)
f3 (t) = g7 (t)
f4 (t) = g6 (t)
f5 (t) = g5 (t)
f6 (t) = g4 (t)
f7 (t) = g3 (t)
f8 (t) = g2 (t) ^ f1 (t)
       = g2 (t) ^ g9 (t)
f9 (t) = g1 (t) ^ f2 (t)
       = g1 (t) ^ g8 (t)
f0 (t) = g0 (t)           (6)
f1 (t) = g9 (t)          
f2 (t) = g8 (t)          
f3 (t) = g7 (t)          
f4 (t) = g6 (t)          
f5 (t) = g5 (t)          
f6 (t) = g4 (t)          
f7 (t) = g3 (t)          
f8 (t) = g2 (t) ^ g9 (t) 
f9 (t) = g1 (t) ^ g8 (t) 

The coefficients for the terms in the above equations can also be found with a calculation involving the polynomial:
    g0ииииииg9
f0  1000000000                               p10иииииp1
f1  0000000001     gf2util divide,1000000000,1000000100
f2  0000000010     gf2util divide,10000000000,1000000100
f3  0000000100     gf2util divide,100000000000,1000000100
f4  0000001000     gf2util divide,1000000000000,1000000100
f5  0000010000     gf2util divide,10000000000000,1000000100
f6  0000100000     gf2util divide,100000000000000,1000000100
f7  0001000000     gf2util divide,1000000000000000,1000000100
f8  0010000001     gf2util divide,10000000000000000,1000000100
f9  0100000010     gf2util divide,100000000000000000,1000000100

Finding the time delay between LFSR stages

It can be seen from inspection of the circuit that the output of each Fibonacci stage differs from the output of a neighboring stage by one clock. But for the Galois configuration, the relationship as simple. A brute force approach for finding the delay for a register in the Galois configuration is to solve for each possible delay until one is found that is in the form of a single g0 term.

g1 (t) = g0 (t-1)
g2 (t) = g0 (t-2)
g3 (t) = g0 (t-1016)
g4 (t) = g0 (t-1017)
g5 (t) = g0 (t-1018)
g6 (t) = g0 (t-1019)
g7 (t) = g0 (t-1020)
g8 (t) = g0 (t-1021)
g9 (t) = g0 (t-1022)