Corrección de errores de Reed-Solomon

En la construcción original de Reed y Solomon, el mensaje${\displaystyle m=(m_{0},\dots ,m_{k-1})\in F^{k}}$se asigna al polinomio${\displaystyle p_{m}}$con $${\displaystyle p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}=m_{0}+m_{1}a+m_{2}a^{2}+\cdots +m_{k-1}a^{k-1}}$$ La palabra clave de${\displaystyle m}$se obtiene mediante evaluación${\displaystyle p_{m}}$en${\displaystyle n}$diferentes puntos${\displaystyle a_{0},\dots ,a_{n-1}}$del campo${\displaystyle F}$. ^{[ 1 ]} Por lo tanto, la función de codificación clásica${\displaystyle C:F^{k}\to F^{n}}$El código Reed-Solomon se define de la siguiente manera: $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

Esta función${\displaystyle C}$es una aplicación lineal , es decir, satisface${\displaystyle C(m)=mA}$para lo siguiente${\displaystyle k\times n}$-matriz${\displaystyle A}$con elementos de${\displaystyle F}$.

$${\displaystyle C(m)=mA={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&1&1&\dots &1\\a_{0}&a_{1}&a_{2}&\dots &a_{n-1}\\a_{0}^{2}&a_{1}^{2}&a_{2}^{2}&\dots &a_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{0}^{k-1}&a_{1}^{k-1}&a_{2}^{k-1}&\dots &a_{n-1}^{k-1}\end{bmatrix}}}$$

Esta matriz es una matriz de Vandermonde sobre${\displaystyle F}$En otras palabras, el código Reed-Solomon es un código lineal y, en el procedimiento de codificación clásico, su matriz generadora es${\displaystyle A}$.

