math - facil - galois field
Adición y multiplicación en un campo de Galois (2)
(Estoy siguiendo el puntero a zxing en la primera respuesta, ya que soy el autor).
La respuesta sobre la suma es exactamente correcta; es por eso que trabajar en este campo es conveniente en una computadora.
Sí, la multiplicación funciona, y es para GF256. a * b es realmente lo mismo que exp (log (a) + log (b)). Y debido a que GF256 tiene solo 256 elementos, solo hay 255 poderes únicos de "x", y lo mismo para el registro. Entonces, estos son fáciles de poner en una tabla de búsqueda. Las tablas se "ajustarán" a 256, por eso es que ve el "% de tamaño". "/ size" es un poco más difícil de explicar en una oración, es porque realmente 1-255 "se ajusta", no 0-255. Entonces no es solo un módulo simple lo que se necesita.
La última pieza quizás sea cómo se reduce el módulo a un polinomio irreductible. El polinomio irreductible es x ^ 8 más algunos términos de menor potencia, a la derecha, llámalo I (x) = x ^ 8 + R (x). Y el polinomio es congruente a 0 en el campo, por definición; I (x) == 0. Entonces x ^ 8 == -R (x). Y, convenientemente, la suma y la resta son las mismas, entonces x ^ 8 == -R (x) == R (x).
El único momento en que necesitamos reducir los polinomios de mayor potencia es cuando construimos la tabla de exponentes. Simplemente siga multiplicando por x (que es un desplazamiento a la izquierda) hasta que se vuelva demasiado grande; obtiene un término x ^ 8. Pero x ^ 8 es lo mismo que R (x). Entonces saca el x ^ 8 y agrega R (x). R (x) simplemente tiene potencias hasta x ^ 7, por lo que está todo en un byte fijo, todo en GF (256). Y sabes cómo agregar en este campo.
¿Ayudas?
Estoy intentando generar códigos QR en una plataforma incrustada extremadamente limitada. Todo en la especificación parece bastante sencillo, excepto para generar las palabras de código de corrección de errores. He analizado varias implementaciones existentes, y todas intentan implementar un montón de cálculos polinomiales que van directamente sobre mi cabeza, particularmente con respecto 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, estoy bastante seguro de que podría implementar esto con la excepción de las partes etiquetadas GF (256) y GF (256) Multiplication.
Ellos ofrecen esta ayuda:
La aritmética polinomial para el código QR se calculará utilizando aritmética de módulo 2 bit-wise y módulo byte-wise 100011101. Este es un campo de Galois de 2 ^ 8 con 100011101 que representa el polinomio de módulo primo del campo x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.
lo cual es bastante griego para mí.
Entonces mi pregunta es esta: ¿Cuál es la forma más fácil de realizar la suma y la 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 debe tener 8 bits de ancho. Varias implementaciones precalculan, o hardcode en dos tablas de búsqueda para ayudar con esto, pero no estoy seguro de cómo se calculan, o cómo los usaría en esta situación. Preferiría no tomar el golpe de memoria de 512 bytes para las dos tablas, pero realmente depende de cuál sea la alternativa. Realmente solo necesito ayuda para entender cómo hacer una sola operación de multiplicación y suma en este circuito.
En la práctica, solo se necesita una tabla. Eso sería para el GP (256) multiplicar. Tenga en cuenta que toda la aritmética es carry-less, lo que significa que no hay propagación de arrastre.
Sumar y restar sin acarreo es equivalente a un xor.
Entonces en GF (256), a + b y a - b son ambos equivalentes a a xor b .
La multiplicación GF (256) también es sin carga, y se puede hacer usando la multiplicación sin carga de una manera similar con la suma / resta sin acarreo. Esto se puede hacer de manera eficiente con soporte de hardware a través de, por ejemplo, el conjunto de instrucciones CLMUL de Intel .
Sin embargo, la parte difícil es reducir el módulo 100011101 . En la división de enteros normal, lo haces usando una serie de pasos para comparar / restar. En GF (256), lo haces de manera casi idéntica usando una serie de pasos compare / xor.
De hecho, es suficientemente malo donde aún es más rápido simplemente precomputar todas las multiplicaciones de 256 x 256 y ponerlas en una tabla de búsqueda de entrada 65536.
La página 3 del siguiente pdf tiene una muy buena referencia sobre la aritmética GF256:
http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf
He realizado una implementación de corrección de errores de Reed-Solomon usando GF (256), pero fue con el polinomio 10010010 lugar de 100011101 .