Galois field arithmetic for coding information with Reed-Solomon codes
Reed-Solomon codes refer to non-binary, block, noise-resistant codes and can be used in the field of information storage to avoid the loss of corrupted information.
There is a post on the hub devoted to coding information with Reed-Solomon codes, but for an example the author uses a simple Galois field. This article describes the work with extended Galois fields, in particular GF (2 ^ m), which are rationally used for digital information. My similar implementation of encoding, decoding, error correction can be found here .
When working with Reed-Solomon codes, the percentage of redundant characters is 2 times the recoverable amount of data. Let me explain with an example: if we have a sequence of 10 characters and want to be able to recover errors in 3 of them (30% of the original information), then we need to store 10 + 3 * 2 = 16 characters. We name each variable: n = 10, the number of information symbols; f = 3, the number of recoverable characters; g = 16, the length of the encoded sequence. Thus, the formula can be written as follows: g = n + f * 2.
To work with information when encoding and decoding data, all arithmetic operations are performed in the Galois fields. The so-called polynomial arithmetic or arithmetic of Galois fields is applied. Thus, the result of any operation is also an element of this field. A particular Galois field consists of a fixed range of numbers. The field characteristic is called some prime number p. Field order, i.e. the number of its elements is a certain natural degree of characteristic pm, where m∈N. For m = 1, the field is called simple. In cases where m> 1, for the formation of a field, a generating polynomial of degree m is also required; such a field is called extended. GF (p ^ m) is the designation of the Galois field.
To work with digital data, it is natural to use p = 2 as a field characteristic. For m = 1, the element of the code sequence will be a bit, for m = 8 - 8 bits, that is, a byte. Actually, Reed-Solomon codes that work with bytes are the most common.
Before proceeding to the encoding and decoding operations, we will understand the arithmetic of Galois fields using the example of GF (2 ^ 3). This field consists of numbers from 0 to 7.
The simplest is the addition operation, which is a simple bitwise addition modulo 2 (XOR).
Example: 5 + 3 = 110 = 6
Unfortunately, the operation of multiplication is much more complicated, in order to carry out it, it is necessary to convert numbers to polynomial form.
Example: 5 = 101 = 1 ∙ x ^ 2 + 0 ∙ x ^ 1 + 1 ∙ x ^ 0 = x ^ 2 + 1
As you can see, the number in polynomial form is a polynomial whose coefficients are the values of the digits in the binary representation of the number.
Multiply two numbers in polynomial form:
5 ∙ 7 = (x ^ 2 + 1) ∙ (x ^ 2 + x + 1) = x ^ 4 + x ^ 3 + x ^ 2 + x ^ 2 + x + 1 = x ^ 4 + x ^ 3 + x + 1 = 11011 = 27
So, firstly, it should be noted that even in polynomial form addition is carried out modulo 2, therefore x ^ 2 + x ^ 2 = 0. Secondly, the result of multiplication 27 is not included in the used field GF (2 ^ 3) (it also consists of numbers from 0 to 7, as mentioned above). To combat this problem, it is necessary to use a generating polynomial. The generating polynomial is irreducible, that is, simple (by analogy with prime numbers it is divisible by 1 and by itself). In arithmetic of Galois fields, an irreducible polynomial is an analogue of primes. For example, we use the generating polynomial f (x) = x ^ 3 + x + 1.
It is also assumed that x satisfies the equation f (x) = x ^ 3 + x + 1 = 0
Let us return to the example with multiplication:
The same result can be obtained as the remainder of the division of the polynomial obtained by multiplying by the generating polynomial:
Let's make a multiplication table:
It is possible to understand the operation of division in polynomial form, but it is rather difficult. Therefore, it is much better to implement it according to the multiplication table.
Example: 6 ÷ 5 = 7
The table of degrees of the Galois field elements is of great importance. Power raising is also carried out in polynomial form, similar to multiplication.
Example: 5 ^ 2 = 〖(x ^ 2 + 1)〗 ^ 2 = x ^ 4 + x ^ 2 + x ^ 2 + 1 = x ^ 4 + x ^ 2 + x + x ^ 2 + x + 1 = x ∙ (x ^ 3 + x + 1) = x ^ 2 + x + 1 = 111 = 7
Thus, we compile a table of degrees:
The degree table is cyclical: the seventh degree corresponds to zero, so the eighth corresponds to the first, etc. You can check this if you wish.
In Galois fields, there is the concept of a primitive term - an element of a field whose degrees contain all nonzero elements of the field. Having looked at the table of degrees, it is clear that all the elements correspond to this condition (well, except for 1 naturally). However, this is not always the case; for example, I will give a table of degrees for GF (16).
For the fields we are considering, that is, with characteristic 2, always choose 2. As the primitive member, given its property, any element of the field can be expressed in terms of the degree of the primitive member.
Example: 5 = 26, 7 = 25
Using this property, and taking into account the cyclicality of the degree table, we will try to multiply the numbers again:
5 ∙ 7 = 2 ^ 6 ∙ 2 ^ 5 = 2 ^ (6 + 5) = 2 ^ 11 = 2 ^ (11 mod 7) = 2 ^ 4 = 6
The result coincided with what we calculated earlier.
And now we will divide:
6 ÷ 5 = 2 ^ 4 ÷ 2 ^ 6 = 2 ^ (4-6) = 2 ^ (- 2) = 2 ^ ((- 2) mod 7) = 2 ^ 5 = 7
The result also true.
Well, for the sake of completeness, let's look at raising to a power:
5 ^ 2 = (〖2 ^ 6)〗 ^ 2 = 2 ^ (6 ∙ 2) = 2 ^ 12 = 2 ^ (12 mod 7) = 2 ^ 5 = 7
Again, unexpectedly got the same result.
Such an approach to multiplication and division is much simpler than real operations using polynomials, and for them there is no need to store a large multiplication table, but just a row of degrees of a primitive field term.