13
$\begingroup$

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?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Welcome! If you have such doubts, why don't you include the diagram in the question? $\endgroup$ – Raphael Apr 7 '12 at 22:53
  • 1
    $\begingroup$ Hi, I need to have a reputation of at least 10 to post images $\endgroup$ – sam Apr 7 '12 at 23:00
  • 1
    $\begingroup$ Duh. There you go! $\endgroup$ – Raphael Apr 7 '12 at 23:01
10
$\begingroup$

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)

See more details in Wikipedia: Linear feedback shift register.

$\endgroup$

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.