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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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