1
$\begingroup$

Consider the primitive polynomial P(x) = x^4 + x^3 + 1, initialized with the bit string (shifting occurs from left to right, were the right-most bit represents the LFSR output): 1101.

List the first 8-bits generated by the LFSR, starting with the bit 1 that is the right-most bit of the initialization sequence above.

This was my work to solve this:

          s1 s2 s3 s4  output (s4 xor s3)

         [[ 1  0  1   1    0 
          0  1  0]]   1    1
          1  0  1     0    1
          1  1  0     1    1
          1  1  1     0    1
          1  1  1     1    0 
          0  1  1     1    0 
          0  0  1     1    0

The answer is : 10110010. Is this because it is in result of what I have put in brackets?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Questions asking for solutions to crypto puzzles or homework exercises are off-topic. While we do accept questions about homework problems, such questions must contain more than just a verbatim copy of the assignment, and should preferably ask for general solving techniques rather than just a solution to a specific puzzle or exercise $\endgroup$
    – kodlu
    Mar 26, 2021 at 20:55

1 Answer 1

Reset to default
1
$\begingroup$

A few things have gone wrong:

  1. You've reversed the initial state, but continued to shift from left to right. If you do reverse then the shift is from right to left.
  2. You've confused the output bit (the oldest bit in the register) with the feedback bit (the new value that is introduced after shifting)
  3. The feedback rule for the polynomial $x^4+x^3+1$ is $s_{i+4}=s_{i+3}\oplus s_{i}$ and so in your notation would be $s_4$ xor $s_1$

With this borne in mind the first two rows of you table should read as follows:

s1  s2  s3  s4  feedback bit (s4 xor s1)  output bit (s1)
1   0   1   1   0                         1
0   1   1   0   0                         0...

and so on

Improve this answer
$\endgroup$
6
  • $\begingroup$ Did you mean feedback bit is s4 xor s3? $\endgroup$
    – hollyjolly
    Mar 26, 2021 at 15:14
  • $\begingroup$ No. The feedback bit is represented by the highest degree monomial in the polynomial (which is $x^4$). The 1 in the polynomial represents the zeroth bit in the register ($s_1$ in your notation) and the $x^3$ represents the bit in position 3 of the register ($s_4$ in your notation). Thus $x^4+x^3+1=0$ is the same as saying $x^4=x^3+1$ which says that the feedback bit is the xor of $s_4$ and $s_1$ in your notation. $\endgroup$
    – Daniel S
    Mar 26, 2021 at 15:18
  • 1
    $\begingroup$ Thank you so much! Your explanations are very clear. $\endgroup$
    – hollyjolly
    Mar 26, 2021 at 15:26
  • 1
    $\begingroup$ Questions asking for solutions to crypto puzzles or homework exercises are off-topic. While we do accept questions about homework problems, such questions must contain more than just a verbatim copy of the assignment, and should preferably ask for general solving techniques rather than just a solution to a specific puzzle or exercise $\endgroup$
    – kodlu
    Mar 26, 2021 at 20:55
  • 1
    $\begingroup$ @hollyjolly: here, the generally appropriate way to thank for an answer is up-voting (up-arrow). And the appropriate way to tell the answer solves the question is accepting it (tick). "Thanks" comments are possible for extraordinarily difficult/long/bright answer, though. $\endgroup$
    – fgrieu ♦
    Mar 27, 2021 at 15:53

Your Answer

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

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