Algoritmo de Berlekamp-Massey - Berlekamp–Massey algorithm

El algoritmo de Berlekamp-Massey es un algoritmo que encontrará el registro de desplazamiento de retroalimentación lineal (LFSR) más corto para una secuencia de salida binaria dada. El algoritmo también encontrará el polinomio mínimo de una secuencia linealmente recurrente en un campo arbitrario . El requisito de campo significa que el algoritmo de Berlekamp-Massey requiere que todos los elementos distintos de cero tengan un inverso multiplicativo. Reeds y Sloane ofrecen una extensión para manejar un anillo .

Elwyn Berlekamp inventó un algoritmo para decodificar códigos Bose – Chaudhuri – Hocquenghem (BCH) . James Massey reconoció su aplicación a los registros de desplazamiento de retroalimentación lineal y simplificó el algoritmo. Massey denominó al algoritmo algoritmo de síntesis LFSR (algoritmo iterativo de Berlekamp), pero ahora se lo conoce como algoritmo de Berlekamp-Massey.

Descripción del algoritmo

El algoritmo de Berlekamp-Massey es una alternativa al decodificador Reed-Solomon Peterson para resolver el conjunto de ecuaciones lineales. Se puede resumir como encontrar los coeficientes Λ _j de un polinomio Λ ( x ) de modo que para todas las posiciones i en un flujo de entrada S :

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

En los ejemplos de código a continuación, C ( x ) es una instancia potencial de Λ ( x ). El polinomio localizador de errores C ( x ) para errores L se define como:

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

o invertido:

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

El objetivo del algoritmo es determinar el grado mínimo L y C ( x ) que resulta en todos los síndromes.

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

siendo igual a 0:

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

Algoritmo: C ( x ) se inicializa a 1, L es el número actual de errores asumidos y se inicializa a cero. N es el número total de síndromes. n se utiliza como iterador principal y para indexar los síndromes de 0 a N −1. B ( x ) es una copia de la última C ( x ) desde que L se actualizó e inicializó en 1. b es una copia de la última discrepancia d (explicada a continuación) desde que L se actualizó e inicializó en 1. m es el número de iteraciones desde que L , B ( x ) yb se actualizaron e inicializaron a 1.

Cada iteración del algoritmo calcula una discrepancia d . En la iteración k esto sería:

${\ Displaystyle d \ obtiene S_ {k} + C_ {1} S_ {k-1} + \ cdots + C_ {L} S_ {kL}.}$

Si d es cero, el algoritmo supone que C ( x ) y L son correctos para el momento, incrementa my continúa.

Si d no es cero, el algoritmo ajusta C ( x ) para que un nuevo cálculo de d sea ​​cero:

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

El término x ^m desplaza B (x) por lo que sigue los síndromes correspondientes ab . Si la actualización anterior de L ocurrió en la iteración j , entonces m = k - j , y una discrepancia recalculada sería:

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

Esto cambiaría una discrepancia recalculada a:

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

El algoritmo también necesita aumentar L (número de errores) según sea necesario. Si L es igual al número real de errores, a continuación, durante el proceso de iteración, las discrepancias se convertirá en cero antes de que n se hace mayor que o igual a 2 l . De lo contrario, L se actualiza y el algoritmo actualizará B ( x ), b , aumentará L y restablecerá m = 1. La fórmula L = ( n + 1 - L ) limita L al número de síndromes disponibles que se utilizan para calcular las discrepancias, y también maneja el caso donde L aumenta en más de 1.

Muestra de código

El algoritmo de Massey (1969 , p. 124) para un campo arbitrario:

  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;

En el caso del código BCH binario GF (2), la discrepancia d será cero en todos los pasos impares, por lo que se puede agregar una verificación para evitar calcularla.

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

Ver también

• Corrección de errores de Reed-Solomon
• Algoritmo Reeds-Sloane , una extensión para secuencias sobre números enteros mod  n
• NLFSR , registro de desplazamiento de retroalimentación no lineal

Referencias

enlaces externos

• "Algoritmo de Berlekamp-Massey" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Algoritmo de Berlekamp-Massey en PlanetMath .
• Weisstein, Eric W. "Algoritmo de Berlekamp-Massey" . MathWorld .
• Implementación de GF (2) en Mathematica
• (en alemán) algoritmo Applet Berlekamp – Massey
• Calculadora en línea GF (2) Berlekamp-Massey