Código BCH

Código de corrección de errores

En teoría de codificación , los códigos de Bose–Chaudhuri–Hocquenghem ( códigos BCH ) forman una clase de códigos de corrección de errores cíclicos que se construyen utilizando polinomios sobre un cuerpo finito (también llamado cuerpo de Galois ). Los códigos BCH fueron inventados en 1959 por el matemático francés Alexis Hocquenghem , e independientemente 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 (por error, 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 el número de errores de símbolos que puede corregir el código. En particular, es posible diseñar códigos BCH binarios que puedan corregir múltiples errores de bit. Otra ventaja de los códigos BCH es la facilidad con la que se pueden decodificar, es decir, mediante un método algebraico conocido como decodificación de síndromes . Esto simplifica el diseño del decodificador para estos códigos, utilizando hardware electrónico pequeño y 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 una potencia prima q ^m con números enteros positivos m y d tales que d ≤ q ^m − 1 , se construye un código BCH primitivo de sentido estrecho sobre el campo finito (o campo de Galois) GF( q ) con longitud de código n = q ^m − 1 y distancia al menos d 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 ) = mcm( 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 lo tanto, el código polinomial definido por g ( x ) es un código cíclico.

Ejemplo

Sea 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 , utilizando 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 de Hamming mínima de al menos 3 y corrige hasta un error. Como 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 denota como: código BCH (15, 11) .

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 de Hamming mínima de al menos 5 y corrige hasta dos errores. Como 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 denota como: código BCH (15, 7) .

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 de Hamming mínima 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 denota como: código BCH (15, 5) . (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 mínima de Hamming de 15 y corrige 7 errores. Tiene 1 bit de datos y 14 bits de suma de comprobación. También se denota como: código BCH (15, 1) . De hecho, este código tiene solo dos palabras de código: 000000000000000 y 111111111111111 (un código de repetición trivial ).

Códigos generales del BCH

Los códigos BCH generales difieren 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 de al 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 tener su origen en lugar de ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ ${\displaystyle \alpha ,\ldots ,\alpha ^{d-1}.}$

Definición. Fija un cuerpo finito donde es una potencia prima. Elige números enteros positivos tales que y es el orden multiplicativo de 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 sobre 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 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 sobre con como polinomio generador se llama código BCH sobre El código BCH sobre y 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 (polinomio de datos y 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 un grado como máximo de . Además, si y , el polinomio generador tiene un grado como máximo de . ${\displaystyle (d-1)m}$ ${\displaystyle q=2}$ ${\displaystyle c=1}$ ${\displaystyle dm/2}$

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

Un código BCH es cíclico.

Codificación

Dado 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 al generador como factor.

El código BCH en sí no es prescriptivo en cuanto al 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 de Hamming mínima respecto de la palabra de código recibida. Por lo tanto, el código BCH puede implementarse como un código sistemático o no, dependiendo de cómo elija el implementador 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 un polinomio arbitrario por el generador. En este caso, el polinomio arbitrario se puede elegir 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 lo 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 textualmente en algún lugar dentro de la palabra clave. Por lo tanto, la codificación sistemática BCH 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 al restar el resto de un dividendo se obtiene 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 camino 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 de código válida. Como siempre es de grado menor que (que es el grado de ), podemos restarlo de forma segura sin alterar ninguno de los coeficientes del mensaje, por lo tanto, tenemos nuestro como ${\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 la adición de una verificación de redundancia cíclica , y si se utiliza un código BCH binario sistemático solo para fines de detección de errores, vemos que los códigos BCH son solo una generalización de las matemáticas de las verificaciones de redundancia cíclica . ${\displaystyle GF(2)}$

La ventaja de la codificación sistemática es que el receptor puede recuperar el mensaje original descartando todo lo que esté después de 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. Calcular los síndromes s _j para el vector recibido
2. Determinar el número de errores t y el polinomio localizador de errores Λ(x) a partir de los síndromes
3. Calcular las raíces del polinomio de ubicación de error para encontrar las ubicaciones de error X _i
4. Calcular los valores de error Y _i en esas ubicaciones de error
5. Corrija los errores

Durante algunos de estos pasos, el algoritmo de decodificación puede determinar que el vector recibido tiene demasiados errores y no se puede corregir. Por ejemplo, si no se encuentra un valor apropiado de t , la corrección fallará. 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 producir sin saberlo 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 de código correcta y un vector de error desconocido. Los valores del síndrome se forman considerando como un polinomio y evaluándolo en Por lo tanto, 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 son los ceros de de los cuales es un múltiplo, examinar los valores del síndrome aísla así el vector de error para que uno 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 los síndromes son todos 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 debe determinar cuántos errores hay y dónde se encuentran.

Si hay un solo error, escríbalo como donde es la ubicación del error y es 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 (determinándola 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 los síndromes calculados y con el mínimo polinomio localizador 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 generalizado de decodificación del BCH. El algoritmo de Peterson se utiliza para calcular los coeficientes polinómicos localizadores 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] Esperemos que tengamos al menos 2 síndromes t s _c , …, s _{c +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. Sea los coeficientes polinómicos desconocidos, que se dan 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 no es cero, entonces podemos encontrar una inversa de esta matriz y resolver los valores de los valores desconocidos. ${\displaystyle S_{v\times v}}$ ${\displaystyle \Lambda }$
6. Si luego 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}$

   Continúe desde el principio de la decodificación de Peterson haciendo más pequeñas ${\displaystyle S_{v\times v}}$
7. Después de tener valores de , tienes el polinomio localizador de errores. ${\displaystyle \Lambda }$
8. Detener el procedimiento de Peterson.

Polinomio localizador de error de factor

Ahora que ya 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 darán como resultado las posiciones en las que 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 para corregir los valores recibidos en esas ubicaciones y recuperar la palabra clave original.

En el caso del BCH binario (con todos los caracteres legibles), esto es trivial; basta con invertir 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 el 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 error ^[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.}$

Entonces, 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 los 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 funciones generadoras .

Consideremos y, por el bien de la simplicidad, supongamos que 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 nos lleva 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 se degenera en un solo sumando 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 obtenerlo, simplemente debemos deshacernos del producto. Podríamos calcular el producto directamente a partir de las raíces ya calculadas de 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.}$

Descodificació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 que localice estas posiciones. Se establecen los valores de las posiciones ilegibles en 0 y se calculan 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, sea ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}$

Ejecutemos el 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 Grado bajo de garantías, que satisfarían condiciones extendidas (mediante ) definitorias 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 utilizar 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 mientras tanto 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 difiera lo menos posible de la palabra recibida en posiciones legibles. Al expresar la palabra recibida como una suma de la palabra clave más cercana y la palabra de error, intentamos encontrar la palabra de error con la menor cantidad de valores distintos de cero en posiciones legibles. Syndrom 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 un polinomio.

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

y comparar coeficientes cerca de potencias a ${\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 en la que podríamos reemplazar el conjunto de síndromes por el conjunto de síndromes definidos por la ecuación. Supongamos que para una palabra de error se cumplen 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}.}$

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 la coordenada donde tenemos un es cero, si Para el objetivo de 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 un conjunto de síndromes por un conjunto de síndromes 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 coeficientes cercanos a 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 se hace con los caracteres ilegibles. Si encontramos posiciones tales que al eliminar su influencia obtenemos un conjunto de síndromes que consisten en todos los ceros, entonces existe un vector de error con errores solo en estas coordenadas. Si denota el polinomio que elimina 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, tratamos de corregir la mayor cantidad de errores (en posiciones legibles), porque con un mayor número de errores podría haber más palabras de código en la misma distancia de la palabra recibida. Por lo tanto, para lo que buscamos, la ecuación debe cumplirse para coeficientes cercanos a potencias que comiencen desde ${\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, se puede multiplicar por un escalar dando el mismo resultado. ${\displaystyle \Lambda (x)}$

Podría suceder que el algoritmo euclidiano encuentre un grado mayor que el que tiene 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 todos modos corregir tantos errores podría ser riesgoso (especialmente sin otras restricciones en la palabra recibida). Por lo general, después de obtener un grado mayor, 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 si la fórmula de Fourney devuelve un error fuera del alfabeto transmitido. ${\displaystyle \Lambda (x)}$ ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ ${\displaystyle \Lambda (x)}$ ${\displaystyle \Lambda (x)}$

Corrija 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 .) Sea el mensaje a transmitir [1 1 0 1 1], o en notación polinomial, Los símbolos de "suma de comprobació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 agregan al mensaje, por lo que la palabra de código 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, imaginemos que hay dos errores de bit en la transmisión, por lo que la palabra de código recibida es [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. En notación polinómica:

${\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 calculamos los síndromes. Tomando y A continuación, aplicamos 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 que no es una sorpresa 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 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 la notación logarítmica que es independiente de los isomorfismos GF(2 ⁴ ). Para la comprobación del cálculo podemos usar la misma representación para la suma que se usó en el ejemplo anterior. 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 el 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}},}$

Nosotros conseguimos

${\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 te preocupes, busca por fuerza bruta una raíz de Las raíces son y (después de encontrarlas, por ejemplo, podemos dividir por el monoma correspondiente y la raíz del monoma resultante se puede 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 We get? ${\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}}}$

El hecho es que esto no debería sorprendernos. ${\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 un pequeño número de errores

Demostremos el comportamiento del algoritmo para el caso con un pequeño número de errores. Sea la palabra recibida [ 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}},}$

Nosotros conseguimos

${\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 que 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 son 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}.}$

Nosotros lo conseguimos

${\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 es que no debería sorprendernos. ${\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 del módulo de aterrizaje de Phobos: software y análisis" (PDF) . Archivado (PDF) desde el original el 2022-10-09 . Consultado el 25 de febrero de 2012 .
5. Marelli, Alessia; Micheloni, Rino (2018). "Códigos BCH para unidades de estado sólido". Dentro de las unidades de estado sólido (SSDS) . Springer Series in Advanced Microelectronics. Vol. 37. págs. 369–406. doi :10.1007/978-981-13-0599-3_11. ISBN 978-981-13-0598-6. Recuperado 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
• Bose, RC ; Ray-Chaudhuri, DK (marzo de 1960), "Sobre una clase de códigos de grupo binarios que corrigen errores" (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 2022-10-09

Fuentes secundarias

• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, pp. 42–45, archivado (PDF) del original el 2022-10-09 , consultado el 21 de abril de 2010^{[ enlace roto ]} Aparentemente, las notas del curso se están rehaciendo 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 de Bose-Chaudhuri con 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
• Reed, 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

Lectura adicional

• Blahut, Richard E. (2003), Códigos algebraicos para 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, NJ: Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos de corrección 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