Suma y multiplicación en un Campo de Galois

Question

Estoy intentando generar códigos QR en una plataforma embebida extremadamente limitada. Todo en la especificación parece bastante directo, excepto por la generación de los códigos de corrección de errores. He revisado varias implementaciones existentes, y todas intentan implementar una serie de cálculos polinómicos que van por encima de mi comprensión, especialmente en lo que respecta a los campos de Galois. La forma más directa que puedo ver, tanto en complejidad matemática como en requisitos de memoria, es un concepto de circuito que se presenta en la propia especificación:

Con su descripción, tengo bastante confianza en que podría implementar esto con la excepción de las partes etiquetadas como adición de GF(256) y multiplicación de GF(256).

Ellos ofrecen esta ayuda:

La aritmética polinómica para QR Code se calculará utilizando aritmética de módulo 2 a nivel de bits y aritmética de módulo 100011101 a nivel de bytes. Este es un campo de Galois de 2^8 con 100011101 representando el polinomio primo del módulo del campo x^8+x^4+x^3+x^2+1.

lo cual es todo un enigma para mí.

Entonces mi pregunta es la siguiente: ¿Cuál es la forma más fácil de realizar la adición y multiplicación en este tipo de aritmética de campo de Galois? Supongamos que ambos números de entrada tienen 8 bits de ancho, y que mi salida también necesita ser de 8 bits de ancho. Varias implementaciones precálculan, o codifican en duro, dos tablas de búsqueda para ayudar con esto, pero no estoy seguro de cómo se calculan, o cómo las usaría en esta situación. Preferiría evitar el golpe de memoria de 512 bytes por las dos tablas, pero realmente depende de cuál sea la alternativa. Realmente solo necesito ayuda para entender cómo realizar una sola operación de multiplicación y adición en este circuito.

Answer 1

Para sus propósitos, los elementos de $GF(256)$ son polinomios en $x$ de grado $\le 7$ con coeficientes en $GF(2)$. $GF(2)$ es simplemente $\{0,1\}$ con suma y multiplicación binaria, pero no hay acarreos: 1+1=0 en $GF(2)$.

Entonces, por ejemplo, $x^4 + x^3 + 1$, $x^7 + x^2 + x$, $x^5 + x^3 + 1$, son todos elementos de $GF(256)$. Hay 256 elementos en total (de ahí el nombre $GF(256)$).

La suma de 2 polinomios en $GF(256)$ es directa. Por ejemplo: $(x^4 + x^3 + 1) + (x^3 + x^2 + 1) = x^4 + x^2$. Esto es simplemente una suma normal de polinomios, pero los coeficientes de los cálculos se realizan en $GF(2)$. Entonces, cuando sumé los términos $x^3$, el coeficiente se convirtió en 1+1=0 (por lo que el término $x^3$ desapareció por completo). Como secuencias de bits, sería: 11001 + 1101 = 10100. Esto es fácil de implementar en la mayoría de los lenguajes de programación: solo es un XOR de las secuencias de bits.

Para multiplicar 2 polinomios en $GF(256)$, primero multiplicas los polinomios como polinomios ordinarios pero nuevamente, recordando que los cálculos se realizan en $GF(2)$. Luego divides el resultado por $x^8+x^4+x^3+x^2+1$ y tomas el resto. A diferencia de la suma, esto es menos sencillo de implementar desde cero. (No puedes usar el operador de multiplicación habitual en tu lenguaje de programación para hacer la multiplicación, porque la multiplicación habitual tiene acarreos, pero $GF(2)$ no los tiene.)

Consulta el ejemplo aquí que es un polinomio ligeramente diferente (utilizan $x^8+x^4+x^3+x+1$ en lugar de $x^8+x^4+x^3+x^2+1$), pero es el mismo proceso. También hay una descripción de un algoritmo de multiplicación allí (tendrás que modificarlo ligeramente para tu polinomio).

Answer 2

Para añadir a la respuesta de Ted, dependiendo de las capacidades de su plataforma, el XOR de secuencias de bits que implementa la suma en GF$(256)$ podría ser implementable como el XOR de bytes; a menudo disponible como una instrucción de máquina, incluso en procesadores simples.

Por otro lado, implementar la multiplicación de dos elementos de GF$(256)$ como la multiplicación de dos polinomios y luego tomar el resto módulo $x^8+x^4+x^3+x^2+1$ es muy consumidor de tiempo. Le recomiendo que lea una excelente descripción tutorial por @Jyrki Lahtonen. Si tiene memoria disponible, la multiplicación en el campo de Galois se puede implementar a través de tablas de logaritmos. Vea aquí para una descripción de las tablas de logaritmos, y siga todos los enlaces allí para tener algunas ideas sobre cómo acelerar las cosas.

