# LFSR Tap sequence 15 bit LFSR

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.

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} + cots + c_{14}x + c_{15}$ which would change the tap locations.

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
|      |     |      |     |      |
+------+     +------+     +------+


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