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 ($ 2^{n}-1 $) erzeugt werden. Dadurch ist das Ausgangssignal nicht mehr pseudozufällig, sondern streng determiniert und kann mit einer Antwort (Lautsprechersystem, Saalakustik usw.) direkt oder über eine schnelle Fourier-Transformation verglichen werden.

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 ($ =2^{16}-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
Audio-Datei / Hörbeispiel MLS.0128.65535.ogg?/i 128 2,9
Audio-Datei / Hörbeispiel MLS.0256.65535.ogg?/i 256 5,8
Audio-Datei / Hörbeispiel MLS.0512.65535.ogg?/i 512 11,6
Audio-Datei / Hörbeispiel MLS.1024.65535.ogg?/i 1024 23,2
Audio-Datei / Hörbeispiel 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

  • 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

Die News der letzten Tage

25.09.2023
Thermodynamik | Optik | Akustik
Licht- und Schallwellen enthüllen negativen Druck
Negativer Druck ist ein seltenes und schwer nachzuweisendes Phänomen in der Physik.
20.09.2023
Sterne | Teleskope | Astrophysik
JWST knipst Überschall-Gasjet eines jungen Sterns
Die sogenannten Herbig-Haro-Objekte (HH) sind leuchtende Gasströme, die das Wachstum von Sternbabies signalisieren.
18.09.2023
Optik | Quantenphysik
Ein linearer Weg zu effizienten Quantentechnologien
Forschende haben gezeigt, dass eine Schlüsselkomponente für viele Verfahren der Quanteninformatik und der Quantenkommunikation mit einer Effizienz ausgeführt werden kann, die jenseits der üblicherweise angenommenen oberen theoretischen Grenze liegt.
17.01.1900
Thermodynamik
Effizientes Training für künstliche Intelligenz
Neuartige physik-basierte selbstlernende Maschinen könnten heutige künstliche neuronale Netze ersetzen und damit Energie sparen.
16.01.1900
Quantencomputer
Daten quantensicher verschlüsseln
Aufgrund ihrer speziellen Funktionsweise wird es für Quantencomputer möglich sein, die derzeit verwendeten Verschlüsselungsmethoden zu knacken, doch ein Wettbewerb der US-Bundesbehörde NIST soll das ändern.
15.01.1900
Teilchenphysik
Schwer fassbaren Neutrinos auf der Spur
Wichtiger Meilenstein im Experiment „Project 8“ zur Messung der Neutrinomasse erreicht.
17.09.2023
Schwarze Löcher
Neues zu supermassereichen binären Schwarzen Löchern in aktiven galaktischen Kernen
Ein internationales Team unter der Leitung von Silke Britzen vom MPI für Radioastronomie in Bonn hat Blazare untersucht, dabei handelt es sich um akkretierende supermassereiche schwarze Löcher in den Zentren von Galaxien.
14.09.2023
Sterne | Teleskope | Astrophysik
ESO-Teleskope helfen bei der Lösung eines Pulsar-Rätsels
Durch eine bemerkenswerte Beobachtungsreihe, an der zwölf Teleskope sowohl am Erdboden als auch im Weltraum beteiligt waren, darunter drei Standorte der Europäischen Südsternwarte (ESO), haben Astronom*innen das seltsame Verhalten eines Pulsars entschlüsselt, eines sich extrem schnell drehenden toten Sterns.
30.08.2023
Quantenphysik
Verschränkung macht Quantensensoren empfindlicher
Quantenphysik hat die Entwicklung von Sensoren ermöglicht, die die Präzision herkömmlicher Instrumente weit übertreffen.
30.08.2023
Atomphysik | Teilchenphysik
Ein einzelnes Ion als Thermometer
Messungen mit neuem Verfahren zur Bestimmung der Frequenzverschiebung durch thermische Strahlung an der PTB unterstützen eine mögliche Neudefinition der Sekunde durch optische Uhren.