Editar: añadido nuevo material sobre multiplicación

Supongamos que queremos multiplicar polinomios binarios $c(x) = \sum_{i=0}^7 c_ix^i$ y $d(x) = \sum_{i=0}^7 d_ix^i$, y encontrar el resto después de dividir el resultado por $m(x) = x^8+x^4+x^3+x^2+1$, es decir, queremos calcular $c(x)d(x)\bmod m(x)$. A veces es conveniente incrustar la división por $m(x)$ en el proceso de multiplicación, y esta idea puede ser particularmente útil en la figura del codificador mostrada en la pregunta en la que se debe multiplicar un polinomio (el que se está retroalimentando en la línea superior de la figura) por $k$ polinomios diferentes (fijos) $g^{(i)}(x), 0 \leq i \leq k-1$. Tenemos $$\begin{align*} e(x) &= c(x)d(x) \bmod m(x)\\ &= \left(\sum_{i=0}^7 c_ix^i\right) d(x) \bmod m(x)\\ &= \left[c_0d(x) + c_1xd(x) + c_2x^2d(x) + \cdots + c_7x^7d(x)\right] \bmod m(x)\\ &= c_0d(x) + c_1[xd(x)\bmod m(x)] + c_2[x (xd(x)\bmod m(x))\bmod m(x) ]+\cdots\\ &\quad\quad\quad\quad\quad\quad\quad \cdots + c_7[x(x^6d(x)\bmod m(x)) \bmod m(x)]\\ &= \sum_{i=0}^7 c_if^{(i)}(x) \end{align*}$$ donde $f^{(0)}(x) = f(x)$ y $f^{(i)}(x) = xf^{(i-1)}(x) \bmod m(x) = x^id(x) \bmod m(x)$. Tenga en cuenta que los $c_i$ son $0$ o $1$. Así, $e(x)$ se inicializa con el polinomio cero y luego si $c_0 = 1$, se añade $d(x)$ a $e(x)$. Luego, si $d(x)$ no se necesita más (no está en la aplicación de código QR que se está considerando aquí), se reemplaza por $$xd(x) \bmod m(x) = \sum_{i=0}^7 d_ix^{i+1} \bmod m(x) = \sum_{i=0}^7 (d_{i-1}\oplus d_7m_i)x^{i}. $$ Si $d(x)$ es necesario en otro lugar, esta operación se realiza en la copia que se ha llamado $f(x)$. A continuación, si $c_1 = 1$, el nuevo $d(x)$ se añade a la suma que se está acumulando en $e(x)$ y el nuevo $d(x)$ se reemplaza por $xd(x) \bmod d(x)$, etc. En resumen, se ejecuta el siguiente proceso de dos pasos para $k = 0, \ldots , 7$.

• Si $c_k = 1$, $e(x):= e(x) + d(x)$
• $d(x) := \sum_{i=0}^7 (d_{i-1}\oplus d_7m_i)x^{i}$

para completar la multiplicación en GF$(256)$ en ocho iteraciones del proceso de dos pasos.

Existen dos ventajas en este enfoque para la aplicación de código QR. Primero, si se elige $d(x)$ como el polinomio que se retroalimenta y $c(x)$ como uno de los $g^{(j)}(x)$, entonces los coeficientes de $c(x)$ están fijos y son conocidos de antemano, por lo que el primer de los dos pasos anteriores puede simplificarse. Segundo, dado que el mismo $d(x)$ está siendo utilizado para multiplicar $k$ $g^{(j)}(x)$ diferentes, la actualización de $d(x)$ puede ser compartida entre las $k$ diferentes multiplicaciones si se organizan para proceder en paralelo en lugar de una a la vez. Además, como una mejora menor, dado que el producto $e(x)$ se suma a un $b(x)$, $e(x)$ puede ser inicializado con el valor de $b(x)$ en lugar del polinomio cero.

Answer 3

Tal vez llegue un poco tarde, pero en caso de que todavía estés buscando métodos para la multiplicación modular (es decir, la multiplicación de elementos de campo finito seguida por una reducción modular), te recomendaría que revises la página de Wikipedia sobre Aritmética de Campo Finito.

Deberías leer la versión modificada del 'algoritmo del campesino', que se describe justo debajo de la figura de la división larga.