Part III: Maximum Length Sequences

A maximum length sequence (MLS) is the basis for several audio measurement systems, such as MLSSA, and CLIO. A MLS system effectively measures the impulse response of loudspeakers, rooms, or whatever. Impulse response could be measured by transmitting an impulse, and recording the response. The problem is that the magnitude of the impulse has to be huge to obtain a decent signal-to-noise ratio. The MLS technique is a clever method for obtaining a very large processing gain, so accurate measurements can be made with moderate sound levels.

Example of a MLS

The theory of polynomial rings and Galois fields underlying MLSs is difficult (at least I find the text by Peterson challenging). On the other hand, the sequences are not difficult to generate (see the 11 line Matlab program below) and the theory is not necessary for understanding how a MLS works.

Sequences come in lengths of M=2N-1, where N is an integer. As a simple example, a MLS of length 15 is:

1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1

The values of the sequence are used as the amplitudes of a sequence of transmitted sound pulses, using the values from right-to-left. In the case of a perfect impulse response, as the sound is received and sampled, the incoming samples simply replicate the sequence (we ignore scale factors and assume the count begins when the first pulse arrives). A buffer of length 15 is initially filled with zeros. As the pulses come in, they fill the buffer, entering from the left.

Sample interval

1. 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2. -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
3. 1 -1 1 0 0 0 0 0 0 0 0 0 0 0 0
4. -1 1 -1 1 0 0 0 0 0 0 0 0 0 0 0
5. 1 -1 1 -1 1 0 0 0 0 0 0 0 0 0 0
6. 1 1 -1 1 -1 1 0 0 0 0 0 0 0 0 0

The full sequence is stored in a second buffer

1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1

The value in the nth position of the first buffer is multiplied by the value in the nth position of the second buffer, and the 15 products are added together to produce the output. Therefore the filter output is 1, 0, 1, -2, 1, 0, for the first 6 sample intervals. The magnitude is never greater than 4 until sample interval 15. At this point the contents of the two buffers are identical, and the filter output is 15. For subsequent intervals, the filter output is a mirror image of the first 14 samples. So as a function of time the filter has one spike when the sample interval is equal to the length, and a more-or-less noisy response at other times.

This result isn't all that impressive, but for a MLS length of 16,383, the filter output when the sequences align will be 16,383, and (for the one sequence I tried) the maximum output at any other sample period is 184. Therefore the peak filter response has a gain of 39 dB relative to the next largest response. The peak filter response is also 84 dB higher than the response to a single pulse - the processing gain referred to above.

Extra taps

Extra taps can be used to obtain a filter response such that the peak is the full processing gain above the response elsewhere. Three periodic repetitions of the sequence are used to construct a filter of length 3M-1. The peak response will still be M, and now the response around the peak will be 1. There will be additional spikes at ±M away from the peak, but the time window can be restricted to exclude this region, so this is not a problem. A comparison of a filter with and without the extra taps, for the case of M=31, illustrates the two responses [43 kb]. Fewer taps can also be used, but the clear area will be smaller.

MLS Measurements

For an imperfect impulse response, the received signal is a superposition of the sequence with various time delays and amplitudes. For example, with one room reflection the received signal would consist of two of the above sequences with a time delay between the direct and reflected signal. The filter output will then have two spikes, separated by the time delay, and with responses proportional to the level of the direct and reflected signals. Thus, the filter output, as a function of time, is essentially the same as what you would measure by transmitting a single loud impulse.

The impulse response is useful in itself, and its Fourier transform yields the frequency response. CLIO uses a sequence of length 16,383, and a sample rate of 51.2 kHz. The full sample time is therefore 320 milliseconds, which provides a frequency resolution is 3.13 Hz. However one of the main virtues of MLS measurements is that stray reflections can be windowed (or time-gated) out, if desired. The filter output is simply truncated before the unwanted reflections arrive. The penalty is that the sample time is reduced, and the frequency resolution is worse. Typically the derived frequency response is not valid below a few hundred Hz.

A window can be used to isolate any particular slice of time you want. For example a wall reflection can be isolated, and its spectrum compared to the spectrum of the direct signal.

Appendix: Matlab Programs for Generating MLSs

The first program is based on a C-program posted by Cepstum ,ltd. (I did have a link, but it no longer works). They also include a program for a sequence of length 2,147,483,647. This program is quite fast.

*********************************************************************

% MLS Sequence generator. generates sequence length 32767

N= 15; M = 2^N-1;

m = zeros(1,N); m(1)=1; m(3)=1; m(4)=1; m(8)=1; m(13)=1;

m(15) = 1;

regout = zeros(1,M);

for ind = 1:M

buf = xor(m(14),m(15));

m(2:N) = m(1:N-1);

m(1)=buf;

regout(ind) = m(15);

end

comp = ~ regout; sequence = regout - comp;

*********************************************************************

The second program is much slower, but will generate sequences from length 7 to length 262,143. The taps are from the book by Peterson. He provides values for up to 34 taps, which corresponds to a length of 17,179,869,183.

*********************************************************************

% MLS Sequence generator. Copyright Arthur C. Ludwig, March 2001

if exist(N') ~= 1; N= 15; end;

if N == 18; taps=[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1]; end;

if N == 17; taps=[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1]; end;

if N == 16; taps=[0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1]; end;

if N == 15; taps=[0 0 0 0 0 0 0 0 0 0 0 0 0 1 1]; end;

if N == 14; taps=[0 0 0 1 0 0 0 1 0 0 0 0 1 1]; end;

if N == 13; taps=[0 0 0 0 0 0 0 0 1 1 0 1 1]; end;

if N == 12; taps=[0 0 0 0 0 1 0 1 0 0 1 1]; end;

if N == 11; taps=[0 0 0 0 0 0 0 0 1 0 1]; end;

if N == 10; taps=[0 0 0 0 0 0 1 0 0 1]; end;

if N == 9; taps=[0 0 0 0 1 0 0 0 1]; end;

if N == 8; taps=[0 0 0 1 1 1 0 1]; end;

if N == 7; taps=[0 0 0 1 0 0 1]; end;

if N == 6; taps=[0 0 0 0 1 1]; end;

if N == 5; taps=[0 0 1 0 1]; end;

if N == 4; taps=[0 0 1 1]; end;

if N == 3; taps=[0 1 1]; end;

M = 2^N-1;

m = ones(1,N);

regout = zeros(1,M);

for ind = 1:M

buf = mod(sum(taps.*m),2);

m(2:N) = m(1:N-1);

m(1)=buf;

regout(ind) = m(N);

end

comp = ~ regout; sequence = regout - comp;

_________________________________

Peterson, W., W., Error Correcting Codes, MIT Press, Cambridge, MA, 1961