Códigos algebraicos y decodificación

Con q símbolos y longitud n hay qⁿ palabras posibles. El código C elige un subconjunto y asigna un mensaje a cada palabra elegida. Las demás palabras no representan directamente mensajes. Usar menos posibilidades introduce redundancia.

La distancia de Hamming d(u,v) cuenta posiciones donde u y v difieren. No resta sus valores como números enteros. El peso wt(u) cuenta posiciones no nulas; sobre un cuerpo, d(u,v)=wt(u−v). En códigos no binarios se cuentan símbolos, no necesariamente bits.

Para al menos dos palabras válidas, d es la menor distancia entre dos distintas. Se detectan hasta d−1 errores: menos de d cambios no convierten una palabra válida en otra. Para corregir de forma única hasta t errores se exige 2t<d.

La razón es triangular. Si r estuviera a distancia como máximo t de c y de c′, tendríamos d(c,c′)≤d(c,r)+d(r,c′)≤2t<d, imposible. Por eso el radio garantizado es .

Un cuerpo finito permite sumar, multiplicar y dividir por elementos no nulos. Un código lineal es un subespacio de ⁿ de dimensión k y contiene qᵏ palabras. Para q primo operamos módulo q. Si q es una potencia prima no prima, no se identifica con enteros módulo q.

Usamos mensajes columna y G de tamaño n×k, con rango k: c=Gm. Una matriz H de tamaño (n−k)×n y rango n−k describe C=ker H.

En un código lineal, la distancia mínima es el menor peso no nulo: la diferencia de dos palabras vuelve al código.

El síndrome depende del error, no del mensaje. Para corregir buscamos un error compatible, dentro del radio garantizado o según un criterio declarado.

Un síndrome nulo significa que r pertenece al código. Puede no haber error o puede haberse sumado una palabra válida no nula. Dos errores con el mismo síndrome difieren en una palabra del código: H(e−e′)=0.

Una bola de radio t contiene todas las palabras con hasta t posiciones cambiadas: . Si 2t<d, las bolas centradas en las palabras válidas son disjuntas.

Caber en el universo exige |C|(n,t)≤qⁿ: cota de Hamming.

Para Singleton, borramos d−1 posiciones fijas. Dos palabras distintas no pueden quedar iguales: entonces diferirían en menos de d posiciones.

Elegimos n puntos distintos α_i en , con 1≤k≤n≤q.

El mensaje son los k coeficientes de un polinomio p de grado menor que k. Se envía . Evaluar es lineal e inyectivo: un polinomio no nulo de grado menor que k no tiene k raíces distintas.

Dos mensajes distintos difieren por un polinomio de grado como máximo k−1: coinciden como mucho en k−1 posiciones.

Si solo hay borrados conocidos, cualquier k evaluaciones intactas permiten interpolar.

Para corregir hasta t errores con n≥k+2t, buscamos un polinomio E no nulo de grado a lo sumo t y Q de grado menor que k+t, tales que en cada posición. Si E se anula donde hubo error y Q=pE, las ecuaciones se cumplen. Son lineales en los coeficientes desconocidos.

Toda solución no nula tiene E≠0: si E fuera cero, Q tendría n raíces y grado menor que n. Además Q−pE tiene grado menor que k+t y al menos n−t≥k+t raíces intactas; por eso es cero. Dividimos Q/E, verificamos grado menor que k y distancia a r como máximo t.

Fuera de las hipótesis, la verificación puede rechazar.

Asociamos (c₀,…,cₙ₋₁) a c₀+c₁x+…+cₙ₋₁xⁿ⁻¹. Multiplicar por x módulo xⁿ−1 gira las posiciones. Un código lineal cíclico es un ideal de [x]/(xⁿ−1), generado por un divisor mónico g de xⁿ−1; su dimensión es n−grado(g).

En BCH se elige n coprimo con q y una raíz n-ésima primitiva α en una extensión. Exigir que g tenga como raíces αᵇ,…,αᵇ⁺ᵟ⁻² da distancia mínima al menos δ. Las raíces consecutivas y el cuerpo son hipótesis concretas. Esta es una construcción por raíces; la presentación por evaluaciones de Reed–Solomon tiene otro punto de partida.

La distancia trata el peor patrón con un número acotado de cambios. Un modelo probabilístico asigna probabilidades a patrones y permite calcular una tasa de error promedio. El decodificador y la regla de decisión también deben especificarse.

Para repetición triple con cambios independientes de probabilidad p, mayoría falla con dos o tres cambios: 3p²(1−p)+p³. La garantía de un error es absoluta bajo ese límite; la fórmula probabilística admite cualquier cantidad de cambios y calcula cuánto pesan los fallos.