Maximum Length Sequence
Eine Maximum Length Sequence (kurz MLS, deutsch Folge maximaler Länge oder Maximalfolge) ist eine pseudozufällige, binäre Zahlenfolge, die unter anderem zur Ermittlung des Impulsverhaltens bestimmter Systeme (zum Beispiel den Nachhall von Räumen) verwendet wird. Auch für digitale Kommunikationssysteme und in der Kryptographie werden solche Folgen maximaler Länge eingesetzt.
Eine Folge maximaler Länge ist ein Polynomring, der traditionell mit Hilfe linear rückgekoppelter binärer Schieberegister mit einem primitiven Polynom als Generatorpolynom erzeugt werden kann. Alternativ kann mit einem Computer durch eine programmierte Folge von Nullen und Einsen eine Folge der Länge (
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 das Signal-Rausch-Verhältnis größer wird.
Eine kommerzielle Anwendung dieses Prinzips stellt das Computerprogramm MLSSA (englisch Maximum Length Sequence System Analyzer, ausgesprochen "Melissa") dar. Die deterministische Impulsfolge wird von einem Computer erzeugt und von ihm mit dem Antwortsignal korreliert. Damit sind auch zeitliche Laufzeitdifferenzen erfassbar.
Eigenschaften
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. Dies gilt aber nur für über Exklusiv-Oder-Gatter rückgekoppelte Schieberegister, da hier die Ausgangsvariable 000...0 wieder als 0 in den Eingang geschrieben wird und damit keine Zustandsänderung erfolgt. Von Computern erzeugte Pseudozufallsfolgen unterliegen dieser Einschränkung nicht.
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
Datei:MLS.Impulse.Response.pdf
Martin Cohn und Abraham 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
Zur Veranschaulichung sind in der folgenden Tabelle einige monophone Audio-Dateien mit einer Sequenzlänge von 65535 (
| Dateiname | Registerlänge | Durchlauf des Registers in Millisekunden |
|---|---|---|
| 128 | 2,9 | |
| 256 | 5,8 | |
| 512 | 11,6 | |
| 1024 | 23,2 | |
| 2048 | 46,4 |
Durch die Datenkompression des ogg-Formates kommt es zu Kompressionsartefakten, die zu Abweichungen vom Original führen können.
Literatur
- Solomon W. Golomb: Shift Register Sequences. Holden-Day, San Francisco u. a. 1967.
- Martin Cohn, Abraham 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
- Impulse response measurements using MLS (PDF; 102 kB; englisch)