código BCH

Código de corrección de errores

En teoría de la codificación , los códigos Bose-Chaudhuri-Hocquenghem ( códigos BCH ) forman una clase de códigos cíclicos de corrección de errores que se construyen utilizando polinomios sobre un campo finito (también llamado campo de Galois ). Los códigos BCH fueron inventados en 1959 por el matemático francés Alexis Hocquenghem , y de forma independiente en 1960 por Raj Chandra Bose y DK Ray-Chaudhuri . ^{[1] [2] [3]} El nombre Bose–Chaudhuri–Hocquenghem (y el acrónimo BCH ) surge de las iniciales de los apellidos de los inventores (erróneamente, en el caso de Ray-Chaudhuri).

Una de las características clave de los códigos BCH es que durante el diseño del código, existe un control preciso sobre la cantidad de errores de símbolos que el código puede corregir. En particular, es posible diseñar códigos BCH binarios que puedan corregir errores de múltiples bits. Otra ventaja de los códigos BCH es la facilidad con la que se pueden decodificar, concretamente, mediante un método algebraico conocido como decodificación de síndrome . Esto simplifica el diseño del decodificador de estos códigos, utilizando un pequeño hardware electrónico de bajo consumo.

Los códigos BCH se utilizan en aplicaciones como comunicaciones por satélite, ^{[4] reproductores} de discos compactos , DVD , unidades de disco , unidades flash USB , unidades de estado sólido , ^[5] y códigos de barras bidimensionales .

Definición e ilustración

Códigos BCH primitivos de sentido estricto

Dado un número primo q y potencia prima q ^m con enteros positivos m y d tales que d ≤ q ^m − 1 , un código BCH primitivo de sentido estricto sobre el campo finito (o campo de Galois) GF( q ) con longitud de código n = q ^m − 1 y la distancia al menos d se construye mediante el siguiente método.

Sea α un elemento primitivo de GF( q ^m ) . Para cualquier entero positivo i , sea m _i ( x ) el polinomio mínimo con coeficientes en GF( q ) de α ⁱ . El polinomio generador del código BCH se define como el mínimo común múltiplo g ( x ) = lcm ( m ₁ ( x ),…, m _{d − 1} ( x ) . Se puede ver que g ( x ) es un polinomio con coeficientes en GF ( q ) y divide a x ⁿ − 1 . Por tanto, el código polinómico definido por g ( x ) es un código cíclico.

Ejemplo

Sean q = 2 y m = 4 (por lo tanto n = 15 ). Consideraremos diferentes valores de d para GF(16) = GF(2 ⁴ ) basados ​​en el polinomio reductor z ⁴ + z + 1 , usando el elemento primitivo α ( z ) = z . Hay catorce polinomios mínimos m _i ( x ) con coeficientes en GF(2) que satisfacen

${\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.}$

Los polinomios mínimos son

${\displaystyle {\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}}$

El código BCH tiene el polinomio generador. ${\displaystyle d=2,3}$

${\displaystyle g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,}$

Tiene una distancia mínima de Hamming de al menos 3 y corrige hasta un error. Dado que el polinomio generador es de grado 4, este código tiene 11 bits de datos y 4 bits de suma de comprobación. También se indica como: (15, 11) código BCH.

El código BCH tiene el polinomio generador. ${\displaystyle d=4,5}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}}$

Tiene una distancia mínima de Hamming de al menos 5 y corrige hasta dos errores. Dado que el polinomio generador es de grado 8, este código tiene 7 bits de datos y 8 bits de suma de comprobación. También se indica como: (15, 7) código BCH.

El código BCH tiene el polinomio generador. ${\displaystyle d=6,7}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}}$

Tiene una distancia mínima de Hamming de al menos 7 y corrige hasta tres errores. Dado que el polinomio generador es de grado 10, este código tiene 5 bits de datos y 10 bits de suma de comprobación. También se indica como: (15, 5) código BCH. (Este polinomio generador en particular tiene una aplicación en el mundo real, en la "información de formato" del código QR ).

El código BCH con y superior tiene el polinomio generador. ${\displaystyle d=8}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}}$

Este código tiene una distancia de Hamming mínima de 15 y corrige 7 errores. Tiene 1 bit de datos y 14 bits de suma de comprobación. También se indica como: (15, 1) código BCH. De hecho, este código tiene solo dos palabras en clave: 000000000000000 y 111111111111111 (un código de repetición trivial ).

Códigos generales BCH

Los códigos BCH generales se diferencian de los códigos BCH primitivos de sentido estricto en dos aspectos.

En primer lugar, se puede relajar el requisito de que sea un elemento primitivo . Al relajar este requisito, la longitud del código cambia del orden del elemento ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (q^{m})}$ ${\displaystyle q^{m}-1}$ ${\displaystyle \mathrm {ord} (\alpha ),}$ ${\displaystyle \alpha .}$

En segundo lugar, las raíces consecutivas del polinomio generador pueden ir desde en lugar de ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ ${\displaystyle \alpha ,\ldots ,\alpha ^{d-1}.}$

Definición. Fijar un campo finito donde hay una potencia primaria. Elija números enteros positivos tales que y sea el orden multiplicativo del módulo ${\displaystyle GF(q),}$ ${\displaystyle q}$ ${\displaystyle m,n,d,c}$ ${\displaystyle 2\leq d\leq n,}$ ${\displaystyle {\rm {gcd}}(n,q)=1,}$ ${\displaystyle m}$ ${\displaystyle q}$ ${\displaystyle n.}$

Como antes, sea una raíz primitiva de la unidad en y sea el polinomio mínimo de para todos. El polinomio generador del código BCH se define como el mínimo común múltiplo. ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle GF(q^{m}),}$ ${\displaystyle m_{i}(x)}$ ${\displaystyle GF(q)}$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle i.}$ ${\displaystyle g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).}$

Nota: si es como en la definición simplificada, entonces es 1 y el orden del módulo es Por lo tanto, la definición simplificada es de hecho un caso especial de la general. ${\displaystyle n=q^{m}-1}$ ${\displaystyle {\rm {gcd}}(n,q)}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle m.}$

Casos especiales

• Un código BCH se denomina código BCH de sentido estricto . ${\displaystyle c=1}$
• Un código BCH se llama primitivo . ${\displaystyle n=q^{m}-1}$

El polinomio generador de un código BCH tiene coeficientes de En general, un código cíclico como polinomio generador se llama código BCH El código BCH y un polinomio generador con potencias sucesivas de como raíces es un tipo de código Reed-Solomon donde el alfabeto del decodificador (síndromes) es el mismo que el alfabeto del canal (datos y polinomio generador), todos los elementos de . ^[6] El otro tipo de código Reed Solomon es un código Reed Solomon de vista original que no es un código BCH. ${\displaystyle g(x)}$ ${\displaystyle \mathrm {GF} (q).}$ ${\displaystyle \mathrm {GF} (q^{p})}$ ${\displaystyle g(x)}$ ${\displaystyle \mathrm {GF} (q^{p}).}$ ${\displaystyle \mathrm {GF} (q^{m})}$ ${\displaystyle g(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (q^{m})}$

Propiedades

El polinomio generador de un código BCH tiene como máximo un grado . Además, si y , el polinomio generador tiene grado como máximo . ${\displaystyle (d-1)m}$ ${\displaystyle q=2}$ ${\displaystyle c=1}$ ${\displaystyle dm/2}$

Un código BCH tiene al menos una distancia de Hamming mínima . ${\displaystyle d}$

Un código BCH es cíclico.

Codificación

Debido a que cualquier polinomio que sea múltiplo del polinomio generador es una palabra de código BCH válida, la codificación BCH es simplemente el proceso de encontrar algún polinomio que tenga el generador como factor.

El código BCH en sí no es prescriptivo sobre el significado de los coeficientes del polinomio; conceptualmente, la única preocupación de un algoritmo de decodificación BCH es encontrar la palabra de código válida con la distancia mínima de Hamming a la palabra de código recibida. Por lo tanto, el código BCH puede implementarse como código sistemático o no, dependiendo de cómo el implementador elija incrustar el mensaje en el polinomio codificado.

Codificación no sistemática: el mensaje como factor

La forma más sencilla de encontrar un polinomio que sea múltiplo del generador es calcular el producto de algún polinomio arbitrario y el generador. En este caso, se puede elegir un polinomio arbitrario utilizando los símbolos del mensaje como coeficientes.

${\displaystyle s(x)=p(x)g(x)}$

Como ejemplo, considere el polinomio generador , elegido para su uso en el código binario BCH (31, 21) utilizado por POCSAG y otros. Para codificar el mensaje de 21 bits {101101110111101111101}, primero lo representamos como un polinomio sobre : ${\displaystyle g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1}$ ${\displaystyle GF(2)}$

${\displaystyle p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1}$

Luego, calcula (también sobre ): ${\displaystyle GF(2)}$

${\displaystyle {\begin{aligned}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1\right)\left(x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1\right)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{aligned}}}$

Por tanto, la palabra clave transmitida es {1100111010010111101011101110101}.

El receptor puede utilizar estos bits como coeficientes y, después de la corrección de errores para garantizar una palabra de código válida, puede volver a calcular ${\displaystyle s(x)}$ ${\displaystyle p(x)=s(x)/g(x)}$

Codificación sistemática: el mensaje como prefijo

Un código sistemático es aquel en el que el mensaje aparece palabra por palabra en algún lugar dentro de la palabra clave. Por lo tanto, la codificación BCH sistemática implica primero incrustar el polinomio del mensaje dentro del polinomio de la palabra clave y luego ajustar los coeficientes de los términos restantes (que no son mensajes) para garantizar que sea divisible por . ${\displaystyle s(x)}$ ${\displaystyle g(x)}$

Este método de codificación aprovecha el hecho de que restar el resto de un dividendo da como resultado un múltiplo del divisor. Por lo tanto, si tomamos nuestro polinomio de mensaje como antes y lo multiplicamos por (para "desplazar" el mensaje fuera del resto), podemos usar la división euclidiana de polinomios para obtener: ${\displaystyle p(x)}$ ${\displaystyle x^{n-k}}$

${\displaystyle p(x)x^{n-k}=q(x)g(x)+r(x)}$

Aquí vemos que es una palabra clave válida. Como siempre es de grado menor que (que es el grado de ), podemos restarlo con seguridad sin alterar ninguno de los coeficientes del mensaje, por lo tanto tenemos nuestro as ${\displaystyle q(x)g(x)}$ ${\displaystyle r(x)}$ ${\displaystyle n-k}$ ${\displaystyle g(x)}$ ${\displaystyle p(x)x^{n-k}}$ ${\displaystyle s(x)}$

${\displaystyle s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)}$

Además (es decir, con códigos BCH binarios), este proceso es indistinguible de agregar una verificación de redundancia cíclica , y si un código BCH binario sistemático se usa solo para propósitos de detección de errores, vemos que los códigos BCH son solo una generalización de las matemáticas de los códigos cíclicos. controles de redundancia . ${\displaystyle GF(2)}$

La ventaja de la codificación sistemática es que el receptor puede recuperar el mensaje original descartando todo lo que sigue a los primeros coeficientes, después de realizar la corrección de errores. ${\displaystyle k}$

Descodificación

Existen muchos algoritmos para decodificar códigos BCH. Los más comunes siguen este esquema general:

1. Calcule los síndromes s _j para el vector recibido.
2. Determine el número de errores t y el polinomio localizador de errores Λ(x) a partir de los síndromes
3. Calcule las raíces del polinomio de ubicación de errores para encontrar las ubicaciones de errores X _i
4. Calcule los valores de error Y _i en esas ubicaciones de error
5. Corrige los errores

Durante algunos de estos pasos, el algoritmo de decodificación puede determinar que el vector recibido tiene demasiados errores y no puede corregirse. Por ejemplo, si no se encuentra un valor apropiado de t , la corrección fallaría. En un código truncado (no primitivo), la ubicación de un error puede estar fuera de rango. Si el vector recibido tiene más errores de los que el código puede corregir, el decodificador puede, sin saberlo, producir un mensaje aparentemente válido que no es el que se envió.

Calcular los síndromes.

El vector recibido es la suma de la palabra clave correcta y un vector de error desconocido. Los valores del síndrome se forman considerándolo como un polinomio y evaluándolo en Así, los síndromes son ^[7] ${\displaystyle R}$ ${\displaystyle C}$ ${\displaystyle E.}$ ${\displaystyle R}$ ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}.}$

${\displaystyle s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)}$

para a ${\displaystyle j=c}$ ${\displaystyle c+d-2.}$

Dado que los ceros de son múltiplos, al examinar los valores del síndrome se aísla el vector de error para que se pueda comenzar a resolverlo. ${\displaystyle \alpha ^{j}}$ ${\displaystyle g(x),}$ ${\displaystyle C(x)}$ ${\displaystyle C\left(\alpha ^{j}\right)=0.}$

Si no hay ningún error, para todos. Si todos los síndromes son cero, entonces se realiza la decodificación. ${\displaystyle s_{j}=0}$ ${\displaystyle j.}$

Calcular el polinomio de ubicación del error.

Si hay síndromes distintos de cero, entonces hay errores. El decodificador necesita determinar cuántos errores y su ubicación.

Si hay un solo error, escríbalo como dónde está la ubicación del error y su magnitud. Entonces los dos primeros síndromes son ${\displaystyle E(x)=e\,x^{i},}$ ${\displaystyle i}$ ${\displaystyle e}$

${\displaystyle {\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}}$

por lo que juntos nos permiten calcular y proporcionar cierta información (determinarla completamente en el caso de los códigos Reed-Solomon). ${\displaystyle e}$ ${\displaystyle i}$

Si hay dos o más errores,

${\displaystyle E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,}$

No resulta inmediatamente obvio cómo empezar a resolver los síndromes resultantes de las incógnitas y ${\displaystyle e_{k}}$ ${\displaystyle i_{k}.}$

El primer paso es encontrar, compatible con síndromes computacionales y con polinomio localizador mínimo posible: ${\displaystyle t,}$

${\displaystyle \Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)}$

Tres algoritmos populares para esta tarea son:

1. Algoritmo de Peterson-Gorenstein-Zierler
2. Algoritmo de Berlekamp-Massey
3. Algoritmo euclidiano de Sugiyama

Algoritmo de Peterson-Gorenstein-Zierler

El algoritmo de Peterson es el paso 2 del procedimiento de decodificación BCH generalizado. El algoritmo de Peterson se utiliza para calcular los coeficientes polinomiales del localizador de errores de un polinomio. ${\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{v}}$

${\displaystyle \Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.}$

Ahora el procedimiento del algoritmo de Peterson-Gorenstein-Zierler. ^{[8] Espere} _que tengamos al menos 2 _t síndromes sc , …, sc _{+2 t −1} . Sea v  =  t .

1. Comience generando la matriz con elementos que son valores del síndrome. ${\displaystyle S_{v\times v}}$

   ${\displaystyle S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.}$

2. Generar un vector con elementos. ${\displaystyle c_{v\times 1}}$
   ${\displaystyle C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.}$
3. Denotemos los coeficientes polinomiales desconocidos, que están dados por ${\displaystyle \Lambda }$
   ${\displaystyle \Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.}$
4. Formar la ecuación matricial
   ${\displaystyle S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.}$
5. Si el determinante de la matriz es distinto de cero, entonces podemos encontrar una inversa de esta matriz y resolver los valores de valores desconocidos. ${\displaystyle S_{v\times v}}$ ${\displaystyle \Lambda }$
6. Si entonces sigue ${\displaystyle \det \left(S_{v\times v}\right)=0,}$

    si ${\displaystyle v=0}$ entonces declarar un polinomio localizador de errores vacío detener el procedimiento de Peterson. fin colocar ${\displaystyle v\leftarrow v-1}$

   continuar desde el comienzo de la decodificación de Peterson haciendo más pequeños ${\displaystyle S_{v\times v}}$
7. Una vez que tenga los valores de , tendrá el polinomio localizador de errores. ${\displaystyle \Lambda }$
8. Detenga el procedimiento de Peterson.

Polinomio localizador de error de factor

Ahora que tienes el polinomio, sus raíces se pueden encontrar en la forma mediante fuerza bruta, por ejemplo, utilizando el algoritmo de búsqueda de Chien . Las potencias exponenciales del elemento primitivo producirán las posiciones donde se producen errores en la palabra recibida; de ahí el nombre de polinomio 'localizador de errores'. ${\displaystyle \Lambda (x)}$ ${\displaystyle \Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)}$ ${\displaystyle \alpha }$

Los ceros de Λ( x ) son α ^{− i ₁} ,…, α ^{− i _v} .

Calcular valores de error

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 luego para corregir los valores recibidos en esas ubicaciones para recuperar la palabra de código original.

Para el caso de BCH binario (con todos los caracteres legibles), esto es trivial; simplemente invierta los bits de la palabra recibida en estas posiciones y tendremos la palabra de código corregida. En el caso más general, los pesos de error se pueden determinar resolviendo el sistema lineal ${\displaystyle e_{j}}$

${\displaystyle {\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}}}$

algoritmo de Forney

Sin embargo, existe un método más eficiente conocido como algoritmo de Forney .

Dejar

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

${\displaystyle v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).}$

Y el polinomio evaluador de errores ^[9]

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}}$

Finalmente:

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

dónde

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

Que si los síndromes pudieran explicarse mediante una palabra de error, que podría ser distinta de cero solo en las posiciones , entonces los valores de error son ${\displaystyle i_{k}}$

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

Para códigos BCH de sentido estricto, c = 1, por lo que la expresión se simplifica a:

${\displaystyle e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

Explicación del cálculo del algoritmo de Forney

Se basa en la interpolación de Lagrange y técnicas de generación de funciones .

Considere y en aras de la simplicidad suponga para y para Entonces ${\displaystyle S(x)\Lambda (x),}$ ${\displaystyle \lambda _{k}=0}$ ${\displaystyle k>v,}$ ${\displaystyle s_{k}=0}$ ${\displaystyle k>c+d-2.}$

${\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.}$

${\displaystyle {\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}}$

Queremos calcular incógnitas y podríamos simplificar el contexto eliminando los términos. Esto conduce al polinomio evaluador de errores. ${\displaystyle e_{j},}$ ${\displaystyle \left(x\alpha ^{i_{j}}\right)^{d-1}}$

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.}$

gracias a que tenemos ${\displaystyle v\leqslant d-1}$

${\displaystyle \Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).}$

Gracias al (truco de interpolación de Lagrange) la suma degenera a una sola suma para ${\displaystyle \Lambda }$ ${\displaystyle x=\alpha ^{-i_{k}}}$

${\displaystyle \Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

Para conseguirlo simplemente debemos deshacernos del producto. Podríamos calcular el producto directamente a partir de raíces ya calculadas , pero podríamos usar una forma más simple. ${\displaystyle e_{k}}$ ${\displaystyle \alpha ^{-i_{j}}}$ ${\displaystyle \Lambda ,}$

Como derivada formal

${\displaystyle \Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),}$

obtenemos nuevamente solo un sumando en

${\displaystyle \Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

Así que finalmente

${\displaystyle e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.}$

Esta fórmula es ventajosa cuando se calcula la derivada formal de la forma ${\displaystyle \Lambda }$

${\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}}$

flexible:

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

dónde

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

Decodificación basada en algoritmo euclidiano extendido

Un proceso alternativo para encontrar tanto el polinomio Λ como el polinomio localizador de errores se basa en la adaptación de Yasuo Sugiyama del algoritmo euclidiano extendido . ^[10] La corrección de caracteres ilegibles también podría incorporarse fácilmente al algoritmo.

Sean posiciones de caracteres ilegibles. Se crea un polinomio localizando estas posiciones. Establezca valores en posiciones ilegibles en 0 y calcule los síndromes. ${\displaystyle k_{1},...,k_{k}}$ ${\displaystyle \Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).}$

Como ya hemos definido para la fórmula de Forney, dejemos que ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}$

Ejecutemos un algoritmo euclidiano extendido para localizar el mínimo común divisor de polinomios y El objetivo no es encontrar el mínimo común divisor, sino un polinomio de grado como máximo y polinomios tales que Bajo grado de garantías, que satisfaría condiciones de definición extendidas (por ) para ${\displaystyle S(x)\Gamma (x)}$ ${\displaystyle x^{d-1}.}$ ${\displaystyle r(x)}$ ${\displaystyle \lfloor (d+k-3)/2\rfloor }$ ${\displaystyle a(x),b(x)}$ ${\displaystyle r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.}$ ${\displaystyle r(x)}$ ${\displaystyle a(x)}$ ${\displaystyle \Gamma }$ ${\displaystyle \Lambda .}$

Definir y usar en el lugar de en la fórmula de Fourney nos dará valores de error. ${\displaystyle \Xi (x)=a(x)\Gamma (x)}$ ${\displaystyle \Xi }$ ${\displaystyle \Lambda (x)}$

La principal ventaja del algoritmo es que, al mismo tiempo, calcula lo requerido en la fórmula de Forney. ${\displaystyle \Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)}$

Explicación del proceso de decodificación.

El objetivo es encontrar una palabra clave que se diferencie lo mínimo posible de la palabra recibida en posiciones legibles. Al expresar la palabra recibida como una suma de la palabra de código más cercana y la palabra de error, intentamos encontrar una palabra de error con un número mínimo de valores distintos de ceros en posiciones legibles. El síndrome restringe la palabra de error por condición ${\displaystyle s_{i}}$

${\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.}$

Podríamos escribir estas condiciones por separado o podríamos crear polinomios

${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}}$

y comparar coeficientes cercanos a potencias ${\displaystyle 0}$ ${\displaystyle d-2.}$

${\displaystyle S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.}$

Supongamos que hay una letra ilegible en la posición, podríamos reemplazar un conjunto de síndromes por un conjunto de síndromes definidos por la ecuación. Supongamos que para una palabra de error se mantienen todas las restricciones del conjunto original de síndromes, entonces ${\displaystyle k_{1},}$ ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$ ${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.}$ ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$

${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.}$

Un nuevo conjunto de síndromes restringe el vector de error

${\displaystyle f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)}$

De la misma manera que el conjunto original de síndromes restringió el vector de error, excepto que la coordenada donde tenemos un es cero, si para localizar posiciones de error podríamos cambiar el conjunto de síndromes de manera similar para reflejar todos los caracteres ilegibles. Esto acorta el conjunto de síndromes por ${\displaystyle e_{j}.}$ ${\displaystyle k_{1},}$ ${\displaystyle f_{k_{1}}=0,}$ ${\displaystyle f_{j}}$ ${\displaystyle e_{j}=0.}$ ${\displaystyle k.}$

En la formulación polinomial, la sustitución de síndromes establecidos por síndromes establecidos conduce a ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$

${\displaystyle T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.}$

Por lo tanto,

${\displaystyle xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).}$

Después de reemplazar por , se requeriría una ecuación para los coeficientes cercanos a las potencias ${\displaystyle S(x)}$ ${\displaystyle S(x)\Gamma (x)}$ ${\displaystyle k,\cdots ,d-2.}$

Se podría considerar la búsqueda de posiciones de error desde el punto de vista de eliminar la influencia de posiciones dadas de manera similar a como ocurre con los caracteres ilegibles. Si encontramos posiciones tales que eliminar su influencia conduce a obtener un conjunto de síndromes que consisten exclusivamente en ceros, entonces existe un vector de error con errores sólo en estas coordenadas. Si denotamos el polinomio eliminando la influencia de estas coordenadas, obtenemos ${\displaystyle v}$ ${\displaystyle \Lambda (x)}$

${\displaystyle S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.}$

En el algoritmo euclidiano, intentamos corregir la mayoría de los errores (en posiciones legibles), porque con un mayor número de errores podría haber más palabras en código a la misma distancia de la palabra recibida. Por lo tanto, para lo que estamos buscando, la ecuación debe ser válida para coeficientes cercanos a potencias a partir de ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ ${\displaystyle \Lambda (x)}$

${\displaystyle k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .}$

En la fórmula de Forney, podría multiplicarse por un escalar dando el mismo resultado. ${\displaystyle \Lambda (x)}$

Podría suceder que el algoritmo euclidiano encuentre un grado superior a tener un número de raíces diferentes igual a su grado, donde la fórmula de Fourney sería capaz de corregir errores en todas sus raíces, de todas formas corregir tantos errores podría ser arriesgado (especialmente sin otros restricciones en la palabra recibida). Generalmente después de obtener un mayor grado, decidimos no corregir los errores. La corrección podría fallar en el caso de que tenga raíces con mayor multiplicidad o el número de raíces sea menor que su grado. El error también podría detectarse mediante la fórmula de Forney que devuelve un error fuera del alfabeto transmitido. ${\displaystyle \Lambda (x)}$ ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ ${\displaystyle \Lambda (x)}$ ${\displaystyle \Lambda (x)}$

Corrige los errores

Utilizando los valores de error y la ubicación de los errores, corrija los errores y forme un vector de código corregido restando los valores de error en las ubicaciones de los errores.

Ejemplos de decodificación

Decodificación de código binario sin caracteres ilegibles

Considere un código BCH en GF(2 ⁴ ) con y . (Esto se usa en códigos QR ). Deje que el mensaje a transmitir sea [1 1 0 1 1], o en notación polinómica. Los símbolos de "suma de verificación" se calculan dividiendo por y tomando el resto, lo que da como resultado o [ 1 0 0 0 0 1 0 1 0 0 ]. Estos se adjuntan al mensaje, por lo que la palabra clave transmitida es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]. ${\displaystyle d=7}$ ${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$ ${\displaystyle M(x)=x^{4}+x^{3}+x+1.}$ ${\displaystyle x^{10}M(x)}$ ${\displaystyle g(x)}$ ${\displaystyle x^{9}+x^{4}+x^{2}}$

Ahora, imagine que hay dos errores de bits en la transmisión, por lo que la palabra clave recibida es [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. En notación polinomial:

${\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}}$

Para corregir los errores, primero calcule los síndromes. Tomando tenemos y A continuación, aplique el procedimiento de Peterson reduciendo por filas la siguiente matriz aumentada. ${\displaystyle \alpha =0010,}$ ${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5}=0001,}$ ${\displaystyle s_{6}=1001.}$

${\displaystyle \left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}}$

Debido a la fila cero, S _3×3 es singular, lo cual no sorprende ya que solo se introdujeron dos errores en la palabra clave. Sin embargo, la esquina superior izquierda de la matriz es idéntica a [ S _2×2 | C _2×1 ] , lo que da lugar a la solución El polinomio localizador de errores resultante es el que tiene ceros en y Los exponentes de corresponden a las ubicaciones de los errores. No es necesario calcular los valores de error en este ejemplo, ya que el único valor posible es 1. ${\displaystyle \lambda _{2}=1000,}$ ${\displaystyle \lambda _{1}=1011.}$ ${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,}$ ${\displaystyle 0100=\alpha ^{-13}}$ ${\displaystyle 0111=\alpha ^{-5}.}$ ${\displaystyle \alpha }$

Decodificación con caracteres ilegibles

Supongamos el mismo escenario, pero la palabra recibida tiene dos caracteres ilegibles [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. Reemplazamos los caracteres ilegibles por ceros mientras creamos el polinomio que refleja sus posiciones. Calculamos los síndromes y (usando notación logarítmica que es independiente de los isomorfismos GF(2 ⁴ ). Para verificar el cálculo podemos usar la misma representación para la suma que se usó en anteriores (Por ejemplo, la descripción hexadecimal de las potencias de son consecutivamente 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 con la suma basada en xor bit a bit). ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$ ${\displaystyle s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},}$ ${\displaystyle s_{6}=\alpha ^{-7}.}$ ${\displaystyle \alpha }$

Hagamos polinomio del síndrome

${\displaystyle S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},}$

calcular

${\displaystyle S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}.}$

Ejecute el algoritmo euclidiano extendido:

${\displaystyle {\begin{aligned}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right)x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\right)x^{3}+\left(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\right)x^{4}+2\alpha ^{5}x^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.\end{aligned}}}$

Hemos alcanzado un polinomio de grado como máximo 3, y como

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},}$

obtenemos

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.}$

Por lo tanto,

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.}$

No se preocupe, encuentre por fuerza bruta una raíz de Las raíces son y (después de encontrar, por ejemplo, podemos dividir por el monom correspondiente y la raíz del monom resultante se podrá encontrar fácilmente). ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.}$ ${\displaystyle \lambda _{0}\neq 1.}$ ${\displaystyle \Lambda .}$ ${\displaystyle \alpha ^{2},}$ ${\displaystyle \alpha ^{10}}$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \Lambda }$ ${\displaystyle \left(x-\alpha ^{2}\right)}$

Dejar

${\displaystyle {\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{aligned}}}$

Busquemos valores de error usando la fórmula.

${\displaystyle e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},}$

¿Dónde están las raíces de ? Obtenemos ${\displaystyle \alpha ^{-i_{j}}}$ ${\displaystyle \Xi (x).}$ ${\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.}$

${\displaystyle {\begin{aligned}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac {\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7})}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0\\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4}+\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{\alpha ^{6}}}=1\end{aligned}}}$

De hecho, eso no debería sorprender. ${\displaystyle e_{3}=e_{4}=1,}$

Por lo tanto, el código corregido es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decodificación con caracteres ilegibles con una pequeña cantidad de errores.

Muestremos el comportamiento del algoritmo para el caso con una pequeña cantidad de errores. Deje que la palabra recibida sea [1 0 0? 1 1 ? 0 0 0 1 0 1 0 0 ].

Nuevamente, reemplace los caracteres ilegibles por ceros mientras crea el polinomio que refleja sus posiciones. Calcule los síndromes y cree el polinomio del síndrome. ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$ ${\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},}$ ${\displaystyle s_{6}=\alpha ^{2}.}$

${\displaystyle {\begin{aligned}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^{3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{aligned}}}$

Ejecutemos el algoritmo euclidiano extendido:

${\displaystyle {\begin{aligned}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2\alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5}+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end{aligned}}}$

