Algorithme de Berlekamp – Massey - Berlekamp–Massey algorithm

L' algorithme de Berlekamp – Massey est un algorithme qui trouvera le registre à décalage à rétroaction linéaire (LFSR) le plus court pour une séquence de sortie binaire donnée. L'algorithme trouvera également le polynôme minimal d'une séquence linéairement récurrente dans un champ arbitraire . L'exigence de champ signifie que l'algorithme de Berlekamp – Massey exige que tous les éléments non nuls aient un inverse multiplicatif. Reeds et Sloane offrent une extension pour manipuler un anneau .

Elwyn Berlekamp a inventé un algorithme de décodage des codes Bose – Chaudhuri – Hocquenghem (BCH) . James Massey a reconnu son application aux registres à décalage à rétroaction linéaire et a simplifié l'algorithme. Massey a appelé l'algorithme l'algorithme de synthèse LFSR (algorithme itératif de Berlekamp), mais il est maintenant connu sous le nom d'algorithme de Berlekamp – Massey.

Description de l'algorithme

L'algorithme de Berlekamp – Massey est une alternative au décodeur Reed – Solomon Peterson pour résoudre l'ensemble des équations linéaires. Il peut se résumer à trouver les coefficients Λ _j d'un polynôme Λ ( x ) de sorte que pour toutes les positions i dans un flux d'entrée S :

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

Dans les exemples de code ci-dessous, C ( x ) est une instance potentielle de Λ ( x ). Le polynôme de localisation d'erreur C ( x ) pour les erreurs L est défini comme suit:

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

ou inversé:

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

Le but de l'algorithme est de déterminer le degré minimal L et C ( x ) qui aboutit à tous les syndromes

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

étant égal à 0:

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

Algorithme: C ( x ) est initialisé à 1, L est le nombre actuel d'erreurs supposées et initialisé à zéro. N est le nombre total de syndromes. n est utilisé comme itérateur principal et pour indexer les syndromes de 0 à N −1. B ( x ) est une copie du dernier C ( x ) depuis que L a été mis à jour et initialisé à 1. b est une copie du dernier écart d (expliqué ci-dessous) depuis que L a été mis à jour et initialisé à 1. m est le nombre de les itérations depuis L , B ( x ) et b ont été mises à jour et initialisées à 1.

Chaque itération de l'algorithme calcule un écart d . À l'itération k, ce serait:

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

Si d est zéro, l'algorithme suppose que C ( x ) et L sont corrects pour le moment, incrémente m et continue.

Si d n'est pas égal à zéro, l'algorithme ajuste C ( x ) pour qu'un recalcul de d soit nul:

${\ Displaystyle C (x) \ obtient C (x) - (d / b) x ^ {m} B (x).}$

Le terme x ^m décale B (x) pour suivre les syndromes correspondant à b . Si la mise à jour précédente de L se produisait à l'itération j , alors m = k - j , et un écart recalculé serait:

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

Cela changerait un écart recalculé en:

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

L'algorithme doit également augmenter L (nombre d'erreurs) si nécessaire. Si L est égal au nombre réel d'erreurs, puis au cours du processus d'itération, les écarts deviendront zéro avant que n devient supérieure ou égale à 2 L . Sinon, L est mis à jour et l'algorithme mettra à jour B ( x ), b , augmentera L et réinitialisera m = 1. La formule L = ( n + 1 - L ) limite L au nombre de syndromes disponibles utilisé pour calculer les écarts, ainsi que gère le cas où L augmente de plus de 1.

Exemple de code

L'algorithme de Massey (1969 , p. 124) pour un champ arbitraire:

  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;

Dans le cas du code binaire GF (2) BCH, l'écart d sera nul sur tous les pas impairs, donc un contrôle peut être ajouté pour éviter de le calculer.

/* ... */
  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;
      }
/* ... */

Voir également

• Correction d'erreurs Reed – Solomon
• Algorithme Reeds – Sloane , une extension pour les séquences sur des entiers mod  n
• NLFSR , registre à décalage de rétroaction non linéaire

Les références

Liens externes

• "Algorithme de Berlekamp-Massey" , Encyclopédie de mathématiques , EMS Press , 2001 [1994]
• Algorithme de Berlekamp – Massey chez PlanetMath .
• Weisstein, Eric W. "Algorithme de Berlekamp – Massey" . MathWorld .
• Implémentation de GF (2) dans Mathematica
• (en allemand) Algorithme Applet Berlekamp – Massey
• Calculateur GF (2) Berlekamp-Massey en ligne