Introducción
En la era digital, la transmisión y almacenamiento de datos son fundamentales. Sin embargo, los canales de comunicación no son perfectos y pueden introducir errores. La Teoría de Códigos utiliza herramientas algebraicas para diseñar sistemas que detecten y corrijan estos errores automáticamente. Desde mensajes de texto hasta exploración espacial, los códigos correctores son esenciales para garantizar la integridad de la información.
Conceptos Básicos
Un código es un conjunto de palabras (secuencias de símbolos) sobre un alfabeto finito, típicamente $\mathbb{F}_q$ (un campo finito con $q$ elementos). La distancia de Hamming entre dos palabras $x$ y $y$, denotada $d(x,y)$, es el número de posiciones en las que difieren. La distancia mínima $d$ de un código es la menor distancia entre dos palabras distintas del código.
Ejemplo 1: Distancia de Hamming
Sean $x = 10110$ e $y = 10011$ en $\mathbb{F}_2^5$. La distancia de Hamming es $d(x,y) = 2$ (posiciones 3 y 5).
Códigos Lineales
Un código lineal $C$ de longitud $n$ y dimensión $k$ sobre $\mathbb{F}_q$ es un subespacio vectorial de $\mathbb{F}_q^n$ con dimensión $k$. Se denota como $[n,k]_q$-código. Una matriz generadora $G$ de $C$ es una matriz $k \times n$ cuyas filas forman una base de $C$.
Teorema 1: Relación entre Distancia Mínima y Peso Mínimo
Para un código lineal $C$, la distancia mínima $d$ es igual al peso mínimo (número de coordenadas no nulas) de una palabra no nula en $C$.
Demostración:
Sea $d$ la distancia mínima y $w$ el peso mínimo. Para cualesquiera $x,y \in C$, $d(x,y) = w(x-y) \geq w$. Como $x-y \in C$, $d \geq w$. Además, existe $z \in C$ con $w(z) = w$, y $d(0,z) = w$, luego $d \leq w$. Por tanto, $d = w$.
Códigos de Hamming
Los códigos de Hamming son una familia de códigos lineales perfectos (alcanzan la cota de Hamming) con distancia mínima $3$. Para $r \geq 2$, el código de Hamming $[n,k]_2$ tiene $n = 2^r – 1$ y $k = n – r$.
Ejemplo 2: Matriz de Verificación de Paridad
El código de Hamming $[7,4]_2$ tiene matriz de verificación:
$$
H = \begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{pmatrix}
$$
Las columnas son todos los vectores no nulos de $\mathbb{F}_2^3$.
Decodificación por Síndrome
Dado un código lineal $C$ con matriz de verificación $H$, el síndrome de una palabra $y \in \mathbb{F}_q^n$ es $s = Hy^T$. Si $y = c + e$ (con $c \in C$ y $e$ el error), entonces $Hy^T = He^T$.
Teorema 2: Corrección de Errores
Un código lineal con distancia mínima $d$ puede corregir hasta $\left\lfloor \frac{d-1}{2} \right\rfloor$ errores.
Demostración:
Sea $t = \left\lfloor \frac{d-1}{2} \right\rfloor$. Para cualquier error $e$ con $w(e) \leq t$, la bola de radio $t$ alrededor de cualquier palabra del código es disjunta. Por tanto, el error puede identificarse unívocamente.
Códigos Cíclicos
Un código cíclico es un código lineal donde cualquier desplazamiento cíclico de una palabra del código también pertenece al código. Estos códigos se estudian mediante polinomios en $\mathbb{F}_q[x]/(x^n – 1)$.
Teorema 3: Generador de Códigos Cíclicos
Un código cíclico $C$ de longitud $n$ sobre $\mathbb{F}_q$ corresponde a un ideal en $\mathbb{F}_q[x]/(x^n – 1)$, generado por un polinomio mónico $g(x)$ que divide a $x^n – 1$.
Demostración:
Como $\mathbb{F}_q[x]/(x^n – 1)$ es un anillo principal, $C$ es generado por $g(x)$. Como $x^n – 1 \in C$, $g(x)$ debe dividirlo.
Ejercicios Resueltos
Ejercicio 1: Peso Mínimo
Calcula el peso mínimo del código generado por $G = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$.
Solución:
Las palabras del código son combinaciones lineales de las filas: $0000$, $1011$, $0110$, $1101$. El peso mínimo es $2$ (para $0110$).
Ejercicio 2: Decodificación
Decodifica $y = 1011001$ en el código de Hamming $[7,4]_2$.
Solución:
Calculamos $Hy^T = 110$, que corresponde a la columna 6 de $H$. El error está en la posición 6, luego la palabra original es $1011011$.
Aplicaciones Prácticas
- Almacenamiento digital: CDs y DVDs usan códigos Reed-Solomon para corregir errores por rayaduras.
- Comunicaciones: Los códigos convolucionales se emplean en telecomunicaciones y WiFi.
- Criptografía: Algoritmos como McEliece se basan en teoría de códigos.
- Computación cuántica: Los códigos correctores protegen información cuántica.
Conclusión
La Teoría de Códigos combina álgebra abstracta y combinatoria para resolver problemas prácticos en transmisión de datos. Desde códigos lineales hasta cíclicos, estas herramientas permiten diseñar sistemas robustos contra errores. Su aplicación es universal, desde dispositivos cotidianos hasta misiones espaciales, demostrando que las matemáticas puras tienen un impacto profundo en la tecnología moderna.
«`