Berlekamp-Massey Algorithmus
Der Berlekamp-Massey Algorithmus ist ein effizienter Algorithmus zum Finden des kürzesten linearen rückgekoppelten Schieberegisters
(in Englisch: linear feedback shift register (LFSR)) für eine gegebene Ausgangssequenz.
Der Algorithmus wurde im Jahre 1968 von Elwyn Berlekamp entwickelt. Ein Jahr darauf wurde die Verbindung
zu den linearen Blockcodes von James Massey beobachtet.
Heute wird er zur Dekodierung des Reed-Solomon-Codes verwendet.
Folgender Pseudocode zeigt die Funktionsweise des verwendeten Algorithmus auf:
Das Applet besteht aus fünf Panels.
Im Eingabe-/Steuerungspanel können Sie die gewünschte Ausgangssequenz in binären Zahlen eingeben, und durch drücken des OK-Knopfes wird Ihre Einabe bestätigt. Anschliessend können Sie mit den Schaltflächen auf diesem Panel das ganze Applet steuern.
Das Panel Lineares Schieberegister zeigt die bis zu diesem Rechnungsschritt berechneten linearen Schieberegister an. Zusätzlich können Sie sich durch drücken von Prüfen die momentane Ausgangssequenz anzeigen lassen.
Die Tabelle zeigt ihnen jeden einzelnen der schon durchgeführten Schritte an. Und durch ein Doppelklick auf eine bestimmte Zeile können Sie sich einen bereits gerechneten und angezeigten Schritt nochmals anzeigen lassen.
Die Entwicklung der linearen Komplexität kann auch graphisch dargestellt werden wie Sie dem Graphenpanel entnehmen können.
Das Flussdiagramm beschreibt den genauen Programmablauf. Der grüne Pfad zeigt Ihnen den genauen Weg der Entscheidungen und Berechnungen an.