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?
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.
1? – poncho Apr 07 '17 at 12:31