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 determinada. El algoritmo también encontrará el polinomio mínimo de una secuencia lineal 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 registros de desplazamiento de retroalimentación lineal y simplificó el algoritmo. ^{[5] [6]} Massey denominó al algoritmo Algoritmo de síntesis LFSR (Algoritmo iterativo Berlekamp), ^[7] pero ahora se conoce como algoritmo Berlekamp-Massey.

Descripción del algoritmo

El algoritmo 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 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 en 1, L es el número actual de errores asumidos y se inicializa en 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 las iteraciones desde 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 ) para que un nuevo cá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) por lo que sigue 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=d-d=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, entonces , durante el proceso de iteración, las discrepancias serán 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 las discrepancias, y también maneja el caso donde L aumenta en más de 1.

Pseudocó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 ; entero L = 0 ; int metro = 1 ; campo K b = 1 ; int norte ;                         /* pasos 2. y 6. */ for ( n = 0 ; n < N ; n ++ ) { /* paso 2. calcular la 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 = norte + 1 - L ; B ( x ) = T ( x ); segundo = re ; metro = 1 ; } else { /* paso 4. */ C ( x ) = C ( x ) - d B ( x ); metro = metro + 1 ; } } devolver 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, discrepancia == 0, no es necesario calcularlo */ if (( n & 1 ) != 0 ) { metro = metro + 1 ; continuar ; } /* ... */                     

Ver 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 de 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), Decodificació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. Editor anterior McGraw-Hill, Nueva York, NY.
5. 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, S2CID  9003708
6. 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 e informática , 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, pag. 124

enlaces externos

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