Berlekamp-Massey-Algorithmus

Der Berlekamp-Massey-Algorithmus 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. Das Verfahren wurde von 1968 bis 1969 von Elwyn Berlekamp und James Massey entwickelt.[1][2] Anwendungen liegen im Bereich der effizienten Decodierung von BCH-Codes und Untergruppen wie den Reed-Solomon-Codes.

VorbemerkungenBearbeiten

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

 

bestimmt. Dabei bezeichnen   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

 

beschrieben werden.

Ziel des Berlekamp-Massey-Algorithmus ist es also, zu einer gegebenen Folge   von Symbolen das Rückkopplungspolynom   und die Länge   des erzeugenden Schieberegisters zu finden.

Einfaches BeispielBearbeiten

Der Einfachheit halber betrachten wir den binären Fall, also einen Körper mit lediglich zwei Elementen:   . Die Addition ist wie folgt definiert:   und   und kann mit einem XOR-Gatter realisiert werden. Für die Multiplikation gilt   und  , 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:

 

Das Rückkopplungspolynom lautet für dieses Beispiel   und die Länge des Schieberegisters ist  .

AlgorithmusBearbeiten

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

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

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   des Schieberegisters und der Anzahl   verarbeiteter Symbole ab. Im Falle einer Diskrepanz gilt für die neue Länge:  .

Für den binären Fall lässt sich der Algorithmus deutlich vereinfachen. In diesem Fall stammen die Eingangsymbole  , die Rückkopplungskoeffizienten   und die Diskrepanz   aus der Menge  . Aus   folgt also sofort   und  .

AnwendungenBearbeiten

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.

LiteraturBearbeiten

  • 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).
  • Elwyn R. Berlekamp: Algebraic Coding Theory. 2. Auflage. Aegean Park Press, 1984, ISBN 0-89412-063-8 (1. Auflage erschienen 1968 bei McGraw-Hill).

EinzelnachweiseBearbeiten

  1. Elwyn R. Berlekamp: Nonbinary BCH Decoding. In: IEEE transactions on information theory. Band 14, 1968, ISSN 0018-9448, S. 242.
  2. James L. Massey: Shift-Register Synthesis and BCH Decoding. In: IEEE transactions on information theory. Band 15, Nr. 1, 1969, ISSN 0018-9448, S. 122–127.

WeblinksBearbeiten