Las matemáticas que sostienen el código QR - Cómo funcionan los campos finitos y el código Reed-Solomon
Por qué se puede leer un código QR sucio
La mayor característica del código QR es que puede restaurar correctamente los datos aunque una parte del código esté sucia o dañada. Con el nivel de corrección de errores H, los datos originales se pueden restaurar por completo aunque se pierda aproximadamente el 30% del total. Lo que sostiene esta función que parece "magia" es un algoritmo de corrección de errores llamado código Reed-Solomon.
El código Reed-Solomon fue presentado en 1960 por Irving S. Reed y Gustave Solomon. No solo se usa en los códigos QR, sino en todas las situaciones en las que se exige fiabilidad de los datos, como los CD/DVD, la radiodifusión digital, las comunicaciones con el espacio profundo (las sondas Voyager de la NASA) y el almacenamiento RAID. El hecho de que un algoritmo ideado hace más de 60 años se use todos los días en smartphones de todo el mundo demuestra la universalidad de las buenas matemáticas.
Campos finitos (campos de Galois) - La base matemática del código QR
Para entender el código Reed-Solomon, primero hay que conocer una estructura matemática llamada "campo finito" (campo de Galois, Galois Field). En la aritmética cotidiana, los números continúan hasta el infinito (1, 2, 3, ...), pero en un campo finito las cuatro operaciones aritméticas se completan con un número determinado de elementos.
El campo finito que usa el código QR es GF(28), es decir, un campo con 256 elementos. Con los 256 números del 0 al 255 se crea un mundo en el que la suma / resta / multiplicación / división son todas cerradas. "Ser cerrado" significa que, sea cual sea la operación, el resultado siempre queda dentro del rango de 0 a 255.
¿Por qué 256? La unidad básica de los datos que maneja una computadora es 1 byte (8 bits), y los valores que se pueden representar con 1 byte son 256, del 0 al 255. Para procesar los datos del código QR en unidades de 1 byte, se eligió un campo finito con exactamente 256 elementos. La estructura abstracta de las matemáticas y las limitaciones físicas de las computadoras se cruzan de forma hermosa en un único punto: GF(28).
Cómo funciona el código Reed-Solomon - Datos protegidos con polinomios
La esencia del código Reed-Solomon es tratar los datos como un "polinomio". Por ejemplo, si hay 3 bytes de datos [65, 118, 42], se consideran como el polinomio 65x2 + 118x + 42.
Este polinomio se divide sobre GF(28) usando un "polinomio generador", y los valores que se obtienen como resto son las "palabras de código de corrección de errores". Estas palabras de código de corrección de errores se añaden a los datos originales y se almacenan en el código QR.
Al leerlo, el polinomio recibido se divide entre el polinomio generador; si el resto es 0, se determina "sin errores", y si no es 0, "con errores". Si hay errores, a partir del patrón del resto se calcula a la inversa "en qué posición" y "de qué forma" hay un error, y se restauran los datos originales. En este proceso de cálculo inverso se usan técnicas matemáticas avanzadas, como el algoritmo de Berlekamp-Massey y el algoritmo de Forney.
Dicho de forma intuitiva, el código Reed-Solomon es un mecanismo que "traza una curva que pasa por los puntos de los datos y, aunque desaparezcan algunos puntos, restaura la curva original a partir de los puntos restantes". Aprovechando la propiedad matemática de que n puntos determinan de forma única un polinomio de grado n-1, si se añaden puntos adicionales (palabras de código de corrección de errores), se puede reconstruir la curva original (los datos) aunque se pierdan algunos puntos.
Las 2 cifras de los niveles de corrección de errores - Tasa de recuperación y proporción de redundancia
En torno a los niveles de corrección de errores L / M / Q / H hay 2 cifras que se confunden con facilidad. Una es el porcentaje de daño que se puede recuperar (tasa de recuperación): aproximadamente el 7% en el nivel L, el 15% en el M, el 25% en el Q y el 30% en el H. La otra es el porcentaje que ocupa el código de corrección de errores (proporción de redundancia), que indica cuántas de las palabras de código incluidas en el código QR se reservan para la corrección de errores. La explicación "con el nivel H se puede leer aunque esté dañado un 30%" se refiere a la primera cifra, y no significa que el código de corrección de errores ocupe el 30% del total.
Este es un compromiso fundamental de la teoría de la información. Como mostró Claude Shannon en "A Mathematical Theory of Communication", publicado en 1948, para aumentar la fiabilidad en un canal de comunicación con ruido es necesario añadir redundancia (información adicional). El nivel de corrección de errores del código QR es precisamente un parámetro que controla la cantidad de esta redundancia.
Los valores reales de la proporción de redundancia aparecen en el desglose de las palabras de código que define la norma ISO/IEC 18004. La versión más pequeña, la versión 1 (21 × 21 módulos), tiene 26 palabras de código en total. Su desglose es de 19 de datos + 7 de corrección de errores en el nivel L y de 9 de datos + 17 de corrección de errores en el nivel H. El porcentaje que ocupa el código de corrección de errores es de aproximadamente el 27% en el nivel L y de aproximadamente el 65% en el nivel H, es decir, se usa mucha más superficie para la corrección de errores que el 7% o el 30% que se mencionan como tasa de recuperación.
Que las 2 cifras no coincidan se debe al procedimiento con el que el código Reed-Solomon corrige los errores. Para corregir un error hay que averiguar 2 cosas, "qué palabra de código" y "en qué valor se ha transformado", por lo que cada error consume 2 símbolos del código de corrección de errores. Además, para evitar el accidente de confundir el valor alterado y "restaurar" otros datos distintos, el diseño no agota la capacidad de corrección hasta el límite. Al sumarse estas 2 razones, el porcentaje de daño que se puede recuperar queda en la mitad o menos del porcentaje del código de corrección de errores. Si se añade redundancia, la tasa de recuperación aumenta, pero lo añadido no se convierte tal cual en tasa de recuperación.
La diferencia de proporción repercute en el tamaño cuando se introducen los mismos datos. Si se compara en la versión 1, los datos que se pueden almacenar son 19 palabras de código en el nivel L y 9 palabras de código en el nivel H. Para introducir la misma cantidad, en el nivel H se necesitan aproximadamente el doble de palabras de código, y hay que elegir una versión más grande en la misma medida. Por ejemplo, unos datos que en el nivel L caben en la versión 3 (29 × 29 módulos) requieren la versión 5 (37 × 37 módulos) en el nivel H, y así cada lado se va alargando. Nivel L o M cuando el espacio de impresión es limitado, y nivel H cuando el riesgo de suciedad o roce es alto, como en exteriores o en fábricas. En la práctica, la decisión consiste en elegir teniendo en cuenta tanto la tasa de recuperación como la proporción de redundancia.
Matemáticas avanzadas ocultas en la vida cotidiana
Cada vez que escaneas un código QR, dentro del smartphone se ejecutan a gran velocidad operaciones con polinomios sobre un campo finito. Pagar en una tienda de conveniencia, subir al tren, entrar a un evento, consultar el menú de un restaurante. Detrás de estos actos cotidianos, la teoría de códigos ideada en la década de 1960 y la teoría de los campos finitos descubierta por Évariste Galois en el siglo XIX se calculan cientos de millones de veces por segundo.
Galois fue un matemático genial que perdió la vida en un duelo a los 20 años, y de la teoría que dejó se decía en su época que "casi nadie podía entenderla". Que esa teoría se haya convertido 200 años después en la base de una tecnología que personas de todo el mundo usan a diario es uno de los episodios más dramáticos de la historia de las matemáticas.