LFSR sequences

Often referred to as pseudonoise or PN sequences, maximal length linear feedback shift register sequences have repetition period 2ⁿ - 1 and are generated by shift registers that go through all their possible states except the one consisting of all 0's, as discussed on page 974. Blocks in such sequences obtained from Partition[list, n, 1] must all be distinct since they correspond to successive complete states of the shift register. This means that every block with length up to n (except all 0's) must occur with equal frequency. (Note that only a small fraction of all possible sequences with this property can be generated by LFSRs.) The regularity of PN sequences is revealed by looking at the autocorrelation RotateLeft[(-1)^list, m] . (-1)^list. This quantity is -1 for all nonzero m for PN sequences (so that all but the first component in Abs[Fourier[(-1)^list]]² are equal), but has mean 0 for truly random sequences. (Related sequences can be generated from RealDigits[1/p, 2] as discussed on page 912.)