Berlekamp-Massey-Algorithmus

Der Berlekamp-Massey-Algorithmus (nach Elwyn Berlekamp und James Massey) dient dazu, das kürzeste, lineare rückgekoppelte Schieberegister zu finden, das eine gegebene Folge von Symbolen ausgibt. Die Symbole können aus einem beliebigen Körper stammen.

Inhaltsverzeichnis

Vorbemerkungen

Bei einem linear rückgekoppelten Schieberegister der Länge L stimmen die ersten L Ausgangssymbole mit den L Anfangsinhalten der Speicherzellen überein. Die folgenden Ausgangssymbole werden durch die Rekursion

 s_j = -\sum_{k=1}^{L} c_k \cdot s_{j-k}

bestimmt. Dabei bezeichnen ck die Rückkopplungskoeffizienten des Schieberegisters. Führt man für eine Verzögerung die Bezeichnung D ein, so kann das rückgekoppelte Schieberegister auch durch das Polynom

 C(D) = 1 + \sum_{k=1}^{L} c_k \cdot D^k

beschrieben werden.

Ziel des Berlekamp-Massey-Algorithmus ist es also, zu einer gegebenen Folge \left( s_0, s_1, \ldots , s_{n-1} \right) von Symbolen das Rückkopplungspolynom C(D) und die Länge L des erzeugenden Schieberegisters zu finden.

Einfaches Beispiel

Der Einfachheit halber betrachten wir den binären Fall, also einen Körper mit lediglich zwei Elementen: \Bbb F_2 =\{0, 1\} . Die Addition ist wie folgt definiert:  1 \oplus 0 = 0 \oplus 1 = 1 und  0 \oplus 0 = 1 \oplus 1 = 0 und kann mit einem XOR-Gatter realisiert werden. Für die Multiplikation gilt  0 \otimes 0 = 0 \otimes 1 = 1 \otimes 0 = 0 und  1 \otimes 1 = 1 , was einer logischen AND-Verknüpfung entspricht.

Der Berlekamp-Massey-Algorithmus ermittelt zur Symbolsequenz (0 0 1 1 0 1 1) das kürzeste, linear rückgekoppelte Schieberegister, welches diese Sequenz ausgibt:

linear rückgekoppeltes Schieberegister

Das Rückkopplungspolynom lautet für dieses Beispiel C(D) = 1 + D + D2 und die Länge des Schieberegisters ist L = 3.

Algorithmus

Für die Beschreibung des Algorithmus werden die folgenden Variablen eingeführt:

Symbol Bedeutung
i Index des Symbols, das momentan verarbeitet wird
C(D) momentanes Rückkopplungspolynom des Schieberegisters
L momentane Länge des Schieberegisters
d aktuelle Diskrepanz, also Differenz zwischen dem aktuellen Symbol si und dem Symbol, das durch das aktuelle Schieberegister erzeugt wird
Cl(D) Rückkopplungspolynom des Schieberegisters, als zum letztem Mal die Länge geändert wurde
l Index, der angibt, in welchem Schritt zum letzten Mal die Länge geändert wurde
dl Wert der Diskrepanz, als zum letzten Mal die Länge geändert wurde
T(D) Temporärer Speicher für das Rückkopplungspolynom C(D)

Damit resultiert der folgende Algorithmus

Berlekamp-Massey-Algorithmus

Das Prinzip des Algorithmus ist einfach zu verstehen: Gestartet wird mit einem Schieberegister der Länge 0, das eine Ausgangssequenz von lauter Nullen erzeugt. In jedem Iterationsschritt wird überprüft, ob das aktuelle Schieberegister das gewünschte Ausgangssymbol ausgibt. Ist dies der Fall, dann wird das Schieberegister beibehalten und die Iteration wird mit dem nächsten Symbol der gegebenen Sequenz fortgesetzt. Stellt man jedoch eine Diskrepanz fest, so wird das Schieberegister angepasst. Ob dabei die Länge des Schieberegisters erhöht werden muss, hängt von der momentanen Länge Li des Schieberegisters und der Anzahl i verarbeiteter Symbole ab. Im Falle einer Diskrepanz gilt für die neue Länge: Li + 1 = max(Li,i + 1 − Li).

Für den binären Fall lässt sich der Algorithmus deutlich vereinfachen. In diesem Fall stammen die Eingangsymbole si, die Rückkopplungskoeffzienten ck und die Diskrepanz d aus der Menge {0,1}. Aus d\neq 0 folgt also sofort d = 1 und d − 1 = 1.

Anwendungen

Der Berlekamp-Massey-Algorithmus kann zur Decodierung des Reed-Solomon-Codes verwendet werden. Ein Reed-Solomon-Code besitzt die Eigenschaft, dass aus den empfangenen Symbolen 2·t Werte der diskreten Fouriertransformation des Fehlermusters bestimmt werden können. Aus diesen 2·t Stützwerten kann mit Hilfe des Berlekamp-Massey-Algorithmus die gesamte Fouriertransformation rekonstruiert werden, sofern höchstens t Symbole des Codeworts fehlerhaft sind.

Mit Hilfe des Berlekamp-Massey-Algorithmus kann effizient bestimmt werden, was das kürzeste, linear rückgekoppelte Schieberegister ist, welches eine gegebene Sequenz erzeugt. Die Länge dieses Schieberegisters wird als lineare Komplexität der Sequenz bezeichnet. Insbesondere in der Kryptographie ist es von Interesse, die lineare Komplexität einer Sequenz zu kennen.

Quellen

  • Elwyn R. Berlekamp: Nonbinary BCH Decoding. In: IEEE transactions on information theory. 14, 1968, ISSN 0018-9448, S. 242.
  • James L. Massey: Shift-Register Synthesis and BCH Decoding. In: IEEE transactions on information theory. 15, Nr. 1, 1969, ISSN 0018-9448, S. 122–127.
  • Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL u. a. 1996, ISBN 0-8493-8523-7 (CRC Press series on discrete mathematics and its applications).

Weblinks

Applet zum Berlekamp-Massey-Algorithmus


Wikimedia Foundation.

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

  • Massey — ist der Familienname folgender Personen: Anna Massey (1937–2011), englische Schauspielerin Charles Carleton Massey (1838–1905), englischer Rechtsanwalt und Theosoph Christopher Massey (* 1990), US amerikanischer Schauspieler Daniel Massey… …   Deutsch Wikipedia

  • Elwyn Berlekamp — Elwyn Ralph Berlekamp (* 6. September 1940 in Dover (Ohio)) ist ein US amerikanischer Mathematiker und Informatiker, der sich insbesondere mit Kodierungstheorie und kombinatorischer Spieltheorie beschäftigt. Berlekamp in Banff 2005 Berlekamp… …   Deutsch Wikipedia

  • James Lee Massey — (* 11. Februar 1934 in Wauseon, Ohio) ist ein Informationstheoretiker und Kryptologe. Er war Professor an der ETH Zürich. Seine bedeutendste Arbeiten waren die Entwicklung des Berlekamp Massey Algorithmus, der Entwurf des… …   Deutsch Wikipedia

  • James Massey — James Lee Massey (* 11. Februar 1934 in Wauseon, Ohio) ist ein Informationstheoretiker und Kryptologe. Er war Professor an der ETH Zürich. Seine bedeutendsten Arbeiten waren die Entwicklung des Berlekamp Massey Algorithmus, der Entwurf des… …   Deutsch Wikipedia

  • Gold-Code — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • Gold-Folge — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • JPL-Folge — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • LFSR — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • LSFR — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • BCH-Code — BCH Codes (Bose Chaudhuri Hocquenghem Codes) sind zyklische fehlerkorrigierende Codes, welche in der digitalen Signalverarbeitung und Datenspeicherung eingesetzt werden. Der Name BCH ergibt sich aus den Anfangsbuchstaben der drei Wissenschaftler …   Deutsch Wikipedia

Share the article and excerpts

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