Maximum Length Sequence

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 mit einem primitiven Polynom als Generatorpolynom erzeugt werden kann. Folgen maximaler Länge haben ein flaches Frequenzspektrum und sind in der spektralen Eigenschaften dem weißen Rauschen ä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-Verhältnis größer wird.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Folgen maximaler Länge haben nach Solomon W. 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Beispielprogramm zur Berechnung der Impulsantwort mithilfe der MLS in Component Pascal

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 effizient berechnet werden.

Beispieldateien[Bearbeiten | Quelltext bearbeiten]

Zur Veranschaulichung sind in der folgenden Tabelle einige monophone Audio-Dateien mit einer Sequenzlänge von 65535 () 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.

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]