DE CERVEZAS y otras cosas: CSI XI: Códigos que corrigen errores

En este blog hemos hablado bastante de codificación de datos. Lo hicimos para hablar de cómo se transmitía la información para que las características del medio de transmisión no afectasen demasiado a la señal. Y más tarde os conté de qué manera se podía codificar la información para que ocupase mucho menos espacio. En este último caso nos parecía estupendo que la misma información pudiese ocupar menos espacio del que ocupaba. Hoy en cambio codificaremos para que la información ocupe más.

Siendo un poco ingenieriles: si ocupa más, tendrá mayor coste almacenar estos datos, así que, ¿qué ganamos al codificar la misma información con más bits?. Bien, pues en este caso en concreto, los bits añadidos nos servirán para saber si se produjo un error durante la transmisión de esta información. Y no sólo eso, sino que además nos permitirá recuperar la información original, esto es, reparar el fallo.

Hoy hablaremos de códigos detectores y correctores de errores.

Para ello necesitamos cierta base. Este tema se presta a una modelización matemática mediante operaciones con matrices y cosas de esas, pero nosotros no llegaremos tan lejos. Nos bastará con entender un concepto muy sencillo: el de distancia de Hamming ¹.

Empecemos: llamamos código a una representación de datos que sigue ciertas reglas para su construcción. Por ejemplo, cuando hablé de la codificación Huffman os conté el proceso o reglas para obtener el código asignado a cada símbolo. Obteníamos para cada uno una palabra codificada. Ésta, por supuesto, satisfacía las reglas de la codificación.

Aquí lo importante es ver que no todas la palabras posibles obedecen las reglas de la codificación. Dicho de otro modo: el conjunto de palabras codificadas es un subconjunto de todas las palabras posibles. Imaginemos que hemos diseñado nuestra codificación de modo que un error de un bit en la palabra provoque que la palabra resultante no pertenezca al conjunto de palabras codificadas. En ese caso, el receptor se dará cuenta de ello y asumirá que ha habido un error. Acabamos de detectar un fallo.

Pongamos el ejemplo más típico: códigos de paridad par. Contamos el número de unos de cada palabra y añadimos un bit a la misma: un 1 si el total de unos es par y un 0 en caso contrario. El receptor realizará el mismo proceso: si ha habido un error de un bit en la transmisión, entonces el bit de paridad no coincidirá con el recibido. Por supuesto, el invento se nos va al traste si hay dos errores en la transmisión. Pero, ¿a que es maravilloso poder detectar, añadiendo un simple bit, todos las inversiones (fallos) posibles de un bit?.

Vamos a poner una medida del número de fallos que puede detectar y corregir un código. Se define como distancia de Hamming el número de bits en que se diferencian dos palabras. Tan sencilo como eso: la distancia de Hamming entre 100110 y 101100 es 2, porque cambian dos bits de una a la otra. La distancia de Hamming de un código es la distancia de Hamming mínima entre dos palabras válidas del código distintas. El código de paridad par que hemos visto antes tiene una distancia de Hamming igual a 2. Porque la mínima distancia entre dos palabras distintas cualesquiera es 1 bit. Pero si hay un error que cambia un bit, entonces también el bit de paridad ha de ser distinto.

Bien, pues aquí no se demostrará, pero el tema (temazo) es que para que un código detecte errores de n bits, su distancia de Hamming debe ser mayor o igual a n+1. Y para que un código corrija errores de n bits, su distancia de Hamming debe ser mayor o igual a 2n+1. Y ya lo más: un código corrige hasta n_c errores y detecta n_a errores si cumple que su distancia de Hamming es mayor igual a 2n_c+n_a+1.

En el dibujo de al lado podemos ver el más simple de los ejemplos. En el primer dibujo vemos un código de paridad par. De las 8 palabras posibles, sólo 4 son válidas. Cada arista representa una distancia de Hamming entre palabras igual a 1. En el primer caso, la distancia de Hamming del código es 2. Si transmitimos un 000 y se produce un error de un bit, entonces alcanzaremos una palabra no válida en el código (puntos negros). En cambio los errores de dos bits (011, 110, 101) serán tomados como palabras válidas.

En el segundo caso las únicas palabras válidas del código son 000 y 111. La distancia de Hamming es entonces 3. Vemos como ahora se detectan errores de hasta dos bits (si damos dos saltos desde cualquier palabra válida llegamos a una no válida). Pero además, errores de 1 bit se 'corrigen' sustituyendo la palabra por la más cercana válida en el código. En cambio, errores de dos bits se corregirían incorrectamente.

Evidentemente, la expresión de Hamming nos indica que, cuanto mayor sea el código que añadamos a la información (1 bit en el primer ejemplo, 2 en el segundo), mayor cantidad de errores podremos detectar y corregir. Pero claro, esa información añadida consume ancho de banda y espacio: supone más dinero. El ingeniero debe alcanzar un compromiso entre el coste de añadir esa información y los beneficios que genera. Como siempre.

La generalización de estos códigos se emplea altamente, por ejemplo para detectar errores en memorias. Los códigos SEC de Hamming (Single Error Correcting) se utilizan para corregir un único error en la transmisión de datos. El que Hamming propuso era capaz de corregir el fallo de 1 bit en 4 bits de datos, empleando códigos de 3 bits. Para corregir un fallo en 8 bits de datos empleando SEC, necesitamos 4 bits añadidos. Para 16 bits, 5 de código...

Los códigos SEC de Hamming son muy sencillos de generar y muy eficientes. Por desgracia, tienen el problema de que cuando se producen más fallos de los tolerados, la corrección genera una palabra inválida y, en principio, no podemos saber si durante la transmisión se produce sólo uno o más fallos. Pero bueno... ¡ni siquiera Hamming era perfecto!