Berlekamp-Massey-Algorithmus - Berlekamp–Massey algorithm

Der Berlekamp-Massey-Algorithmus ist ein Algorithmus , der das kürzeste lineare Rückkopplungsschieberegister (LFSR) für eine bestimmte binäre Ausgangssequenz findet. Der Algorithmus findet auch das minimale Polynom einer linear wiederkehrenden Sequenz in einem beliebigen Feld . Die Feldanforderung bedeutet, dass der Berlekamp-Massey-Algorithmus erfordert, dass alle Nicht-Null-Elemente eine multiplikative Inverse haben. Reeds und Sloane bieten eine Erweiterung für einen Ring an .

Elwyn Berlekamp erfand einen Algorithmus zum Decodieren von Bose-Chaudhuri-Hocquenghem-Codes (BCH) . James Massey erkannte seine Anwendung auf lineare Rückkopplungsschieberegister und vereinfachte den Algorithmus. Massey nannte den Algorithmus den LFSR-Synthesealgorithmus (Berlekamp Iterative Algorithm), aber er ist jetzt als Berlekamp-Massey-Algorithmus bekannt.

Beschreibung des Algorithmus

Der Berlekamp-Massey-Algorithmus ist eine Alternative zum Reed-Solomon-Peterson-Decoder zur Lösung des Satzes linearer Gleichungen. Es kann zusammengefasst werden, indem die Koeffizienten Λ _j eines Polynoms Λ ( x ) gefunden werden, so dass für alle Positionen i in einem Eingangsstrom S :

${\ displaystyle S_ {i + \ nu} + \ Lambda _ {1} S_ {i + \ nu -1} + \ cdots + \ Lambda _ {\ nu -1} S_ {i + 1} + \ Lambda _ {\ nu } S_ {i} = 0.}$

In den folgenden Codebeispielen ist C ( x ) eine mögliche Instanz von Λ ( x ). Das Fehlerlokalisierungspolynom C ( x ) für L- Fehler ist definiert als:

${\ displaystyle C (x) = C_ {L} x ^ {L} + C_ {L-1} x ^ {L-1} + \ cdots + C_ {2} x ^ {2} + C_ {1} x +1}$

oder umgekehrt:

${\ Anzeigestil C (x) = 1 + C_ {1} x + C_ {2} x ^ {2} + \ cdots + C_ {L-1} x ^ {L-1} + C_ {L} x ^ { L}.}$

Das Ziel des Algorithmus ist es, den minimalen Grad L und C ( x ) zu bestimmen, der zu allen Syndromen führt

${\ displaystyle S_ {n} + C_ {1} S_ {n-1} + \ cdots + C_ {L} S_ {nL}}$

gleich 0 sein:

${\ displaystyle S_ {n} + C_ {1} S_ {n-1} + \ cdots + C_ {L} S_ {nL} = 0, \ qquad L \ leq n \ leq N-1.}$

Algorithmus: C ( x ) wird auf 1 initialisiert, L ist die aktuelle Anzahl angenommener Fehler und wird auf Null initialisiert. N ist die Gesamtzahl der Syndrome. n wird als Hauptiterator und zur Indizierung der Syndrome von 0 bis N −1 verwendet. B ( x ) ist eine Kopie des letzten C ( x ), seit L aktualisiert und auf 1 initialisiert wurde. B ist eine Kopie der letzten Diskrepanz d (unten erläutert), seit L aktualisiert und auf 1 initialisiert wurde. M ist die Anzahl von Iterationen seit L , B ( x ) und b wurden aktualisiert und auf 1 initialisiert.

Jede Iteration des Algorithmus berechnet eine Diskrepanz d . Bei Iteration k wäre dies:

${\ displaystyle d \ erhält S_ {k} + C_ {1} S_ {k-1} + \ cdots + C_ {L} S_ {kL}.}$

Wenn d Null ist, nimmt der Algorithmus an, dass C ( x ) und L für den Moment korrekt sind, erhöht m und fährt fort.

Wenn d nicht Null ist, passt der Algorithmus C ( x ) so an, dass eine Neuberechnung von d Null wäre:

${\ displaystyle C (x) \ erhält C (x) - (d / b) x ^ {m} B (x).}$

Der x ^m -Term verschiebt B (x) so, dass er den Syndromen folgt, die b entsprechen . Wenn die vorherige Aktualisierung von L bei Iteration j erfolgt , ist m = k - j und eine neu berechnete Diskrepanz wäre:

${\ displaystyle d \ erhält S_ {k} + C_ {1} S_ {k-1} + \ cdots - (d / b) (S_ {j} + B_ {1} S_ {j-1} + \ cdots) .}$

Dies würde eine neu berechnete Diskrepanz ändern in:

${\ displaystyle d = d- (d / b) b = dd = 0.}$

Der Algorithmus muss bei Bedarf auch L (Anzahl der Fehler) erhöhen . Wenn L gleich der tatsächlichen Anzahl von Fehlern ist, werden die Diskrepanzen während des Iterationsprozesses Null, bevor n größer oder gleich 2 L wird . Andernfalls wird L aktualisiert und der Algorithmus aktualisiert B ( x ), b , erhöht L und setzt m = 1 zurück. Die Formel L = ( n + 1 - L ) begrenzt L auf die Anzahl der verfügbaren Syndrome, die zur Berechnung von Diskrepanzen verwendet werden, und auch behandelt den Fall, in dem L um mehr als 1 erhöht wird.

Codebeispiel

Der Algorithmus von Massey (1969 , S. 124) für ein beliebiges Feld:

  polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */
  /* connection polynomial */
  polynomial(field K) C(x) = 1;  /* coeffs are c_j */
  polynomial(field K) B(x) = 1;
  int L = 0;
  int m = 1;
  field K b = 1;
  int n;

  /* steps 2. and 6. */
  for (n = 0; n < N; n++) {
      /* step 2. calculate discrepancy */
      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};

      if (d == 0) {
          /* step 3. discrepancy is zero; annihilation continues */
          m = m + 1;
      } else if (2 * L <= n) {
          /* step 5. */
          /* temporary copy of C(x) */
          polynomial(field K) T(x) = C(x);

          C(x) = C(x) - d b^{-1} x^m B(x);
          L = n + 1 - L;
          B(x) = T(x);
          b = d;
          m = 1;
      } else {
          /* step 4. */
          C(x) = C(x) - d b^{-1} x^m B(x);
          m = m + 1;
      }
  }
  return L;

Im Fall von binärem GF (2) BCH-Code ist die Diskrepanz d bei allen ungeraden Schritten Null, so dass eine Prüfung hinzugefügt werden kann, um eine Berechnung zu vermeiden.

/* ... */
  for (n = 0; n < N; n++) {
      /* if odd step number, discrepancy == 0, no need to calculate it */
      if ((n&1) != 0) {
          m = m + 1;
          continue;
      }
/* ... */

Siehe auch

• Reed-Solomon-Fehlerkorrektur
• Reeds-Sloane-Algorithmus , eine Erweiterung für Sequenzen über ganze Zahlen mod  n
• NLFSR , nichtlineares Rückkopplungsschieberegister

Verweise

Externe Links

• "Berlekamp-Massey-Algorithmus" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Berlekamp-Massey-Algorithmus bei PlanetMath .
• Weisstein, Eric W. "Berlekamp-Massey-Algorithmus" . MathWorld .
• Implementierung von GF (2) in Mathematica
• (in deutscher Sprache) Applet Berlekamp-Massey-Algorithmus
• Online GF (2) Berlekamp-Massey Rechner