Algoritmo de Forney

En teoría de codificación , el algoritmo de Forney (o 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

Es necesario introducir la terminología y la configuración...

Las palabras clave parecen polinomios. Por diseño, el polinomio generador tiene raíces consecutivas α ^c , α ^{c +1} , ..., α ^{c + d −2} .

Síndromes

Polinomio de localización de error ^[2]

${\displaystyle \Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}}$

Los ceros de Λ( x ) son X ₁ ⁻¹ , ..., X _ν ⁻¹ . Los ceros son los recíprocos de las ubicaciones de error . ${\displaystyle X_{j}=\alpha ^{i_{j}}}$

Una vez que se conocen las ubicaciones de los errores, el siguiente paso es determinar los valores de error en esas ubicaciones. Los valores de error se utilizan para corregir los valores recibidos en esas ubicaciones y recuperar la palabra clave original.

En el caso más general, los pesos de error e _j se pueden determinar resolviendo el sistema lineal

${\displaystyle s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,}$

${\displaystyle s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,}$

${\displaystyle \cdots \,}$

Sin embargo, existe un método más eficiente conocido como algoritmo de Forney, que se basa en la interpolación de Lagrange . Primero se calcula el polinomio evaluador de errores ^[3]

${\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}\,}$

Donde S ( x ) es el polinomio del síndrome parcial: ^[4]

${\displaystyle S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{2t-1}x^{2t-1}.}$

Luego evalúa los valores de error: ^[3]

${\displaystyle e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}$

El valor c suele denominarse "primera raíz consecutiva" o "fcr". Algunos códigos seleccionan c = 1 , por lo que la expresión se simplifica a:

${\displaystyle e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}}$

Derivada formal

Λ'( x ) es la derivada formal del polinomio localizador de errores Λ( x ): ^[3]

${\displaystyle \Lambda '(x)=\sum _{i=1}^{\nu }i\,\cdot \,\lambda _{i}\,x^{i-1}}$

En la expresión anterior, observe que i es un entero y λ _i sería un elemento del cuerpo finito. El operador ⋅ representa la multiplicación ordinaria (suma repetida en el cuerpo finito) que es el mismo que el operador de multiplicación del cuerpo finito, es decir

${\displaystyle i\lambda =(1+\ldots +1)\lambda =\lambda +\ldots +\lambda .}$

Por ejemplo, en la característica 2, según que i sea par o impar. ${\displaystyle i\lambda =0,\lambda }$

Derivación

Interpolación de Lagrange

Gill (sin fecha, págs. 52-54) ofrece una derivación del algoritmo de Forney.

Borrados

Definir el polinomio localizador de borrado

${\displaystyle \Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})}$

Donde las posiciones de borrado están dadas por j _i . Aplique el procedimiento descrito anteriormente, sustituyendo Γ por Λ.

Si hay errores y borrados, utilice el polinomio localizador de errores y borrados.

${\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}$

Véase también

• Código BCH
• Corrección de errores de Reed-Solomon

Referencias

1. Forney 1965
2. Gill sin fecha, pág. 24
3. Gill sin fecha, pág. 47
4. Gill (sin fecha, pág. 48)

• Forney, G. (octubre de 1965), "Sobre la decodificación de códigos BCH", IEEE Transactions on Information Theory , 11 (4): 549–557, doi :10.1109/TIT.1965.1053825, ISSN  0018-9448
• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, pp. 42–45, archivado desde el original (PDF) el 30 de junio de 2014 , consultado el 21 de abril de 2010
• El libro de W. Wesley Peterson