Algoritmo de Berlekamp-Massey

El algoritmo de Berlekamp-Massey es un algoritmo que encuentra el registro de desplazamiento con retroalimentación lineal (LFSR) más corto para una secuencia de salida binaria dada. El algoritmo también encuentra el polinomio mínimo de una secuencia recurrente lineal en un campo arbitrario . El requisito del campo significa que el algoritmo de Berlekamp-Massey requiere que todos los elementos no nulos tengan un inverso multiplicativo . ^{[ 1 ]} Reeds y Sloane ofrecen una extensión para manejar un anillo . ^{[ 2 ]}

Shojiro Sakata extendió el algoritmo de Berlekamp-Massey a matrices multidimensionales; ^{[ 3 ]} el algoritmo resultante de Berlekamp-Massey-Sakata (BMS) se utiliza para decodificar algunos códigos de geometría algebraica , incluidos códigos de geometría algebraica de un punto, y se han desarrollado variantes para códigos multipunto a partir de curvas algebraicas. ^{[ 4 ]}

Elwyn Berlekamp inventó un algoritmo para decodificar códigos Bose-Chaudhuri-Hocquenghem (BCH) . ^{[ 5 ] [ 6 ]} James Massey reconoció su aplicación a los registros de desplazamiento con retroalimentación lineal y simplificó el algoritmo. ^{[ 7 ] [ 8 ]} Massey denominó al algoritmo Algoritmo de síntesis LFSR (Algoritmo iterativo de Berlekamp), ^{[ 9 ]} pero ahora se le conoce como el algoritmo de Berlekamp-Massey.

El algoritmo de Berlekamp-Massey es una alternativa al decodificador de 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 una secuencia 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 que se muestran a continuación, C ( x ) es una instancia potencial de Λ ( x ). El polinomio localizador de errores C ( x ) para L errores 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 al revés:

${\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 del último C ( x ) desde que L se actualizó y se inicializó a 1. b es una copia de la última discrepancia d (explicada más adelante) desde que L se actualizó y se inicializó a 1. m es el número de iteraciones desde que L , B ( x ) y b se actualizaron y se inicializaron a 1.

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

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

Si d es cero, el algoritmo asume que C ( x ) y L son correctos por el momento, incrementa m y continúa.

Si d no es cero, el algoritmo ajusta C ( x ) de modo que un recálculo de d sea cero:

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

El término x ^m ​​desplaza B(x) de modo que siga los síndromes correspondientes a b . 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\gets 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 incrementar L (número de errores) según sea necesario. Si L es igual al número real de errores, entonces durante el proceso de iteración, las discrepancias se convertirán en cero antes de que n sea mayor o igual a 2 L. De lo contrario, L se actualiza y el algoritmo actualizará B ( x ), b , incrementará L y restablecerá m = 1. La fórmula L = ( n + 1 − L ) limita L al número de síndromes disponibles utilizados para calcular las discrepancias, y también maneja el caso en que L aumenta en más de 1.

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

 polinomio(campo K ) s(x) = ... /* los coeficientes son s j ; secuencia de salida como polinomio de grado N-1) */ /* polinomio de conexión */ polinomio(campo K) C(x) = 1; /* los coeficientes son c j */ polinomio(campo K) B(x) = 1; entero L = 0; entero m = 1; campo K b = 1; entero n; /* pasos 2 y 6 */ para (n = 0; n < N; n++) { /* paso 2. calcular la discrepancia */ campo K d = s n + ∑ L i=1 c i s n - iSi (d == 0) { /* paso 3. La discrepancia es cero; la aniquilación continúa */ m = m + 1; } else if (2 * L <= n) { /* paso 5. */ /* copia temporal de C(x) */ polinomio(campo K) T(x) = C(x); C(x) = C(x) - db −1 x m B(x); L = n + 1 - L; B(x) = T(x); b = d; m = 1; } else { /* paso 4. */ C(x) = C(x) - db −1 x m B(x); m = m + 1; } } devolver L;

En el caso del código BCH GF(2) binario, 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 ++ ) { /* si el número de pasos es impar, la discrepancia es igual a 0, no es necesario calcularla */ if (( n & 1 ) != 0 ) { m = m + 1 ; continue ; } /* ... */

• Corrección de errores de Reed-Solomon
• Algoritmo de Reeds-Sloane , una extensión para secuencias sobre enteros módulo n 
• Registro de desplazamiento con retroalimentación no lineal (NLFSR)

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