💘 🛥️ 🌘 Implementação de software de multiplicação em campos de Galois 👩🏿‍🎓 🙆🏼 ⏫

Eu queria, de alguma forma, tornar a transmissão de informações mais confiável por meio do canal de rádio. Este não é um tipo de projeto industrial ou algo sério. É mais para hobbies e autodesenvolvimento. Afetados por traumas de infância - a falta de um carro controlado por rádio normalmente funcionando. Desde então, sempre quis ser capaz de controlar de forma fácil e natural qualquer coisa no rádio ...

E então, eu divago. Na infância e na adolescência, para a codificação de correção de erros, pode-se aplicar a verificação da paridade pelo método da matriz, mas agora isso não é mais sério. Depois de pesquisar na Internet, decidi parar de codificar usando o método Reed-Solomon. O algoritmo não é inteiramente novo, foi usado nos primeiros CDs, mas ao mesmo tempo, pelo que eu sei, não perdeu sua relevância no momento. Neste artigo sobre os próprios códigos Reed-Solomon, não vou expandir muito - isso foi feito para mim no Habré muitas vezes e por muitas pessoas. Aqui eu quero descrever a implementação do algoritmo de multiplicação em GF [256]. No entanto, para não forçar o leitor a pular nos links, descreverei brevemente por que você tem que lidar

com os campos de Galois.

Reed-Solomon Redundant Coding é sobre matrizes. Usamos matrizes para codificação e decodificação. Nestes processos, existem operações de multiplicação de matrizes e operações de localização de matrizes inversas - divisão. A divisão aqui requer não um número inteiro aproximado, mas o mais real, exato. E a divisão exata para um computador é uma tarefa insolúvel: dividir um por três é zero inteiro e um número infinito de triplos após o ponto decimal, mas 640 kilobytes de memória são suficientes para todos.

Galois viveu no início do século 19, viveu muito pouco (21 anos, em geral sobre sua personalidade a história é interessante, mas agora não é sobre isso). Seu trabalho foi muito útil na codificação digital. Um campo de Galois finito é um conjunto de números de zero a n. A essência e o interesse desses campos é que, para os elementos desse conjunto, você pode definir operações de adição-multiplicação-subtração-divisão de modo que o resultado da operação esteja neste próprio campo. Por exemplo, vamos pegar um conjunto (campo):

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

2 + 2 = 4 neste campo, bem como no campo de nossos números reais usuais. Mas 5 + 6 não é 11, como estamos acostumados, mas 5 + 6 = 3, e isso é ótimo! 3 está incluído neste campo (em geral, adição e subtração para este campo específico é apenas um XOR bit a bit). Para multiplicação e divisão, a regra também é cumprida: o resultado da multiplicação ou divisão de quaisquer dois números do campo (definir ... Além disso, falarei apenas "campo") estará neste campo.

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

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

Um pouco sobre aritmética. Adição e subtração, conforme mencionado anteriormente, é a mesma operação em campos de Galois (esse é exatamente o caso para campos de base 2) e é implementada como XOR bit a bit.

A + B = A xor B

A - B = A xor B

Simplesmente horrível. Mas quando se trata de multiplicação e divisão, lê-se algo que, para uma pessoa com relações tensas com a matemática (sim, isso é sobre mim) não é tão claro quanto um dia na lua.

Ao multiplicar, cada operando é representado como um polinômio. Acontece da seguinte forma: toma-se a representação binária do número e se escreve a soma, onde a potência de x é o número do dígito binário e seu coeficiente é o valor do dígito.

Exemplo:

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

Além disso, os polinômios são multiplicados de acordo com as regras de multiplicação de polinômios, ou seja, cada termo no primeiro colchete é multiplicado por cada termo no segundo, mas não apenas assim, mas levando em consideração o fato de que o coeficiente não pode ser mais do que um.

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

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

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

Ou seja, os coeficientes são adicionados módulo 2. Um exemplo de multiplicação em 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}) =

= (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

Em seguida, "adicionamos" (entre aspas - porque o módulo 2) termos semelhantes, e obtemos

x^{3} + x

, que convertemos para o número normal

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}$ e assim por diante. Isso significa que 2 elevado a qualquer potência pode ser representado como um dois elevado de zero a 6 usando a operação de obter o resto da divisão por 7 no caso de uma potência positiva e uma fórmula simples $2^{- x} = 2^{(7 - (x m o d 7))}$ se o expoente é um número negativo

Na verdade, se nos lembrarmos da propriedade de multiplicar graus, então multiplicar números é muito simplificado. E para multiplicar 6 por 3, olhamos agora em que grau dois é igual a 6 e em que grau dois é igual a 3, somamos as potências e vemos o resultado - dois até certo ponto, que pode ser representado como 2 à potência de 0 a 6 exemplo:

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

Com a divisão, tudo fica muito claro também:

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

E parece que é isso! a felicidade do programador é a implementação da aritmética no campo de Galois - algumas linhas de código, não há necessidade de se preocupar com polinômios ... Sim, e o desempenho de tal código será alto, mas então me deparei com mais um problema: A tabela de potências de dois no campo GF [8] com o polinômio gerador 11 foi encontrada facilmente. Até mesmo este recurso é. Mas eu não pesquisei a tabela de graus para GF [256], então decidi compilá-la sozinho, C # vai me ajudar. Tive que implementar o algoritmo de multiplicação de acordo com as regras dos polinômios.

Aqui está uma função de multiplicação de trabalho para GF [2 ^ n] com um polinômio arbitrário. Limitação - eu uso aritmética de 32 bits, então n deve ser menor que 16. Além disso, aqui é adicionada uma função para encontrar o número do bit mais significativo de um 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;
}

Agora, usando a função acima, você pode criar uma tabela de potências de dois para o GF que preciso [256] e escrever um módulo aritmético de Galois para stm32 usando duas tabelas de 256 cada - uma para o direto, a segunda para converter o número de volta em sua potência. Eu nem comecei a implementar a codificação Reed-Solomon ainda, mas quando estiver pronta, acho que vou compartilhá-la aqui. Esperançosamente, será mais curto.

Implementação de software de multiplicação em campos de Galois

More articles: