Qué es un código corrector: añadir redundancia con cabeza

Un código QR con un trozo roto o manchado se sigue leyendo. Un CD con un arañazo suena igual. Una sonda a millones de kilómetros nos manda fotos con la señal casi ahogada por el ruido. En los tres casos hay datos que se estropean por el camino y, aun así, el mensaje llega entero. No es magia: es matemática que se diseñó para eso. Este curso explica cómo funciona, y esta primera lección pone las bases: qué es un código, cómo se mide lo «parecidas» que son dos palabras y cómo se decide qué se quiso decir cuando llega algo estropeado.

La idea

Quieres enviar un mensaje por un canal imperfecto: un cable, el aire, un disco, una memoria. El canal a veces cambia algún símbolo. Si mandas el mensaje tal cual, el receptor no puede saber si lo que ha recibido es lo que enviaste: cualquier secuencia es un mensaje posible.

La solución es añadir redundancia. En lenguaje natural ya la hay: si lees «mxtemáticas» sabes que es «matemáticas», porque no existe ninguna otra palabra parecida. El castellano no usa todas las combinaciones de letras, y ese «desperdicio» permite detectar y arreglar erratas.

Un código corrector hace lo mismo, pero a propósito y con matemáticas. Se eligen unas pocas secuencias «válidas» entre todas las posibles, y se eligen lejos unas de otras. Si llega algo que no es válido, se busca la palabra válida más cercana. Todo el curso gira en torno a una pregunta: ¿cómo elegir esas palabras para que estén lo más lejos posible entre sí gastando la mínima redundancia?

Repaso Aritmética módulo 2

Trabajamos con bits, es decir, con los símbolos 0 y 1. En «aritmética módulo 2» solo existen esos dos números y se suman así: $0+0=0$, $0+1=1$, $1+0=1$ y $1+1=0$ (como «par más par es par, impar más impar es par»). Sumar bit a bit dos palabras binarias equivale a la operación «o exclusivo»: el resultado tiene un 1 donde ambas palabras difieren. En esta lección apenas la necesitamos; la usaremos mucho desde la lección 3.

Definiciones

Un alfabeto es un conjunto finito de símbolos. Casi siempre será $\{0,1\}$ (alfabeto binario), pero puede ser mayor; lo llamaremos $A$ y su tamaño $q$. Una palabra de longitud $n$ es una sucesión de $n$ símbolos del alfabeto, que escribiremos como vector fila, por ejemplo $x=(1,0,1,1,0)$. Las posiciones se numeran de 1 a $n$.

Un código de bloque de longitud $n$ es un subconjunto $C$ de las palabras de longitud $n$. Sus elementos son las palabras código. Si $C$ tiene $M$ palabras, se pueden enviar $M$ mensajes distintos: cada mensaje se asocia a una palabra código antes de transmitirlo. A esa asociación la llamaremos codificar.

La tasa del código mide cuánta información útil lleva cada símbolo enviado:

$$R=\frac{\log_q M}{n}.$$

Aquí $\log_q M$ cuenta cuántos símbolos de información caben en el código. Para $q=2$, un código con $M=2^k$ palabras lleva $k$ bits de información y tiene tasa $R=k/n$: de cada $n$ bits, $k$ son «información» y el resto, redundancia. Cuanto más cerca de 1, menos redundancia (más eficiente, pero con menos protección).

Dos códigos muy sencillos

El código de repetición de longitud 3 repite cada bit tres veces: el 0 se envía como $000$ y el 1 como $111$. Tiene $n=3$ y $M=2$ palabras, así que $R=1/3$.

El código de paridad de longitud 3 toma dos bits de mensaje y añade un tercero que hace que la cantidad de unos sea par:

mensaje	palabra código
00	000
01	011
10	101
11	110

Tiene $n=3$ y $M=4$ palabras, y $R=2/3$.

Distancia de Hamming

La distancia de Hamming $d(x,y)$ entre dos palabras de la misma longitud es el número de posiciones en las que difieren. Por ejemplo, $d(10110,\,11100)=2$, porque se diferencian en las posiciones 2 y 4. Es una distancia de verdad: nunca es negativa, vale 0 solo si las palabras son iguales y cumple la desigualdad triangular.

La distancia mínima de un código con al menos dos palabras es

$$d=\min\{\,d(x,y) : x,y\in C,\ x\neq y\,\}.$$

Un código de longitud $n$ con $M$ palabras y distancia mínima $d$ se dice de parámetros $(n,M,d)$. El de repetición es un $(3,2,3)$: sus dos palabras difieren en las tres posiciones. El de paridad es un $(3,4,2)$: dos palabras distintas siempre difieren en al menos dos posiciones, y hay pares a distancia exactamente 2, como $000$ y $011$.

Detectar y corregir

La distancia mínima decide cuántos errores aguanta un código. Un código de distancia $d$ detecta hasta $d-1$ errores, porque con menos de $d$ cambios no se llega a otra palabra código, y corrige hasta $t=\lfloor (d-1)/2\rfloor$, porque con tan pocos errores la palabra enviada sigue siendo la más cercana a lo recibido (en la lección 5 verás el porqué con un dibujo).

Repaso Qué significa ⌊x⌋

Es la parte entera de $x$: el mayor entero que no supera $x$. Por ejemplo, $\lfloor 2{,}5 \rfloor = 2$ y $\lfloor 1 \rfloor = 1$. Así, con $d=3$ se tiene $t=\lfloor 2/2 \rfloor = 1$, y con $d=4$, $t=\lfloor 3/2 \rfloor = 1$: un código de distancia 4 corrige los mismos errores que uno de distancia 3.

Decodificar por la palabra más cercana consiste justo en eso: ante una palabra recibida $r$, se devuelve la palabra código $c$ con $d(r,c)$ mínima. Si hay empate entre varias, el decodificador no puede decidir con seguridad.

Un código con $d=1$ no detecta nada. Con $d=2$ detecta un error pero no lo corrige. Hacen falta $d=3$ para corregir un error, y $d=5$ para corregir dos.

Ejemplo resuelto

El código de repetición $(3,2,3)$. Como $d=3$, detecta hasta 2 errores y corrige $t=\lfloor 2/2\rfloor=1$.

Envías el bit 1, es decir, la palabra $111$, y el canal cambia el símbolo de la posición 2: llega $r=101$. Calculamos las distancias a las dos palabras código:

• $d(101,000)=2$,
• $d(101,111)=1$.

La más cercana es $111$, así que se decodifica $1$. Se ha corregido el error. Es la «votación por mayoría» de toda la vida.

Si hubiera habido dos errores (llega, por ejemplo, $001$), las distancias serían $1$ a $000$ y $2$ a $111$: se decodifica $0$, que es incorrecto. El código corrige un error, pero con dos se equivoca sin avisar. Con $d=3$ puedes usar el código para corregir 1 error o para detectar 2, pero no las dos cosas a la vez: si corriges, dos errores se convierten en una corrección equivocada. Si solo detectas, $001$ no es palabra código y saltaría la alarma.

El código de paridad $(3,4,2)$ solo tiene $d=2$. Si envías $011$ y llega $111$, sabes que algo ha ido mal, porque $111$ tiene un número impar de unos y no es palabra código. Pero está a distancia 1 de $011$, de $101$ y de $110$: hay tres candidatas empatadas. Se detecta sin corregir.

Una mirada al futuro. Con repetición, para corregir un error gastamos $R=1/3$: enviamos tres bits por cada bit de información. Se puede hacer mucho mejor. En las lecciones 3 y 4 construiremos un código de longitud 7 con $M=16$ palabras (los cuatro bits de información van acompañados de tres de redundancia) y distancia mínima 3. Es un $(7,16,3)$ (en la lección 3 lo escribiremos $[7,4,3]$): corrige también un error, pero con tasa $R=4/7$, más de la mitad. Es el código de Hamming y será nuestro ejemplo hilo a lo largo del curso.

Detectar sin corregir en la vida diaria

Muchos identificadores llevan un dígito o una letra de control que solo sirve para detectar. La letra del DNI es el resto de dividir el número entre 23, convertido en una letra con una tabla: para 12345678, el resto es 14 y la letra es Z. Si te equivocas en un solo dígito, el resto cambia siempre, así que la letra no coincide y el error se detecta. Pero con la letra sola no se sabe cuál de los ocho dígitos falló ni cuál era el correcto: es detectar sin corregir. Algo parecido hacen el IBAN o el ISBN; puedes probarlo en el validador de DNI. Los códigos correctores de verdad añaden la redundancia justa para poder además localizar el error.

Ejercicios

Ejercicio 1

Calcula la distancia de Hamming entre $x=10110$ e $y=11100$ y entre $x$ y $z=01001$.

Ver la solución

Comparamos posición a posición.

$x=1\,0\,1\,1\,0$ e $y=1\,1\,1\,0\,0$ difieren en las posiciones 2 y 4, así que $d(x,y)=2$.

$x=1\,0\,1\,1\,0$ y $z=0\,1\,0\,0\,1$ difieren en las cinco posiciones, así que $d(x,z)=5$.

Ejercicio 2

Considera el código de repetición de longitud 5, que repite cada bit cinco veces.

1. ¿Cuáles son sus parámetros $(n,M,d)$ y su tasa?
2. ¿Cuántos errores corrige? ¿Y cuántos detecta?
3. Decodifica por la palabra más cercana la recepción $01001$.

Ver la solución

1. Las palabras código son $00000$ y $11111$, que difieren en las 5 posiciones. Es un $(5,2,5)$ y su tasa es $R=1/5$.
2. Detecta $d-1=4$ errores y corrige $t=\lfloor 4/2\rfloor=2$.
3. $d(01001,00000)=2$ y $d(01001,11111)=3$. La más cercana es $00000$: se decodifica el bit 0. Es decir, gana la mayoría de ceros (tres ceros frente a dos unos).

Ejercicio 3

Sea $C=\{00000,\ 01011,\ 10101,\ 11110\}$.

1. Calcula su distancia mínima y sus parámetros $(n,M,d)$.
2. Decodifica por la palabra más cercana la recepción $11011$.
3. Para la recepción $11000$, ¿qué ocurre?

Ver la solución

1. Hay seis pares. Los que incluyen $00000$ dan los pesos de las otras palabras: $d(00000,01011)=3$, $d(00000,10101)=3$ y $d(00000,11110)=4$. Los otros tres pares: $d(01011,10101)=4$, $d(01011,11110)=3$ y $d(10101,11110)=3$. El mínimo es $d=3$, así que $C$ es un $(5,4,3)$: corrige 1 error.
2. Las distancias de $11011$ a las cuatro palabras son 4, 1, 3 y 2, respectivamente. La más cercana es $01011$, a distancia 1: se decodifica $01011$.
3. Las distancias de $11000$ son 2 a $00000$, 3 a $01011$, 3 a $10101$ y 2 a $11110$. Hay un empate entre $00000$ y $11110$: el decodificador no puede decidir. Es lo esperable, porque $11000$ está a dos errores de dos palabras distintas y el código solo garantiza corregir uno.

En resumen

• Un código de bloque es un conjunto de palabras de longitud $n$ elegidas a propósito para estar lejos unas de otras; la tasa mide cuánta redundancia gastan.
• La distancia de Hamming cuenta las posiciones en que difieren dos palabras; la distancia mínima $d$ del código mide cuánto de lejos están sus palabras.
• Un código detecta hasta $d-1$ errores y corrige hasta $t=\lfloor (d-1)/2\rfloor$.
• Decodificar es elegir la palabra código más cercana a lo recibido.
• Hay códigos mucho mejores que repetir: el de Hamming $(7,16,3)$ corrige un error con tasa $4/7$.

Siguiente lección: Cuerpos finitos: sumar y multiplicar con pocos símbolos