¿Por qué funciona el código QR aunque esté roto?

Un código QR no guarda solo tu mensaje: guarda también unos bytes de más, calculados a partir de él con un código de Reed-Solomon. Cuando una mancha estropea algunos bytes, el lector resuelve unas ecuaciones en un cuerpo de 256 elementos, averigua cuáles mienten y qué valían, y los repone. Mientras el daño sea pequeño y los tres cuadrados de las esquinas sigan visibles, el QR se lee como si nada.

La idea

Qué hay dentro de un QR

Un QR es una cuadrícula de cuadraditos blancos y negros, los módulos. El más pequeño, la versión 1, mide 21 × 21 módulos. Cada versión añade 4 módulos por lado, hasta la versión 40, de 177 × 177 (lo dice la norma ISO/IEC 18004).

Hay dos clases de módulos. Unos no llevan información, sino que ayudan a leer. Los más visibles son los patrones de búsqueda, los tres cuadrados de las esquinas. Cada uno son tres cuadrados concéntricos, y cualquier recta que pase por su centro cruza franjas negras y blancas en la proporción 1 : 1 : 3 : 1 : 1. Eso permite al lector encontrar el código en la imagen, y su posición relativa le da la situación y la orientación. Hara cuenta que escogieron esa proporción tras estudiar qué razones aparecen en textos y figuras impresos y comprobar que esta casi nunca sale. Hay otros módulos más discretos: las líneas de cuadros alternos blancos y negros que marcan la posición de cada fila y columna, los cuadrados pequeños de alineación de las versiones mayores, que ayudan a corregir deformaciones moderadas de la imagen, y la información de formato, que dice cuál es el nivel de corrección y cuál la máscara aplicada.

Los demás módulos llevan bits. Se agrupan de ocho en ocho para formar bytes, que la norma llama palabras del código. Unas son datos (tu texto o tu dirección web) y otras son de corrección, calculadas a partir de las de datos. En la versión 1 hay 26 palabras en total, repartidas en 208 módulos.

El QR lo creó Masahiro Hara en Denso, la empresa japonesa del automóvil, para marcar piezas en la industria. Según su propio relato, empezó a desarrollarlo en 1992 y el código estaba listo en 1994. «QR Code» es hoy una marca registrada de Denso Wave, la empresa en la que trabajaba Hara cuando escribió ese relato. Entre los motivos para elegir Reed-Solomon, Hara cuenta que corrige bien los errores en ráfaga, como los que deja la suciedad.

Cuatro niveles

Quien genera el QR elige cuánta redundancia añadir. Hay cuatro niveles, y la norma da cuánto daño se puede reponer, de forma aproximada y como porcentaje de las palabras del código:

Nivel	L	M	Q	H
Se recupera, aprox.	7 %	15 %	25 %	30 %

Ese porcentaje se paga con espacio. En la versión 1, de 26 palabras, el nivel L deja 19 para datos y 7 para corrección. Los niveles M, Q y H dejan 16, 13 y 9 palabras de datos. Con la librería qrcode, una dirección web de 40 caracteres cabe en la versión 3 (29 × 29 módulos) con los niveles L y M, pasa a la versión 4 (33 × 33) con el Q y a la versión 5 (37 × 37) con el H. Más corrección significa un QR mayor o con módulos más pequeños, y eso lo hace más difícil de leer en una pantalla pequeña o a distancia. La norma dice que el L es adecuado cuando la impresión es buena o se quiere el símbolo más pequeño, el M es el nivel «estándar», el Q es de «alta fiabilidad» y el H ofrece la máxima.

Pruébalo: escribe un texto, elige un nivel y estropea el QR con la tinta o el típex, con una mancha, un arañazo o un logo en el centro. El panel dice si todavía se lee (lo lee jsQR, una librería lectora de QR que corrige con Reed-Solomon) y cuántos módulos de datos has cambiado. Fíjate también en qué pasa si tocas los cuadrados de las esquinas.

Dos cosas que verás. La primera: el logo en el centro funciona porque, para el lector, es un daño más. Tapa módulos, estropea unas cuantas palabras, y si son menos de las que el nivel puede reponer, el QR se lee. No hay nada especial en el logo, y por eso conviene un nivel alto si piensas poner uno. La segunda: cambiar módulos de los patrones de las esquinas no se corrige. Esos módulos no son palabras del código, así que Reed-Solomon no los ve. Si se estropean demasiado, el lector ni siquiera sabe dónde está el QR.

Por qué sobra información y por qué eso basta

La idea es la del instituto: por dos puntos pasa una sola recta, y por tres, una sola parábola. Un polinomio de grado menor que $k$ queda fijado por $k$ de sus puntos, sean cuales sean.

Imagina que tu mensaje fueran los $k$ coeficientes de un polinomio y que, en vez de mandarlos, mandaras sus valores en $n$ puntos, con $n$ mayor que $k$. Es como apuntar siete puntos de una parábola cuando bastan tres. Si el canal estropea algunos valores, los que sobreviven siguen estando sobre la misma curva, y los falsos se delatan porque no encajan. Mientras queden suficientes valores correctos, solo hay una curva que pase por casi todos: la que sale es la tuya.

En el QR no hay números reales, sino bytes. Un byte tiene 256 valores posibles, y se pueden sumar y multiplicar bytes (con unas reglas especiales) de modo que siempre sale otro byte y se puede dividir entre cualquier byte distinto de cero. Esa estructura se llama cuerpo finito, y se explica en la lección de cuerpos finitos. Todo lo de «polinomio por pocos puntos» funciona igual en ella.

Hay una regla para contar. Cada palabra de corrección que se añade permite reponer una palabra cuya posición ya se conoce (un borrón: se sabe que está mal, solo falta saber su valor). Pero si no se sabe cuál está mal (un error), hace falta una palabra de corrección para averiguar dónde y otra para averiguar cuánto. Por eso, con $r$ palabras de corrección se corrigen hasta $r/2$ errores o hasta $r$ borrones. La lección sobre errores y borrones lo desarrolla.

Bytes, no módulos

Hay otra razón para trabajar con bytes. Una mancha de tinta estropea módulos vecinos, y la norma coloca los ocho módulos de cada palabra juntos, en un rectángulo de 2 × 4 cuando no hay nada por medio. Así, una mancha pequeña toca pocas palabras, aunque cambie muchos bits. Para un código que cuenta palabras erróneas, da igual que se hayan estropeado uno o los ocho bits de cada una. Un código que contara bits se vería superado por una mancha que a este apenas le molesta.

Hay un segundo truco, el entrelazado. Un QR grande no usa un solo bloque de Reed-Solomon, sino varios, cada uno con sus palabras de datos y de corrección. Las palabras de los bloques se envían alternadas: la primera de cada bloque, luego la segunda de cada bloque, y así. De esa forma una mancha compacta reparte sus palabras estropeadas entre varios bloques, y cada uno tiene que corregir pocas. Por ejemplo, la versión 5 con el nivel Q tiene 134 palabras, divididas en 4 bloques con 18 palabras de corrección cada uno: como mucho, 9 palabras erróneas por bloque. Como las palabras de los cuatro bloques van alternadas, una mancha que estropee 12 palabras seguidas deja unas 3 en cada bloque, y se corrige. Sin entrelazado, esas 12 caerían en un solo bloque y no. (El número de bloques sale de la librería qrcode; la norma lo da en su tabla 9, que no se lee en la copia pública consultada.)

Si quieres ver el mismo fenómeno con una imagen cualquiera y cualquier código, usa Raya y corrige: reparte una imagen en bloques de Reed-Solomon, la rayas y ves cuándo se corrige y cuándo no.

Qué pasa de verdad (y qué no)

• Los porcentajes son aproximados. La norma los llama «aproximados». En la versión 1-M, por ejemplo, la norma corrige 4 palabras de 26, un 15,4 %. Y su propio ejemplo de la versión 6-H da un 32,6 %, no un 30 %.
• Es un máximo. El 30 % se alcanza si el daño estropea ese número de palabras y ninguna más. Si en vez de una mancha compacta hay ruido repartido por todo el QR, cada módulo cambiado puede tocar una palabra distinta y se llega mucho antes al límite.
• Con los patrones de búsqueda tapados no hay nada que corregir. Los tres cuadrados no forman parte del código corrector.
• No todos los lectores aprovechan lo mismo. La norma contempla los borrones (palabras ilegibles de posición conocida), pero aquí no se ha comprobado cuáles de los lectores reales los usan. En el código de jsQR, el lector de la demo, no aparece ningún tratamiento de borrones: solo corrige errores, que es la mitad de potente. A cambio, jsQR usa todas las palabras de corrección y no reserva las de protección que pide la norma (se explican más abajo): en la versión 1 corrige 3, 5, 6 y 8 palabras erróneas con L, M, Q y H, una más que la norma con L y con M.

Las matemáticas de verdad

El cuerpo. Un byte $b_7\dots b_0$ es el polinomio $b_7x^7+\dots+b_0$ con coeficientes en $\mathbb{F}_2$. Sumar bytes es sumar coeficientes módulo 2, es decir, un XOR bit a bit. Multiplicar es multiplicar polinomios y reducir módulo el polinomio de la norma:

$$p(x)=x^8+x^4+x^3+x^2+1 \quad(100011101\text{ en binario, } 285\text{ en decimal}).$$

La norma ISO/IEC 18004 lo describe como el cuerpo de Galois de $2^8$ elementos con 100011101 como polinomio primo. Como $p$ es irreducible, $\mathbb{F}_2[x]/(p)$ es un cuerpo de 256 elementos, el $\mathrm{GF}(256)$. Además, $\alpha = x$ genera todos los elementos no nulos: tiene orden 255 (basta calcular sus 255 primeras potencias con un programa y ver que no se repiten). Por eso todo elemento no nulo es una potencia $\alpha^j$, con $0\le j<255$, y $\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$, que es el byte 1D.

El código. Cada bloque tiene $n$ palabras, de las cuales $k$ son de datos y $r=n-k$ de corrección. Llamamos $D(x)=d_0x^{k-1}+\dots+d_{k-1}$ al polinomio de los datos y

$$g(x)=\prod_{i=0}^{r-1}(x-\alpha^i)$$

al polinomio generador. Las $r$ palabras de corrección son los coeficientes del resto $R(x)$ de dividir $x^rD(x)$ entre $g(x)$, que tiene grado menor que $r$. La palabra enviada es

$$C(x)=x^rD(x)+R(x),$$

(en característica 2 sumar es restar), que es un múltiplo de $g(x)$. Así $C(\alpha^i)=0$ para $i=0,\dots,r-1$: cada palabra válida es un polinomio que se anula en esas $r$ potencias de $\alpha$. Es la forma sistemática: los datos van tal cual al principio y la corrección detrás. Es un código de Reed-Solomon, el de la lección de códigos de Reed-Solomon, con dos detalles que cambian respecto de allí. Las raíces empiezan en $\alpha^0$ en vez de $\alpha^1$ (la lección usa $g(x)=(x-\alpha)\cdots(x-\alpha^{n-k})$), lo cual no cambia nada esencial. Y como en el QR $n$ es siempre menor que 255 (el bloque más largo tiene 153 palabras), se trata de un código acortado: es lo mismo que uno de longitud 255 con ceros delante que no se envían.

La distancia. Es $d=n-k+1$. Sea $C$ una palabra no nula con $w$ coeficientes no nulos, en las posiciones con potencias $x^{e_1},\dots,x^{e_w}$. Si $w\le r$, las $w$ primeras ecuaciones $C(\alpha^i)=0$ forman un sistema de Vandermonde con matriz $(\alpha^{ie_j})$ y determinante no nulo (los $\alpha^{e_j}$ son distintos porque $n\le255$), y obligarían a que todos los coeficientes fueran 0. Luego $w\ge r+1=n-k+1$. La cota de Singleton (1964) dice que $d\le n-k+1$ para cualquier código, de modo que aquí se alcanza: es un código de distancia máxima separable (MDS).

Cuánto corrige. Si se estropean $e$ palabras en posiciones desconocidas y $b$ en posiciones conocidas, hay $2e+b$ incógnitas (para cada error, posición y valor; para cada borrón, solo el valor), y $r$ ecuaciones. Con $2e+b\le r$ el problema tiene solución única. Dos soluciones distintas darían dos palabras del código a distancia $\le 2e+b\le r<d$, absurdo. En particular se corrigen $t=\lfloor (n-k)/2\rfloor$ errores o hasta $n-k$ borrones.

El síndrome. El lector calcula, con la palabra recibida $\tilde C=C+E$ ($E$ es el error), los números $S_i=\tilde C(\alpha^i)=E(\alpha^i)$ para $i=0,\dots,r-1$. Si $E$ tiene un solo error de valor $\epsilon$ en la posición de la potencia $x^m$, entonces $S_i=\epsilon\,\alpha^{im}$: $S_0$ da el valor y el cociente $S_1/S_0=\alpha^m$ da la posición. Con varios errores aparecen sumas de esos términos y hay que separarlas; eso lo hacen algoritmos como el de Berlekamp-Massey o el de Euclides (jsQR usa este último), que aquí no desarrollamos. La lección sobre cómo corregir errores en Reed-Solomon explica otro método, el sistema lineal de Berlekamp-Welch, y menciona estos dos.

Un ejemplo con números reales

La norma ISO/IEC 18004 incluye en su anexo I un QR de versión 1 con nivel M que codifica el texto 01234567 (modo numérico). Son $n=26$ palabras, $k=16$ de datos y $r=10$ de corrección. Las palabras de datos, en hexadecimal, son

10 20 0C 56 61 80 EC 11 EC 11 EC 11 EC 11 EC 11.

Las primeras seis llevan el modo, la longitud, los ocho dígitos y una marca de final; el resto es relleno, la pareja EC 11 repetida. Las 10 de corrección que da la norma son

A5 24 D4 C1 ED 36 C7 87 2C 55.

Si se calcula con un programa el resto de dividir $x^{10}D(x)$ entre $g(x)$, con $g(x)=\prod_{i=0}^{9}(x-\alpha^i)$ en el cuerpo de $p(x)$, salen exactamente esos 10 bytes. Es una comprobación independiente de dos cosas: el polinomio $p$ y la forma de $g$. Además $C(\alpha^i)=0$ para $i=0,\dots,9$ y $C(\alpha^{10})\neq0$.

Ahora estropeamos una palabra. La décima (posición 9, empezando en 0) valía 11; le sumamos (XOR) 5A y llega 4B. El lector calcula los síndromes y obtiene

$$S_0=\texttt{5A},\qquad S_1=\texttt{9C},\qquad S_2=\texttt{0A}.$$

$S_0$ es el valor del error. El cociente $S_1/S_0$ es $\alpha^{16}$, y como la palabra de la posición 9 multiplica a $x^{25-9}=x^{16}$, el exponente 16 delata la posición. Con eso el lector resta 5A en esa palabra y recupera 11.

