🐫 👨🏿‍✈️ 🐍 Implementación de software de multiplicación en campos de Galois 🔃 🤰🏻 ⬜️

Quería de alguna manera hacer más confiable la transmisión de información a través del canal de radio. Este no es un tipo de proyecto industrial, o algo más serio. Es más por pasatiempos y desarrollo personal. Afectado por un trauma infantil: la falta de un automóvil controlado por radio que funcione normalmente. Desde entonces, siempre he querido poder controlar fácil y naturalmente cualquier cosa en la radio ...

Y entonces, estoy divagando. En la niñez y la adolescencia, para la codificación de corrección de errores, se podría aplicar la verificación de paridad por el método de la matriz, pero ahora esto no es serio. Después de haber buscado en Internet, decidí detenerme en la codificación utilizando el método Reed-Solomon. El algoritmo no es del todo nuevo, se utilizó en los primeros CD, pero al mismo tiempo, hasta donde yo sé, no ha perdido su relevancia en este momento. En este artículo sobre los códigos Reed-Solomon en sí mismos, no voy a expandir mucho - esto fue hecho por mí en Habré muchas veces y por mucha gente. Aquí quiero describir la implementación del algoritmo de multiplicación en GF [256]. Sin embargo, para no obligar al lector a saltar sobre los enlaces, describiré brevemente por qué tiene que lidiar

con los campos de Galois.

La codificación redundante Reed-Solomon se trata de matrices. Usamos matrices para codificar y decodificar. En estos procesos, hay operaciones de multiplicación de matrices y operaciones de encontrar matrices inversas: división. La división aquí no requiere un número entero aproximado, sino el más real, exacto. Y la división exacta para una computadora es una tarea insoluble: dividir uno entre tres es cero enteros y un número infinito de triples después del punto decimal, pero 640 kilobytes serán suficientes para todos.

Galois vivió a principios del siglo XIX, vivió muy poco (21 años, en general sobre su personalidad la historia es interesante, pero ahora no se trata de eso). Su trabajo fue muy útil en la codificación digital. Un campo de Galois finito es un conjunto de números de cero a n. La esencia y el interés de estos campos es que para los elementos de este conjunto, puede definir operaciones de suma-multiplicación-resta-división de modo que el resultado de la operación esté en este campo mismo. Por ejemplo, tomemos un conjunto (campo):

[0, 1, 2, 3, 4, 5, 6, 7]

$[0,1,2,3,4,5,6,7]$

2 + 2 = 4 en este campo, así como en el campo de nuestros números reales habituales. Pero 5 + 6 no es 11, como estamos acostumbrados, sino 5 + 6 = 3, ¡y esto es genial! 3 está incluido en este campo (en general, la suma y resta para este campo en particular es solo un XOR bit a bit). Para la multiplicación y la división, también se cumple la regla: el resultado de multiplicar o dividir dos números cualesquiera del campo (conjunto ... Además, hablaré sólo "campo") estará en este campo.

, . « » , ( « », « »). , , 256, ( ) 8, . GF[256], GF Galois Field.

. , , , , , « » ( stm32 ) - .

Un poco de aritmética. La suma y la resta, como se mencionó anteriormente, es la misma operación en los campos de Galois (este es exactamente el caso de los campos de base 2), y se implementa como XOR bit a bit.

A + B = A xor B

$A+B = A \operatorname{xor} B$

A - B = A xor B

$A-B = A \operatorname{xor} B$

Simplemente horrible. Pero cuando se trata de multiplicación y división, uno lee algo que para una persona con relaciones tensas con las matemáticas (sí, esto se trata de mí) no es tan claro como un día en la luna.

Al multiplicar, cada operando se representa como un polinomio. Sucede como sigue: se toma una representación binaria de un número y se escribe la suma, donde la potencia de x es el número del dígito binario y su coeficiente es el valor del dígito.

Ejemplo:

5 = 101_{2} = 1 \cdot x^{2} + 0 \cdot x^{1} + 1 \cdot x^{0} = x^{2} + 1

$5=101_2=1\cdot x^2+0\cdot x^1+1\cdot x^0=x^2+1$

Además, los polinomios se multiplican de acuerdo con las reglas de multiplicación de polinomios, es decir, cada término del primer corchete se multiplica por cada término del segundo, pero no solo así, sino teniendo en cuenta el hecho de que el coeficiente no puede ser más de uno.

x^{2} + x^{2} = 0

$x^2+x^2=0$

x^{2} + x^{2} + x^{2} = x^{2}

$x^2+x^2+x^2=x^2$

x^{2} + x^{2} + x^{2} + x^{2} = 0

$x^2+x^2+x^2+x^2=0$

Es decir, los coeficientes se suman módulo 2. Un ejemplo de multiplicación en GF [8]:

6 \cdot 3 = 110_{2} \cdot 11_{2} = (1 \cdot x^{2} + 1 \cdot x^{1} + 0 \cdot x^{0}) \cdot (1 \cdot x^{1} + 1 \cdot x^{0}) =

$6\cdot 3 = 110_2\cdot 11_2= (1\cdot x^2+1\cdot x^1+0\cdot x^0)\cdot (1\cdot x^1+1\cdot x^0)=$

= (x^{2} + x) (x + 1) = x^{2} \cdot x + x^{2} \cdot 1 + x \cdot x + x \cdot 1 =

$=(x^2+x)(x+1)=x^2\cdot x+x^2\cdot 1+x\cdot x+x\cdot 1=$

= x^{3} + x^{2} + x^{2} + x

$=x^3+x^2+x^2+x$

Luego "agregamos" (entre comillas, porque módulo 2) términos similares, y obtenemos

x^{3} + x

$x^3+x$ , que convertimos al número habitual

1010_{2} = 10

$1010_2=10$ ...

GF[8], 10 : « ? 10 [0,1,2,3,4,5,6,7]». . . ( ), . , , «» . ? ? ( , , , ). , . GF[8] : 11 13, 1011 1101 $x^3+x+1$ $x^3+x^2+1$

, 6 3 GF[8] . $x^3+x$ . $x^3+x+1$ . , , - «», . . , $x^3$ ( $x^3$ ). 1. ( $x^3+x+1$ ). , ( GF[8] ) $(x^3+x) +(x^3+x+1)$ . 2, , 1. , ( ) ( ). , , ( – ), 1.

. $6 \cdot 3 = 1$ GF[8] c 11.

. - 256256 ( 88, ), . , . — , . , , ( 0). , GF[8] 2,

$2^0=1$        $2^7=1$

$2^1=2$        $2^8=2$

$2^2=4$        $2^9=4$

$2^3=3$        $2^{10}=3$

$2^4=6$        $2^{11}=6$

$2^5=7$        $2^{12}=7$

$2^6=5$        $2^{13}=5$

, , 1 7 2 . , $2^7=2^0$ $2^8=2^1$ , $2^9=2^2$ y así. Esto significa que 2 elevado a cualquier potencia se puede representar como un dos elevado a la potencia de cero a 6 utilizando la operación de obtener el resto de la división por 7 en el caso de una potencia positiva y una fórmula simple $2^{-x}=2^{(7-(x\: mod\:7))}$ si el exponente es un número negativo

En realidad, si recordamos la propiedad de multiplicar grados, entonces la multiplicación de números se simplifica enormemente. Y para multiplicar 6 por 3, ahora miramos en qué grado dos es igual a 6 y en qué grado dos es igual a 3, sumamos las potencias y vemos el resultado - dos hasta cierto punto, que se puede representar como 2 elevado a la potencia de 0 a 6 ejemplo:

6 \cdot 3 = 2^{4} \cdot 2^{3} = 2^{(4 + 3)} = 2^{7} = 2^{0} = 1

$6\cdot 3=2^4\cdot 2^3=2^{(4+3)} = 2^7 = 2^0 = 1$

Con la división, todo se vuelve muy claro también:

3 / 6 = 2^{3} / 2^{4} = 2^{(3 - 4)} = 2^{- 1} = 2^{(7 - (1 m o d 7))} = 2^{6} = 5

$3/6=2^3/2^4=2^{(3-4)} = 2^{-1} = 2^{(7-(1\: mod\:7))} = 2^6 = 5$

¡Y parece que esto es todo! La felicidad del programador es la implementación de la aritmética en el campo de Galois: un par de líneas de código, no hay necesidad de preocuparse por los polinomios ... Sí, y el rendimiento de dicho código será alto, pero luego me encontré con un problema más: la tabla de potencias de dos en el campo GF [8] con el polinomio generador 11 se encuentra fácilmente. Incluso este recurso lo es. Pero no busqué en Google la tabla de grados para GF [256], así que decidí compilarla yo mismo, C # me ayudará. Tuve que implementar el algoritmo de multiplicación de acuerdo con las reglas de los polinomios.

Aquí hay una función de multiplicación de trabajo para GF [2 ^ n] con un polinomio arbitrario. Restricción: uso aritmética de 32 bits, por lo que n debe ser menor que 16. También aquí se agrega una función para encontrar el número del bit más significativo de un número.

private uint GetLeadBitNum(UInt32 Val) {
    int BitNum = 31;
    uint CmpVal = 1u << BitNum;
    while (Val < CmpVal) {
        CmpVal >>= 1;
        BitNum--;
    }
    return (uint)BitNum;
}
private uint Galois_b2_ext_mult(uint m1, uint m2, uint Poly) {
    if (0 == m1 || 0 == m2) { return 0; }
    uint m1_tmp = m1;
    uint m2_tmp;
    uint m1_bit_num = 0;
    
    //  ,      2   .
    //    (         ( )),    ,
    //  ,       - ,      ,       
    //( -      2)
    uint PolyMultRez = 0;

    while (m1_tmp != 0) {
        uint bit_m1 = (m1_tmp & 1u) == 0u ? 0u : 1u;
        m1_tmp = m1_tmp >> 1;
        m2_tmp = m2;
        uint m2_bit_num;
        m2_bit_num = 0;
        while (m2_tmp != 0) {
            uint bit_m2 = (m2_tmp & 1u) == 0u ? 0u : 1u;
            m2_tmp = m2_tmp >> 1;
            if ((bit_m1 != 0) && (bit_m2 != 0)) {
                int BitNum = (int)(m2_bit_num + m1_bit_num);
                PolyMultRez ^= 1u << BitNum;
            }
            m2_bit_num = m2_bit_num + 1;
        }
        m1_bit_num = m1_bit_num + 1;
    }

    //     PolyMultRez.         .
    //   :    ,     . 
    //  -  
    // ,   ,         
    //    ,        
    uint TmpDivisor_lead_bit_n;
    uint TmpQuotient;
    uint TmpDivisor = Poly;
    uint TmpDividend = PolyMultRez;
    uint TmpDividend_LeadBitNum;
    uint TmpMult_bitNum;
    uint TmpMult_rez;

    TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    TmpDivisor_lead_bit_n = GetLeadBitNum(TmpDivisor);

    while (TmpDividend_LeadBitNum >= TmpDivisor_lead_bit_n) {

        TmpQuotient = (TmpDividend_LeadBitNum - TmpDivisor_lead_bit_n);

        TmpMult_bitNum = 0;
        TmpMult_rez = 0;
        while (TmpDivisor != 0) {
            uint bit_TmpMult = (TmpDivisor & 1u) == 0u ? 0u : 1u;
            TmpDivisor >>= 1;
            TmpMult_rez ^= bit_TmpMult << (int)(TmpQuotient + TmpMult_bitNum);
            TmpMult_bitNum = TmpMult_bitNum + 1;
        }
        TmpDividend = TmpDividend ^ TmpMult_rez;
        TmpDivisor = Poly;
        TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    }            
    //           .
    return TmpDividend;
}

Ahora, usando la función anterior, puede crear una tabla de potencias de dos para el GF que necesito [256] y escribir un módulo aritmético de Galois para stm32 usando dos tablas de 256 cada una, una para el directo y la segunda para convertir el número a su potencia. Ni siquiera he comenzado a implementar la codificación Reed-Solomon todavía, pero cuando esté lista, creo que la compartiré aquí. Ojalá sea más corto.

Implementación de software de multiplicación en campos de Galois

More articles: