🍠 🅿️ 🍣 Software implementation of multiplication in Galois fields ⚡️ 🛀🏼 💃🏻

I wanted to somehow make more reliable transmission of information through the radio channel. This is not some kind of industrial project, or something else serious. It is more for hobbies and self-development. Affected by childhood trauma - the lack of a normally working radio-controlled car. Since then, I have always wanted to be able to easily and naturally control anything on the radio ...

And so, I digress. In childhood and adolescence, for error-correcting coding, one could apply the parity check by the matrix method, but now this is not serious. Having looked through the Internet, I decided to stop at coding using the Reed-Solomon method. The algorithm is not entirely new, it was used in the first CDs, but at the same time, as far as I know, it has not lost its relevance at the moment. In this article about the Reed-Solomon codes themselves, I will not expand much - this was done for me on Habré many times and by many people. Here I want to describe the implementation of the multiplication algorithm in GF [256]. Nevertheless, in order not to force the reader to jump on links, I will briefly describe why you have to deal

with Galois fields at all .

Reed-Solomon Redundant Coding is about matrices. We use matrices for encoding and decoding. In these processes, there are both operations of matrix multiplication and operations of finding inverse matrices - division. Division here requires not an approximate integer, but the most real, exact. And the exact division for a computer is an unsolvable task: divide one by three is zero integers and an infinite number of triples after the decimal point, but 640 kilobytes of memory is enough for everyone.

Galois lived at the beginning of the 19th century, he lived very little (21 years, in general about his personality the story is interesting, but now it's not about that). His work was very useful in digital coding. A finite Galois field is a set of numbers from zero to n. The essence and interest of these fields is that for the elements of this set, you can define addition-multiplication-subtraction-division operations such that the result of the operation will be in this field itself. For example, let's take a set (field):

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

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

2 + 2 = 4 in this field, as well as in the field of our usual real numbers. But 5 + 6 is not 11, as we are used to, but 5 + 6 = 3, and this is great! 3 is included in this field (in general, addition and subtraction for this particular field is just a bitwise XOR). For multiplication and division, the rule is also fulfilled: the result from multiplying or dividing any two numbers from the field (set ... Further I will speak only "field") will be in this field.

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

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

A little about arithmetic. Addition and subtraction, as mentioned earlier, is the same operation in Galois fields (this is exactly the case for base 2 fields), and it is implemented as bitwise XOR.

A + B = A xor B

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

A - B = A xor B

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

Just horrible. But when it comes to multiplication and division, one reads something that for a person with strained relations with mathematics (yes, this is about me) is not as clear as a day on the moon.

When multiplying, each operand is represented as a polynomial. It happens as follows: the binary representation of the number is taken, and the sum is written, where the power of x is the number of the binary digit, and its coefficient is the value of the digit.

Example:

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$

Further, the polynomials are multiplied according to the rules of multiplication of polynomials, that is, each term in the first bracket is multiplied by each term in the second, but not just like that, but taking into account the fact that the coefficient cannot be more than one.

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$

That is, the coefficients are added modulo 2. An example of multiplication in 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$

Then we "add" (in quotes - because modulo 2) similar terms, and we get

x^{3} + x

$x^3+x$ , which we convert to the usual number

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$ and so on. This means that 2 to any power can be represented as a two to the power from zero to 6 using the operation of obtaining the remainder of division by 7 in the case of a positive power and a simple formula $2^{-x}=2^{(7-(x\: mod\:7))}$ if the exponent is a negative number

Actually, if we recall the property of multiplying degrees, then multiplying numbers is greatly simplified. And in order to multiply 6 by 3, we now look to what degree two is equal to 6 and to what degree two is equal to 3, add the powers and see the result - two to some extent, which can be represented as 2 to the power from 0 to 6 example:

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$

With division, everything becomes very clear too:

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$

And it looks like this is it! the programmer's happiness is the implementation of arithmetic in the Galois field - a couple of lines of code, no need to bother with polynomials ... Yes, and the performance of such a code will be high, but then I ran into one more problem: The table of powers of two in the GF field [8] with the generating polynomial 11 is found easily. Even this resource is. But I didn't googling the table of degrees for GF [256], so I decided to compile it myself, C # will help me. I had to implement the multiplication algorithm according to the rules of polynomials.

Here is a working multiplication function for GF [2 ^ n] with an arbitrary polynomial. Limitation - I use 32-bit arithmetic, so n must be less than 16. Also, here is added a function to find the number of the most significant bit of a number

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

Now, using the above function, you can create a table of powers of two for the GF I need [256] and write a Galois arithmetic module for stm32 using two tables of 256 each - one for the direct, the second for converting the number back to its power. I haven't even started to implement the Reed-Solomon coding yet, but when it's ready, I think I'll share it here. Hopefully it will be shorter.

Software implementation of multiplication in Galois fields

More articles: