La corrección de errores Reed–Solomon, explicada de forma sencilla

La corrección de errores Reed–Solomon es el caballo de batalla silencioso que mantiene los CD sonando pese a los arañazos, las naves espaciales comunicándose a través del sistema solar y los códigos QR escaneándose con un logotipo pegado en el centro. Corrige grupos enteros de errores, y puedes captar cómo lo hace sin una sola ecuación.

Inventado por Irving Reed y Gustave Solomon en 1960, este código es una de las ideas más exitosas de la historia de la comunicación. Está en todas partes y, sin embargo, es casi invisible. Construyamos una intuición de cómo funciona, por qué es tan bueno sobreviviendo a los daños y por qué ese obstinado código QR con el logotipo de tu empresa aún se lee a la perfección. 🐾

¿Quién inventó los códigos Reed–Solomon?

Irving Reed y Gustave Solomon publicaron el código en 1960, construyendo sobre los cimientos que Claude Shannon y Richard Hamming habían puesto una década antes. Donde los códigos de Hamming arreglan un solo bit invertido, Reed y Solomon apuntaron más alto: corregir muchos errores a la vez, incluidas las ráfagas caóticas que ocurren cuando toda una región de datos queda borrada.

Esa ambición convirtió su código en la solución de referencia allí donde el daño llega en grumos en lugar de en bits solitarios, lo que resulta ser casi en todas partes en el mundo físico. Un arañazo en un disco, una mancha en una etiqueta o un desvanecimiento en una señal de radio destruyen todos tramos de datos adyacentes, y Reed–Solomon se come ese tipo de daño para desayunar.

¿Cómo funciona Reed–Solomon, de forma intuitiva?

Olvida los bits por un momento y piensa en puntos de una gráfica. Supongamos que tu mensaje define una curva suave. Para dibujar una línea recta, solo necesitas de verdad dos puntos, pero ¿y si trazaras diez puntos a lo largo de esa misma línea y los enviaras todos?

Ahora imagina que unos pocos de esos puntos se emborronan o se descolocan en el trayecto. Como los puntos adicionales son redundantes, aún puedes ver con claridad la línea subyacente: los puntos que sobreviven revelan exactamente por dónde debe ir la curva, y los dañados destacan por ser los que no encajan. Reed–Solomon funciona con este principio: trata tus datos como definidores de una curva matemática y envía puntos adicionales, de modo que, aunque algunos se corrompan, la curva original (y por tanto tu mensaje) pueda reconstruirse.

Traza más puntos de los que necesitas para definir una curva, y unos pocos puntos arruinados no podrán ocultar por dónde va la curva. Esa redundancia —puntos adicionales que deben coincidir todos— es el corazón de Reed–Solomon.

¿Qué son los símbolos y los cuerpos finitos?

Un detalle clave: Reed–Solomon no trabaja sobre bits individuales. Trabaja sobre símbolos: pequeños grupos de bits tratados como una sola unidad, a menudo un byte (8 bits) cada uno. Esto es precisamente por lo que es tan bueno contra las ráfagas: si ocho bits adyacentes se destruyen juntos, eso es solo un símbolo dañado, no ocho errores separados.

Las matemáticas ocurren sobre algo llamado cuerpo finito (también conocido como cuerpo de Galois): un sistema numérico autónomo con un conjunto fijo y finito de valores, donde la suma y la multiplicación siempre producen otro valor dentro del conjunto. No necesitas dominar el álgebra; lo importante es que un cuerpo finito permite a Reed–Solomon hacer aritmética exacta y cíclica sobre los símbolos sin redondeos ni desbordamientos. Es el pulcro patio de recreo matemático que hace posible una reconstrucción fiable.

¿Cuántos errores puede corregir?

Aquí está la regla elegante que rige todo: para corregir t errores de símbolo, Reed–Solomon añade 2t símbolos de comprobación. En palabras, cada dos símbolos de comprobación adicionales compran el poder de corregir por completo un símbolo dañado.

Símbolos de comprobación añadidos	Errores de símbolo corregibles
2	1
4	2
10	5
2t	t

¿Por qué 2 por error y no 1? Porque una corrección completa requiere resolver dos misterios a la vez: dónde está el error y cuál debería ser el valor correcto. Cada símbolo de comprobación aporta una pieza de ese rompecabezas, así que necesitas dos por error. (Si un escáner ya sabe que la ubicación de un símbolo está dañada —un «borrado»—, solo necesita un símbolo de comprobación para arreglarlo, una eficiencia extra que Reed–Solomon puede aprovechar.)

¿Por qué lo usan los códigos QR y los CD?

Reed–Solomon es la elección estándar allí donde un reintento es imposible y el daño llega en grumos. Eso describe una gama notable de tecnología:

