Errores y borrones: cuánto puede corregir un código

En la lección anterior aprendiste a codificar con $G$ y a comprobar con $H$ si una palabra es del código. Falta saber cuánto daño aguanta un código. Esa es la pregunta de hoy, y la respuesta cabe en una sola cifra: la distancia mínima $d$. Es lo que permite que un QR se lea aunque lo hayas manchado de café, o que un CD suene con un arañazo.

La idea

Imagina que cada palabra del código es un punto y que a su alrededor dibujas una bola: todas las palabras que están a distancia de Hamming menor o igual que $t$ de ella. Si las bolas de dos palabras distintas no se tocan, cualquier palabra recibida cae como mucho en una bola, y sabes cuál era la original. Eso es corregir.

El daño puede ser de dos tipos:

• Un error: un símbolo ha cambiado y no sabes cuál. El 1 que ves podría ser un 0 estropeado.
• Un borrón (también se dice borrado): un símbolo se ha perdido, pero sabes en qué posición. Ves «?» en lugar de un valor.

El borrón es más fácil de reparar porque ya has hecho la mitad del trabajo: localizar el fallo. Con un error hay que averiguar dónde y cuánto vale. Por eso un código corrige el doble de borrones que de errores, más o menos.

Cuánto se detecta y cuánto se corrige

Sea $C$ un código de distancia mínima $d$. Dos palabras código distintas se diferencian al menos en $d$ posiciones. De ahí salen todas las cifras.

• Detectar errores. Si hay entre 1 y $d-1$ errores, la palabra recibida no puede ser otra palabra código (estaría a distancia menor que $d$ de la enviada, pero no a distancia 0). Así que se detectan $d-1$ errores.
• Corregir errores. Las bolas de radio $t$ alrededor de dos palabras código no se cortan si $2t+1 \le d$. Por tanto se corrigen $t = \lfloor (d-1)/2 \rfloor$ errores (⌊x⌋ es la parte entera, repasada en la lección 1).
• Corregir borrones. Borra $d-1$ posiciones de dos palabras código distintas: como difieren en al menos $d$ posiciones, siguen difiriendo en alguna de las que quedan. Cada palabra queda identificada por sus símbolos visibles, y se corrigen $d-1$ borrones.
• Todo a la vez. Con $e$ errores y $b$ borrones se corrige siempre que

$$2e + b \le d-1.$$

Cada error cuesta el doble que un borrón: hay que localizarlo y además corregirlo.

Por ejemplo, con $d=5$ puedes corregir 2 errores, o 4 borrones, o 1 error y 2 borrones ($2\cdot 1 + 2 = 4$).

Dos cotas: lo máximo que se puede pedir

Un buen código tiene $d$ grande y también $k$ grande (mucha información). Pero ambas cosas compiten. Si alguien te propone un código binario $[8,5,3]$, ¿merece la pena buscarlo? Dos límites clásicos responden en un minuto (es el ejercicio 3).

Cota de Singleton. Para todo código $[n,k,d]$ se cumple

$$d \le n-k+1.$$

La razón de una línea: si borras $d-1$ posiciones, dos palabras código distintas siguen diferenciándose en alguno de los $n-d+1$ símbolos que quedan. Así que esos símbolos distinguen las $q^k$ palabras, y con $n-d+1$ símbolos solo hay $q^{n-d+1}$ posibilidades: hace falta $n-d+1 \ge k$.

Los códigos que alcanzan la igualdad $d=n-k+1$ se llaman MDS (de maximum distance separable): son los que mejor reparten la redundancia. Los de repetición $[3,1,3]$ y de paridad $[3,2,2]$ lo son. Los Reed-Solomon también lo serán, como verás en la lección 9.

Cota de Hamming (empaquetamiento de esferas). Una bola de radio $t$ en $\mathbb{F}_q^n$ contiene

$$V = \sum_{i=0}^{t} \binom{n}{i}(q-1)^i$$

palabras: la propia palabra, las $n(q-1)$ que difieren en una posición, y así hasta $t$. Aquí $\binom{n}{i}$ es el número de formas de elegir las $i$ posiciones dañadas, y $(q-1)^i$ el de darles un valor equivocado. Las $q^k$ bolas no se solapan y caben todas en el espacio de $q^n$ palabras, luego

$$q^k \cdot V \le q^n.$$

Cuando se da la igualdad, las bolas llenan el espacio sin dejar huecos: el código es perfecto. Toda palabra posible está a distancia $\le t$ de exactamente una palabra código.

Ejemplo resuelto

Usamos el Hamming $[7,4,3]$ de siempre, con

$$H=\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}.$$

Qué corrige. Como $d=3$: detecta $d-1=2$ errores, corrige $t=1$ error y corrige $d-1=2$ borrones. Mezclas posibles: $2e+b\le 2$, es decir, 1 error o hasta 2 borrones.

Es perfecto. Con $n=7$, $q=2$, $t=1$: $V = 1 + 7 = 8$, y

$$2^4 \cdot 8 = 16\cdot 8 = 128 = 2^7.$$

Hay igualdad. Cada una de las 128 palabras de $\mathbb{F}_2^7$ es una palabra código o está a distancia 1 de una sola. No sobra ningún hueco: por eso el síndrome de la próxima lección siempre apunta a algo.

No es MDS. Singleton da $n-k+1 = 7-4+1 = 4$, pero $d=3$. El Hamming es perfecto en el sentido de Hamming, pero no alcanza Singleton. Ambas cotas miden cosas distintas.

Corregir 2 borrones. Enviamos $c=(1,0,1,1,0,1,0)$ y recibimos $(?,0,1,1,?,1,0)$: se han borrado las posiciones 1 y 5. Llamamos $x_1$ y $x_5$ a lo desconocido y usamos $Hc^T=0$ fila a fila, sumando módulo 2:

• Fila 2: $x_1 + x_3 + x_4 + x_6 = x_1 + 1 + 1 + 1 = x_1 + 1 = 0$, luego $x_1 = 1$.
• Fila 1: $x_1 + x_2 + x_4 + x_5 = 1 + 0 + 1 + x_5 = x_5 = 0$, luego $x_5 = 0$.
• Fila 3 (comprobación): $x_2+x_3+x_4+x_7 = 0+1+1+0 = 0$. Correcto.

Recuperamos $c=(1,0,1,1,0,1,0)$. Con dos borrones cualesquiera funciona siempre: dos palabras código distintas difieren en al menos $d=3$ posiciones, así que no pueden coincidir en las 5 que quedan visibles.

Con 3 borrones ya no. Si se borran las posiciones 1, 2 y 3, lo visible es $(?,?,?,1,0,1,0)$. Las columnas 1, 2 y 3 de $H$ suman cero: $(1,1,0)+(1,0,1)+(0,1,1)=(0,0,0)$. Por tanto $(1,1,1,0,0,0,0)$ es palabra código, y sumándola a $c$ sale otra palabra código, $(0,1,0,1,0,1,0)$, que coincide con $c$ en todo lo visible. No hay forma de elegir entre las dos: el código, con $d=3$, no puede deshacer más de $d-1=2$ borrones en general.

Herramienta: el QR

Un código QR protege sus datos con un código Reed-Solomon (lo verás en la lección 9) y deja elegir el nivel de corrección: L, M, Q o H. Según Denso Wave, la empresa que lo inventó, corrigen aproximadamente el 7 %, el 15 %, el 25 % y el 30 % de las palabras código. Cuanto más alto el nivel, más redundancia, más grande el dibujo y mayor daño que aguanta. En la herramienta QR que corrige errores puedes estropear un QR y ver hasta dónde lo recupera.

Ejercicios

Ejercicio 1

Con el Hamming $[7,4,3]$ recibes $(0,?,1,0,1,?,0)$, con borrones en las posiciones 2 y 6. Recupera la palabra enviada.

Ver la solución

Llamamos $x_2$ y $x_6$ a lo desconocido. Con $Hc^T=0$:

• Fila 1: $x_1 + x_2 + x_4 + x_5 = 0 + x_2 + 0 + 1 = 0$, luego $x_2 = 1$.
• Fila 2: $x_1 + x_3 + x_4 + x_6 = 0 + 1 + 0 + x_6 = 0$, luego $x_6 = 1$.
• Fila 3 (comprobación): $x_2 + x_3 + x_4 + x_7 = 1+1+0+0 = 0$. Correcto.

La palabra enviada fue $(0,1,1,0,1,1,0)$, que es la codificación del mensaje $(0,1,1,0)$.

Ejercicio 2

Un código tiene $d=6$. Calcula cuántos errores detecta, cuántos corrige y cuántos borrones corrige. Después, para cada número de errores $e$, di cuántos borrones $b$ como máximo puede corregir a la vez.

Ver la solución

Detecta $d-1 = 5$ errores. Corrige $t=\lfloor 5/2\rfloor = 2$ errores. Corrige $d-1=5$ borrones.

Mezclas: $2e+b\le 5$.

• $e=0$: $b\le 5$.
• $e=1$: $b\le 3$.
• $e=2$: $b\le 1$.

Con $e=3$ ya no cabe ni un borrón ($6>5$).

Ejercicio 3

¿Puede existir un código binario lineal $[8,5,3]$? Prueba primero con Singleton y después con Hamming.

Ver la solución

Singleton: $n-k+1 = 8-5+1 = 4 \ge 3$. No lo descarta.

Hamming: con $t=1$ la bola tiene $V=1+8=9$ palabras, y haría falta

$$2^5\cdot 9 = 288 \le 2^8 = 256,$$

que es falso. Las 32 bolas no caben en el espacio. No existe un código binario $[8,5,3]$. (Sí existen el $[7,4,3]$ y el $[15,11,3]$: son códigos de Hamming de la lección 4, y los dos alcanzan la cota con igualdad; por ejemplo, $2^{11}\cdot16=2^{15}$.)

En resumen

• Un error cambia un símbolo en un sitio desconocido; un borrón lo pierde en un sitio conocido.
• Con distancia mínima $d$: se detectan $d-1$ errores, se corrigen $\lfloor (d-1)/2 \rfloor$ errores y se corrigen $d-1$ borrones.
• En general se corrige mientras $2e+b\le d-1$.
• Singleton: $d\le n-k+1$ (con igualdad, MDS). Hamming: $q^k\cdot V\le q^n$ (con igualdad, perfecto).
• El Hamming $[7,4,3]$ es perfecto pero no MDS; Reed-Solomon será MDS.

Siguiente lección: Decodificación por síndrome