Con cuatro palabras estropeadas, un decodificador de Reed-Solomon (el de la librería galois de Python) corrige el bloque entero. Con cinco también lo hace, porque $d=11$. Con seis, avisa de que no puede corregir. Sin embargo, la norma no da por buenos cinco errores, y por eso su anexo B presenta este código como $(26, 16, 4)$: 4 errores. Reserva $p$ palabras de corrección (las llama misdecode protection codewords) y exige $b+2e\le r-p$, con $p=2$ en la versión 1-M. (La norma escribe $e+2t\le d-p$, con otras letras: su $e$ son los borrones, su $t$ los errores y su $d$ el número de palabras de corrección, no la distancia.) Así, $10-2=8$ permite 4 errores. Con borrones es aún más prudente: cuando son más de la mitad de las palabras de corrección, sube $p$ a 3, y en los símbolos con menos de 8 palabras de corrección desaconseja usarlos. La razón que da es que, si se gasta casi toda la capacidad en borrones, aumenta la posibilidad de que un error pase sin detectarse. Con la versión 1-L, $p=3$ y se corrigen 2 palabras.

Los porcentajes, con números

Con los datos de la versión 1 se ve de dónde sale cada porcentaje. En la versión 1-L hay 7 palabras de corrección, $p=3$ y se corrigen $\lfloor(7-3)/2\rfloor=2$ palabras, el $2/26\approx 7{,}7\,\%$. En la 1-M, $\lfloor(10-2)/2\rfloor=4$, el $4/26\approx 15{,}4\,\%$. Para Q y H, con 13 y 17 palabras de corrección, como mucho se corrigen $\lfloor 13/2\rfloor=6$ y $\lfloor 17/2\rfloor=8$ palabras, el $23{,}1\,\%$ y el $30{,}8\,\%$ de 26: del mismo orden que el 25 % y el 30 % que da la norma. (La parte de la norma que fija $p$ para Q y H falta en la copia pública consultada.) Estas cuentas no están en la norma, que solo dice «aproximado».

La tabla de la versión 1, comprobada con la librería qrcode:

Nivel	Palabras totales	De datos	De corrección	Errores que corrige (según la norma)
L	26	19	7	2
M	26	16	10	4
Q	26	13	13	como mucho 6
H	26	9	17	como mucho 8

Y ahora, ¿qué?

Si quieres ver cómo funciona por dentro, el curso de códigos correctores parte de los cuerpos finitos y llega a la decodificación completa.

Queda una pregunta: ¿por qué bytes? Reed-Solomon alcanza la mejor distancia posible para su longitud y dimensión, pero a cambio, en la forma que usa el QR, necesita un alfabeto con más símbolos que palabras tiene el bloque: con 256 símbolos por palabra, bloques de hasta 255 palabras. Es lo que obliga al QR a trabajar con bytes y a repartir los datos en bloques.

Fuentes

• M. Hara, QRコードの開発と普及 (en japonés), Synthesiology 12(1), 2019, y su versión en inglés, «Development and popularization of QR code». De aquí salen el año 1994, el inicio del desarrollo en 1992, la elección de Reed-Solomon por las ráfagas, los cuatro niveles (que Hara da como porcentaje de la superficie del código) y la proporción 1 : 1 : 3 : 1 : 1.
• ISO/IEC 18004:2006, QR Code 2005 bar code symbology specification (copia pública). De aquí salen el tamaño de las versiones, la tabla de niveles, el polinomio $x^8+x^4+x^3+x^2+1$, la fórmula $e+2t\le d-p$ con sus valores de $p$, el orden alterno de los bloques y el ejemplo de la versión 1-M. Hay ediciones posteriores que no se han consultado; las cifras citadas son las de 2006. La tabla 9 (bloques) y el anexo A (polinomios generadores) no están legibles en esa copia.
• QR code, Wikipedia (fuente secundaria, solo para atribuir a Hara la invención).
• I. S. Reed y G. Solomon, Polynomial codes over certain finite fields, J. SIAM 8(2), 1960.
• R. C. Singleton, Maximum distance q-nary codes, IEEE Trans. Inform. Theory 10(2), 1964.
• Cálculos propios con Python (galois) y la librería qrcode de Node, en el repositorio de la web.