Maximum-length sequences, cellular automata, and random numbers (Q1821479)

The statistical properties of maximum-length sequences generated by linear-feedback shift registers are investigated. Two-dimensional bit patterns constructed from these sequences are found to exhibit characteristic triangular structures, in the simplest case consisting of triangles of zeros supported by a backbone of ones. The size distribution of these triangles is given, and the relation with cellular automata is pointed out. Randomness is defined in terms of the correlation functions of any order. Not only the pair correlation function, but also all higher order correlation functions are two-valued. The number of correlation functions of any order that deviate from randomness is determined exactly. All maximum-length sequences of the same length are found to be equally random in a strict sense, although their suitability as a source of random numbers may differ widely in different applications; longer sequences are more random. It is concluded that extremely long maximum- length sequences, with periods of up to \(2^{9689}-1\), can in fact be used a reliable random-number generators for many purposes. Fast software or hardware programs for the production of these sequences are readily constructed.