Algoritmo de Berlekamp-Massey

Algoritmo de Berlekamp-Massey

El algoritmo 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 del campo significa que el algoritmo 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 de 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 el algoritmo 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. Puede resumirse como la búsqueda de 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 siguientes, 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_{n-L}}$

siendo igual a 0:

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=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ó e inicializó a 1. b es una copia de la última discrepancia d (explicada a continuación) desde que L se actualizó e inicializó a 1. m es el número de iteraciones desde que L , B ( x ) y b 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\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}$

Si d es cero, el algoritmo supone 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 sigue los síndromes correspondientes a b . Si la actualización anterior de L se produjo 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=d-d=0.}$

El algoritmo también debe aumentar 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 , aumentará L y restablecerá m = 1. La fórmula L = ( n + 1 − L ) limita L al número de síndromes disponibles utilizados para calcular discrepancias, y también maneja el caso donde L aumenta en más de 1.

Pseudocódigo

El algoritmo de Massey (1969, pág. 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 ; int L = 0 ; int m = 1 ; campo K b = 1 ; int n ;                         /* pasos 2. y 6. */ for ( n = 0 ; n < N ; n ++ ) { /* paso 2. calcular discrepancia */ campo K d = s_n + ;                 ${\displaystyle \sum _{i=1}^{L}c_{i}\cdot s_{n-i}}$ if ( 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 ) - d B ( x ); L = n + 1 - L ; B ( x ) = T ( x ); b = d ; m = 1 ; } else { /* paso 4. */ C ( x ) = C ( x ) - d B ( x ); m = m + 1 ; } } return L ;      ${\displaystyle b^{-1}x^{m}}$                            ${\displaystyle b^{-1}x^{m}}$        

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

Véase también

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

Referencias

1. Reeds y Sloane 1985, pág. 2
2. Cañas, JA; Sloane, NJA (1985), "Síntesis de registro de desplazamiento (módulo n)" (PDF) , SIAM Journal on Computing , 14 (3): 505–513, CiteSeerX  10.1.1.48.4652 , doi :10.1137/0214038
3. Berlekamp, ​​Elwyn R. (1967), Descodificación BCH no binaria , Simposio internacional sobre teoría de la información, San Remo, Italia{{citation}}: CS1 maint: location missing publisher (link)
4. 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.
5. Massey, JL (enero de 1969), "Síntesis de registros de desplazamiento y decodificación BCH" (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122–127, doi :10.1109/TIT.1969.1054260, S2CID  9003708
6. Ben Atti, Nadia; Diaz-Toca, Gema M.; Lombardi, Henri (abril de 2006), "El algoritmo Berlekamp–Massey revisado", Álgebra aplicable en ingeniería, comunicación y computación , 17 (1): 75–82, arXiv : 2211.11721 , CiteSeerX 10.1.1.96.2743 , doi :10.1007/s00200-005-0190-z, S2CID  14944277 
7. Massey 1969, pág. 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 de Berlekamp–Massey de Applet
• Calculadora Berlekamp-Massey GF(2) en línea