# Sequence output by a Galois type LFSR

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?

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

## 1 Answer

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.