🦕 🤚🏽 🤹🏻 Galois字段中乘法的软件实现 👩🏻‍🏫 🤦 👸🏻

我想以某种方式使通过无线电信道的信息传输更加可靠。这不是某种工业项目，也不是其他严肃的事情。它更多是出于爱好和自我发展。受童年创伤的影响-缺少正常工作的无线电遥控车。从那时起，我一直希望能够轻松自然地控制广播中的任何内容...

所以，我离题了。在童年和青春期，对于纠错编码，可以通过矩阵方法应用奇偶校验，但是现在这并不严重。通过互联网浏览后，我决定停止使用Reed-Solomon方法进行编码。该算法并不完全是新算法，它已在第一张CD中使用，但是据我所知，与此同时，它目前并没有失去其相关性。在有关Reed-Solomon代码本身的这篇文章中，我不会做太多扩展-在Habré上为我做过很多次，并有很多人为我完成。在这里，我想描述GF [256]中乘法算法的实现。尽管如此，为了不强迫读者跳入链接，我将简要描述为什么您必须处理

Galois领域。

Reed-Solomon冗余编码与矩阵有关。我们使用矩阵进行编码和解码。在这些过程中，既有矩阵乘法运算，又有求逆矩阵除法运算。除法此处不需要近似整数，但需要最真实，最精确的整数。计算机的精确除法是一项无法解决的任务：一分为三是零个整数，小数点后可以有无数个三元组，但是对于每个人来说640 KB就足够了。

加洛瓦（Galois）活在19世纪初，但几乎没有活（21岁，关于他的个性，这个故事很有趣，但现在不那么重要了）。他的工作在数字编码中非常有用。有限的Galois字段是一组从零到n的数字。这些字段的本质和兴趣在于，对于此集合的元素，您可以定义加减乘除运算，以便运算结果将在此字段本身中。例如，让我们来看一个集合（字段）：

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

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

在这个字段以及我们通常的实数字段中为2 + 2 = 4。但是5 + 6不是11，就像我们习惯的那样，而是5 + 6 = 3，这太棒了！ 3包含在该字段中（通常，此特定字段的加减法只是按位XOR）。对于乘法和除法，也要满足该规则：将字段中的任何两个数字相乘或除的结果（定值...此外，我将仅说“字段”）将在此字段中。

通常，字段元素的数量不是任意的。它被称为“场特征”，可以是素数或素数的幂（它被称为“场阶”，该度数的基数称为“场基”）。幸运的是，一个字节可以加密的数字数量为256，这是8的幂的两个（素数），我们可以将一个字节的所有可能值的集合作为有限的Galois字段。GF巧妙地称为GF [256]，代表Galois Field。

就是这样了。如果您在Galois字段中对字节使用算术，那么在将由字节组成的矩阵相除时，您将永远不会获得无法写入一个字节的数字，这意味着如何实现“在硬件中”（我主要使用stm32）编码编码算法变得更加清晰。

关于算术的一些知识。如前所述，加法和减法在Galois字段中是相同的操作（对于基数为2的字段正是这种情况），并且实现为按位XOR。

A + B = A xor B

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

A - B = A xor B

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

太可怕了。但是当涉及到乘法和除法时，人们读到的东西对于一个与数学关系紧张的人（是的，这是关于我的）并不像在月亮上度过一天那样清晰。

在相乘时，每个操作数都表示为多项式。它发生如下情况：取数字的二进制表示形式，并写和，其中x的幂是二进制数字的位数，其系数是数字的值。

例：

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$

此外，多项式是根据多项式相乘的规则相乘的，也就是说，第一个括号中的每个项与第二个括号中的每个项相乘，但不仅如此，还要考虑到系数不能大于一个的事实。

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$

也就是说，系数的模数为2。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$

然后我们“添加”（用引号引起的-因为模2）类似的术语，我们得到

x^{3} + x

$x^3+x$ ，我们将其转换为普通数

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$ . , 2 6 7 $2^{-x}=2^{(7-(x\: mod\:7))}$ , —

, , . 6 3 , 6 3, — - , 2 0 6 :

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$

通过除法，一切也变得非常清晰：

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$

看起来就是这样！程序员的幸福是在Galois领域中实现了算术-几行代码，不需要去烦恼多项式...是的，这样的代码的性能会很高，但是我又遇到了另一个问题：GF字段[8]中有2的幂的表能生成多项式11容易。即使是这种资源。但是我没有使用GF [256]的度数表，所以我决定自己编译，C＃会帮助我。我必须根据多项式的规则来实现乘法算法。

这是带有任意多项式的GF [2 ^ n]的工作乘法函数。限制-我使用32位算术，因此n必须小于16。这里还添加了一个函数，用于查找数字的最高有效位的数字

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;
}

现在，使用上述功能，您可以为需要的GF创建2的幂表，并使用两个256的表为stm32编写一个Galois算术模块-一个用于直接，第二个用于将数字转换回其幂。我什至还没有开始实现Reed-Solomon编码，但是准备就绪后，我想在这里分享。希望它会更短。

Galois字段中乘法的软件实现

More articles: