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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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