• CD y DVD: un arañazo destruye un tramo de datos adyacentes, exactamente el escenario de ráfaga que Reed–Solomon maneja mejor, así que tu música sigue sonando.
• Sondas del espacio profundo: las señales de naves lejanas son débiles y ruidosas, y reenviar a través de horas luz es poco práctico, así que los datos deben repararse a sí mismos al llegar.
• Códigos QR: los códigos impresos se emborronan, se arrugan y se cubren, y no pueden pedir que se los reenvíe, así que llevan la redundancia de Reed–Solomon integrada en la cuadrícula.
• Almacenamiento y difusión de datos: los discos duros, la televisión digital y más se apoyan en ella para mantener los bits intactos.

En todos los casos el atractivo es el mismo: corrección robusta, apta para ráfagas, sin necesidad de una segunda oportunidad. Es la promesa de Shannon de una comunicación fiable sobre un canal ruidoso, cumplida en la práctica; consulta nuestra introducción a la teoría de la información para la teoría que la sustenta.

¿Por qué los códigos QR con logotipos siguen escaneándose?

Este es el que gusta al público, y ahora la razón está clara. Un código QR se crea con una cantidad elegida de redundancia Reed–Solomon entretejida en su cuadrícula. Cuando un diseñador coloca un logotipo en el centro, está destruyendo deliberadamente algunos de los símbolos del código, pero el escáner no entra en pánico. Trata el logotipo exactamente como un arañazo o una mancha de café.

Mientras el número de símbolos dañados se mantenga por debajo del presupuesto de corrección del código (su t), Reed–Solomon reconstruye los datos ocultos a partir de los símbolos supervivientes y los símbolos de comprobación, y el código se lee a la perfección. Agranda demasiado el logotipo —más allá del presupuesto— y ninguna matemática podrá salvarlo. Ese presupuesto es exactamente lo que fijas cuando eliges un nivel de corrección de errores, como se explica en corrección de errores de los códigos QR. Los niveles más altos añaden más símbolos de comprobación, lo que permite logotipos más grandes y más desgaste.

¿Cuáles son los límites?

Reed–Solomon no es magia. Su presupuesto de corrección se fija cuando se crea el código, así que el daño que supera los t símbolos por bloque no puede recuperarse, y, en un código QR, algunas regiones como los patrones de posición no están protegidas en absoluto por la corrección de errores, porque el escáner las necesita intactas solo para localizar el código. Cúbrelas y ni siquiera un Reed–Solomon impecable podrá ayudar, y por eso un logotipo pertenece al área de datos, nunca sobre un patrón de posición de una esquina. La anatomía de un código QR muestra exactamente qué parte es cuál.

Reed–Solomon en una frase

Al tratar los datos como puntos que definen una curva y enviar puntos adicionales como símbolos sobre un cuerpo finito, Reed–Solomon corrige hasta t errores de símbolo por cada 2t símbolos de comprobación que añade: las matemáticas a prueba de ráfagas que mantienen legibles los CD, las naves espaciales y los códigos QR con logotipo.

¿Quieres un código que sobreviva al mundo real? Puedes crear un código QR gratis con QR Puppy y elegir cuánta protección Reed–Solomon lleva.

Preguntas frecuentes

¿Quién inventó los códigos Reed–Solomon y cuándo?

Irving Reed y Gustave Solomon los publicaron en 1960. Su objetivo era corregir muchos errores a la vez, especialmente las ráfagas de daño que afectan al almacenamiento y la comunicación del mundo real, yendo mucho más allá de las correcciones de un solo bit de los códigos anteriores.

¿Por qué Reed–Solomon trabaja sobre símbolos en lugar de bits?

Porque agrupar bits en símbolos lo hace excelente contra los errores en ráfaga. Si un tramo de bits adyacentes se destruye junto, eso cuenta como un solo símbolo dañado en lugar de muchos errores separados, así que un grumo de daño es barato de arreglar.

¿Cuántos errores puede corregir Reed–Solomon?

Corrige hasta t errores de símbolo por cada 2t símbolos de comprobación añadidos. Necesitas dos símbolos de comprobación por error corregible porque cada corrección debe determinar tanto la ubicación del error como su valor correcto.

¿Por qué los códigos QR con logotipos siguen escaneándose?

Un logotipo destruye algunos de los símbolos del código, pero Reed–Solomon lo trata como un arañazo y reconstruye los datos ocultos, siempre que el área cubierta se mantenga dentro del presupuesto de corrección del código. Agranda el logotipo más allá de ese presupuesto y dejará de funcionar.

¿Hay algún daño que Reed–Solomon no pueda arreglar en un código QR?

Sí. El daño que supera el presupuesto de corrección es irrecuperable, y los patrones de posición de las esquinas no están protegidos en absoluto por la corrección de errores. Si esos se cubren, el escáner ni siquiera puede localizar el código, así que mantén los logotipos en el área de datos.