We consider an LFSR of length n bits. 1. Explain why the generated key sequence cannot have a period

We consider an LFSR of length n bits. 1. Explain why the generated key sequence cannot have a period longer than 2n – 1 bits. Solution An n bit LFSR has 2n possible states. Thus the period is at most 2n . However, the all zero state cannot appear in a maximal period sequence, since it would generate an all zero output. 2. Explain why an LFSR that generates maximal period sequences must have an even number of ones in its tap sequence (connection polynomial). (5 points) Hint: Consider the state with all ones. Solution If an LFSR has an odd number of taps and enters the state with all ones, then the bit to be shifted in is the xor of an odd nummber of ones and hence one. So, the device is stuck in this state. 3. The output sequence of an LFSR starts with 100000001. What is the minimal size of the LFSR? Your answer should exhibit an LFSR of this size that does produce the given sequence and give a motivation why no shorter LFSR will do.