Algoritmo de Berlekamp-Massey

El algoritmo Berlekamp-Massey es un algoritmo para encontrar el registro de desplazamiento más corto con retroalimentación lineal para una secuencia binaria dada como entrada. El algoritmo también le permite encontrar el polinomio mínimo de la secuencia recurrente lineal de entrada sobre un campo arbitrario .

El algoritmo fue descubierto por Alvin Berlekamp en 1968 [1] . James Massey encontró una aplicación del algoritmo a los códigos lineales al año siguiente [2] . Esto se convirtió en la clave para la aplicación práctica de los códigos Reed-Solomon .

Descripción del algoritmo

Algoritmo B.M. es un método alternativo para resolver SLAE, que se puede describir de la siguiente manera:

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) representa Λ(x). El localizador de errores C(x) para errores L se define como:

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:

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

El propósito del algoritmo es determinar el mínimo L y el correspondiente C(x), lo que da errores en todo el síndrome.

{\displaystyle S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{nL))

resultando en cero:

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 en 1, L denota el número actual de errores encontrados hasta el momento y se inicializa en cero. N es el número total de elementos del síndrome de error. n es el contador principal, también es el índice de los elementos del síndrome de 0 a ( N -1). B(x) es una copia de la última C(x) en el momento de actualizar L , y se inicializa en 1. b es una copia de la última discrepancia d (ver más abajo), nuevamente, en el momento de actualizar L y se inicializa en 1. m es el número de iteraciones que han pasado desde la actualización L , B(x) yb y también se inicializa en uno.

En cada iteración, se calcula la discrepancia d . En la iteración k-ésima será:

d=S_{k}+C_{1}\ S_{k-1}+\cdots +C_{L}\ S_{kL}.

Si d es cero, significa que C(x) y L son correctos por ahora, es suficiente para incrementar m y continuar con la iteración.

Si d no es cero, el algoritmo corrige C(x) para establecer d en cero :

C(x)=C(x)\ -\ (d/b)\ x^{m}\ B(x).

Multiplicar por x m es esencialmente un cambio de los coeficientes B(x) por m, es decir, cada coeficiente tiene lugar m más alto para coincidir con el síndrome de b . Si la última vez que L se actualizó en la iteración j (y ahora tenemos la k-ésima iteración), entonces m = k - j , y la discrepancia recalculada es:

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

Es decir, sustituyendo, vemos que se anula:

d=d-(d/b)b=dd=0.\

Además, el valor de L (el número de errores encontrados) a veces necesita ser corregido. Si L es igual al número real de símbolos erróneos, entonces, en el curso de las iteraciones, las discrepancias se pondrán a cero antes de que n sea mayor o igual a (2 L ). De lo contrario, L se actualiza y el algoritmo actualiza B(x), b, L mismo (incrementos) y m se restablece a 1. La expresión L = (n + 1 - L) limita L al número de elementos de síndrome disponibles utilizados para calcular las discrepancias, y al mismo tiempo resuelve el problema de aumentar L en más de uno.

Código de ejemplo

Algoritmo de Massey (1969 , p. 124):

polinomio ( campo K ) s ( x ) = ... /* los coeficientes son s_j; secuencia de salida como polinomio de grado N-1) */ /* polinomio de conexion */ polinomio ( campo K ) C ( x ) = 1 ; /* los coeficientes son c_j */ polinomio ( campo K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; campo Kb = 1 ; _ intn ; _ /* 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 }; si ( re == 0 ) { /* paso 3. la discrepancia es cero; la aniquilación continúa */ metro = metro + 1 _ } si no ( 2 * L <= n ) { /* paso 5. */ /* copia temporal de C(x) */ polinomio ( campo K ) T ( x ) = C ( x ); do ( x ) = do ( x ) - re segundo ^ { -1 } x ^ metro segundo ( x ); L = norte + 1 - L ; B ( x ) = T ( x ); segundo = re ; metro = 1 ; } más { /* paso 4. */ do ( x ) = do ( x ) - re segundo ^ { -1 } x ^ metro segundo ( x ); metro = metro + 1 _ } } devolver L ;

Algoritmo para sucesiones binarias

Establezca la secuencia de bits requerida . ${\displaystyle s_{0},s_{1},...,s_{n-1))$
Crear matrices , longitudes , establecer valores iniciales , , , , . $b$ $t$ $C$ $norte$ $b_{0}\flecha izquierda 1$ $c_{0}\flecha izquierda 1$ ${\ estilo de visualización N \ flecha izquierda 0}$ ${\ estilo de visualización L \ flecha izquierda 0}$ ${\ estilo de visualización m \ flecha izquierda -1}$
Adiós : ${\ estilo de visualización N < n}$
1. Calcula _ ${\displaystyle d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{NL))$
2. Si , entonces la función actual genera la sección seleccionada de la secuencia; dejar la función igual. $re=0$ ${\displaystyle s_{NL},s_{N-L+1},...,s_{N))$
3. Si : $d\not=0$
  - Guarde una copia de la matriz en formato . $C$ $t$
  - Calcula nuevos valores . $c_{Nm}\leftarrow c_{Nm}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},...,c_ {n-1}\leftarrow c_{n-1}\oplus b_{n-N+m-1}$
  - Si , establezca valores y copie en . $2L\leqslant N$ ${\ estilo de visualización L \ flecha izquierda N + 1-L}$ ${\ estilo de visualización m \ flecha izquierda N}$ $t$ $b$
4. ${\ estilo de visualización N \ flecha izquierda N + 1}$ .
Como resultado, la matriz es una función de retroalimentación, es decir, para cualquier . $C$ $c_{L}s_{i}\oplus c_{L-1}s_{i+1}\oplus c_{L-2}s_{i+2}\oplus ...\oplus c_{0} s_{i+L}=0$ $i$

Notas

↑ Elwyn R. Berlekamp , Teoría de la codificación algebraica, Nueva York: McGraw-Hill, 1968. Edición revisada, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
↑ JL Massey , Síntesis de registro de desplazamiento y decodificación BCH . Archivado el 27 de septiembre de 2011 en Wayback Machine , IEEE Trans. Teoría de la información, IT-15 (1969), 122-127.

Literatura

Blahut R. Teoría y práctica de los códigos de control de errores. — M .: Mir , 1986. — 576 p.
VL Kurakin, AS Kuzmin, AV Mikhalev, AA Nechaev. Secuencias lineales recurrentes sobre anillos y módulos. // I. de Matemáticas. Ciencias. Matemáticas Contemporáneas. y es Appl. Encuestas temáticas, vol. 10, 1994, I. de Matemáticas. Ciencias, vol. 76, No. 6, 1995. MR : 1365809

Enlaces

Algoritmo de Berlekamp-Massey (inglés) en el sitio web de PlanetMath .
Weisstein, Eric W. Berlekamp-Massey Algoritmo - MathWorld .

Implementación

Implementación en línea de algoritmos Reed-Sloane y Berlekamp-Massey sobre GF(P) (enlace no disponible) en SignalsLab
Implementación de GF(2 ) en Mathematica