Maximum length sequence

A maximum length sequence (MLS) is a pseudo-random sequence used for measuring impulse responses (e.g., of room reverberation).

They are polynomial rings generated using feedback binary shift registers and are so called because they are periodic and reproduce every binary sequence that can be reproduced by the shift registers (i.e., for m registers they produce a sequence of length 2^m - 1). Maximum length sequences are spectrally flat, with the exception of a zero DC term, and are used instead of impulse responses because, being longer, they inject more energy into a system; extracted impulse responses thus have a higher signal-to-noise ratio.

Generation of maximum length sequences

MLS are generated using linear feedback shift registers. An MLS generating system with four shift registers is shown in Fig. 1. This can be expressed using the recursive relation,

a₃(n + 1) = a₀(n) + a₁(n).

Because MLS are periodic and shift registers cycle through every possible binary value (with the exception of the zero vector), registers can be initialized to any state, with the exception of the zero vector.

MLS are inexpensive to implement in hardware or software, and relatively low-order feedback shift registers can generate long sequences; a sequence generated using 20 shift registers is 2²⁰ - 1 samples long, which is equivalent to approximately 23.8 seconds if played back as audio with a sampling rate of 44.1 kHz.

Extraction of impulse responses

If a LTI system's impulse response is to be measured using a MLS, the response can be extracted from the measured system output y(n) by taking its cross-correlation with the MLS sequence. This is because the autocorrelation of a MLS is 1 for zero-lag, and nearly zero (−1/N where N is the sequence length) for all other lags; in other words, the autocorrelation of the MLS can be said to approach unit impulse function as MLS sequence length increases.

If the impulse response of a system is h(n) and the MLS is s(n), then

Taking the cross-correlation with respect to s(n) of both sides,

φ_sy = h(n) * φ_ss

and assuming that φ_ss is an impulse (valid for long sequences)

See also

• Impulse response
• Frequency response
• Polynomial ring