Código BCH

En la 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 usando 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 D.K. Ray-Chaudhuri. El nombre Bose–Chaudhuri–Hocquenghem (y el acrónimo BCH) surge de las iniciales de los inventores' apellidos (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ímbolo que el código puede corregir. En particular, es posible diseñar códigos BCH binarios que puedan corregir múltiples errores de bits. Otra ventaja de los códigos BCH es la facilidad con la que pueden decodificarse, es decir, a través de un método algebraico conocido como decodificación de síndromes. 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, reproductores de discos compactos, DVD, unidades de disco, unidades flash USB, unidades de estado sólido, criptografía cuántica resistente 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 enteros positivos m y d tal 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 con el siguiente método.

Sea α un elemento primitivo de GF(q^m). Para cualquier entero positivo i, sea m_i(x) sea 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 xⁿ − 1. Por lo tanto, el código polinomial 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 ⁴) basado 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

mi()α α i)mod()z4+z+1)=0.{displaystyle m_{i}left(alpha ^{i}right){bmod {left(z^{4}+z+1right)}=0}

Los polinomios mínimos son

m1()x)=m2()x)=m4()x)=m8()x)=x4+x+1,m3()x)=m6()x)=m9()x)=m12()x)=x4+x3+x2+x+1,m5()x)=m10()x)=x2+x+1,m7()x)=m11()x)=m13()x)=m14()x)=x4+x3+1.{x}{4} {x} {x} {x}=0}

El código BCH con d=2,3{displaystyle d=2,3} ha generador polinomial

g()x)=lcm()m1()x),m2()x))=m1()x)=x4+x+1.[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.

El código BCH con d=4,5{displaystyle d=4,5} ha generador polinomial

g()x)=lcm()m1()x),m2()x),m3()x),m4()x))=m1()x)m3()x)=()x4+x+1)()x4+x3+x2+x+1)=x8+x7+x6+x4+1.{cH00} {cH00} {cH00} {cH00} {cH00}(x)}(x)}(x),m_{3}(x),m_{4}(x)=m_{1}(x}(x)}(x)7}7==cH0}

Tiene una distancia de Hamming mínima 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.

El código BCH con d=6,7{displaystyle d=6,7} ha generador polinomial

g()x)=lcm()m1()x),m2()x),m3()x),m4()x),m5()x),m6()x))=m1()x)m3()x)m5()x)=()x4+x+1)()x4+x3+x2+x+1)()x2+x+1)=x10+x8+x5+x4+x2+x+1.{x} {x} {3}(x)

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. (Este polinomio generador en particular tiene una aplicación en el mundo real, en los patrones de formato del código QR).

El código BCH con d=8{displaystyle d=8} más alto tiene polinomio generador

g()x)=lcm()m1()x),m2()x),...,m14()x))=m1()x)m3()x)m5()x)m7()x)=()x4+x+1)()x4+x3+x2+x+1)()x2+x+1)()x4+x3+1)=x14+x13+x12+⋯ ⋯ +x2+x+1.#### {x}{1}(x)}(x)}(x)}(x)}m_{3}(x)m_{5}(x)m_{7}(x)}{2}=m_{1}(x) +x^{2}+x+1.end{aligned}}

Este código tiene una distancia Hamming mínima de 15 y corrige 7 errores. Tiene 1 bit de datos y 14 bits de suma de comprobación. De hecho, este código tiene solo dos palabras clave: 000000000000000 y 111111111111111.

Códigos BCH generales

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

Primero, el requisito de que α α {displaystyle alpha } ser un elemento primitivo GF()qm){displaystyle mathrm {GF} (q^{m}} se puede relajar. Al relajar este requisito, la longitud del código cambia de qm− − 1{displaystyle q^{m}-1} a ord()α α ),{displaystyle mathrm {ord} (alpha),} el orden del elemento α α .{displaystyle alpha.}

En segundo lugar, las raíces consecutivas del polinomio generador pueden correr desde α α c,...... ,α α c+d− − 2{displaystyle alpha ^{c},ldotsalpha ^{c+d-2} en lugar de α α ,...... ,α α d− − 1.{displaystyle alphaldotsalpha ^{d-1}

Definición. Arreglar un campo finito GF()q),{displaystyle GF(q),} Donde q{displaystyle q} es un poder primario. Elija números enteros positivos m,n,d,c{displaystyle m,n,d,c} tales que 2≤ ≤ d≤ ≤ n,{displaystyle 2leq dleq n,} gcd()n,q)=1,{displaystyle {rm {gcd}(n,q)=1,} y m{displaystyle m} es el orden multiplicativo q{displaystyle q} modulo n.{displaystyle n.}

Como antes, deja α α {displaystyle alpha } ser un primitivo n{displaystyle n}raíz de la unidad dentro GF()qm),{displaystyle GF(q^{m}),} y dejar mi()x){displaystyle m_{i}(x)} ser el mínimo polinomio sobre GF()q){displaystyle GF(q)} de α α i{displaystyle alpha ^{i} para todos i.{displaystyle i.}El polinomio generador del código BCH se define como el múltiple menos común g()x)=lcm()mc()x),...... ,mc+d− − 2()x)).{displaystyle g(x)={rm {lcm} {m_{c}(x),ldotsm_{c+d-2}(x)). }

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

Casos especiales

• Un código BCH con c=1{displaystyle c=1} se llama código BCH de sentido estrecho.
• Un código BCH con n=qm− − 1{displaystyle n=q^{m}-1} se llama primitivo.

El polinomio del generador g()x){displaystyle g(x)} de un código BCH tiene coeficientes de GF()q).{displaystyle mathrm {GF} (q).}En general, un código cíclico sobre GF()qp){displaystyle mathrm {GF} (q^{p}} con g()x){displaystyle g(x)} como el polinomio del generador se llama código BCH GF()qp).{displaystyle mathrm {GF} (q^{p}).}El código BCH sobre GF()qm){displaystyle mathrm {GF} (q^{m}} y el polinomio generador g()x){displaystyle g(x)} con poderes sucesivos α α {displaystyle alpha } como raíces es un tipo de código Reed-Solomon donde el decodificador (syndromes) alfabeto es el mismo que el canal (datos y generador polinomial) alfabeto, todos los elementos GF()qm){displaystyle mathrm {GF} (q^{m}}. El otro tipo de código Reed Solomon es una vista original Código Reed Solomon que no es un código BCH.

Propiedades

El polinomio generador de un código BCH tiene grado en la mayoría ()d− − 1)m{displaystyle (d-1)m}. Además, si q=2{displaystyle q=2} y c=1{displaystyle c=1}, el polinomio generador tiene grado en la mayoría dm/2{displaystyle dm/2}.

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

Un código BCH es cíclico.

Codificación

Debido a que cualquier polinomio que sea un 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í mismo 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 un código sistemático o no, dependiendo de cómo el implementador elija incorporar 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 un múltiplo del generador es calcular el producto de algún polinomio arbitrario y el generador. En este caso, el polinomio arbitrario se puede elegir utilizando los símbolos del mensaje como coeficientes.

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

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

p()x)=x20+x18+x17+x15+x14+x13+x11+x10+x9+x8+x6+x5+x4+x3+x2+1{x}+x^{6}+x^{4}+x}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x}}+x^{9}+x}}+x^{8}+x^{6}+x^{5}+x^{4}+0}+x^{2}}+0}+0}}}+x}}}}}+x^}}}}+0}+0}+0}+x^{2}}}}}}}}}+x}+x^{4}

Entonces, computar (también encima) GF()2){displaystyle GF(2)}):

s()x)=p()x)g()x)=()x20+x18+x17+x15+x14+x13+x11+x10+x9+x8+x6+x5+x4+x3+x2+1)()x10+x9+x8+x6+x5+x3+1)=x30+x29+x26+x25+x24+x22+x19+x17+x16+x15+x14+x12+x10+x9+x8+x6+x5+x4+x2+1# {x} {x}}

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

El receptor puede utilizar estos bits como coeficientes en s()x){displaystyle s(x)} y, después de la corrección de error para asegurar una palabra clave válida, puede recomputar p()x)=s()x)/g()x){displaystyle p(x)=s(x)/g(x)}

Codificación sistemática: El mensaje como prefijo

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

Este método de codificación aprovecha el hecho de que restar el resto de un dividendo resulta en un múltiplo del divisor. Por lo tanto, si tomamos nuestro mensaje polinomio p()x){displaystyle p(x)} como antes y multiplicarlo xn− − k{displaystyle x^{n-k} (para "esquivar" el mensaje fuera del camino del resto), podemos entonces utilizar la división Euclideana de los polinomios para producir:

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

Aquí, vemos que q()x)g()x){displaystyle q(x)g(x)} es una palabra clave válida. As r()x){displaystyle r(x)} es siempre de grado menos que n− − k{displaystyle No. (que es el grado de g()x){displaystyle g(x)}), podemos restarla de forma segura p()x)xn− − k{displaystyle p(x)x^{n-k} sin alterar ninguno de los coeficientes de mensaje, por lo tanto tenemos nuestros s()x){displaystyle s(x)} como

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

Cambio GF()2){displaystyle GF(2)} (es decir, con códigos BCH binarios), este proceso es indistinguible a partir de un cheque de redundancia cíclica, y si un código BCH binario sistemático se utiliza sólo para propósitos de error-detección, vemos que los códigos BCH son sólo una generalización de las matemáticas de cheques de redundancia cíclica.

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

Decodificación

Hay 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) de los síndromes
3. Calcular las raíces de la ubicación de error polinomial para encontrar las ubicaciones de error X_i
4. Calcular los valores de error Y_i en esas ubicaciones de errores
5. Corregir 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 R{displaystyle R. es la suma de la palabra clave correcta C{displaystyle C} y un vector de error desconocido E.{displaystyle E.} Los valores del síndrome se forman considerando R{displaystyle R. como un polinomio y evaluarlo α α c,...... ,α α c+d− − 2.{displaystyle alpha ^{c},ldotsalpha ^{c+d-2} Así los síndromes son

sj=R()α α j)=C()α α j)+E()α α j){displaystyle s_{j}=Rleft(alpha ^{j}right)=Cleft(alpha ^{j}right)+Eleft(alpha ^{j}right)}

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

Desde α α j{displaystyle alpha ^{j} son los ceros de g()x),{displaystyle g(x),} de los cuales C()x){displaystyle C(x)} es un múltiple, C()α α j)=0.{displaystyle Cleft(alpha ^{j}right)=0.} Examinar los valores del síndrome por lo tanto aisla el vector de error para que uno pueda comenzar a resolver por él.

Si no hay error, sj=0{displaystyle s_{j}=0} para todos j.{displaystyle J. Si los síndromes son todos cero, entonces se hace la decodificación.

Calcular el polinomio de ubicación del error

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

Si hay un solo error, escriba esto como E()x)=exi,{displaystyle E(x)=e,x^{i},} Donde i{displaystyle i} es la ubicación del error y e{displaystyle e} es su magnitud. Entonces los primeros dos síndromes son

sc=eα α cisc+1=eα α ()c+1)i=α α isc{fnMicrosoft Sans Serif} ^{c,i}s_{c+1}e,alpha ^{(c+1),i}=alpha ^{i}s_{c}end{aligned}}

así que juntos nos permiten calcular e{displaystyle e} y proporcionar información sobre i{displaystyle i} (determinándolo completamente en el caso de los códigos Reed-Solomon).

Si hay dos o más errores,

E()x)=e1xi1+e2xi2+⋯ ⋯ {displaystyle E(x)=e_{1}x^{i_{1}+e_{2}x^{i_{2}}+cdots ,}

No es inmediatamente obvio cómo comenzar a resolver los síndromes resultantes para los desconocidos ek{displaystyle E_{k} y ik.{displaystyle Yo...

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

▪ ▪ ()x)=∏ ∏ j=1t()xα α ij− − 1){displaystyle Lambda (x)=prod _{j=1}left(xalpha) - Sí.

Tres algoritmos populares para esta tarea son:

1. Peterson–Gorenstein–Zierler algoritmo
2. algoritmo de Berlekamp-Massey
3. Sugiyama Euclidean algoritmo

Algoritmo de Peterson-Gorenstein-Zierler

El algoritmo de Peterson es el paso 2 del procedimiento generalizado de decodificación de BCH. El algoritmo de Peterson se utiliza para calcular los coeficientes polinomios localizadores de errores λ λ 1,λ λ 2,...... ,λ λ v{displaystyle lambda _{1},lambda ################################################################################################################################################################################################################################################################ ¿Qué? de un polinomio

▪ ▪ ()x)=1+λ λ 1x+λ λ 2x2+⋯ ⋯ +λ λ vxv.{displaystyle Lambda (x)=1+lambda _{1}x+lambda ##{2}x^{2}+cdots +lambda _{v}x^{v}

Ahora el procedimiento del algoritmo Peterson-Gorenstein-Zierler. Esperemos que tengamos al menos 2 t síndromes s_c, …, s_c+2t−1. Sea v = t.

Factor de polinomio localizador de errores

Ahora que tienes el ▪ ▪ ()x){displaystyle Lambda (x)} polinomio, sus raíces se pueden encontrar en la forma ▪ ▪ ()x)=()α α i1x− − 1)()α α i2x− − 1)⋯ ⋯ ()α α ivx− − 1){displaystyle Lambda (x)=left(alpha ^{i_{1}x-1right)left(alpha ^{i_{2}x-1right)cdots left(alpha ^{i_{i_{i}x-1right)}} por fuerza bruta, por ejemplo, usando el algoritmo de búsqueda Chien. El exponencial poderes del elemento primitivo α α {displaystyle alpha } cederá las posiciones en las que ocurren errores en la palabra recibida; por lo tanto el nombre de polinomio "contrator del terrorismo".

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

Calcular valores de error

Una vez que se conocen las ubicaciones de error, 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 voltear los bits para la palabra recibida en estas posiciones, y tenemos la palabra clave corregida. En el caso más general, el peso del error ej{displaystyle E_{j} puede determinarse resolviendo el sistema lineal

sc=e1α α ci1+e2α α ci2+⋯ ⋯ sc+1=e1α α ()c+1)i1+e2α α ()c+1)i2+⋯ ⋯ ⋮ ⋮ {displaystyle {begin{aligned}s_{c} ^{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 \ {}\cdots end{aligned}}}}}}}}}}

Algoritmo de Forney

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

Dejar

S()x)=sc+sc+1x+sc+2x2+⋯ ⋯ +sc+d− − 2xd− − 2.{displaystyle S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+cdots +s_{c+d-2}x^{d-2}

v⩽ ⩽ d− − 1,λ λ 0ل ل 0▪ ▪ ()x)=.. i=0vλ λ ixi=λ λ 0∏ ∏ k=0v()α α − − ikx− − 1).{displaystyle vleqslant d-1,lambda ¿Qué? Lambda (x)=sum ################################################################################################################################################################################################################################################################ ################################################################################################################################################################################################################################################################ ¿Qué? ################################################################################################################################################################################################################################################################ ^{-i_{k}x-1right).}

Y el polinomio evaluador de errores

Ω Ω ()x)↑ ↑ S()x)▪ ▪ ()x)modxd− − 1{displaystyle Omega (x)equiv S(x)Lambda (x){bmod {x^{d-1}}}

Por último:

▪ ▪ .()x)=.. i=1vi⋅ ⋅ λ λ ixi− − 1,{displaystyle Lambda '(x)=sum ##{i=1} {v}icdot lambda ¿Qué?

dónde

i⋅ ⋅ x:=.. k=1ix.{displaystyle icdot x:=sum ¿Qué?

Que si los síndromes pueden ser explicados por una palabra de error, que podría ser no cero solamente en posiciones ik{displaystyle i_{k}, entonces los valores de error son

ek=− − α α ikΩ Ω ()α α − − ik)α α c⋅ ⋅ ik▪ ▪ .()α α − − ik).{displaystyle E_{k}=-{alpha ^{i_{k} Omega left(alpha ^{-i_{k}right) over alpha ^{ccdot "Lambda" Bien.

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

ek=− − Ω Ω ()α α − − ik)▪ ▪ .()α α − − ik).{displaystyle E_{k}=-{ Omega left(alpha ^{-i_{k}right) over Lambda 'left(alpha Bien.

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.

Considerar S()x)▪ ▪ ()x),{displaystyle S(x)Lambda (x),} y por el bien de la sencillez suponen λ λ k=0{displaystyle lambda ¿Qué? para v,}" xmlns="http://www.w3.org/1998/Math/MathML">k■v,{displaystyle k confianzav,}v,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b71b48e1c6af649e1a1c0a4ebbb91474bc57bb6d" style="vertical-align: -0.671ex; width:6.084ex; height:2.509ex;"/> y sk=0{displaystyle S_{k}=0} para c+d-2.}" xmlns="http://www.w3.org/1998/Math/MathML">k■c+d− − 2.{displaystyle k]c+d-2.}c+d-2.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b76aaf9e3b51e2b9c836d4859012e71f19b8407" style="vertical-align: -0.505ex; width:14.023ex; height:2.343ex;"/> Entonces...

S()x)▪ ▪ ()x)=.. j=0JUEGO JUEGO .. i=0jsj− − i+1λ λ ixj.{displaystyle S(x)Lambda (x)=sum _{j=0}{infty }sum ################################################################################################################################################################################################################################################################ _{i}x^{j}

S()x)▪ ▪ ()x)=S()x){}λ λ 0∏ ∏ l l =1v()α α il l x− − 1)}={}.. i=0d− − 2.. j=1vejα α ()c+i)⋅ ⋅ ijxi}{}λ λ 0∏ ∏ l l =1v()α α il l x− − 1)}={}.. j=1vejα α cij.. i=0d− − 2()α α ij)ixi}{}λ λ 0∏ ∏ l l =1v()α α il l x− − 1)}={}.. j=1vejα α cij()xα α ij)d− − 1− − 1xα α ij− − 1}{}λ λ 0∏ ∏ l l =1v()α α il l x− − 1)}=λ λ 0.. j=1vejα α cij()xα α ij)d− − 1− − 1xα α ij− − 1∏ ∏ l l =1v()α α il l x− − 1)=λ λ 0.. j=1vejα α cij()()xα α ij)d− − 1− − 1)∏ ∏ l l ▪ ▪ {}1,⋯ ⋯ ,v}∖ ∖ {}j}()α α il l x− − 1){displaystyle {begin{aligned}S(x)Lambda (x) limit=S(x)left{lambda ¿Por qué? ¿Qué? {fnMicrosoft Sans Serif}* ¿Por qué? {fnMicrosoft Sans Serif} ^{ci_{j}sum - ¿Por qué? ¿Qué? ¿Por qué? =1}{v}left(alpha ^{i_{ell }x-1right)right}=left{sum {fnMicrosoft Sans Serif} ^{ci_{j}{frac {left(xalpha ¿Qué? Está bien. ¿Por qué? ################################################################################################################################################################################################################################################################ ¿Por qué? ^{ci_{j}{frac {left(xalpha ¿Qué? ^{i_{j}}prod _{ell =1}left(alpha ^{i_{i_ell }x-1right)\\fnMicrosoft Sans Serif} ¿Por qué? ^{ci_{j}left(left(xalpha) ¿Qué? _{ell in {1,cdotsv}setminus {j}left(alpha) ^{i_{ell }x-1right)end{aligned}

Queremos calcular desconocidos ej,{displaystyle e_{j},} y podríamos simplificar el contexto eliminando el ()xα α ij)d− − 1{displaystyle left(xalpha ¿Qué? términos. Esto lleva al evaluador de errores polinomial

Ω Ω ()x)↑ ↑ S()x)▪ ▪ ()x)modxd− − 1.{displaystyle Omega (x)equiv S(x)Lambda (x){bmod {x^{d-1}}}}

Gracias v⩽ ⩽ d− − 1{displaystyle vleqslant d-1} tenemos

Ω Ω ()x)=− − λ λ 0.. j=1vejα α cij∏ ∏ l l ▪ ▪ {}1,⋯ ⋯ ,v}∖ ∖ {}j}()α α il l x− − 1).{displaystyle Omega (x)=-lambda ¿Qué? {fnMicrosoft Sans Serif} ^{ci_{j}prod _{ell in {1,cdotsv}setminus {j}}left(alpha ^{i_{ell }x-1right). }

Gracias ▪ ▪ {displaystyle Lambda } (el truco de interpolación de Lagrange) la suma degenera a sólo un summand para x=α α − − ik{displaystyle x=alpha ^{-i_{k}}

Ω Ω ()α α − − ik)=− − λ λ 0ekα α c⋅ ⋅ ik∏ ∏ l l ▪ ▪ {}1,⋯ ⋯ ,v}∖ ∖ {}k}()α α il l α α − − ik− − 1).{displaystyle Omega left(alpha ^{-i_{k}right)=-lambda ### {0}e_{k}alpha ^{ccdot i_{k}prod _{ell in {1,cdotsv}setminus {k}left(alpha) Alfa - Sí.

Para conseguir ek{displaystyle E_{k} Deberíamos deshacernos del producto. Podríamos calcular el producto directamente de raíces ya calculadas α α − − ij{displaystyle alpha ^{-i_{j}} de ▪ ▪ ,{displaystyle Lambda} pero podríamos usar una forma más simple.

Como derivada formal

▪ ▪ .()x)=λ λ 0.. j=1vα α ij∏ ∏ l l ▪ ▪ {}1,⋯ ⋯ ,v}∖ ∖ {}j}()α α il l x− − 1),{displaystyle Lambda '(x)=lambda ¿Por qué? ^{i_{j}prod ¿Por qué?

obtenemos nuevamente solo un sumando en

▪ ▪ .()α α − − ik)=λ λ 0α α ik∏ ∏ l l ▪ ▪ {}1,⋯ ⋯ ,v}∖ ∖ {}k}()α α il l α α − − ik− − 1).{displaystyle Lambdaleft(alfa ^{-i_{k}right)=lambda ¿Qué? ^{i_{k}prod _{ell in {1,cdotsv}setminus {k}left(alpha) Alfa - Sí.

Así que finalmente

ek=− − α α ikΩ Ω ()α α − − ik)α α c⋅ ⋅ ik▪ ▪ .()α α − − ik).{displaystyle E_{k}=-{frac {Alpha ^{i_{k} Omega left(alpha {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}} {fnMicrosoft Sans Serif}} {fnMicrosoft Sans Serif} ^{ccdot i_{k} Lambda 'left(alpha) Sí.

Esta fórmula es ventajosa cuando se calcula el derivado formal de ▪ ▪ {displaystyle Lambda } forma

▪ ▪ ()x)=.. i=1vλ λ ixi{displaystyle Lambda (x)=sum ###{i=1} {v}lambda ¿Qué?

produciendo:

▪ ▪ .()x)=.. i=1vi⋅ ⋅ λ λ ixi− − 1,{displaystyle Lambda '(x)=sum ##{i=1} {v}icdot lambda ¿Qué?

dónde

i⋅ ⋅ x:=.. k=1ix.{displaystyle icdot x:=sum ¿Qué?

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. La corrección de caracteres ilegibles también podría incorporarse fácilmente al algoritmo.

Vamos k1,...,kk{displaystyle K_{1},... k_{k} ser posiciones de caracteres imparables. Uno crea polinomio localizando estas posiciones .. ()x)=∏ ∏ i=1k()xα α ki− − 1).{displaystyle Gamma (x)=prod ¿Por qué? - Sí.Fijar valores en posiciones no legibles a 0 y calcular los síndromes.

Como ya hemos definido para la fórmula Forney S()x)=.. i=0d− − 2sc+ixi.{displaystyle S(x)=sum ¿Qué?

Vamos a ejecutar algoritmo Euclideano extendido para localizar menos divisor común de polinomios S()x).. ()x){displaystyle S(x)Gamma (x)} y xd− − 1.{displaystyle x^{d-1}El objetivo no es encontrar el divisor menos común, sino un polinomio r()x){displaystyle r(x)} de grado en la mayoría ⌊ ⌊ ()d+k− − 3)/2⌋ ⌋ {displaystyle lfloor (d+k-3)/2rfloor } y polinomios a()x),b()x){displaystyle a(x),b(x)} tales que r()x)=a()x)S()x).. ()x)+b()x)xd− − 1.{displaystyle r(x)=a(x)S(x)Gamma (x)+b(x)x^{d-1}Bajo grado de r()x){displaystyle r(x)} garantías, que a()x){displaystyle a(x)} satisfaría la prórroga (por .. {displaystyle "Gamma") las condiciones para definir ▪ ▪ .{displaystyle Lambda.}

Definición Ξ Ξ ()x)=a()x).. ()x){displaystyle Xi (x)=a(x)Gamma (x)} y uso Ξ Ξ {displaystyle Xi} en el lugar de ▪ ▪ ()x){displaystyle Lambda (x)} en la fórmula Fourney nos dará valores de error.

La principal ventaja del algoritmo es que mientras tanto computa Ω Ω ()x)=S()x)Ξ Ξ ()x)modxd− − 1=r()x){displaystyle Omega (x)=S(x)Xi (x){bmod {x}^{d-1}=r(x)} requerido en la fórmula Forney.

Explicación del proceso de decodificación

El objetivo es encontrar una palabra clave que difiere de la palabra recibida mínimamente como sea posible en posiciones legibles. Al expresar la palabra recibida como una suma de palabra clave más cercana y palabra de error, estamos tratando de encontrar palabra de error con un número mínimo de no-zeros en posiciones legibles. Síndrome si{displaystyle S_{i} restringe palabra de error por condición

si=.. j=0n− − 1ejα α ij.{displaystyle S_{i}=sum ################################################################################################################################################################################################################################################################ ^{ij}

Podríamos escribir estas condiciones por separado o podríamos crear un polinomio

S()x)=.. i=0d− − 2sc+ixi{displaystyle S(x)=sum ¿Qué?

y comparar coeficientes cerca de poderes 0{displaystyle 0} a d− − 2.{displaystyle d-2.}

S()x)={}0,⋯ ⋯ ,d− − 2}E()x)=.. i=0d− − 2.. j=0n− − 1ejα α ijα α cjxi.{fnMicrosoft Sans Serif}E(x)=sum - ¿Qué? ################################################################################################################################################################################################################################################################ ^{ij}alpha ^{cj}x^{i}

Supongamos que no hay carta legible en posición k1,{displaystyle k_{1},} podríamos sustituir el conjunto de síndromes {}sc,⋯ ⋯ ,sc+d− − 2}{displaystyle ¿Qué? por conjunto de síndromes {}tc,⋯ ⋯ ,tc+d− − 3}{displaystyle {t_{c},cdotst_{c+d-3}} definida por ecuación ti=α α k1si− − si+1.{displaystyle T_{i}=alpha ^{k_{1}s_{i}-s_{i+1} Suponga para una palabra de error todas las restricciones por conjunto original {}sc,⋯ ⋯ ,sc+d− − 2}{displaystyle ¿Qué? de síndromes mantener, que

ti=α α k1si− − si+1=α α k1.. j=0n− − 1ejα α ij− − .. j=0n− − 1ejα α jα α ij=.. j=0n− − 1ej()α α k1− − α α j)α α ij.{displaystyle T_{i}=alpha ^{k_{1}s_{i}-s_{i+1}=alpha ^{k_{1}sum ################################################################################################################################################################################################################################################################ ^{ij}-sum ################################################################################################################################################################################################################################################################ ^{j}alpha ^{ij}=sum - ¿Por qué? Alfa ^{ij}

Nuevo conjunto de síndromes restringe el vector de error

fj=ej()α α k1− − α α j){displaystyle F_{j}=e_{j}left(alpha) ¿Qué?

de la misma manera el conjunto original de síndromes restringió el vector de error ej.{displaystyle E_{j}. Excepto la coordenadas k1,{displaystyle k_{1},} donde tenemos fk1=0,{displaystyle ¿Qué? an fj{displaystyle f_{j} es cero, si ej=0.{displaystyle e_{j}=0} Para el objetivo de localizar posiciones de error podríamos cambiar el conjunto de síndromes de la manera similar para reflejar todos los caracteres no legibles. Esto acorta el conjunto de síndromes por k.{displaystyle k.}

En la formulación polinomio, la sustitución de los síndromes establecidos {}sc,⋯ ⋯ ,sc+d− − 2}{displaystyle ¿Qué? por síndromes establecidos {}tc,⋯ ⋯ ,tc+d− − 3}{displaystyle {t_{c},cdotst_{c+d-3}} conduce a

T()x)=.. i=0d− − 3tc+ixi=α α k1.. i=0d− − 3sc+ixi− − .. i=1d− − 2sc+ixi− − 1.{displaystyle T(x)=sum ##{i=0} {d-3}t_{c+i}x^{i}=alpha ^{k_{1}sum ¿Por qué? ¿Qué?

Por lo tanto,

xT()x)={}1,⋯ ⋯ ,d− − 2}()xα α k1− − 1)S()x).{displaystyle xT(x){stackrel {fnMicrosoft Sans Serif}left(xalpha) ^{k_{1}-1right)S(x). }

Después de la sustitución de S()x){displaystyle S(x)} por S()x).. ()x){displaystyle S(x)Gamma (x)}, uno requeriría ecuación para coeficientes cerca de poderes k,⋯ ⋯ ,d− − 2.{displaystyle k,cdotsd-2.}

Uno podría considerar la búsqueda de posiciones de error desde el punto de vista de eliminar la influencia de posiciones dadas de forma similar a los caracteres no legibles. Si encontramos v{displaystyle v} posiciones tales que eliminar su influencia conduce a la obtención de un conjunto de síndromes consistentes en todos los ceros, que existe un vector de error con errores solamente en estas coordenadas. Si ▪ ▪ ()x){displaystyle Lambda (x)} denota el polinomio eliminando la influencia de estas coordenadas, obtenemos

S()x).. ()x)▪ ▪ ()x)={}k+v,⋯ ⋯ ,d− − 2}0.{displaystyle S(x)Gamma (x)Lambda (x){stackrel {cK+v,cdotsd-2} {=}0}

En el algoritmo de Euclidean, intentamos corregir a la mayoría 12()d− − 1− − k){displaystyle {tfrac {1}{2}(d-1-k)} errores (en posiciones legibles), porque con mayor cuenta de errores podría haber más codewords en la misma distancia de la palabra recibida. Por tanto, ▪ ▪ ()x){displaystyle Lambda (x)} estamos buscando, la ecuación debe mantener para coeficientes cerca de poderes a partir de

k+⌊12()d− − 1− − k)⌋.{displaystyle k+leftlfloor {frac} {2}(d-1-k)rightrfloor.}

En la fórmula Forney, ▪ ▪ ()x){displaystyle Lambda (x)} podría ser multiplicado por un escalar dando el mismo resultado.

Podría suceder que el algoritmo de Euclidea encuentre ▪ ▪ ()x){displaystyle Lambda (x)} de grado superior a 12()d− − 1− − k){displaystyle {tfrac {1}{2}(d-1-k)} tener un número de raíces diferentes iguales a su grado, donde la fórmula Fourney sería capaz de corregir errores en todas sus raíces, de todos modos corregir tales errores podría ser arriesgado (especialmente sin otras restricciones a la palabra recibida). Por lo general después de llegar ▪ ▪ ()x){displaystyle Lambda (x)} de mayor grado, decidimos no corregir los errores. La corrección podría fallar en el caso ▪ ▪ ()x){displaystyle Lambda (x)} tiene raíces con mayor multiplicidad o el número de raíces es menor que su grado. El fracaso también podría ser detectado por la fórmula Forney que devuelve el error fuera del alfabeto transmitido.

Corrige los errores

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

Ejemplos de decodificación

Decodificación de código binario sin caracteres ilegibles

Considere un código BCH en GF(2⁴Con d=7{displaystyle d=7} y g()x)=x10+x8+x5+x4+x2+x+1{displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}. (Esto se utiliza en códigos QR.) Que el mensaje sea transmitido [1 1 0 1 1], o en notación polinómica, M()x)=x4+x3+x+1.{displaystyle M(x)=x^{4}+x^{3}+x+1.}Los símbolos "checksum" se calculan dividiendo x10M()x){displaystyle x^{10}M(x)} por g()x){displaystyle g(x)} y tomando el resto, resultando en x9+x4+x2{displaystyle x^{9}+x^{4}+x^{2} o [ 1 0 0 0 0 1 0 0 ]. Se adjuntan al mensaje, por lo que la palabra clave transmitida es [ 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 ].

Ahora, imagine que hay dos errores de bit 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:

R()x)=C()x)+x13+x5=x14+x11+x10+x9+x5+x4+x2{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 calcula los síndromes. Tomando α α =0010,{displaystyle alpha =0010,} tenemos s1=R()α α 1)=1011,{displaystyle S_{1}=R(alpha ^{1})=1011,} s2=1001,{displaystyle s_{2}=1001,} s3=1011,{displaystyle s_{3}=1011,} s4=1101,{displaystyle s_{4}=1101,} s5=0001,{displaystyle s_{5}=0001,} y s6=1001.{displaystyle s_{6}=1001.}A continuación, aplicar el procedimiento de Peterson reduciendo la siguiente matriz aumentada.

[S3× × 3SilencioC3× × 1]=[s1s2s3s4s2s3s4s5s3s4s5s6]=[101110011011110110011011110100011011110100011001]⇒ ⇒ [000100001000011100000001101100010000000000000000]{displaystyle left[S_{3times ################################################################################################################################################################################################################################################################ {begin{bmatrix}0001 ventaja0000 recíproca0111000 recíproca0001⁄41010003000 Puls0000 pén0000 pén0000 péndulo.}

Debido a la fila cero, S_3×3 es singular, que no es ninguna sorpresa ya que sólo dos errores fueron introducidos en la palabra clave. Sin embargo, la esquina superior izquierda de la matriz es idéntica a [S_2×2 Silencio C_2×1], que da lugar a la solución λ λ 2=1000,{displaystyle lambda _{2}=1000,} λ λ 1=1011.{displaystyle lambda _{1}=1011.}El localizador de errores resultante polinomial es ▪ ▪ ()x)=1000x2+1011x+0001,{displaystyle Lambda (x)=1000x^{2}+1011x+0001,} que tiene ceros 0100=α α − − 13{displaystyle 0100=alpha ^{-13} y 0111=α α − − 5.{displaystyle 0111=alpha ^{-5}Los exponentes de α α {displaystyle alpha } corresponden a las ubicaciones de errores. No hay necesidad de calcular los valores de error en este ejemplo, ya que el único valor posible es 1.

Decodificación con caracteres ilegibles

Supongamos el mismo escenario, pero la palabra recibida tiene dos caracteres imparables [ 1 0 0 1 0 1 1 0 0 0 ]. Reemplazamos los caracteres no legibles por ceros mientras creamos el polinomio que refleja sus posiciones .. ()x)=()α α 8x− − 1)()α α 11x− − 1).{displaystyle Gamma (x)=left(alpha ^{8}x-1right)left(alpha ^{11}x-1right). } Computamos los síndromes s1=α α − − 7,s2=α α 1,s3=α α 4,s4=α α 2,s5=α α 5,{displaystyle S_{1}=alpha ^{-7},s_{2}=alpha ^{1},s_{3}=alpha ^{4},s_{4}=alpha ^{2},s_{5}=alpha ^{5} y s6=α α − − 7.{displaystyle S_{6}=alpha ^{-7} (Usando notación de registro que es independiente en GF(2⁴) isomorfismos. Para la comprobación de cálculo podemos utilizar la misma representación para adición que se utilizó en el ejemplo anterior. Descripción hexadecimal de los poderes de α α {displaystyle alpha } son sucesivamente 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 con la adición basado en xor bitwise.)

Hagamos polinomio del síndrome

S()x)=α α − − 7+α α 1x+α α 4x2+α α 2x3+α α 5x4+α α − − 7x5,{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

S()x).. ()x)=α α − − 7+α α 4x+α α − − 1x2+α α 6x3+α α − − 1x4+α α 5x5+α α 7x6+α α − − 3x7.{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:

( S ( x ) Γ ( x ) x 6 ) = ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 + α 7 x 6 + α − 3 x 7 x 6 ) = ( α 7 + α − 3 x 1 1 0 ) ( x 6 α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 + 2 α 7 x 6 + 2 α − 3 x 7 ) = ( α 7 + α − 3 x 1 1 0 ) ( α 4 + α − 5 x 1 1 0 ) ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 α − 3 + ( α − 7 + α 3 ) x + ( α 3 + α − 1 ) x 2 + ( α − 5 + α − 6 ) x 3 + ( α 3 + α 1 ) x 4 + 2 α − 6 x 5 + 2 x 6 ) = ( ( 1 + α − 4 ) + ( α 1 + α 2 ) x + α 7 x 2 α 7 + α − 3 x α 4 + α − 5 x 1 ) ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 ) = ( α − 3 + α 5 x + α 7 x 2 α 7 + α − 3 x α 4 + α − 5 x 1 ) ( α − 5 + α − 4 x 1 1 0 ) ( α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 ( α 7 + α − 7 ) + ( 2 α − 7 + α 4 ) x + ( α − 5 + α − 6 + α − 1 ) x 2 + ( α − 7 + α − 4 + α 6 ) x 3 + ( α 4 + α − 6 + α − 1 ) x 4 + 2 α 5 x 5 ) = ( α 7 x + α 5 x 2 + α 3 x 3 α − 3 + α 5 x + α 7 x 2 α 3 + α − 5 x + α 6 x 2 α 4 + α − 5 x ) ( α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 α − 4 + α 4 x + α 2 x 2 + α − 5 x 3 ) . {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&0end{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}+2alpha ^{7}x^{6}+2alpha ^{-3}x^{7}end{pmatrix}}\[6pt]={}&{begin{pmatrix}alpha ^{7}+alpha ^{-3}x&1\1&0end{pmatrix}}{begin{pmatrix}alpha ^{4}+alpha ^{-5}x&1\1&0end{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}+2alpha ^{-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&1end{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&1end{pmatrix}}{begin{pmatrix}alpha ^{-5}+alpha ^{-4}x&1\1&0end{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(2alpha ^{-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}+2alpha ^{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}xend{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 llegado al polinomio de grado máximo 3, y como

()− − ()α α 4+α α − − 5x)α α − − 3+α α 5x+α α 7x2α α 3+α α − − 5x+α α 6x2− − ()α α 7x+α α 5x2+α α 3x3))()α α 7x+α α 5x2+α α 3x3α α − − 3+α α 5x+α α 7x2α α 3+α α − − 5x+α α 6x2α α 4+α α − − 5x)=()1001),{displaystyle {begin{pmatrix}-left(alpha) ^{4}+alpha ^{-5}xright) ^{7}x^{2}\alpha ^{3}+alpha ^{-5}x+alpha ^{6}x^{2} ventaja-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} ^{-3}+alpha ^{5}x+alpha ^{7}x^{2}\alpha ^{3}+alpha ^{-5}x+alpha ^{6}x^{2} ^{-5}xend{pmatrix}={begin{pmatrix}1 limit0 limit1end{pmatrix}}}}

obtenemos

()− − ()α α 4+α α − − 5x)α α − − 3+α α 5x+α α 7x2α α 3+α α − − 5x+α α 6x2− − ()α α 7x+α α 5x2+α α 3x3))()S()x).. ()x)x6)=()α α − − 3+α α − − 2x+α α 0x2+α α − − 2x3+α α − − 6x4α α − − 4+α α 4x+α α 2x2+α α − − 5x3).{displaystyle {begin{pmatrix}-left(alpha) ^{4}+alpha ^{-5}xright) ^{7}x^{2}\alpha ^{3}+alpha ^{-5}x+alpha ^{6}x^{2} ventaja-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,

S()x).. ()x)()α α 3+α α − − 5x+α α 6x2)− − ()α α 7x+α α 5x2+α α 3x3)x6=α α − − 4+α α 4x+α α 2x2+α α − − 5x3.{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}

Vamos ▪ ▪ ()x)=α α 3+α α − − 5x+α α 6x2.{displaystyle Lambda (x)=alpha ^{3}+alpha ^{-5}x+alpha ^{6}x^{2} No te preocupes. λ λ 0ل ل 1.{displaystyle lambda _{0}neq 1.} Encontrar por fuerza bruta una raíz de ▪ ▪ .{displaystyle Lambda.} Las raíces son α α 2,{displaystyle alpha ^{2} y α α 10{displaystyle alpha ^{10} (después de encontrar por ejemplo α α 2{displaystyle alpha ^{2} podemos dividir ▪ ▪ {displaystyle Lambda } por monom ()x− − α α 2){displaystyle left(x-alpha ^{2}right)} y la raíz del monom resultante se puede encontrar fácilmente).

Dejar

Ξ Ξ ()x)=.. ()x)▪ ▪ ()x)=α α 3+α α 4x2+α α 2x3+α α − − 5x4Ω Ω ()x)=S()x)Ξ Ξ ()x)↑ ↑ α α − − 4+α α 4x+α α 2x2+α α − − 5x3modx6{displaystyle {begin{aligned}Xi (x) recur=Gamma (x)Lambda (x)=alpha ^{3}+alpha ^{4}x^{2}+alpha ^{2}x^{3}+alpha ^{-5}x^{4}\\Omega (x) recur=S(x)Xi (x)equiv alpha ^{-4}+alpha ^{4}x+alpha ^{2}x^{2}+alpha ¿Qué?

Busquemos valores de error usando la fórmula

ej=− − Ω Ω ()α α − − ij)Ξ Ξ .()α α − − ij),{displaystyle E_{j}=-{frac {Omega left(alfa ¿Qué? Xi 'left(alpha) - Sí.

Donde α α − − ij{displaystyle alpha ^{-i_{j}} son raíces de Ξ Ξ ()x).{displaystyle Xi (x). } Ξ Ξ .()x)=α α 2x2.{displaystyle Xi '(x)=alpha ^{2}x^{2} Tenemos

e1=− − Ω Ω ()α α 4)Ξ Ξ .()α α 4)=α α − − 4+α α − − 7+α α − − 5+α α 7α α − − 5=α α − − 5α α − − 5=1e2=− − Ω Ω ()α α 7)Ξ Ξ .()α α 7)=α α − − 4+α α − − 4+α α 1+α α 1α α 1=0e3=− − Ω Ω ()α α 10)Ξ Ξ .()α α 10)=α α − − 4+α α − − 1+α α 7+α α − − 5α α 7=α α 7α α 7=1e4=− − Ω Ω ()α α 2)Ξ Ξ .()α α 2)=α α − − 4+α α 6+α α 6+α α 1α α 6=α α 6α α 6=1{displaystyle {begin{aligned}e_{1} {Omega (alpha ^{4}}{ Xi '(alpha ^{4}}={frac Alfa ^{-7}+alpha ^{-5}+alpha ^{7}{alpha ^{-5}={frac Alpha ¿Qué? {omega (alpha ^{7}}{Xi '(alpha ^{7}}={frac Alfa ^{-4}+alpha ^{1}+alpha ^{1}{alpha ¿Qué? {Omega (alpha ^{10}}{ Xi '(alpha ^{10}}={frac {alpha ^{-4}+alpha ^{-1}+alpha ^{7}+alpha ^{-5}{alpha {fnK} {fnK} {fnK} {fnK}} {fnK}} {fnK}}} {fnK}} {fnK}}}} {fnK}}}} {f}}}}}}} {fnf}fnfnKf}f}f}}}f}}f}}}}}fnfnfnfnfnfnfnfnfnfnfnf}fnfnKfnKfnfnK\fnf}fnfnKfnKfnfnKfnKfnKfn\fnKfnKfnKfnfnKfnKfnKfnK\fnKf}\fnKf}fnK ¿Qué? {Omega (alpha ^{2}}{ Xi '(alpha ^{2}}={frac Alfa ^{6}+alpha ^{6}+alpha ^{1}{alpha ^{6}={frac Alpha ^{6}=1end{aligned}

Hecho, eso e3=e4=1,{displaystyle E_{3}=e_{4}=1,} no debe ser sorprendente.

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

Permítanos mostrar el comportamiento del algoritmo para el caso con una pequeña cantidad de errores. Que la palabra recibida sea [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Una vez más, sustitúyase a los caracteres no legibles por ceros mientras crea el polinomio que refleja sus posiciones .. ()x)=()α α 8x− − 1)()α α 11x− − 1).{displaystyle Gamma (x)=left(alpha ^{8}x-1right)left(alpha ^{11}x-1right). }Computar los síndromes s1=α α 4,s2=α α − − 7,s3=α α 1,s4=α α 1,s5=α α 0,{displaystyle S_{1}=alpha ^{4},s_{2}=alpha ^{-7},s_{3}=alpha ^{1},s_{4}=alpha ^{1},s_{5}=alpha ^{0} y s6=α α 2.{displaystyle s_{6}=alpha ^{2}Crear síndrome polinomio

S()x)=α α 4+α α − − 7x+α α 1x2+α α 1x3+α α 0x4+α α 2x5,S()x).. ()x)=α α 4+α α 7x+α α 5x2+α α 3x3+α α 1x4+α α − − 1x5+α α − − 1x6+α α 6x7.{displaystyle {begin{aligned}S(x) ventaja=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) ^{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}

Ejecutemos el algoritmo euclidiano extendido:

( S ( x ) Γ ( x ) x 6 ) = ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 + α − 1 x 6 + α 6 x 7 x 6 ) = ( α − 1 + α 6 x 1 1 0 ) ( x 6 α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 + 2 α − 1 x 6 + 2 α 6 x 7 ) = ( α − 1 + α 6 x 1 1 0 ) ( α 3 + α 1 x 1 1 0 ) ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 α 7 + ( α − 5 + α 5 ) x + 2 α − 7 x 2 + 2 α 6 x 3 + 2 α 4 x 4 + 2 α 2 x 5 + 2 x 6 ) = ( ( 1 + α 2 ) + ( α 0 + α − 6 ) x + α 7 x 2 α − 1 + α 6 x α 3 + α 1 x 1 ) ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 α 7 + α 0 x ) {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&0end{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}+2alpha ^{-1}x^{6}+2alpha ^{6}x^{7}end{pmatrix}}\&={begin{pmatrix}alpha ^{-1}+alpha ^{6}x&1\1&0end{pmatrix}}{begin{pmatrix}alpha ^{3}+alpha ^{1}x&1\1&0end{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+2alpha ^{-7}x^{2}+2alpha ^{6}x^{3}+2alpha ^{4}x^{4}+2alpha ^{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&1end{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}xend{pmatrix}}end{aligned}}}

Hemos llegado al polinomio de grado máximo 3, y como

()− − 1α α − − 1+α α 6xα α 3+α α 1x− − ()α α − − 7+α α 7x+α α 7x2))()α α − − 7+α α 7x+α α 7x2α α − − 1+α α 6xα α 3+α α 1x1)=()1001),{displaystyle {begin{pmatrix}-1 ^{-1}+alpha ^{6}x\alpha ^{3}+alpha ^{1}x limitada-left(alpha ^{-7}+alpha ^{7}x+alpha ^{7}x^{2}derecha)end{pmatrix}{begin{pmatrix}alpha ^{-7}+alpha ^{7}x+alpha ^{7}x^{2} ^{6}x\alpha ^{3}+alpha ^{1}x limitada1end{pmatrix}={begin{pmatrix}1 {0}}}

obtenemos

()− − 1α α − − 1+α α 6xα α 3+α α 1x− − ()α α − − 7+α α 7x+α α 7x2))()S()x).. ()x)x6)=()α α 4+α α 7x+α α 5x2+α α 3x3+α α 1x4+α α − − 1x5α α 7+α α 0x).{displaystyle {begin{pmatrix}-1 ^{-1}+alpha ^{6}x\alpha ^{3}+alpha ^{1}x limitada-left(alpha ^{-7}+alpha ^{7}x+alpha ^{7}x^{2}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}xend{pmatrix}}

Por lo tanto,

S()x).. ()x)()α α 3+α α 1x)− − ()α α − − 7+α α 7x+α α 7x2)x6=α α 7+α α 0x.{displaystyle S(x)Gamma (x)left(alpha ^{3}+alpha ^{1}xright)-left(alfa ^{-7}+alpha ^{7}x+alpha ^{7}x^{2}right)x^{6}=alpha ^{7}+alpha ^{0}x.}

