Recently I've become entranced with Maximum Length Sequences (MLS). They first came to my attention when I was involved with some acoustic signal processing, where they are used to measure ocean (or room) reverberations. One interesting property, and useful application, of an MLS is that its autocorrelation is a unit impulse function (a Dirac delta function). This feature allows extracting the response of a system by calculating the cross-correlation of its measured output with the MLS.

There are other "magical" properties. For example, consider the sequence I0 = 0011101. As Laxton and Anderson pointed out, six additional sequences (e.g., I1 = 0111010) can be obtained by cyclically shifting I0 to the left. Moreover if we add (modulo 2) two of these seven unique sequences, then we obtain another sequence in this MLS set. This is a very rare property for a general n-bit sequence and is related to the fact that the zeros and ones in such a sequence must be distributed in a very special way. For example, the number of ones in the sequence must be one greater than the number of zeros.

The most interesting property of an MLS to me is the fact that although they are deterministic, they can be used as approximate pseudo-random numbers. This immediately makes me think of using them for Monte Carlo simulations. I haven't yet seen any real published work using them for a practical problem--although a lot of work has been done on their usefulness as pseudo-random numbers by Compagner in Delft (what a beautiful city and university, by the way). Besides the fact that I'd like to play with them in a real way by using them in Monte Carlo simulations, there is also another interesting property they have: each MLS can be associated with a so-called companion polynomial. This brings up another wacky idea to my mind: can this somehow be used in Gaussian quadrature?