Campo de Galois

Un campo de Galois (cuerpo finito, Galois Field) es una estructura algebraica con un número finito de elementos en la que las cuatro operaciones aritméticas (suma, resta, multiplicación y división) se cumplen sin contradicciones. Debe su nombre al matemático francés del siglo XIX Évariste Galois. Existe cuando el número de elementos es una potencia de un número primo, p^n, y se denota GF(p^n).

El código Reed-Solomon que se utiliza en la corrección de errores de los códigos QR funciona sobre GF(2^8) = GF(256). GF(256) tiene 256 elementos, del 0 al 255, lo que coincide exactamente con el rango de valores que se puede representar con 1 byte. Como los datos de un código QR se procesan byte a byte, la compatibilidad con GF(256) es perfecta.

Con la aritmética entera habitual, por ejemplo, 200 + 100 = 300, lo que supera el rango de 1 byte. Sin embargo, la suma en GF(256) se define mediante XOR (o exclusivo), por lo que el resultado siempre queda dentro del rango de 0 a 255. La multiplicación también se define como una operación polinómica módulo un polinomio primitivo, y no se produce desbordamiento. Esta propiedad de "operación cerrada" garantiza matemáticamente la corrección de errores sobre bloques de datos de longitud fija.

En la implementación, calcular cada multiplicación de GF(256) mediante operaciones polinómicas resulta lento, por lo que lo habitual es precalcular una tabla de logaritmos / una tabla de antilogaritmos (de 256 entradas cada una) y convertir la multiplicación en "suma de logaritmos + consulta del antilogaritmo". En el interior de los codificadores / decodificadores de códigos QR van incorporadas estas tablas de 256 bytes.