LFSR Tap sequence 15 bit LFSR

Question

I have been asked to create an LFSR with a polynomial of x^15 + x + 1 and i am confused where the tap sequence would go.

The examples I was given show a 4 bit tap sequence with two polynomials: x^3 + 1 and x^2 + 1. These were shown having tap at positions 0101 and 0101 respectively, where the bold represents the tap sequence.

I am confused about where the tap sequence would go for x^15 + x + 1, since in the first above example, there is 4 bits but taps are at either ends with the polynomial x^3+1. So how would x^15 be placed on a 15 bit LFSR? surly it would not fit? (x^14 + 1 being taps at either end of the 15 bit LFSR following the examples?)

I have written code for this also and have placed taps 000001111100000, which i think is the correct tap sequence, however this outputs only 14 bits, being way under what i estimated. 0s and 1s being different then mentioned above. This also doesnt match the 4 bit examples i was given which is confusing me very much.

Where am i going wrong, any advice on this would be appreciated, thanks.

Answer 1

Let $[s_0, s_1, \ldots, s_{14}]$ denote the initial contents of the shift register (which holds 15 bits). The output sequence is $$s_0, s_1, s_2, \ldots, s_{14}, s_{15}, s_{16}, \ldots$$ in that order with $s_{15}$ being the first computed bit that is fed back into the shift register. That is, $s_{15}$ is computed as a linear function (meaning XOR operations) of the initial contents $[s_0, s_1, \ldots, s_{14}]$ of the shift register which then shifts its contents one place leftwards with $s_0$ being sent out into the dark dirty world while $s_{15}$ enters the shift register on the right, thus making the shift register contents $[s_1, s_2, \ldots, s_{14}, s_{15}]$. Thus the change in shift register contents looks like $$(s_0, \quad s_1, \quad \ldots, \quad s_{13}, \quad s_{14})\\ \downarrow\\ (s_1, \quad s_2, \quad \ldots, \quad s_{14}, \quad s_{15})\\ \downarrow\\(s_2, \quad s_3, \quad \ldots, \quad \quad s_{15}, \quad s_{16})\\ \downarrow\\ \cdots \quad \cdots$$ and more generally as

$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+13}, \quad s_{i+14}\biggr)\\ \downarrow\\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+14}, \quad {\Large{\oplus}}_{j=0}^{14}c_{15-j} s_{i+j}\biggr),$$ where $c_{15}x^{15}+c_{14}x^{14} + \cdots + c_1 x + c_0 = x^{15}+x+1$ is the feedback polynomial. In other words, $$s_{i+15} = c_{15}s_{i}\oplus c_1s_{i+14} = s_i \oplus s_{i+14}$$ and so the taps are on the zero-th and the 14th stage of the shift register.

Just be aware that there is an alternative convention which defines the feedback polynomial as $c_0 x^{15} + c_1x^{14} + \cdots + c_{14}x + c_{15}$ which would change the tap locations.

Answer 2

For a polynomial $P(x) = x^3 + x^2 + 1 = x^3 + x^2 + x^0 $, the associated Galois representation of the LFSR is as follow:

+-----------------------------------------+
|                           |             |
|    +------+     +------+  |  +------+   |
|    |      |     |      |  v  |      |   |
+---->  S0  +----->  S1  +--+-->  S2  +-------> output
     |      |     |      |     |      |
     +------+     +------+     +------+

The degree of the polynomial is $3$, so it will be a 3 cell LFSR.

The $x^2$ indicates a tap before $S2$.

---

Why this polynomial generates a tap before $S2$ ?

If the 3 bits above defines a polynomial, iterating the LFSR is equivalent as multiplying by $x$ and reducing modulo $P$.

Notice that : $$x^3 + x^2 + x^0 \equiv 0 \mod P$$ thus: $$x^3 \equiv -x^2 - x^0 \mod P$$ and because we are in $\operatorname{GF}(2)$, $-1 = 1$: $$x^3 \equiv x^2 + x^0 \mod P$$

in our example case we have:

\begin{array}{rl} (s_0 \cdot x^0 + s_1 \cdot x^1 + s_2 \cdot x^2) \cdot x &\equiv s_0 \cdot x^1 + s_1 \cdot x^2 + s_2 \cdot x^3\\ &\equiv s_0 \cdot x^1 + s_1 \cdot x^2 + s_2 \cdot (x^2 + x^0)\\ &\equiv s_2 \cdot x^0 + s_0 \cdot x^1 + s_1 \cdot x^2 + s_2 \cdot x^2\\ &\equiv s_2 \cdot x^0 + s_0 \cdot x^1 + (s_1 \oplus s_2) \cdot x^2 \end{array}

Thus you can see the diagram drawn above: a tap before $S_2$ and the feedback before $S_0$.

Answer 3

For m-bit LFSR, a valid feedback polynomial has dergree m, i.e. p(x) = x^m + .. + 1. If degree of polynomial is less than the length of LFSR, then it is just a delayed response.

For example, a 4-bit LFSR, polynomial x^4 + x^3 + 1 or x^4 + x + 1 is a valid feedback polinomial.

For your question, where tap sequence go? Here is a simple explaination. You take the bits at the locations, given in tap sequence (e.g. [15,1] for x^15 + x + 1), xor all of them and feedback to first bit by shifting all to forward.

For a program, it is quite simple, here is a python code to do that,

import numpy as np
from pylfsr import LFSR

# Initial State of LFSR
s = '000001111100000'
s = [int(b) for  b in s]

L = LFSR(initstate=s, fpoly=[15,1])
L.info()

#Generate N-bits
N = 50
temseq = L.runKCycle(N)

# 50 bits generated
seq  = L.getSeq()

Or visualize it like this

import numpy as np
from pylfsr import LFSR

# Initial State of LFSR
s = '000001111100000'
s = [int(b) for  b in s]

L = LFSR(initstate=s, fpoly=[15,1])
L.info()

print('')
print('count\tstate \t\t\toutbit \t seq')
print('-'*50)
for _ in range(20):
    L.next()
    print(L.count,  L.getState(), '',L.outbit, L.getSeq(),sep='\t')

Outout will be

15 bit LFSR with feedback polynomial  x^15 + x^1 + 1
Expected Period (if polynomial is primitive) =  32767
Current :
 State        :  [0 0 0 0 0 1 1 1 1 1 0 0 0 0 0]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1

count   state           outbit   seq
--------------------------------------------------
1   000000111110000     0   0
2   000000011111000     0   00
3   000000001111100     0   000
4   000000000111110     0   0000
5   000000000011111     0   00000
6   100000000001111     1   000001
7   010000000000111     1   0000011
8   101000000000011     1   00000111
9   010100000000001     1   000001111
10  101010000000000     1   0000011111
11  110101000000000     0   00000111110
12  111010100000000     0   000001111100
13  111101010000000     0   0000011111000
14  111110101000000     0   00000111110000
15  111111010100000     0   000001111100000
16  111111101010000     0   0000011111000000
17  111111110101000     0   00000111110000000
18  111111111010100     0   000001111100000000
19  111111111101010     0   0000011111000000000