Maximum length sequence

from Wikipedia, the free encyclopedia

A Maximum Length Sequence (short MLS , German  sequence of maximum length or maximum length sequence ) is a pseudo-random , binary number sequence that certain inter alia, for determining the impulse response systems (for example, the reverberation is of spaces) used. Such sequences of maximum length are also used for digital communication systems and in cryptography .

A sequence of maximum length is a polynomial ring that can traditionally be generated with the aid of linearly fed back binary shift registers with a primitive polynomial as a generator polynomial . Alternatively, a sequence of length ( ) can be generated with a computer through a programmed sequence of zeros and ones . As a result, the output signal is no longer pseudo-random, but strictly determined and can be compared with an answer (loudspeaker system, hall acoustics, ...) directly or via a fast Fourier transformation .

Sequences of maximum length have a flat frequency spectrum and their spectral properties are similar to white noise .

In contrast to short pulses , a sequence of maximum length has a longer duration and, with the same power, a higher total energy , which increases the signal-to-noise ratio during measurements .

A commercial application of this principle is the computer program MLSSA ( English Maximum Length Sequence System Analyzer , pronounced "Melissa"). The deterministic pulse sequence is generated by a computer and correlated by him with the response signal. This means that time differences in time can also be recorded.

properties

According to Solomon W. Golomb (1967), sequences of maximum length have the following properties:

1. Balance

The number of binary ones is exactly one greater than the number of binary zeros. However, this only applies to shift registers that are fed back via exclusive-OR gates , since here the output variable 000 ... 0 is again written to the input as 0 and there is no change in status. Computer generated pseudorandom sequences are not subject to this limitation.

2. Sections of equal values

Equal values ​​of all sections (consecutive zeros or consecutive ones) are

  • half the length 1
  • a quarter of the length 2
  • one eighth of the length 3
  • ...

3. Correlation

The autocorrelation and cross-correlation of the sequences are periodic and binary.

example

Example of a sequence of maximum length with a length of 31 bits : 

0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1

ad 1.)

  • Number of ones = 16
  • Number of zeros = 15

ad 2.)

  • Number of sections of consecutive zeros = 8, of which
    • 4 of length 1
    • 2 of length 2
    • 1 of length 3
    • 1 of length 4
  • Number of sections of consecutive ones = 8, of which
    • 4 of length 1
    • 2 of length 2
    • 1 of length 3
    • 0 of length 4
    • 1 of length 5

Relationship to Hadamard Transformation

Sample program for calculating the impulse response using the MLS in Component Pascal

In 1977, Cohn and Lempel showed the relationship between the Maximum Length Sequence and the Walsh-Hadamard transformation . With the help of this relationship, the correlation of a Maximum Length Sequence can be calculated efficiently in a manner similar to the Fast Fourier Transform .

Sample files

The following table shows some monophonic audio files with a sequence length of 65535 ( ) and various register lengths . The signals are square-wave and the sampling rate is 44100 Hertz to cover the full audible frequency range; one sequence run takes 1.486 seconds. After the end of a sequence, this is repeated until a total duration of ten seconds is reached:

Filename Register length Run through the register in milliseconds
Audio file / audio sample MLS.0128.65535.ogg ? / i 128 2.9
Audio file / audio sample MLS.0256.65535.ogg ? / i 256 5.8
Audio file / audio sample MLS.0512.65535.ogg ? / i 512 11.6
Audio file / audio sample MLS.1024.65535.ogg ? / i 1024 23.2
Audio file / audio sample MLS.2048.65535.ogg ? / i 2048 46.4

The data compression of the above-mentioned format leads to compression artifacts that can lead to deviations from the original.

literature

  • Solomon W. Golomb: Shift Register Sequences . Holden-Day, San Francisco a. a. 1967.
  • Martin Cohn, A. Lempel: On Fast M-Sequence Transforms (=  IEEE Transactions on Information Theory . Volume 23 , no. 1 ). 1977, ISSN  0018-9448 , p. 135-137 , doi : 10.1109 / TIT.1977.1055666 .

Web links