A maximum length sequence (MLS) is a type of
pseudorandom binary sequence
A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar to a truly rand ...
.
They are bit sequences generated using maximal
linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a ...
s and are so called because they are
periodic and reproduce every
binary sequence
A bitstream (or bit stream), also known as binary sequence, is a sequence of bits.
A bytestream is a sequence of bytes. Typically, each byte is an 8-bit quantity, and so the term octet stream is sometimes used interchangeably. An octet may ...
(except the zero vector) that can be represented by the shift registers (i.e., for length-''m'' registers they produce a sequence of length 2
''m'' − 1). An MLS is also sometimes called an n-sequence or an m-sequence. MLSs are
spectrally flat, with the exception of a near-zero DC term.
These sequences may be represented as coefficients of irreducible polynomials in a
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
over
Z/2Z.
Practical applications for MLS include measuring
impulse responses (e.g., of room
reverberation or arrival times from towed sources in the ocean). They are also used as a basis for deriving pseudo-random sequences in digital communication systems that employ
direct-sequence spread spectrum
In telecommunications, direct-sequence spread spectrum (DSSS) is a spread-spectrum modulation technique primarily used to reduce overall signal interference. The direct-sequence modulation makes the transmitted signal wider in bandwidth than ...
and
frequency-hopping spread spectrum
Frequency-hopping spread spectrum (FHSS) is a method of transmitting radio signals by rapidly changing the carrier frequency among many distinct frequencies occupying a large spectral band. The changes are controlled by a code known to both tr ...
transmission system
:''See Transmission (mechanics) for a car's transmission system''
In telecommunications, a transmission system is a system that transmits a signal from one place to another. The signal can be an electrical, optical or radio signal.
Some transmissi ...
s, optical dielectric multilayer reflector design, and in the efficient design of some
fMRI
Functional magnetic resonance imaging or functional MRI (fMRI) measures brain activity by detecting changes associated with blood flow. This technique relies on the fact that cerebral blood flow and neuronal activation are coupled. When an area ...
experiments.
Generation
![MLS shiftregisters L4](https://upload.wikimedia.org/wikipedia/commons/0/01/MLS_shiftregisters_L4.png)
MLS are generated using maximal
linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a ...
s. An MLS-generating system with a shift register of length 4 is shown in Fig. 1. It can be expressed using the following recursive relation:
:
where ''n'' is the time index and
represents
modulo-2 addition. For bit values 0 = FALSE or 1 = TRUE, this is equivalent to the XOR operation.
As 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.
Polynomial interpretation
A
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
over
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
can be associated with the linear-feedback shift register. It has degree of the length of the shift register, and has coefficients that are either 0 or 1, corresponding to the taps of the register that feed the
xor gate. For example, the polynomial corresponding to Figure 1 is ''x''
4 + ''x''
3 + 1.
A necessary and sufficient condition for the sequence generated by a LFSR to be maximal length is that its corresponding polynomial be
primitive.
Implementation
MLS are inexpensive to implement in hardware or software, and relatively low-order feedback shift registers can generate long sequences; a sequence generated using a shift register of length 20 is 2
20 − 1 samples long (1,048,575 samples).
Properties of maximum length sequences
MLS have the following properties, as formulated by
Solomon Golomb
Solomon (; , ),, ; ar, سُلَيْمَان, ', , ; el, Σολομών, ; la, Salomon also called Jedidiah ( Hebrew: , Modern: , Tiberian: ''Yăḏīḏăyāh'', "beloved of Yah"), was a monarch of ancient Israel and the son and succe ...
.
Balance property
The occurrence of 0 and 1 in the sequence should be approximately the same. More precisely, in a maximum length sequence of length
there are
ones and
zeros. The number of ones equals the number of zeros plus one, since the state containing only zeros cannot occur.
Run property
A "run" is a sub-sequence of consecutive "1"s or consecutive "0"s within the MLS concerned. The number of runs is the number of such sub-sequences.
Of all the "runs" (consisting of "1"s or "0"s) in the sequence :
* One half of the runs are of length 1.
* One quarter of the runs are of length 2.
* One eighth of the runs are of length 3.
* ... etc. ...
Correlation property
The circular
autocorrelation of an MLS is a
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 & ...
function (with DC offset and time delay, depending on implementation). For the ±1 convention, i.e., bit value 1 is assigned
and bit value 0
, mapping XOR to the negative of the product:
where
represents the complex conjugate and
represents a
circular shift
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...
.
The linear autocorrelation of an MLS approximates a Kronecker delta.
Extraction of impulse responses
If a
linear time invariant
In system analysis, among other fields of study, a linear time-invariant (LTI) system is a system that produces an output signal from any input signal subject to the constraints of linearity and time-invariance; these terms are briefly defin ...
(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 circular cross-correlation with the MLS. 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 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,
:
and assuming that φ
''ss'' is an impulse (valid for long sequences)
:
Any signal with an impulsive autocorrelation can be used for this purpose, but signals with high
crest factor
Crest or CREST may refer to:
Buildings
*The Crest (Huntington, New York), a historic house in Suffolk County, New York
*"The Crest", an alternate name for 63 Wall Street, in Manhattan, New York
* Crest Castle (Château Du Crest), Jussy, Switzer ...
, such as the impulse itself, produce impulse responses with poor
signal-to-noise ratio. It is commonly assumed that the MLS would then be the ideal signal, as it consists of only full-scale values and its digital crest factor is the minimum, 0 dB. However, after
analog reconstruction, the sharp discontinuities in the signal produce strong intersample peaks, degrading the crest factor by 4-8 dB or more, increasing with signal length, making it worse than a sine sweep. Other signals have been designed with minimal crest factor, though it is unknown if it can be improved beyond 3 dB.
Relationship to Hadamard transform
Cohn and Lempel
showed the relationship of the MLS to the
Hadamard transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
. This relationship allows the
correlation of an MLS to be computed in a fast algorithm similar to the
FFT
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the ...
.
See also
*
Barker code
In telecommunication technology, a Barker code, or Barker sequence, is a finite sequence of digital values with the ideal autocorrelation property. It is used as a synchronising pattern between sender and receiver.
Explanation
Binary digits ha ...
*
Complementary sequences
: ''For complementary sequences in biology, see complementarity (molecular biology). For integer sequences with complementary sets of members see Lambek–Moser theorem.''
In applied mathematics, complementary sequences (CS) are pairs of sequences ...
*
Federal Standard 1037C
Federal Standard 1037C, titled Telecommunications: Glossary of Telecommunication Terms, is a United States Federal Standard issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, a ...
*
Frequency response
In signal processing and electronics, the frequency response of a system is the quantitative measure of the magnitude and phase of the output as a function of input frequency. The frequency response is widely used in the design and analysis of s ...
*
Gold code
A Gold code, also known as Gold sequence, is a type of binary sequence, used in telecommunication ( CDMA) and satellite navigation ( GPS). Gold codes are named after Robert Gold. Gold codes have bounded small cross-correlations within a set, which ...
*
Impulse response
*
Polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
References
*
External links
* — Short on-line tutorial describing how MLS is used to obtain the
impulse response of a
linear time-invariant system. Also describes how nonlinearities in the system can show up as spurious spikes in the apparent impulse response.
* — Paper describing MLS generation. Contains C-code for MLS generation using up to 18-tap-LFSRs and matching Hadamard transform for impulse response extraction.
* A (binaural) room impulse response database generated by means of maximum length sequences.
*{{cite web , id=XAPP052 v1.1 , title=Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators — Obsolete , date=July 1996 , publisher=Xilinx , url=http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf — Implementing lfsr's in FPGAs includes listing of taps for 3 to 168 bits
Pseudorandomness
Polynomials
Binary sequences