Existen procedimientos de codificación alternativos que producen un código Reed-Solomon sistemático . Un método utiliza la interpolación de Lagrange para calcular polinomios.${\displaystyle p_{m}}$de tal manera que$${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$Entonces${\displaystyle p_{m}}$se evalúa en los otros puntos${\displaystyle a_{k},\dots ,a_{n-1}}$.

$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

Esta función${\displaystyle C}$es una aplicación lineal. Para generar la matriz de codificación sistemática G correspondiente, multiplique la matriz A por la inversa de la submatriz cuadrada izquierda de A.

$${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

${\displaystyle C(m)=mG}$para lo siguiente${\displaystyle k\times n}$-matriz${\displaystyle G}$con elementos de${\displaystyle F}$. $${\displaystyle C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

Una transformada discreta de Fourier es esencialmente lo mismo que el procedimiento de codificación; utiliza el polinomio generador.${\displaystyle p_{m}}$para asignar un conjunto de puntos de evaluación a los valores del mensaje como se muestra arriba: $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

La transformada inversa de Fourier podría utilizarse para convertir un conjunto libre de errores de n < q valores de mensaje de nuevo en el polinomio de codificación de k coeficientes, con la restricción de que para que esto funcione, el conjunto de puntos de evaluación utilizados para codificar el mensaje debe ser un conjunto de potencias crecientes de α : $${\displaystyle a_{i}=\alpha ^{i}}$$$${\displaystyle a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$$

Sin embargo, la interpolación de Lagrange realiza la misma conversión sin la restricción del conjunto de puntos de evaluación o el requisito de un conjunto de valores de mensaje sin errores y se utiliza para la codificación sistemática, y en uno de los pasos del decodificador de Gao .

El remitente calcula un polinomio relacionado.${\displaystyle c(x)}$de grado${\displaystyle n-1}$dónde${\displaystyle n\leq q-1}$y envía el polinomio${\displaystyle c(x)}$. El polinomio${\displaystyle c(x)}$se construye multiplicando el polinomio del mensaje${\displaystyle m(x)}$, que tiene grado${\displaystyle k-1}$, con el polinomio generador${\displaystyle g(x)}$de grado${\displaystyle n-k}$que es conocido tanto por el remitente como por el receptor.${\displaystyle c(x)=m(x)g(x)}$.

Esta función${\displaystyle C}$es una aplicación lineal , es decir, satisface${\displaystyle C(m)=mA}$para lo siguiente${\displaystyle k\times n}$-matriz${\displaystyle A}$con elementos de${\displaystyle F}$.

$${\displaystyle A={\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

${\displaystyle C(m)=mA}$para lo siguiente${\displaystyle k\times n}$matriz${\displaystyle G}$con elementos de${\displaystyle F}$.

$${\displaystyle c(x)=mA={\begin{bmatrix}m_{k-1}&\cdots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

El procedimiento de codificación para la vista BCH de los códigos Reed-Solomon se puede modificar para producir un procedimiento de codificación sistemático , en el que cada palabra clave contiene el mensaje como prefijo y simplemente agrega símbolos de corrección de errores como sufijo. Aquí, en lugar de enviar${\displaystyle c(x)=m(x)g(x)}$, el codificador construye el polinomio transmitido${\displaystyle c(x)}$de tal manera que los coeficientes de la${\displaystyle k}$Los monomios más grandes son iguales a los coeficientes correspondientes de${\displaystyle m(x)}$y los coeficientes de orden inferior de${\displaystyle c(x)}$son elegidos de tal manera que${\displaystyle c(x)}$se vuelve exactamente divisible por${\displaystyle g(x)}$. Entonces los coeficientes de${\displaystyle m(x)}$son una subsecuencia de los coeficientes de${\displaystyle c(x)}$Para obtener un código que sea sistemático en general, construimos el polinomio del mensaje.${\displaystyle c(x)}$interpretando el mensaje como la secuencia de sus coeficientes.

Formalmente, la construcción se realiza mediante la multiplicación${\displaystyle c(x)}$por${\displaystyle x^{t}}$para dejar espacio para el${\displaystyle t=n-k}$símbolos de verificación, dividiendo ese producto por${\displaystyle g(x)}$para hallar el resto y luego compensar ese resto restándolo.${\displaystyle t}$Los símbolos de verificación se crean calculando el resto.${\displaystyle r(x)}$: $${\displaystyle r(x)=c(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$$

El resto tiene como máximo un grado${\displaystyle t-1}$, mientras que los coeficientes de${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$en el polinomio${\displaystyle c(x)\cdot x^{t}}$son cero. Por lo tanto, la siguiente definición de la palabra clave${\displaystyle c(x)}$tiene la propiedad de que el primero${\displaystyle k}$Los coeficientes son idénticos a los coeficientes de${\displaystyle c(x)}$: $${\displaystyle c(x)=m(x)\cdot x^{t}-r(x)\,.}$$

Como resultado,${\displaystyle c(x)}$es exactamente divisible por${\displaystyle g(x)}$: ^{[ 11 ]}

$${\displaystyle c(x)\equiv m(x)\cdot x^{t}-r(x)\equiv r(x)-r(x)\equiv 0\mod g(x)\,.}$$

Esta función${\displaystyle C}$es una función lineal. Para generar la matriz de codificación sistemática G correspondiente, multiplique la matriz A por la inversa de la submatriz cuadrada izquierda de A (o establezca la submatriz cuadrada izquierda de G como la matriz identidad y codifique cada fila).

$${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

${\displaystyle C(m)=mG}$para lo siguiente${\displaystyle k\times n}$matriz${\displaystyle G}$con elementos de${\displaystyle F}$.

$${\displaystyle c(x)=mG={\begin{bmatrix}m_{k-1}&\ldots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

El mensaje transmitido,${\displaystyle (c_{0},\ldots ,c_{i},\ldots ,c_{n-1})}$, se considera como los coeficientes de un polinomio $${\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.}$$

Como resultado del procedimiento de codificación de Reed-Solomon, s ( x ) es divisible por el polinomio generador. $${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$$ donde α es un elemento primitivo.

Dado que s ( x ) es un múltiplo del generador g ( x ), se deduce que "hereda" todas sus raíces: $${\displaystyle s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0.}$$ Por lo tanto, $${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k.}$$

El polinomio transmitido se corrompe durante la transmisión por un polinomio de error. $${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$$ para producir el polinomio recibido $${\displaystyle r(x)=s(x)+e(x).}$$

El coeficiente e _i será cero si no hay error en esa potencia de x , y distinto de cero si hay un error. Si hay ν errores en distintas potencias i _k de x , entonces $${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.}$$

El objetivo del decodificador es encontrar el número de errores ( _ν ) , las posiciones de los errores ( ik ) y los valores de error en esas posiciones ( _eik ) . A partir de estos, se puede calcular e ( x ) y restarlo de r ( _x ) para obtener el mensaje original enviado s ( x ).

El decodificador comienza evaluando el polinomio tal como se recibe en los puntos${\displaystyle \alpha ^{1}\dots \alpha ^{n-k}}$. Llamamos a los resultados de esa evaluación los "síndromes" S _j . Se definen como $${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}{(\alpha ^{j})}^{i_{k}},\quad j=1,2,\ldots ,n-k.\end{aligned}}}$$ Tenga en cuenta que${\displaystyle s(\alpha ^{j})=0}$porque${\displaystyle s(x)}$tiene raíces en${\displaystyle \alpha ^{j}}$, como se muestra en la sección anterior.

La ventaja de analizar los síndromes radica en que el polinomio del mensaje se elimina. En otras palabras, los síndromes solo se relacionan con el error y no se ven afectados por el contenido real del mensaje transmitido. Si todos los síndromes son cero, el algoritmo se detiene e informa que el mensaje no se corrompió durante la transmisión.

Para mayor comodidad, definamos los localizadores de error X _k y los valores de error Y _k como $${\displaystyle X_{k}=\alpha ^{i_{k}},\quad Y_{k}=e_{i_{k}}.}$$

Entonces, los síndromes se pueden escribir en términos de estos localizadores de errores y valores de error como $${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}.}$$

Esta definición de los valores del síndrome es equivalente a la anterior ya que${\displaystyle {(\alpha ^{j})}^{i_{k}}=\alpha ^{j\cdot i_{k}}={(\alpha ^{i_{k}})}^{j}=X_{k}^{j}}$.

Los síndromes dan un sistema de n − k ≥ 2 ν ecuaciones con 2 ν incógnitas, pero ese sistema de ecuaciones es no lineal en X _k y no tiene una solución obvia. Sin embargo, si se conociera X _k (véase más adelante), entonces las ecuaciones del síndrome proporcionan un sistema de ecuaciones lineal. $${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}},}$$ lo cual se puede resolver fácilmente para los valores de error Y _k .

En consecuencia, el problema consiste en encontrar X _k , porque entonces se conocería la matriz de la izquierda, y ambos lados de la ecuación podrían multiplicarse por su inversa, obteniendo Y _k

En la variante de este algoritmo donde las ubicaciones de los errores ya se conocen (cuando se utiliza como código de borrado ), este es el final. Las ubicaciones de los errores ( X _k ) ya se conocen por algún otro método (por ejemplo, en una transmisión FM, las secciones donde el flujo de bits no estaba claro o se vio afectado por interferencias se pueden determinar probabilísticamente a partir del análisis de frecuencia ). En este escenario, hasta${\displaystyle n-k}$Los errores pueden corregirse.

El resto del algoritmo sirve para localizar los errores y requerirá valores de síndrome hasta${\displaystyle 2\nu }$, en lugar de solo el${\displaystyle \nu }$utilizados hasta ahora. Por eso es necesario añadir el doble de símbolos correctores de errores de los que se pueden corregir sin conocer su ubicación.

Existe una relación de recurrencia lineal que da lugar a un sistema de ecuaciones lineales . Resolver esas ecuaciones permite identificar las ubicaciones de los errores X _k .

Definimos el polinomio localizador de errores Λ( x ) como $${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }.}$$

Los ceros de Λ( x ) son los recíprocos${\displaystyle X_{k}^{-1}}$. Esto se deduce de la construcción de notación de producto anterior, ya que si${\displaystyle x=X_{k}^{-1}}$, entonces uno de los términos multiplicados será cero,${\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}$, lo que hace que todo el polinomio se evalúe a cero: $${\displaystyle \Lambda (X_{k}^{-1})=0.}$$

Dejar${\displaystyle j}$sea ​​cualquier número entero tal que${\displaystyle 1\leq j\leq \nu }$Multiplica ambos lados por${\displaystyle Y_{k}X_{k}^{j+\nu }}$y seguirá siendo cero: $${\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}}$$

Suma para k = 1 a ν , y seguirá siendo cero: $${\displaystyle \sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0.}$$

Suma cada término por separado: $${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

Extraer los valores constantes de${\displaystyle \Lambda }$que no se ven afectados por la suma: $${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

Estas sumas ahora son equivalentes a los valores del síndrome, que conocemos y podemos sustituir. Por lo tanto, esto se reduce a $${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0.}$$

Restar${\displaystyle S_{j+\nu }}$de ambos lados rinde $${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }.}$$

Recordemos que j se eligió como cualquier entero entre 1 y v inclusive, y esta equivalencia es válida para todos esos valores. Por lo tanto, tenemos v ecuaciones lineales, no solo una. Este sistema de ecuaciones lineales se puede resolver para los coeficientes Λ _i del polinomio de localización de errores: $${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}.}$$ Lo anterior supone que el decodificador conoce el número de errores ν , pero este número aún no se ha determinado. El decodificador PGZ no determina ν directamente, sino que lo busca probando valores sucesivos. El decodificador primero asume el valor más grande para un valor de prueba ν y establece el sistema lineal para ese valor. Si las ecuaciones se pueden resolver (es decir, el determinante de la matriz es distinto de cero), entonces ese valor de prueba es el número de errores. Si el sistema lineal no se puede resolver, entonces el valor de prueba ν se reduce en uno y se examina el siguiente sistema más pequeño. ^{[ 16 ]}

Utilice los coeficientes Λ _i encontrados en el último paso para construir el polinomio de localización de errores. Las raíces del polinomio de localización de errores se pueden encontrar mediante una búsqueda exhaustiva. Los localizadores de errores X _k son los recíprocos de esas raíces. El orden de los coeficientes del polinomio de localización de errores se puede invertir, en cuyo caso las raíces de ese polinomio invertido son los localizadores de errores.${\displaystyle X_{k}}$(no sus recíprocos)${\displaystyle X_{k}^{-1}}$). La búsqueda de Chien es una implementación eficiente de este paso.

Una vez que se conocen los localizadores de error X _k , se pueden determinar los valores de error. Esto se puede hacer mediante la solución directa de Y _k en la matriz de ecuaciones de error dada anteriormente, o utilizando el algoritmo de Forney .

Calcula i _k tomando la base logarítmica${\displaystyle \alpha }$de X _k . Esto generalmente se hace utilizando una tabla de búsqueda precalculada .

Finalmente, e ( x ) se genera a partir de i _k y e _{i k} y luego se resta de r ( x ) para obtener el mensaje enviado originalmente s ( x ), con los errores corregidos.

Consideremos el código Reed-Solomon definido en GF (929) con α = 3 y t = 4 (este se utiliza en los códigos de barras PDF417 ) para un código RS(7,3). El polinomio generador es $${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522.}$$ Si el polinomio del mensaje es p ( x ) = 3 x ² + 2 x + 1 , entonces una palabra clave sistemática se codifica de la siguiente manera: $${\displaystyle s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455,}$$$${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474.}$$ Los errores en la transmisión podrían provocar que se reciba esto en su lugar: $${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474.}$$ Los síndromes se calculan evaluando r en potencias de α : $${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732,}$$$${\displaystyle S_{2}=r(3^{2})=637,\quad S_{3}=r(3^{3})=762,\quad S_{4}=r(3^{4})=925,}$$ cediendo el sistema $${\displaystyle {\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}.}$$

Utilizando la eliminación gaussiana , $${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},}$$ entonces $${\displaystyle \Lambda (x)=329x^{2}+821x+001,}$$ con raíces x ₁ = 757 = 3 ⁻³ y x ₂ = 562 = 3 ⁻⁴ . Los coeficientes se pueden invertir: $${\displaystyle R(x)=001x^{2}+821x+329,}$$ para producir raíces 27 = 3 ³ y 81 = 3 ⁴ con exponentes positivos, pero normalmente esto no se usa. El logaritmo de las raíces invertidas corresponde a las ubicaciones de error (de derecha a izquierda, la ubicación 0 es el último término en la palabra clave).

Para calcular los valores de error, aplique el algoritmo de Forney : $${\displaystyle \Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,}$$$${\displaystyle \Lambda '(x)=658x+821,}$$$${\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,}$$$${\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122.}$$

Restar${\displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}}$A partir del polinomio recibido r ( x ) se reproduce la palabra clave original s .

Utilizando los mismos datos que en el ejemplo de Peterson Gorenstein Zierler anterior:

El valor final de C es el polinomio localizador de errores, Λ( x ).

Utilizando los mismos datos que en el ejemplo de Peterson-Gorenstein-Zierler anterior: