Linear Feedback Shift Register - Output-stream Properties

Output-stream Properties

• Ones and zeroes occur in 'runs'. The output stream 0110100, for example consists of five runs of lengths 1,2,1,1,2, in order. In one period of a maximal LFSR, 2n −1 runs occur (for example, a six bit LFSR will have 32 runs). Exactly half of these runs will be one bit long, a quarter will be two bits long, up to a single run of zeroes n − 1 bits long, and a single run of ones n bits long. This distribution almost equals the statistical expectation value for a truly random sequence. However, the probability of finding exactly this distribution in a sample of a truly random sequence is rather low.
• LFSR output streams are deterministic. If you know the present state, you can predict the next state. This is not possible with truly random events.
• The output stream is reversible; an LFSR with mirrored taps will cycle through the output sequence in reverse order.