# 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)