imported>Heribert3: wird umbrochen, ohne ()

2026-03-22T11:10:47Z

wird umbrochen, ohne ()

Neue Seite

Eine '''Maximum Length Sequence''' (kurz '''MLS''', {{deS|'''Folge maximaler Länge'''}} oder '''Maximalfolge''') ist eine [[Pseudozufall|pseudozufällige]], [[Binärcode|binäre]] [[Folge (Mathematik)|Zahlenfolge]]. Der Name kommt von ihrer Periodizität und der Tatsache, dass sie jede binäre Sequenz (außer dem Nullvektor) reproduzieren, die durch die Schieberegister dargestellt werden kann (d. h. für Register der Länge m erzeugen sie eine Sequenz der Länge 2<sup>m</sup> - 1). Eine MLS wird manchmal auch als '''n-sequence''' oder '''m-sequence''' bezeichnet. Sie wird unter anderem zur Ermittlung des Impulsverhaltens bestimmter Systeme (zum Beispiel den [[Nachhall]] von Räumen) verwendet. Auch für [[Digitalsignal|digitale]] [[Kommunikationssystem]]e 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ückgekoppeltes Schieberegister|linear rückgekoppelter binärer Schieberegister]] mit einem [[Primitives Polynom|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 <math> 2^{n} - 1</math> 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ßes Rauschen (Physik)|weißen Rauschen]] ähnlich.

Im Gegensatz zu kurzen [[Dirac-Impuls|Impulsen]] hat eine Folge maximaler Länge eine längere Dauer und bei gleicher [[Leistung (Physik)|Leistung]] eine höhere Gesamt[[energie]], wodurch bei Messungen das [[Signal-Rausch-Verhältnis]] größer wird.

Eine kommerzielle Anwendung dieses Prinzips stellt das Computerprogramm ''MLSSA'' ({{enS|''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 [[Periodizität (Mathematik)|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|mini|Beispielprogramm zur Berechnung der [[Impulsantwort]] mithilfe der MLS in [[Component Pascal]]]]

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 [[Monophonie (Elektroakustik)|monophone]] [[Audioformat|Audio-Dateien]] mit einer Sequenzlänge von 65535 (<math>= 2^{16} - 1</math>) und verschiedenen Registerlängen aufgeführt. Die Signale haben Rechteckform, und die Abtastrate beträgt 44100 [[Hertz (Einheit)|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:

{| class="wikitable"
|- class="hintergrundfarbe6"
! Dateiname
! Registerlänge
! Durchlauf des Registers in Millisekunden
|-
|{{Audio|MLS.0128.65535.ogg|MLS.0128.65535.ogg}}|| 128 || 2,9
|-
|{{Audio|MLS.0256.65535.ogg|MLS.0256.65535.ogg}}|| 256 || 5,8
|-
|{{Audio|MLS.0512.65535.ogg|MLS.0512.65535.ogg}}|| 512 || 11,6
|-
|{{Audio|MLS.1024.65535.ogg|MLS.1024.65535.ogg}}|| 1024 || 23,2
|-
|{{Audio|MLS.2048.65535.ogg|MLS.2048.65535.ogg}}|| 2048 || 46,4
|}

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

== Literatur ==
* {{Literatur
|Autor=Solomon W. Golomb
|Titel=Shift Register Sequences
|Verlag=Holden-Day
|Ort=San Francisco u. a.
|Datum=1967}}
* {{Literatur
|Autor=Martin Cohn, [[Abraham Lempel]]
|Titel=On Fast M-Sequence Transforms
|Reihe=IEEE Transactions on Information Theory
|BandReihe=23
|NummerReihe=1
|Datum=1977
|ISSN=0018-9448
|Seiten=135–137
|DOI=10.1109/TIT.1977.1055666}}

== Weblinks ==
* [https://jenshee.dk/signalprocessing/mls.pdf Impulse response measurements using MLS] (PDF; 102 kB; englisch)

[[Kategorie:Rauschen]]
[[Kategorie:Akustische Messtechnik]]
[[Kategorie:Folgen und Reihen]]

Maximum Length Sequence - Versionsgeschichte

imported>Heribert3: wird umbrochen, ohne ()