Los códigos correctores de errores explicados

Ningún canal es perfecto. Los rayos cósmicos invierten bits en la memoria, los arañazos borran partes de un disco y las señales de radio se desvanecen. En lugar de esperar lo mejor, los sistemas digitales añaden redundancia de una forma ingeniosa, para que el receptor pueda deducir lo que se envió aunque una parte llegue mal. Las matemáticas de estos códigos, iniciadas a finales de la década de 1940, protegen discretamente casi cada bit que almacenamos o enviamos.

Tres círculos superpuestos con los siete bits de una palabra de código Hamming, con un círculo resaltado donde falla una comprobación de paridad
Tres círculos superpuestos con los siete bits de una palabra de código Hamming, con un círculo resaltado donde falla una comprobación de paridad

Detectar errores con la paridad

La protección más sencilla es un único bit de paridad: se añade un 1 o un 0 para que el número total de unos sea par. Si un bit se invierte por el camino, la cuenta se vuelve impar y el receptor sabe que algo ha ido mal. La paridad no puede decir qué bit es erróneo, y dos inversiones se anulan sin que se note, pero es barata y se usó durante décadas en memorias y enlaces serie. Sin embargo, detectar un error es solo la mitad del trabajo: después hay que volver a enviar los datos.

Corregir por repetición

Para corregir un error sin volver a preguntar, el receptor necesita redundancia suficiente para dejarlo en minoría. Enviar cada bit tres veces, 000 o 111, le permite quedarse con la mayoría: una inversión en un trío se corrige. El precio es alto: tres bits por cada bit de datos, y dos inversiones en el mismo trío siguen ganando. La pregunta que dio origen a la teoría de códigos fue si se podía hacer mejor.

El código de Hamming

En 1947, Richard Hamming trabajaba en los Bell Labs con una computadora de relés que leía los programas de tarjetas perforadas. Cuando la máquina encontraba un error durante el fin de semana, simplemente se detenía, y el lunes Hamming volvía para encontrarse con cálculos desperdiciados. Si una máquina puede detectar un error, se preguntó, ¿por qué no puede localizarlo y corregirlo? Su respuesta, publicada en 1950, envía 4 bits de datos como 7. Tres bits de paridad, en las posiciones 1, 2 y 4, comprueban cada uno un grupo distinto de posiciones superpuestas, elegido de modo que cada error único rompa una combinación única de comprobaciones.

El síndrome

El receptor vuelve a calcular las tres comprobaciones. Si todas pasan, la palabra se acepta. Si algunas fallan, escribir las comprobaciones que fallan como dígitos binarios, con la comprobación 4 como dígito más alto, da un número del 1 al 7: el síndrome, que es exactamente la posición del bit invertido. Volver a invertirlo restaura la palabra de código. El truco funciona porque las posiciones están numeradas de modo que la expansión binaria de cada una enumera las comprobaciones a las que pertenece, y por eso el código se ve tan ordenado cuando se dibuja como tres círculos superpuestos.

La distancia de Hamming

La distancia de Hamming entre dos palabras es el número de posiciones en que difieren. En el código (7,4), dos palabras de código cualesquiera están a una distancia de al menos 3. Una palabra con un error sigue a distancia 1 de la palabra de código enviada y a al menos 2 de todas las demás, así que decodificarla como la palabra de código más cercana la corrige. En general, un código cuyas palabras de código están separadas al menos d detecta d − 1 errores y corrige (d − 1)/2 de ellos, redondeado hacia abajo. Añadir un bit de paridad global eleva la distancia a 4, lo que da el código extendido que corrige un error y detecta dos.

El límite de Shannon

En 1948, dos años antes del artículo de Hamming, Claude Shannon demostró un teorema sorprendente. Todo canal ruidoso tiene una capacidad, y por debajo de ella se pueden enviar datos a cualquier velocidad con tan pocos errores como se quiera, usando códigos lo bastante largos; por encima, los errores son inevitables. Shannon demostró que esos códigos existen, pero no cómo construirlos. Encontrar códigos prácticos que se acerquen a su límite llevó medio siglo, desde los códigos Reed-Solomon en 1960 hasta los turbocódigos en 1993 y el redescubrimiento de los códigos de comprobación de paridad de baja densidad (LDPC).

Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.
Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.

Códigos por todas partes

Los códigos Reed-Solomon permiten que los CD suenen a pesar de los arañazos y que los códigos QR se escaneen con hasta un 30 % del símbolo dañado. La memoria de los servidores usa códigos Hamming extendidos para corregir bits sueltos invertidos por los rayos cósmicos. Las imágenes de los planetas exteriores de las Voyager se protegieron con códigos de Golay y, más tarde, Reed-Solomon, y los códigos LDPC y polares del 5G y el Wi-Fi exprimen casi cada bit que permite el canal. Incluso el código de barras de un libro y el último dígito de un número de cuenta bancaria son sencillos códigos detectores de errores.

Explóralo

Abre el simulador de códigos correctores de errores para codificar cuatro bits de datos cualesquiera con el código Hamming (7,4), invertir bits haciendo clic en ellos en los círculos o en la fila, y ver cómo los círculos que fallan y el síndrome señalan el error antes de que el decodificador lo repare. Activa el bit de paridad adicional para ver cómo se detectan los errores dobles, y envía un mensaje por un canal ruidoso para comparar lo que llega con y sin el código.

Preguntas frecuentes

¿Qué diferencia hay entre detección y corrección de errores?

La detección solo le dice al receptor que algo va mal, así que debe volver a pedir los datos; un bit de paridad o una suma de verificación hacen esto. La corrección permite al receptor reconstruir el original sin preguntar, lo que necesita más redundancia. Los sistemas que no pueden volver a preguntar, como una sonda espacial a millones de kilómetros o un DVD, dependen de la corrección.

¿Por qué no enviar simplemente todo dos veces?

Dos copias muestran que hubo un error, pero no cuál es la copia correcta, y duplican el coste. Tres copias permiten una votación por mayoría, pero lo triplican. El código de Hamming corrige un error único por bloque de siete con menos del doble de bits, y los códigos más largos lo hacen mucho mejor.

¿Quién fue Richard Hamming?

Un matemático estadounidense, 1915-1998, que trabajó en el Proyecto Manhattan y después durante treinta años en los Bell Labs. Además de por sus códigos, es conocido por la ventana de Hamming en el procesamiento de señales, por la distancia de Hamming y por su conferencia «You and Your Research». Recibió el Premio Turing en 1968.

¿Puede un código corregir cualquier número de errores?

Solo con suficiente redundancia. Un código puede corregir hasta (d − 1)/2 errores por bloque, donde d es la distancia mínima entre palabras de código, y los códigos más largos con más bits de comprobación alcanzan un d mayor. El teorema de Shannon fija el límite definitivo: ningún código puede superar la capacidad del canal.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir el simulador de códigos correctores de errores