HOME

TheInfoList



OR:

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 sh ...
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 response In signal processing and control theory, the impulse response, or impulse response function (IRF), of a dynamic system is its output when presented with a brief input signal, called an Dirac delta function, impulse (). More generally, an impulse ...
s (e.g., of room
reverberation Reverberation (also known as reverb), in acoustics, is a persistence of sound, after a sound is produced. Reverberation is created when a sound or signal is reflected causing numerous reflections to build up and then decay as the sound is abso ...
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 t ...
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 Signal (electrical engineering), electrical, optical ...
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 o ...
experiments.


Generation

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 sh ...
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: :\begin a_3 +1= a_0 + a_1 \ a_2 +1= a_3 \\ a_1 +1= a_2 \\ a_0 +1= a_1 \\ \end 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 exa ...
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 Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
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 220 − 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 2^n-1 there are 2^ ones and 2^-1 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 Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable ...
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 s = +1 and bit value 0 s = -1, mapping XOR to the negative of the product: R(n)=\frac 1 N \sum_^N s , s^* +nN = \begin 1 &\text n = 0, \\ -\frac 1 N &\text 0 < n < N. \end where s^* represents the complex conjugate and +nN 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 define ...
(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 Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable ...
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 :y = (h*s) \, Taking the cross-correlation with respect to ''s'' 'n''of both sides, :_ = h _\, and assuming that φ''ss'' is an impulse (valid for long sequences) :h = _.\, 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 Signal-to-noise ratio (SNR or S/N) is a measure used in science and engineering that compares the level of a desired signal to the level of background noise. SNR is defined as the ratio of signal power to the noise power, often expressed in deci ...
. 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 In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...
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 sy ...
*
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 In signal processing and control theory, the impulse response, or impulse response function (IRF), of a dynamic system is its output when presented with a brief input signal, called an Dirac delta function, impulse (). More generally, an impulse ...
*
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 In signal processing and control theory, the impulse response, or impulse response function (IRF), of a dynamic system is its output when presented with a brief input signal, called an Dirac delta function, impulse (). More generally, an impulse ...
of a
linear time-invariant system 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 define ...
. 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