Hubbry Logo
Maximum length sequenceMaximum length sequenceMain
Open search
Maximum length sequence
Community hub
Maximum length sequence
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Maximum length sequence
Maximum length sequence
Maximum length sequence
View on Wikipedia
from Wikipedia

A maximum length sequence (MLS) is a type of pseudorandom binary sequence.

They are bit sequences generated using maximal linear-feedback shift registers and are so called because they are periodic and reproduce every binary sequence (except the zero vector) that can be represented by the shift registers (i.e., for length-m registers they produce a sequence of length 2m − 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 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[1]). They are also used as a basis for deriving pseudo-random sequences in digital communication systems that employ direct-sequence spread spectrum and frequency-hopping spread spectrum transmission systems, and in the efficient design of some fMRI experiments.[2]

Generation

[edit]
Figure 1: The next value of register a3 in a feedback shift register of length 4 is determined by the modulo-2 sum of a0 and a1.

MLS are generated using maximal linear-feedback shift registers. 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

[edit]

A polynomial over GF(2) 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 .

A necessary and sufficient condition for the sequence generated by a LFSR to be maximal length is that its corresponding polynomial be primitive.[3]

Implementation

[edit]

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

[edit]

MLS have the following properties, as formulated by Solomon Golomb.[4]

Balance property

[edit]

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

[edit]

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. [vague]

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

[edit]