Hemos alcanzado un polinomio de grado como máximo 3, y como

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},}$

obtenemos

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}.}$

Por lo tanto,

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.}$

No te preocupes porque la raíz de es ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{1}x.}$ ${\displaystyle \lambda _{0}\neq 1.}$ ${\displaystyle \Lambda (x)}$ ${\displaystyle \alpha ^{3-1}.}$

Dejar

${\displaystyle {\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0}x{\bmod {x^{6}}}\end{aligned}}}$

Busquemos valores de error usando la fórmula donde están las raíces del polinomio ${\displaystyle e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),}$ ${\displaystyle \alpha ^{-i_{j}}}$ ${\displaystyle \Xi (x).}$

${\displaystyle \Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.}$

Obtenemos

${\displaystyle {\begin{aligned}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right)}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3}}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_{3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3}}}=1\end{aligned}}}$

El hecho de que esto no debería sorprender. ${\displaystyle e_{3}=1}$

Por lo tanto, el código corregido es [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Citas

1. Reed y Chen 1999, pág. 189
2. Hocquenghem 1959
3. Bose y Ray-Chaudhuri 1960
4. "Sistema de codificación Phobos Lander: software y análisis" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 25 de febrero de 2012 .
5. Marelli, Alessia; Micheloni, Rino (2018). "Códigos BCH para unidades de estado sólido". Unidades de estado sólido internas (SSDS) . Serie Springer en Microelectrónica Avanzada. vol. 37. págs. 369–406. doi :10.1007/978-981-13-0599-3_11. ISBN 978-981-13-0598-6. Consultado el 23 de septiembre de 2023 .
6. Gill sin fecha, pág. 3
7. Lidl y Pilz 1999, pág. 229
8. Gorenstein, Peterson y Zierler 1960
9. Gill sin fecha, pág. 47
10. Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa y Toshihiko Namekawa. Un método para resolver ecuaciones clave para decodificar códigos Goppa. Información y control, 27:87–99, 1975.

Referencias

Fuentes primarias

• Hocquenghem, A. (septiembre de 1959), "Codes correcteurs d'erreurs", Chiffres (en francés), 2 , París: 147-156
• Bosé, RC ; Ray-Chaudhuri, DK (marzo de 1960), "Sobre una clase de error al corregir códigos de grupo binario" (PDF) , Información y control , 3 (1): 68–79, doi :10.1016/s0019-9958(60)90287- 4, ISSN  0890-5401, archivado (PDF) desde el original el 9 de octubre de 2022.

Fuentes secundarias

• Gill, John (sin fecha), EE387 Notas n.° 7, Folleto n.° 28 (PDF) , Universidad de Stanford, págs. 42–45, archivado (PDF) desde el original el 9 de octubre de 2022 , consultado el 21 de abril de 2010^{[ enlace muerto ]} Aparentemente se están rehaciendo las notas del curso para 2012: http://www.stanford.edu/class/ee387/ Archivado el 5 de junio de 2013 en Wayback Machine.
• Gorenstein, Daniel ; Peterson, W. Wesley ; Zierler, Neal (1960), "Los códigos Bose-Chaudhuri de corrección de dos errores son casi perfectos", Información y control , 3 (3): 291–294, doi : 10.1016/s0019-9958(60)90877-9
• Lidl, Rudolf; Pilz, Günter (1999), Álgebra abstracta aplicada (2ª ed.), John Wiley
• Caña, Irving S .; Chen, Xuemin (1999), Codificación de control de errores para redes de datos , Boston, MA: Kluwer Academic Publishers , ISBN 0-7923-8528-4

Otras lecturas

• Blahut, Richard E. (2003), Códigos algebraicos para la transmisión de datos (2ª ed.), Cambridge University Press , ISBN 0-521-55374-1
• Gilbert, WJ; Nicholson, WK (2004), Álgebra moderna con aplicaciones (2ª ed.), John Wiley
• Lin, S.; Costello, D. (2004), Codificación de control de errores: fundamentos y aplicaciones , Englewood Cliffs, Nueva Jersey: Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos correctores de errores , Nueva York, NY: North-Holland Publishing Company
• Rudra, Atri, CSE 545, Códigos de corrección de errores: combinatoria, algoritmos y aplicaciones, Universidad de Buffalo, archivado desde el original el 18 de diciembre de 2012