Reed-Solomon codes. Part 2 - Galois Field Arithmetic

Hello, friends! Last time, you and I started talking about how Reed-Solomon codes help ensure the required level of data storage reliability. Today we’ll dwell on the arithmetic of the Galois fields, which is used in the calculations.









First, a brief excursion into the last part . We found out that in order to be able to recover lost data, you must first generate “redundant data” in a certain way. Moreover, from a mathematical point of view, this task (coding) is reduced to constructing a certain generating matrix and performing the operation of multiplying this matrix by the vector of the original data. The recovery (decoding) procedure, in turn, consists in inverting the generating matrix and multiplying it by the vector of the preserved data. Schematically it can be represented as follows.



Coding procedure:

')





Decoding procedure:

Limitations of rational number arithmetic

We have already noted some of the difficulties encountered in the implementation of encoding / decoding procedures on specific hardware platforms. For example, numbers in computer memory are usually represented by a fixed number of bytes. As a result, by multiplying the elements of the generating matrix, one can get an overflow of discharges. Or, when the generating matrix is ​​addressed as its elements, rational numbers may arise that are problematic to store with arbitrary precision. Therefore, today we will talk about how you can implement these procedures, avoiding the above problems. The Galois field theory, which we have already talked about a bit in the last article, will help us in this.



Immediately make a few comments. Firstly, the article is primarily designed for an engineering audience, so I tried to avoid strict mathematical definitions. For those who want a more formal introduction to this area, it makes sense to immediately refer to the relevant literature. For my part, I can recommend Ernest Borisovich Vinberg’s book The Course of Algebra. Second, directly for the implementation of redundant coding algorithms, only a basic understanding of the theory of finite fields is sufficient. You can simply assume that some consistent tables of multiplication, division, addition, subtraction, and all calculations are made using these tables. This is a hint for those who do not really want to dive deep into this section of algebra.

Fields and arithmetic operations in finite sets

Before proceeding directly to the discussion of the Galois fields, let us repeat once more what we want to achieve. We want to be able to multiply matrices by vectors, to invert matrices. And most importantly, we want to deal only with integers and not worry about overflow when performing multiplication and addition operations.



Also, to avoid confusion, it makes sense to immediately understand the terminology. First of all, what is a field in terms of general algebra? As Wikipedia tells us, “a field is a set for which elements the operations of addition, subtraction, multiplication and division (except division by zero) are defined, and the properties of these operations are close to the properties of ordinary numerical operations.” What is a Galois field? A Galois field is an arbitrary field consisting of a finite number of elements. $$$GF (p)$, $$$GF (p ^ n)$- standard designation of Galois fields, where the number of field elements is indicated in brackets.



In modern computers, a fixed number of bits is usually used to store numbers. It is not difficult to calculate that everything exists. $$$2 ^ n$different n-bit numbers, from 0 to $$$(2 ^ n - 1)$. In other words, we have some finite set of numbers. On this set, we will now try to determine the operations of multiplication, division, addition, and subtraction in a consistent way. And so that the result of any operation was also $$$n$bit number! In this case, it is said that the set is closed with respect to the entered operations .



The subtraction operation in systems of finite sets is usually introduced through the concept of zero and opposite elements. Zero element $$$0$- this is an element for which the equality holds: $$$a + 0 = a$where $$$a$Is an arbitrary element of the set. Element $$$b$is the opposite for $$$a$if equality is true $$$a + b = 0$. Usually the opposite element is denoted as $$$-a$. If we want from $$$x$subtract $$$y$we find the opposite element $$$-y$and fold it with $$$x$. Accordingly, in order to be able to subtract arbitrary elements of a finite set, each element of this set must have the opposite.



Similarly, the situation with the division operation. The concept of single and inverse elements is introduced. Single element $$$1$Is the element for which the equality is true $$$a * 1 = a$where $$$a$Is an arbitrary element of the set. Element $$$b$(denoted by $$$1 / a$) is called the inverse of $$$a$, if a $$$a * b = 1$. As with the subtraction, if we want $$$x$divide by nonzero $$$y$we have to find the inverse element $$$1 / y$and multiply it by $$$x$. In order to be able to divide arbitrary elements, each element of the set (with the exception of zero) must have the opposite.

Construction of Galois fields GF (p)

How can we determine the specified arithmetic operations on a finite set of numbers, and so that the set is closed with respect to them? In other words, we want an arbitrary finite set of elements to be turned into a Galois field. The first thing that comes to mind is to use modular arithmetic. Then if our set contains $$$p$elements, the result of the product of numbers $$$a * b$will be the number $$$(a * b) mod p$. The sum of the numbers is defined as $$$(a + b) mod p$.



As an exercise, let's create addition and multiplication tables for a set consisting of $$$p = 5$items $$$\ {0, 1, 2, 3, 4 \}$ .





The lower two tables show the opposite and inverse values ​​for each element of our set. Armed with these tables, we can perform all the arithmetic operations we need. Hooray!

Building Galois Fields $$$GF (p ^ n)$

It seems that we are on the right path to success. The only thing that may not suit us so far is the size of our field - 5. It is clear that to simplify the software implementation, it makes sense to work with sets containing $$$2 ^ n$numbers Then we can operate with nibbles, bytes, words, etc.



At first glance it seems what a difference - 5 or 256 elements in the set, take the result of the multiplication or addition operation in the corresponding module and is ready. Let's try again to create a multiplication table for the set, but this time containing $$$4 = 2 ^ 2$element - $$$\ {0, 1, 2, 3 \}$ . Here's what happened:





If you look closely at the resulting table, you can find one serious flaw in it. Pay attention to the line for element 2. There is no single element in this line! This means that we will not be able to divide the other elements by 2, since for him there is no opposite! It means that it is necessary to build the tables of addition and multiplication in some other way. Modular arithmetic, unfortunately, no longer works.



