# Choosing taps for Linear Feedback Shift Register

I am confused about how taps are chosen for Linear Feedback Shift Registers.

I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, R3, R2, R1$ and $R0$ and the taps come out of $R0$ and $R3$.

How are these taps decided? When I am given a connection polynomial but no diagram, how do I know what values I should XOR? • Welcome! If you have such doubts, why don't you include the diagram in the question? – Raphael Apr 7 '12 at 22:53
• Hi, I need to have a reputation of at least 10 to post images – sam Apr 7 '12 at 23:00
• Duh. There you go! – Raphael Apr 7 '12 at 23:01

The taps are decided by the polynomial in a straightforward way: for $X^n$, you connect the $n$th tap. Note that in your diagram the first tap is $R4$, the 2nd is $R3$ etc..
Since your polynomial is $X^5+X^2+1$ the feedback is an XOR of the output of the 2nd tap ($R3$) and the 5th tap ($R0$). The "$+1$" of the polynomial ($X^0$) is usually always there and corresponds to the "feedback" itself, i.e., the line connected into the first bit ($R4$).
The output should be the "feedback" line (rather than $R0$). This is important since the polynomial is identified with the generated sequence, and if you take the output of $R0$ you generate a different sequence, not the one identified with $X^5+X^2+1$ (although they are the same up to a prefix)