El código de Hamming

El código de Hamming es la manera de enviar un mensaje de forma que, si un bit se estropea por el camino, el receptor no solo se dé cuenta sino que sepa cuál fue y lo repare, sin pedir que se repita nada. Lo consigue añadiendo unos pocos bits redundantes calculados con una astucia: a un mensaje de cuatro bits le bastan tres de comprobación, siete en total, para localizar cualquier error único entre los siete. Richard Hamming lo inventó en 1947 en los Laboratorios Bell por un motivo muy concreto —una máquina que tiraba su trabajo de fin de semana a la basura— y con ello fundó la teoría de los códigos correctores, que hoy está en cada disco duro, cada módulo de memoria, cada llamada de móvil y cada foto enviada desde una sonda espacial.

La historia la contó el propio Hamming muchas veces. En los Laboratorios Bell, los cálculos se hacían en máquinas de relés que leían tarjetas perforadas, y los investigadores como él, sin prioridad, tenían las máquinas los fines de semana. La máquina detectaba los errores —ya usaba un bit de paridad, que avisa cuando el número de unos de una palabra no es el esperado— pero al detectar uno se limitaba a abandonar el trabajo y pasar al siguiente. Dos fines de semana seguidos Hamming encontró el lunes que su cálculo se había interrumpido en la primera hora. «Si la máquina puede saber que hay un error, ¿por qué no puede saber dónde está y arreglarlo?», se preguntó, y la respuesta le ocupó los dos años siguientes. El artículo salió en 1950, con retraso porque Bell quiso patentarlo primero.

El truco está en dónde se colocan los bits de comprobación, y la figura lo hace visible. Se numeran las siete posiciones del 1 al 7. Los bits de paridad van en las posiciones que son potencias de dos, la 1, la 2 y la 4; los cuatro bits de datos, en las demás. El primer bit de paridad vigila todas las posiciones cuyo número, escrito en binario, tiene un 1 en el último lugar: la 1, la 3, la 5 y la 7. El segundo vigila las que tienen un 1 en el penúltimo: 2, 3, 6 y 7. El tercero, las que lo tienen en el antepenúltimo: 4, 5, 6 y 7. Cada paridad se ajusta para que el número de unos de su grupo sea par. Al recibir la palabra, el receptor rehace las tres comprobaciones. Si las tres cuadran, no ha habido error. Si alguna falla, se escribe un 1 por cada comprobación fallida y un 0 por cada correcta, en orden, y ese número binario —el síndrome— es la posición exacta del bit estropeado. Un error en la posición 6, que es 110 en binario, hace fallar la segunda y la tercera comprobación y no la primera; el síndrome 110 dice «6». Se voltea ese bit y el mensaje sale intacto. Los tres círculos de la figura son la misma idea dibujada: cada bit de datos está en la intersección de los círculos que lo vigilan, y los círculos que se ponen en naranja se cortan justo en el culpable.

El código tiene un límite, y la figura lo muestra en cuanto se estropean dos bits. El síndrome sigue señalando una posición, pero es la equivocada: el receptor «corrige» un bit sano y entrega un mensaje falso con toda confianza. La razón es una noción geométrica que Hamming introdujo en el mismo artículo y que lleva su nombre, la distancia: el número de bits en que difieren dos palabras. Las dieciséis palabras válidas del código (7,4) están todas a distancia tres o más unas de otras; un error las aleja una unidad de la palabra original y las deja aún a dos de cualquier otra, así que la más cercana es la correcta; con dos errores la palabra recibida queda a distancia uno de alguna otra palabra válida y el receptor la elige. Añadir un octavo bit que sea la paridad de los otros siete —el código (8,4) del segundo botón— no permite corregir dos errores, pero sí distinguir si ha habido uno o dos, y en el segundo caso pedir un reenvío en lugar de inventar. Es el compromiso que todo código tiene que elegir: cuántos bits de más enviar a cambio de cuántos errores corregir o detectar, y el botón que envía dos mil mensajes por un canal con ruido permite ver cómo cambia la cuenta según lo ruidoso que sea el canal.

Claude Shannon, en el despacho de al lado, había demostrado dos años antes algo que parecía imposible y que el código de Hamming hacía tangible: que por un canal con ruido se puede transmitir sin errores a una velocidad distinta de cero, siempre que se envíe redundancia bien elegida y no se pase de cierta capacidad. Shannon dijo qué era posible sin decir cómo; Hamming dio el primer cómo. Los que siguieron fueron más potentes y menos evidentes. Los códigos de Reed y Solomon de 1960 tratan los datos como coeficientes de un polinomio y corrigen ráfagas de errores consecutivos, y por eso están en los CD, donde una raya del disco borra miles de bits seguidos, en los códigos QR, que se leen con la mitad tapada, y en las sondas Voyager. Las memorias RAM de los servidores llevan una extensión del propio Hamming que corrige un bit y detecta dos, exactamente el código (8,4) de la figura a mayor escala. Y los códigos de comprobación de paridad de baja densidad que llevan el 5G y el wifi moderno rozan el límite de Shannon a costa de una decodificación que solo un ordenador puede hacer.

Hamming veía en su código algo más que una herramienta. En las conferencias que dio al final de su vida, recogidas en El arte de hacer ciencia e ingeniería, insistía en que la lección no era el código sino la pregunta: dejar de aceptar que la máquina se detuviera y preguntarse qué hacía falta para que no lo hiciera. La figura conserva esa pregunta. Un bit que cambia por el camino es un hecho del mundo, inevitable; que el mensaje llegue bien de todas formas es una decisión de diseño, y cuesta exactamente tres bits de cada siete. El resto del itinerario mira el otro lado del problema: qué pasa cuando el que cambia los bits no es el ruido sino un adversario, y para eso está la clave pública.