So, we found out that if the set contains $$$4 = 2 ^ 2$an object, then modular arithmetic does not allow to set consistent operations of multiplication. In fact, similar problems will arise for any set, the number of elements $$$p$which is not a prime number. But what else can you think of?

Addition to GF (p ^ n)

Let us, for the sake of simplicity, assume that the set on which we want to define arithmetic operations contains $$$2 ^ n$items. These are, strictly speaking, numbers $$$\ {0, 1, 2, 3, ..., 2 ^ n - 1 \}$ . Any number $$$a$of this set can be represented as an expansion:

$$

$$a = a_0 + a_12 ^ 1 + a_22 ^ 2 + ... + a_ {n-1} 2 ^ {n-1}, a_i \ in \ {0,1 \}$$

In essence, this is the usual binary representation of a number. Thus, we can also consider any number from our set as a vector of length $$$n$whose elements are zeros and ones:

$$

$$a = [a_0, a_1, a_2, ..., a_ {n-1}], a_i \ in \ {0,1 \}$$

We introduce the operation of adding two arbitrary numbers through the addition of the corresponding vectors of the binary decomposition. Moreover, the addition of the components of the vectors will be modulo 2 (in general, if the number of elements $$$p ^ n$modulo $$$p$). Thus, the resulting vector will also be a binary representation of some number and, as a result, will belong to our set (the set will be closed with respect to the addition operation).

$$

$$a = [a_0, a_1, a_2, ..., a_ {n-1}], a_i \ in \ {0,1 \} \\ b = [b_0, b_1, b_2, ..., b_ {n -1}], b_i \ in \ {0,1 \} \\ c = a + b = [(a_0 + b_0) mod2, ..., (a_ {n-1} + b_ {n-1}) mod2]$$

It is easy to see that the addition operation we introduced is equivalent to the XOR bit operation. Which is very good, since modern processors can perform this operation extremely quickly. But that is not all. It's obvious that $$$a \ oplus a = 0$for an arbitrary number $$$a$. This means that the opposite element to $$$a$is himself $$$a$. So in the field $$$GF (2 ^ n)$addition is the same as subtraction!

Multiplication in GF (p ^ n)

It remains to introduce the operation of multiplication on our set. This is done as follows. Let's temporarily assume that any number $$$a$of our set, it is a polynomial of the following form:

$$

$$a (x) = a_0 + a_1x + a_2x ^ 2 + ... + a_ {n-1} x ^ {n-1}, a_i \ in {0,1}$$

Here the coefficients of the polynomial are taken from the binary decomposition of the number $$$a$. With this approach, for example, the number $$$100 = 01100100b$the polynomial will be matched $$$x ^ 6 + x ^ 5 + x ^ 2$.



The multiplication operation of two numbers can be determined by multiplying polynomials corresponding to given numbers:

$$

$$a × b = (a_0 + a_1x + ... + a_ {n-1} x ^ {n-1}) × (b_0 + b_1x + ... + b_ {n-1} x ^ {n-1})$$

Moreover, when multiplying all operations with the coefficients of polynomials are performed modulo 2.



But now, obviously, another problem may arise. By multiplying two degree polynomials $$$n-1$may turn out to be a higher degree polynomial that will not match any of the numbers in our set. This is solved as follows. An irreducible polynomial of degree is chosen. $$$n$. Roughly speaking, it is such a polynomial that cannot be represented as a product of other polynomials, more in the article . After this, using the algorithm for dividing polynomials by a column , which many may still remember from the school curriculum, we divide the result of the product into an irreducible polynomial. Once again I remind you that when dividing by a bar, operations with the coefficients of polynomials are also performed modulo 2. As a result, we get a polynomial of degree not higher than $$$n-1$which we take for the result of the product of two numbers. Here is an example of performing the multiplication of two numbers over the field $$$GF (2 ^ 8)$using an irreducible polynomial $$$x ^ 8 + x ^ 4 + x ^ 3 + x + 1$. This polynomial is used in the AES / Rijndael encryption algorithm.



We reviewed the field $$$GF (2 ^ n)$. Arbitrary fields $$$GF (p ^ n)$are built in a similar way, only instead of the binary representation of the number used $$$p$-personal and all calculations are performed by module $$$p$.

Isomorphism of fields and Galois fields of arbitrary size

And what will happen if you choose another irreducible polynomial? You can even put a more general question. Suppose I don’t like all these polynomials and divisions by a bar at all, so I’ll rather think up my own consistent multiplication table using some other principle. Will it be something fundamentally new? The answer is no. All these resulting fields will be isomorphic .



Translating from a "mathematical" language, isomorphism means that the differences are only in the designation of field elements and one can be reduced to another by choosing the appropriate mapping rule.



The finite sets of elements that we have considered so far have been of two types. The first type of set had a number of elements equal to some prime number. $$$p$. On such sets, we were able to specify the multiplication and addition tables using only modular arithmetic. The second type includes sets that have $$$p ^ n$, $$$p$- simple $$$n> 1$number of items. On such sets it is possible to specify multiplication / addition using a scheme with polynomials. Is it possible to specify in a similar way multiplication / addition for sets of arbitrary size, say, containing 6 elements? The answer is no, it is impossible.



Strictly speaking, finite fields are called Galois fields, because he discovered their following important properties:

1. The number of elements of the final field is always $$$p ^ n$where $$$p$prime number as well $$$n$any kind.
2. All size fields $$$p ^ n$isomorphic.

Conclusion

The second article of the cycle comes to an end. The first two articles presented brief theoretical information related to Reed-Solomon codes and Galois fields. In the next part I plan to elaborate in more detail on the features of the software implementation of the above-mentioned algorithms. Thank.