Vamos ▪ ▪ ()x)=α α 3+α α 1x.{displaystyle Lambda (x)=alpha ^{3}+alpha ^{1}x.} No te preocupes. λ λ 0ل ل 1.{displaystyle lambda _{0}neq 1.} La raíz de ▪ ▪ ()x){displaystyle Lambda (x)} es α α 3− − 1.{displaystyle alpha ^{3-1}

Dejar

Ξ Ξ ()x)=.. ()x)▪ ▪ ()x)=α α 3+α α − − 7x+α α − − 4x2+α α 5x3,Ω Ω ()x)=S()x)Ξ Ξ ()x)↑ ↑ α α 7+α α 0xmodx6{displaystyle {begin{aligned}Xi (x) recur=Gamma (x)Lambda (x)=alpha ^{3}+alpha ^{-7}x+alpha ^{-4}x^{2}+alpha ^{5}x^{3},\\Omega (x) recur=S(x)Xi (x)equiv alpha ^{7}+alpha ^{0}x{bmod {x^{6}end{aligned}}

Busquemos valores de error usando fórmula ej=− − Ω Ω ()α α − − ij)/Ξ Ξ .()α α − − ij),{displaystyle E_{j}=- Omega left(alpha ^{-i_{j}right)/ Xi 'left(alpha) ¿Qué? Donde α α − − ij{displaystyle alpha ^{-i_{j}} son raíces de polinomio Ξ Ξ ()x).{displaystyle Xi (x). }

Ξ Ξ .()x)=α α − − 7+α α 5x2.{displaystyle Xi '(x)=alpha ^{-7}+alpha ^{5}x^{2}

Obtenemos

e1=− − Ω Ω ()α α 4)Ξ Ξ .()α α 4)=α α 7+α α 4α α − − 7+α α − − 2=α α 3α α 3=1e2=− − Ω Ω ()α α 7)Ξ Ξ .()α α 7)=α α 7+α α 7α α − − 7+α α 4=0e3=− − Ω Ω ()α α 2)Ξ Ξ .()α α 2)=α α 7+α α 2α α − − 7+α α − − 6=α α − − 3α α − − 3=1{displaystyle {begin{aligned}e_{1} {Omega left(alpha ^{4}right)}{ Xi 'left(alpha ^{4}right)}={frac {alpha ^{7}+alpha ^{4}{alpha ^{-7}+alpha ^{-2}={frac Alpha ¿Qué? {Omega left(alpha ^{7}right)}{ Xi 'left(alpha ^{7}right)}={frac {alpha ^{7}+alpha ^{7}{alpha ^{-7}+alpha ¿Qué? {Omega left(alpha ^{2}right)}{ Xi 'left(alpha ^{2}right)}={frac {alpha ^{7}+alpha ^{2}{alpha ^{-7}+alpha ^{-6}={frac {alpha }{-3}{alpha ^{-3}=1end{aligned}

El hecho de que e3=1{displaystyle E_{3}=1} no debe ser sorprendente.

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