2
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.