The circular autocorrelation of an MLS is a Kronecker delta function[5][6] (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.

The linear autocorrelation of an MLS approximates a Kronecker delta.

Extraction of impulse responses

[edit]

If a linear time invariant (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, 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.[7][8] 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.[9] Other signals have been designed with minimal crest factor, though it is unknown if it can be improved beyond 3 dB.[10]

Relationship to Hadamard transform

[edit]

Cohn and Lempel[11] showed the relationship of the MLS to the Hadamard transform. This relationship allows the correlation of an MLS to be computed in a fast algorithm similar to the FFT.

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Maximum length sequence

View on Grokipedia
from Grokipedia
A maximum length sequence (MLS), also known as an m-sequence, is a deterministic of length 2n−12^n - 1 generated by an nn-stage (LFSR) configured with a primitive polynomial, representing the longest possible periodic output for such a register without repeating the all-zero state. These sequences exhibit statistical properties closely resembling , including a balanced distribution of 1s and 0s and an ideal function that peaks sharply at zero lag while remaining low elsewhere. MLSs are generated through a feedback mechanism where the output of specific register stages is linearly combined using exclusive-OR (XOR) operations and fed back to the input, causing the register to cycle through all 2n−12^n - 1 non-zero states before repeating. The choice of a primitive over the GF(2) ensures the maximal period; for example, the x3+x+1x^3 + x + 1 produces a sequence of length 7 from a 3-stage LFSR. This deterministic yet unpredictable nature distinguishes MLSs from truly random sequences, allowing efficient computation and reproduction. Notable properties of MLSs include a near-equal count of 1s (2n−12^{n-1}) and 0s (2n−1−12^{n-1} - 1), equal numbers of runs of each length (up to n), and a two-level autocorrelation of 2n−12^n - 1 at lag zero and −1-1 at all other lags within one period. These characteristics enable MLSs to serve as test signals for linear systems, where convolving an MLS input with a system's output yields the via fast Hadamard transforms, requiring only additions and subtractions for efficiency. In applications, MLSs are widely employed in spread-spectrum communications for pseudonoise generation. They also facilitate acoustic measurements, such as room impulse response estimation, by allowing rapid, low-level excitation without audible distortion. Additional uses include built-in self-testing for digital circuits via test pattern generation and response analysis, as well as cyclic redundancy checks (CRC) for error detection in data transmission.

Introduction

Definition

A maximum length sequence (MLS), also known as an m-sequence, is a type of generated by a maximal (LFSR) of degree nn, achieving the longest possible period of 2n−12^n - 1 for that register length. The sequence is deterministic and periodic, repeating every 2n−12^n - 1 symbols, but within one full period, it mimics the statistical behavior of random due to its uniform traversal of all non-zero states of the LFSR. Key characteristics of an MLS include its binary nature, consisting of symbols that can be represented as 0 and 1, and its common mapping to +1 and -1 in applications requiring symmetry, such as and testing. This mapping results in a nearly zero mean over one period, enhancing its utility as . MLSs are widely used for generating pseudorandom signals in identification, and techniques because of their noise-like appearance despite being fully deterministic. The sequence is typically notated as sks_k for k=0,1,…,2n−2k = 0, 1, \dots, 2^n - 2, where sk=±1s_k = \pm 1.

Historical Development

The development of maximum length sequences (MLS), also known as m-sequences, traces its roots to the and 1950s, emerging from research on linear feedback shift registers (LFSRs) amid wartime demands for secure communications and radar systems resistant to jamming. During , efforts to create noise-like signals for anti-interference purposes laid foundational groundwork, with early experiments in pseudorandom sequences appearing in spread-spectrum techniques by the late , such as Mortimer Rogoff's work on using stored noise signals. In the 1950s, advanced the mathematical understanding of LFSRs while at the , identifying sequences that achieve maximal period lengths for pseudorandom properties suitable for and error-correcting codes. Golomb's research culminated in his influential 1967 book Shift Register Sequences, which systematically formalized the construction and characteristics of these sequences, establishing them as a of digital sequence theory. Key early applications emerged in space communications during the late 1950s and 1960s, including the use of m-sequences in 1958 for determining the orbit of Explorer I and in 1961 for ranging to , achieving unprecedented accuracy improvements. By the , MLS gained traction in acoustics through Manfred R. Schroeder's pioneering 1975 paper on diffuse sound reflection via maximum-length sequences, which inspired practical measurement systems like MLSSA in the late for room analysis. Into the 1990s, MLS transitioned from theoretical constructs to standard tools in , supporting efficient correlation-based testing in communications and beyond, as evidenced by their integration into standards like GPS and systems.

Mathematical Foundations

Linear Feedback Shift Registers

A (LFSR) consists of a chain of n flip-flops or memory elements arranged in series, forming a , with feedback connections from selected output positions (taps) combined using exclusive-OR (XOR) gates, which perform modulo-2 addition, to generate the input for the first stage. The structure operates synchronously, shifting the contents of the register toward the output on each clock cycle, while the feedback bit determines the new value entering the input end. In the context of generating maximum length sequences (MLS), the LFSR produces binary sequences, typically represented as elements in {0,1}, which can be mapped to {+1,-1} for applications by substituting 0 → +1 and 1 → -1. The operation of an LFSR is governed by a linear recurrence relation over the finite field GF(2), where the next state of the register is computed as the XOR of the tapped positions. For a register of length n, if the current state is sk,sk+1,…,sk+n−1s_k, s_{k+1}, \dots, s_{k+n-1}, the next bit sk+ns_{k+n} is given by sk+n=∑i∈Tsk+i(mod2),s_{k+n} = \sum_{i \in T} s_{k+i} \pmod{2}, where T denotes the set of tap positions (with indices starting from 0 or 1 depending on convention). This recursive process generates a periodic sequence, and the LFSR must be initialized to a non-all-zero state to avoid locking into a trivial constant-zero output. A maximal LFSR is configured such that its feedback polynomial is primitive over GF(2), ensuring the register cycles through all 2n−12^n - 1 possible non-zero states before repeating, thereby producing an MLS of maximum period 2n−12^n - 1. The all-zero state is excluded from the cycle, as it leads to perpetual zeros under the linear feedback rule. For illustration, consider a simple n=3 LFSR with taps at positions 1 and 3 (corresponding to the x3+x+1x^3 + x + 1), initialized to the state [1,1,1]. The sequence of output bits generated is 1,1,1,0,1,0,0 (or equivalently, shifting through states: 111 → 110 → 101 → 100 → 011 → 010 → 001 → 111), repeating every 7 steps and visiting all non-zero ternary combinations.

Primitive Polynomials

A primitive of degree nn over the Galois field is defined as an whose one root in the extension field GF(2n2^n) is a primitive element, generating the entire of order 2n−12^n - 1. Equivalently, it is an p(x)p(x) that divides x2n−1+1x^{2^n - 1} + 1 but does not divide xd+1x^d + 1 for any proper dd of 2n−12^n - 1. In the context of linear feedback shift registers (LFSRs), the feedback polynomial must be primitive to ensure the register produces a maximum length sequence (MLS) of period exactly 2n−12^n - 1, traversing all possible nonzero states. The coefficients of the determine the tap positions in the LFSR; for instance, the primitive x4+x+1x^4 + x + 1 over corresponds to taps at positions 4 and 1 (with the constant term implicit), yielding an MLS of 15 for a 4-stage register. To test whether an of degree nn over is primitive, one verifies that the smallest positive kk such that xk≡1(modp(x))x^k \equiv 1 \pmod{p(x)} is exactly k=2n−1k = 2^n - 1. This involves checking that p(x)p(x) divides x2n−1+1x^{2^n - 1} + 1 and that the order is not smaller by testing against the prime factors of 2n−12^n - 1. Examples of primitive polynomials over for small degrees nn include:
Degree nnPrimitive PolynomialPeriod
2x2+x+1x^2 + x + 13
3x3+x+1x^3 + x + 17
4x4+x+1x^4 + x + 115
5x5+x2+1x^5 + x^2 + 131

Generation

Polynomial Interpretation

Maximum length sequences admit an algebraic interpretation in terms of polynomials over the . Consider a primitive p(x)p(x) of degree nn over , which serves as the for generating the sequence. The sequence {sk}k=0∞\{s_k\}_{k=0}^\infty satisfies the linear defined by the coefficients of p(x)p(x), where the feedback is given by the polynomial's non-leading terms. For instance, with p(x)=x3+x+1p(x) = x^3 + x + 1, the recurrence is sk+3=sk+1+sk(mod2)s_{k+3} = s_{k+1} + s_k \pmod{2} for k≥0k \geq 0, with initial conditions determining the specific shift of the . The of the sequence provides a compact algebraic representation. The S(x)=∑k=0∞skxkS(x) = \sum_{k=0}^\infty s_k x^k can be expressed as S(x)=P(x)/p∗(x)S(x) = P(x) / p^*(x), where p∗(x)p^*(x) is the of p(x)p(x) (defined as p∗(x)=xnp(1/x)p^*(x) = x^n p(1/x)) and P(x)P(x) is a of degree less than nn determined by the initial nn terms of the sequence. For initial conditions corresponding to the (starting from a single 1), this reduces to the power series expansion of 1/p(x)1 / p(x) in the ring of over . The periodicity arises because the sequence repeats every 2n−12^n - 1 terms, reflecting the structure of the GF(2) / (p(x)), where the element xx has multiplicative order 2n−12^n - 1 due to the primitivity of p(x)p(x). This ensures no shorter cycles, as any proper would contradict the maximal order of primitive polynomials. An explicit formula for the sequence entries links it directly to finite field elements. Let α\alpha be a root of p(x)p(x) in the extension field GF(2n2^n); then α\alpha is a primitive element generating the of nonzero field elements. The sequence is given by sk=Tr⁡(αk)s_k = \operatorname{Tr}(\alpha^k), where Tr⁡:GF⁡(2n)→GF⁡(2)\operatorname{Tr}: \operatorname{GF}(2^n) \to \operatorname{GF}(2) is the absolute trace function defined as Tr⁡(y)=∑i=0n−1y2i\operatorname{Tr}(y) = \sum_{i=0}^{n-1} y^{2^i}. This trace representation underscores the balanced and pseudorandom of , as the trace maps elements uniformly to or 1 over the field.

Practical Implementation

Maximum length sequences are commonly implemented in software using simulations of linear feedback shift registers (LFSRs), where state is updated via right-shifting and XOR operations on specified tap positions defined by the primitive polynomial. Languages like Python or are suitable, with the register typically represented as an integer or initialized to a non-zero value to ensure the sequence cycles through all 2^n - 1 non-zero states. For instance, the feedback bit is computed as the XOR of the bits at the tap locations, then shifted into the register's most significant position. In hardware, MLS generation leverages field-programmable gate arrays (FPGAs) or application-specific integrated circuits (ASICs), employing D flip-flops for the stages and XOR gates for feedback computation based on the taps. This configuration enables compact, high-throughput designs; for example, VHDL-based FPGA implementations for 8-, 16-, and 32-bit LFSRs demonstrate low resource usage and maximal sequence lengths, suitable for applications. The following pseudocode illustrates an n=4 MLS generation using the primitive polynomial x4+x+1x^4 + x + 1 (taps at positions 0 and 1, 0-based from the least significant bit), starting from state 0001 ( 1). The output is the least significant bit at each step, yielding the full 15-bit : 100010011010111.

n = 4 state = 1 # Initial non-zero state: binary 0001 [sequence](/page/Sequence) = [] taps = [0, 1] # Positions for x^4 + x + 1 for _ in range(2**n - 1): output = state & 1 # Extract LSB as output [sequence](/page/Sequence).append(output) feedback = 0 for tap in taps: feedback ^= (state >> tap) & 1 state = (state >> 1) | (feedback << (n - 1)) # Shift right, insert feedback at MSB # Output: [1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]

n = 4 state = 1 # Initial non-zero state: binary 0001 [sequence](/page/Sequence) = [] taps = [0, 1] # Positions for x^4 + x + 1 for _ in range(2**n - 1): output = state & 1 # Extract LSB as output [sequence](/page/Sequence).append(output) feedback = 0 for tap in taps: feedback ^= (state >> tap) & 1 state = (state >> 1) | (feedback << (n - 1)) # Shift right, insert feedback at MSB # Output: [1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]

This approach uses bit operations for efficiency, with each iteration performing O(1) work per tap. Generating the complete MLS requires O(2^n) time due to the sequence length, while state storage is O(n bits; however, for longer sequences, parallel methods—such as table lookups or matrix over GF(2)—can compute segments in sub-linear time relative to length. A common variation for signal processing maps the binary {0,1} sequence to {+1,-1} by transforming each bit b to 1 - 2b, preserving autocorrelation properties while enabling bipolar representations in analog or digital systems.

Properties

Balance Property

The balance property of a maximum length sequence (MLS) states that, in a sequence of length N=2n−1N = 2^n - 1 generated by an nn-stage linear feedback shift register using a primitive feedback polynomial, the number of symbols equal to one polarity (e.g., +1 in bipolar representation) is 2n−12^{n-1}, while the number equal to the opposite polarity (e.g., -1) is 2n−1−12^{n-1} - 1. This near-equality holds regardless of the specific primitive polynomial chosen, as long as the sequence achieves maximum period. This property arises because the MLS cycles through all 2n−12^n - 1 non-zero states of the exactly once per period. For the output bit (typically the least significant bit), exactly half of all possible 2n2^n states have a 1 in that position (2n−12^{n-1} states), including the all-zero state which has a 0. Excluding the all-zero state leaves 2n−12^{n-1} states with output 1 and 2n−1−12^{n-1} - 1 states with output 0. In bipolar mapping (e.g., 0 to +1 and 1 to -1, or vice versa), this translates directly to the symbol counts. The balance property implies a negligible (DC) in the sequence, with the cumulative sum over one period equaling ±1\pm 1. This makes MLS suitable for applications requiring unbiased pseudorandom signals, such as simulating flips in statistical testing or avoiding lines at zero in . For example, an MLS of degree n=3n=3 (length N=7N=7) generated by the primitive polynomial x3+x2+1x^3 + x^2 + 1 yields the bipolar sequence [+1, +1, +1, -1, -1, +1, -1], containing four +1s and three -1s.

Run Property

The run property of a maximum length sequence (MLS) of period N=2n−1N = 2^n - 1 characterizes the distribution of runs, where a run is a maximal of consecutive identical symbols (either all 0s or all 1s). This property ensures that the sequence exhibits run lengths that closely approximate those expected in a random binary sequence with equal probability for 0 and 1, contributing to its pseudorandom appearance. Specifically, among all runs in one period, are of length 1, one quarter are of length 2, one eighth are of length 3, and so on; the total number of runs is 2n−12^{n-1}. Due to the slight imbalance in symbol counts (one more 1 than 0), there is one run of length nn consisting of 1s and one run of length n−1n-1 consisting of 0s, with the distribution for shorter runs adjusted accordingly (for k=1k = 1 to n−2n-2, there are 2n−k−12^{n-k-1} runs of length kk for 1s and the same for 0s; for k=n−1k = n-1, there is one run of n−1n-1 1s and two runs of n−1n-1 0s in some formulations, but the overall holds with the noted exception). The proof of this property relies on the structure of the (LFSR) generating the MLS, which cycles through all 2n−12^n - 1 non-zero states exactly once per period. A run of length kk corresponds to a sequence of k−1k-1 consecutive state transitions where the output symbol remains the same, followed by a transition that changes it. This can be analyzed using the associated with the LFSR, where nodes represent (n-1)-bit states and edges represent the next bit, allowing the count of such transition paths to be determined combinatorially from the primitive polynomial defining the feedback. For illustration, consider an MLS of degree n=3 with period 7 generated by the primitive polynomial x3+x+1x^3 + x + 1, yielding the sequence 1 1 0 1 0 0 1. The runs are a length-2 run of 1s, a length-1 run of 0s, a length-1 run of 1s, a length-2 run of 0s, and a length-1 run of 1s. This shows two runs of length 1 for 1s, one run of length 1 for 0s, one run of length 2 for 1s, and one run of length 2 for 0s, consistent with the property for small n (where the longest run of length 3 for 1s appears in a cyclic shift).

Correlation Properties

Maximum length sequences (MLS), or m-sequences, possess exceptional correlation properties that render them pseudorandom with deterministic structure, particularly in their autocorrelation and cross-correlation behaviors. The autocorrelation function measures the similarity between the sequence and its shifted version, exhibiting a sharp peak at zero lag that drops to a minimal constant level elsewhere, mimicking while enabling precise in applications. The periodic autocorrelation C(τ)C(\tau) of a binary MLS of length N=2n−1N = 2^n - 1, with symbols mapped to {+1,−1}\{+1, -1\}, is given by C(τ)=∑i=0N−1sis(i+τ)mod  N,C(\tau) = \sum_{i=0}^{N-1} s_i s_{(i + \tau) \mod N}, where sis_i denotes the ii-th symbol. This function achieves the ideal two-level form: C(0)=NC(0) = N and C(τ)=−1C(\tau) = -1 for all nonzero lags τ≢0(modN)\tau \not\equiv 0 \pmod{N}. When normalized, C(τ)/NC(\tau)/N approximates the δ(τ)\delta(\tau), with the out-of-phase values exactly −1/N-1/N. This two-level autocorrelation arises from the sequence's generation via a (LFSR) governed by a primitive polynomial over the GF(2)\mathrm{GF}(2). The linear recurrence ensures that any nontrivial cyclic shift correlates with the original sequence in precisely (N−1)/2(N - 1)/2 positions where the symbols agree and (N+1)/2(N + 1)/2 where they disagree under the ±1\pm 1 mapping, yielding the off-peak value of [(N−1)/2−(N+1)/2]=−1[(N - 1)/2 - (N + 1)/2] = -1. The field properties guarantee the sequence visits all nonzero states exactly once per period, underpinning the uniform distribution of shift overlaps. The between two distinct MLS of the same length NN, generated from different primitive polynomials, is bounded but lacks the ideal delta-like behavior of ; its magnitude is typically O(N)O(\sqrt{N})
Add your contribution
Related Hubs
User Avatar
No comments yet.