Sequence output by a Galois type LFSR

Question

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?

Answer 1

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.