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. [1] Reeds y Sloane ofrecen una extensión para manejar un anillo . [2]
Elwyn Berlekamp inventó un algoritmo para decodificar códigos Bose – Chaudhuri – Hocquenghem (BCH) . [3] [4] James Massey reconoció su aplicación a los registros de desplazamiento de retroalimentación lineal y simplificó el algoritmo. [5] [6] Massey denominó al algoritmo algoritmo de síntesis LFSR (algoritmo iterativo de Berlekamp), [7] 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 :
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:
o invertido:
El objetivo del algoritmo es determinar el grado mínimo L y C ( x ) que resulta en todos los síndromes.
siendo igual a 0:
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:
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:
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:
Esto cambiaría una discrepancia recalculada a:
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 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:
polinomio ( campo K ) s ( x ) = ... / * los coeficientes son s_j; secuencia de salida como polinomio de N-1 grado) * / / * polinomio de conexión * / polinomio ( campo K ) C ( x ) = 1 ; / * los coeficientes son c_j * / polinomio ( campo K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; campo K b = 1 ; int n ; / * pasos 2. y 6. * / para ( n = 0 ; n < N ; n ++ ) { / * paso 2. calcular la discrepancia * / campo K d = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i }; if ( d == 0 ) { / * paso 3. la discrepancia es cero; la aniquilación continúa * / m = m + 1 ; } Demás si ( 2 * L <= n ) { / * el paso 5. * / / * copia temporal de C (x) * / polinomio ( campo K ) T ( x ) = C ( x ); C ( x ) = C ( x ) - re segundo ^ { -1 } x ^ m B ( x ); L = n + 1 - L ; B ( x ) = T ( x ); b = d ; m = 1 ; } más { / * paso 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 ++ ) { / * si número de paso impar, discrepancia == 0, no es necesario calcularlo * / if (( n & 1 ) ! = 0 ) { m = m + 1 ; continuar ; } / * ... * /
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
- ^ Reeds y Sloane 1985 , p. 2
- ^ Cañas, JA; Sloane, NJA (1985), "Shift-Register Synthesis (Modulo n)" (PDF) , SIAM Journal on Computing , 14 (3): 505–513, CiteSeerX 10.1.1.48.4652 , doi : 10.1137 / 0214038
- ^ Berlekamp, Elwyn R. (1967), decodificación BCH no binaria , Simposio internacional sobre teoría de la información, San Remo, Italia
- ^ Berlekamp, Elwyn R. (1984) [1968], Teoría de la codificación algebraica (edición revisada), Laguna Hills, CA: Aegean Park Press, ISBN 978-0-89412-063-3. Editorial anterior McGraw-Hill, Nueva York, NY.
- ^ Massey, JL (enero de 1969), "Síntesis de registro de desplazamiento y decodificación BCH" (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122-127, doi : 10.1109 / TIT.1969.1054260
- ^ Ben Atti, Nadia; Díaz-Toca, Gema M .; Lombardi, Henri (abril de 2006), "The Berlekamp-Massey Algorithm revisited" , Álgebra aplicable en ingeniería, comunicación y computación , 17 (1): 75–82, CiteSeerX 10.1.1.96.2743 , doi : 10.1007 / s00200-005- 0190-z
- ↑ Massey , 1969 , p. 124
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