Códigos lineales: un código que es un subespacio

En la lección anterior construimos los alfabetos buenos: los cuerpos finitos, donde se puede sumar, restar, multiplicar y dividir. Ahora los usamos. Un código de bloque, tal como lo vimos en la primera lección, es una lista de palabras. Si la lista tiene millones de palabras, ¿cómo la guardas? ¿Cómo calculas su distancia mínima sin comparar todas las parejas? Los códigos lineales contestan a las dos preguntas a la vez: toda la lista cabe en unas pocas filas de números.

La idea

Imagina un código con $2^{20}$ palabras, algo más de un millón. Para hallar su distancia mínima habría que comparar cada palabra con todas las demás: del orden de medio billón de parejas. Y para codificar haría falta una tabla enorme que dijera qué palabra corresponde a cada mensaje.

Los códigos lineales evitan todo eso con una condición muy sencilla: si sumas dos palabras del código, el resultado sigue siendo una palabra del código. Lo mismo si multiplicas una palabra por un escalar. Los matemáticos dicen que el código es un subespacio vectorial.

Esa estructura tiene dos premios. Primero, el código se describe con unas pocas palabras «ladrillo» (una base) y todas las demás salen de combinarlas. Segundo, desde cualquier palabra el código se ve igual: si le restas a todas las palabras una palabra del código, obtienes el mismo conjunto. Por eso la distancia mínima se calcula mirando solo desde la palabra cero.

Definición

Sea $\mathbb{F}_q$ un cuerpo finito. Un código lineal $C$ de longitud $n$ sobre $\mathbb{F}_q$ es un subespacio vectorial de $\mathbb{F}_q^n$. Dicho con palabras de andar por casa:

• la palabra cero $(0,\dots,0)$ está en $C$;
• si $x, y \in C$, entonces $x+y \in C$;
• si $x \in C$ y $a \in \mathbb{F}_q$, entonces $ax \in C$.

En el caso binario, $\mathbb{F}_2=\{0,1\}$, multiplicar por un escalar solo puede dar $0\cdot x = 0$ o $1\cdot x = x$, así que basta comprobar que la suma de dos palabras del código es del código.

La dimensión $k$ del código es la dimensión de ese subespacio. Como una base tiene $k$ vectores y cada coeficiente toma $q$ valores,

El peso $\mathrm{wt}(x)$ de una palabra es el número de posiciones distintas de cero. Se tiene $d(x,y)=\mathrm{wt}(x-y)$: los símbolos en que dos palabras difieren son exactamente los símbolos no nulos de su diferencia.

Un código lineal de longitud $n$, dimensión $k$ y distancia mínima $d$ se llama código $[n,k,d]_q$ (o $[n,k,d]$ si el cuerpo se sobreentiende). Observa los corchetes: la notación $(n,M,d)$ de la primera lección hablaba de un código cualquiera con $M$ palabras; en un lineal, $M=q^k$. La tasa es $R=k/n$: la fracción de cada palabra que lleva información.

La distancia mínima es el peso mínimo no nulo

En un código cualquiera, la distancia mínima exige comparar todas las parejas. En un código lineal basta esto:

La razón cabe en una línea: si $x$ e $y$ son palabras distintas del código, $x-y$ es una palabra del código no nula y $d(x,y)=\mathrm{wt}(x-y)$; recíprocamente, cada palabra no nula $c$ cumple $\mathrm{wt}(c)=d(c,0)$, con $0$ también del código. Así que el conjunto de distancias entre parejas y el conjunto de pesos de palabras no nulas son el mismo.

Pasamos de comparar del orden de $|C|^2$ parejas a mirar $|C|-1$ pesos. Y en la lección siguiente veremos que ni siquiera hace falta listar las palabras.

Ejemplo resuelto

Tomamos el código de Hamming $[7,4,3]$ binario, nuestro ejemplo hilo. Sus palabras son todas las combinaciones de las cuatro filas de

(En la próxima lección veremos por qué esta matriz «fabrica» el código; de momento, solo nos interesan las filas.)

Paso 1: dimensión y número de palabras. Hay $k=4$ filas independientes (las cuatro primeras columnas forman la matriz identidad: cada fila es la única con un 1 en su columna, así que ninguna es combinación de las otras). Entonces $|C|=2^4=16$ palabras, de longitud $n=7$.

Paso 2: cerrado por la suma. Sumamos las dos primeras filas, módulo 2:

Es otra palabra del código, porque es la suma de las filas 1 y 2 de $G$. De hecho, la suma de dos palabras cualesquiera sigue siendo combinación de las filas, es decir, palabra del código. En cambio, $(1,0,0,0,0,0,0)$ no está en el código. Como las cuatro primeras columnas de $G$ son la identidad, los cuatro primeros símbolos de una combinación son sus coeficientes. Una combinación que empiece por $1,0,0,0$ solo puede ser la fila 1, que es $(1,0,0,0,1,1,0)\neq(1,0,0,0,0,0,0)$.

Paso 3: lista de pesos. Las 16 palabras son las combinaciones $mG$, con $m$ uno de los 16 mensajes de 4 bits. Puedes verlas todas aquí:

Contando los pesos:

(1 + 7 + 7 + 1 = 16, como debe ser.) Por ejemplo, la suma del paso 2, $1100011$, tiene peso 4.

Paso 4: distancia mínima. El peso mínimo no nulo es 3, así que $d=3$ sin comparar las $\binom{16}{2}=120$ parejas. Los parámetros son $[7,4,3]$, y como $t=\lfloor (3-1)/2\rfloor=1$, el código corrige un error. Su tasa es $R=4/7$: de cada 7 símbolos, 4 son información y 3 son la redundancia que permite corregir.

Ejercicios

Ejercicio 1

Decide si son lineales (sobre $\mathbb{F}_2$):

a) $C_1=\{000,\,110,\,011,\,101\}$

b) $C_2=\{0000,\,1100,\,0011,\,1110\}$

Ejercicio 2

Sea $C$ el código binario de longitud 5 generado por las palabras $10110$ y $01101$. Escribe todas sus palabras, y halla $n$, $k$, $d$ y la tasa.

Ejercicio 3

Sobre $\mathbb{F}_3=\{0,1,2\}$ (suma módulo 3) considera el código $C$ generado por $(1,0,1,1)$ y $(0,1,1,2)$.

a) ¿Cuántas palabras tiene?

b) Escribe las 9 palabras.

c) Calcula $d$.

En resumen

• Un código lineal es un subespacio de $\mathbb{F}_q^n$: contiene al cero y es cerrado por suma y por múltiplos escalares.
• Si tiene dimensión $k$, tiene $q^k$ palabras, y se describe con $[n,k,d]_q$; la tasa es $k/n$.
• En un código lineal, la distancia mínima es el peso mínimo de una palabra no nula.
• El código de Hamming $[7,4,3]$ tiene 16 palabras con pesos $0$ (una), $3$ (siete), $4$ (siete) y $7$ (una).

Siguiente lección: Matriz generatriz y matriz de paridad