Corrección de errores Reed-Solomon en códigos QR
Cómo funcionan los códigos Reed-Solomon en los códigos QR: aritmética de cuerpos de Galois, polinomios generadores y entrelazado de codewords.
Corrección de errores Reed-Solomon en códigos QR
La corrección de errores es lo que hace que los códigos QR sean notablemente resistentes. El motor matemático detrás de esta resistencia es la corrección de errores Reed-Solomon (RS), un código de bloque basado en aritmética de cuerpos finitos.
Qué hace Reed-Solomon
Los códigos RS añaden codewords redundantes a sus datos. Si algunos codewords se corrompen — por suciedad, rayones, desvanecimiento o colocación de logotipo intencional — el decodificador puede localizar las posiciones corrompidas y reconstruir los datos originales. Un código RS que añade 2t codewords de corrección de errores puede corregir hasta t codewords corrompidos.
Aritmética de cuerpos de Galois
Los códigos RS en códigos QR operan sobre GF(256) — el cuerpo de Galois con 256 elementos. Cada elemento corresponde a un byte (0-255), y el cuerpo define operaciones especiales de suma (XOR) y multiplicación (usando un polinomio primitivo). El polinomio primitivo para códigos QR es:
x^8 + x^4 + x^3 + x^2 + 1 (decimal 285)
Toda la aritmética de codewords — codificación, cálculo de síndromes y corrección de errores — usa operaciones GF(256).
Polinomios generadores
El codificador crea un polinomio generador cuyas raíces son potencias consecutivas del elemento primitivo. Para n codewords de corrección de errores, el polinomio generador tiene grado n. El polinomio de datos se divide entre el polinomio generador, y el resto se convierte en los codewords de corrección de errores.
Entrelazado de codewords
Los códigos QR grandes dividen los datos en múltiples bloques, cada uno con su propia corrección de errores RS. Los codewords de los diferentes bloques se entrelazan luego en el flujo de bits final. Esto distribuye el impacto del daño localizado entre múltiples bloques, mejorando la recuperación ante grandes áreas de daño contiguo.
El lado de la decodificación
Al decodificar, el escáner:
- Calcula síndromes — si todos los síndromes son cero, no existen errores
- Usa el algoritmo de Berlekamp-Massey para encontrar el polinomio localizador de errores
- Aplica la búsqueda de Chien para encontrar las posiciones de error
- Usa el algoritmo de Forney para calcular las magnitudes de error
- Corrige los codewords erróneos
Implicaciones prácticas
| Nivel de EC | Codewords de EC (%) | Codewords corregibles (%) |
|---|---|---|
| L | ~20 % | ~7 % |
| M | ~38 % | ~15 % |
| Q | ~55 % | ~25 % |
| H | ~65 % | ~30 % |
El porcentaje «corregible» es aproximadamente la mitad del porcentaje de codewords de EC, porque cada error requiere dos codewords de EC para localizarlo y repararlo. Si las posiciones de error ya se conocen (borrados), basta con un codeword de EC por posición.
Puntos clave
- Los códigos Reed-Solomon añaden codewords redundantes para la detección y corrección de errores
- La aritmética opera en GF(256) usando el polinomio primitivo x^8+x^4+x^3+x^2+1
- Cada error corregible consume dos codewords de EC
- El entrelazado entre bloques distribuye el daño localizado
- La decodificación RS usa síndromes, el algoritmo de Berlekamp-Massey, la búsqueda de Chien y el algoritmo de Forney