2
$\begingroup$

I have provided a diagram of a Galois type LFSR. I am told it outputs a sequence of period 31.

Find the sequence output by this LFSR.

By applying the shifts I got the seemingly trivial answr of $0,0,0,0,1$ which I know must be wrong since it has a period of 31. Where have I gone wrong?

Galois type LFSR

$\endgroup$
  • 1
    $\begingroup$ What's the state of the LFSR after it has output the 1? $\endgroup$ – poncho Apr 7 '17 at 12:31
4
$\begingroup$

You made a mistake in the propagation of the feedback.

If you follow the LFSR very slowly this is what you get:

initial state:
+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+--->+  0  +---->+  0  +--+->+  0  +--+->+  0  +--+->+  1  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

the 1 get on the branch and we are going to do the xor
+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  1  |     |  1  |     |  1  |     |   |
+-1->+  ?  +--0->+  ?  +-0+->+  ?  +-0+->+  ?  +-0+->+  ?  +---1---> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

compute the XORs
+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+-1->+  ?  +--0->+  ?  +--+1>+  ?  +--+1>+  ?  +--+1>+  ?  +-----1-> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+


move the results to the next box (and output 1)
+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  |  |     |  |  |     |  |  |     |   |
+--->+  1  +---->+  0  +--+->+  1  +--+->+  1  +--+->+  1  +-------> ouput: 1
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

So you have $10111$ instead of $10000$. Which will be then iterated and so on.

$\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.