Maximum Length Sequence

Maximum Length Sequence

Eine Maximum Length Sequence (kurz MLS, deutsch Folge maximaler Länge oder Maximalfolge) ist eine pseudozufällige, binäre Folge, die vorwiegend zur Ermittlung des Impulsverhaltens bestimmter Systeme (zum Beispiel den Nachhall von Räumen) verwendet wird. Auch für digitale Kommunikationssysteme werden solche Folgen maximaler Länge eingesetzt.

Eine Folge maximaler Länge ist ein Polynomring, der mit Hilfe linear rückgekoppelter binärer Schieberegister erzeugt werden kann. Folgen maximaler Länge haben ein flaches Frequenzspektrum und sind identisch und sind somit weißem Rauschen recht ähnlich.

Im Gegensatz zu kurzen Impulsen hat eine Folge maximaler Länge eine längere Dauer und bei gleicher Leistung eine höhere Gesamtenergie, wodurch bei Messungen der Signal-Rausch-Abstand größer wird.

Inhaltsverzeichnis

Eigenschaften

Folgen maximaler Länge haben nach Solomon Golomb (1967) die folgenden Eigenschaften:

1. Gleichgewicht

Die Anzahl der binären Einsen ist exakt um eins größer als die Anzahl der binären Nullen.

2. Abschnitte gleicher Werte

Von allen Abschnitten gleicher Werte (aufeinanderfolgende Nullen beziehungsweise aufeinanderfolgende Einsen) ist

  • die Hälfte der Länge 1
  • ein Viertel der Länge 2
  • ein Achtel der Länge 3

...

3. Korrelation

Die Autokorrelation und Kreuzkorrelation der Folgen ist periodisch und binär.

Beispiel

Beispiel einer Folge maximaler Länge mit 31 bit Länge:

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.)

  • Anzahl der Einsen = 16
  • Anzahl der Nullen = 15

ad 2.)

  • Anzahl der Abschnitte aufeinanderfolgender Nullen = 8, davon
    • 4 der Länge 1
    • 2 der Länge 2
    • 1 der Länge 3
    • 1 der Länge 4
  • Anzahl der Abschnitte aufeinanderfolgender Einsen= 8, davon
    • 4 der Länge 1
    • 2 der Länge 2
    • 1 der Länge 3
    • 0 der Länge 4
    • 1 der Länge 5

Beziehung zur Hadamard-Transformation

Cohn und Lempel zeigten 1977 die Beziehung der Maximum Length Sequence zur Walsh-Hadamard-Transformation. Mit Hilfe dieser Beziehung kann die Korrelation einer Maximum Length Sequence auf ähnliche Weise wie die Schnelle Fourier-Transformation schnell berechnet werden.

Beispielprogramm zur Berechnung der Impulsantwort mithilfe der MLS in Component Pascal

Beispieldateien

Zur Veranschaulichung sind in der folgenden Tabelle einige monophone Audio-Dateien mit einer Sequenzlänge von 65535 ( = 216 − 1) und verschiedenen Registerlängen aufgeführt. Die Signale haben Rechteckform, und die Abtastrate beträgt 44100 Hertz, um den vollen hörbaren Frequenzbereich abzudecken; dabei dauert ein Sequenz-Durchlauf 1,486 Sekunden. Nach dem Ende einer Sequenz wird diese jeweils wiederholt, bis eine Gesamtdauer von zehn Sekunden erreicht wird:

Dateiname Registerlänge Durchlauf des Registers in Millisekunden
MLS.0128.65535.ogg?/i 128 2,9
MLS.0256.65535.ogg?/i 256 5,8
MLS.0512.65535.ogg?/i 512 11,6
MLS.1024.65535.ogg?/i 1024 23,2
MLS.2048.65535.ogg?/i 2048 46,4

Durch die Datenkompression des ogg-Formates kommt es zu Kompressionsartefakten, die zu Abweichungen vom Original führen können.

Siehe auch

Literatur

  • Golomb, S. Shift Register Sequences, San Francisco, Holden-Day (1967)
  • Cohn, M. and Lempel, A. On Fast M-Sequence Transforms, IEEE Trans. Information Theory, vol. IT-23, pp. 135–137 (January 1977)

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Maximum length sequence — 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 that can be… …   Wikipedia

  • Maximum length sequence — Une maximum length sequence (MLS) est une pseudorandom binary sequence (en) (PRBS) c est à dire une suite périodique de valeurs produite par un linear feedback shift register (LFSR) qui explore toutes les valeurs pouvant être produites par… …   Wikipédia en Français

  • Maximum parsimony — Maximum parsimony, often simply referred to as parsimony, is a non parametric statistical method commonly used in computational phylogenetics for estimating phylogenies. Under maximum parsimony, the preferred phylogenetic tree is the tree that… …   Wikipedia

  • M-sequence — An M sequence may refer to: *Regular sequence, which is an important topic in commutative algebra. *A maximum length sequence, which is a type of pseudorandom binary sequence …   Wikipedia

  • Maximum parsimony (phylogenetics) — Parsimony is a non parametric statistical method commonly used in computational phylogenetics for estimating phylogenies. Under parsimony, the preferred phylogenetic tree is the tree that requires the least evolutionary change to explain some… …   Wikipedia

  • Sequence alignment — In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences.[1]… …   Wikipedia

  • Regular sequence (algebra) — In commutative algebra, if R is a commutative ring and M an R module, an element r in R is called M regular if r is not a zerodivisor on M , and M/rM is nonzero. An R regular sequence on M is a d tuple: r1, ..., rd in R such that for each i le; d …   Wikipedia

  • Davenport–Schinzel sequence — In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of… …   Wikipedia

  • Run length limited — or RLL coding is a technique that is used to store data on recordable media. Specifically, RLL prevents long stretches of repeated bits from causing the signal recorded on media to not change for an excessive period, by modulating the data. RLL… …   Wikipedia

  • Attribute sequence — A clause attribute is a characteristic of a clause. Some examples of clause attributes are: the number of literals in a clause (i.e., clause length) the number of term symbols in a clause the number of constants in a clause the number of… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”