En la teoría de la codificación , el algoritmo de Forney (o el algoritmo de Forney ) calcula los valores de error en ubicaciones de error conocidas. Se utiliza como uno de los pasos para decodificar códigos BCH y códigos Reed-Solomon (una subclase de códigos BCH). George David Forney Jr. desarrolló el algoritmo. [1]
Procedimiento
- Necesidad de introducir la terminología y la configuración ...
Las palabras de código parecen polinomios. Por diseño, el polinomio generador tiene raíces consecutivas α c , α c +1 , ..., α c + d −2 .
Síndromes
Polinomio de ubicación del error [2]
Los ceros de Λ ( x ) son X 1 −1 , ..., X ν −1 . Los ceros son los recíprocos de las ubicaciones de error.
Una vez que se conocen las ubicaciones de los errores, el siguiente paso es determinar los valores de error en esas ubicaciones. Luego, los valores de error se utilizan para corregir los valores recibidos en esas ubicaciones para recuperar la palabra de código original.
En el caso más general, los pesos de error e j se pueden determinar resolviendo el sistema lineal
Sin embargo, existe un método más eficiente conocido como algoritmo de Forney, que se basa en la interpolación de Lagrange . Primero calcule el polinomio del evaluador de errores [3]
Donde S ( x ) es el polinomio del síndrome parcial: [4]
Luego evalúe los valores de error: [3]
El valor c a menudo se denomina "primera raíz consecutiva" o "fcr". Algunos códigos seleccionan c = 1 , por lo que la expresión se simplifica a:
Derivado formal
Λ '( x ) es la derivada formal del polinomio del localizador de errores Λ ( x ): [3]
En la expresión anterior, tenga en cuenta que i es un número entero y λ i sería un elemento del campo finito. El operador · representa la multiplicación ordinaria (suma repetida en el campo finito) y no el operador de multiplicación del campo finito.
Derivación
Gill (nd , págs. 52-54) da una derivación del algoritmo de Forney.
Borrados
Definir el polinomio del localizador de borrado
Donde las ubicaciones de borrado vienen dadas por j i . Aplicar el procedimiento descrito anteriormente, sustituyendo Γ por Λ.
Si hay errores y borrados, utilice el polinomio localizador de errores y borrados.
Ver también
Referencias
- ↑ Forney, 1965
- ^ Gill nd , pág. 24
- ^ a b c Gill nd , pág. 47
- ↑ Gill (sin fecha , p. 48)
- Forney, G. (octubre de 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory , 11 (4): 549–557, doi : 10.1109 / TIT.1965.1053825 , ISSN 0018-9448
- Gill, John (sf), EE387 Notes # 7, Handout # 28 (PDF) , Stanford University, págs. 42–45, archivado del original (PDF) el 30 de junio de 2014 , consultado el 21 de abril de 2010
- Libro de W. Wesley Peterson