A Galois Field Arithmetic Primer | Electronics etc…
Introduction
A Galois Field Introduction by Example
Base Galois Fields
A Real World Example of a Base Galois Field
GF(2)
Extended Galois Fields
Extended Galois Field Addition
Extended Galois Field Multiplication
A Field Defining Irreducible Polynomial
A Primitive Polynomial
From Abstract Alpha to a Real Value
Selecting Primitive Polynomials
The Benefit of Primitive Polynomials
Linear Feedback Shift Register
Multiplication through Addition of Exponents
References
Footnotes
Introduction
In my blog post about Reed-Solomon coding,<br>I used regular integers for all calculations. These are impractical for a real-world<br>implementation, but since everybody knows integer math since first grade, it made things<br>easier to learn things one step at a time.
Instead of working with pure integers, actual Reed-Solomon implementations<br>use elements from a Galois or finite field<br>as symbols.
I’ve been sitting on implementing and writing about a Reed-Solomon decoder for almost<br>4 years now1, and I’m still not quite there, but a first step is to have<br>enough Galois field understanding so that the lack of it isn’t an obstacle. That’s what<br>this blog is about. Don’t expect a solid theoretical treatise, you can find many of those<br>as part of university courses, but something that is sufficient to refer back to in the<br>future when I’ve forgotten some of the details.
If you want to get a deeper understanding, check out the references at the bottom.
A Galois Field Introduction by Example
In mathematics, a field is a set of elements for which addition, subtraction, multiplication<br>and division operations have been defined, with properties that we take for granted when dealing<br>with rational or real numbers, such as the associative and distributive properties2,<br>the rules for adding and multiplying with 0, and so forth.
For rational or real numbers, the number of elements in the field is infinite. A Galois field<br>only has a limited number of elements, yet still has these kind of operations and properties.
A good example of a Galois field is \(\text{GF}(5)\) which has integer numbers 0 to 4 as elements.<br>Addition, subtraction, and multiplication work the same as for regular integers but each<br>such operation is followed by a modulo 5 operation.
Here are a few example operations in \(\text{GF}(5)\):
\[\begin{align}<br>1 + 3 = (1+3) \bmod 5 = 4 \bmod 5 = 4 \\<br>2 + 6 = (2+6) \bmod 5 = 8 \bmod 5 = 3 \\<br>3 \cdot 4 = (3 \cdot 4) \bmod 5 = 12 \bmod 5 = 2 \\<br>\end{align}\]
Division is a bit less intuitive. It is defined as the multiplication by the inverse of the<br>divisor:
\[\frac{a}{b} = a \cdot b^{-1}\]
One way of finding the multiplicative inverse of the divisor is by multiplying it with all possible<br>elements and checking if the result is 1.
Let’s say we want to do \(2/3\) in \(\text{GF}(5)\). We need to find \(3^{-1}\) so that \(3<br>\cdot 3^{-1} = 1\). There are 5 different options \(0,1,2,3,4\):
\[\begin{align}<br>(3 \cdot 0) \bmod 5 = 0 \\<br>(3 \cdot 1) \bmod 5 = 3 \\<br>\boldsymbol{(3 \cdot 2) \bmod 5 = 1} \\<br>(3 \cdot 3) \bmod 5 = 4 \\<br>(3 \cdot 4) \bmod 5 = 2 \\<br>\end{align}\]
We can see that \((3 \cdot 2)\bmod 5 = 1\), so \(3^{-1}=2\).
And thus:
\[2/3 = 2 \cdot 3^{-1} = (2 \cdot 2) \bmod 5 = 4\]
There are other ways to calculate the multiplicative inverse. For simple cases, you can use<br>Fermat’s Little Theorem,<br>which says:
\[a^{p-1} \equiv 1 \pmod{p}\]
or, after dividing both sides by \(a\):
\[a^{p-2} \equiv a^{-1} \pmod{p}\]
In our example \(a=3\) and \(p=5\), so:
\[3^{-1} = 3^{5-2} = 3^3 = 27\]
\[27 \pmod{5} = 2\]
A more general algorithm is the<br>Extended Euclidean Algorithm.
Base Galois Fields
The example above is one of a base Galois field
\[\text{GF}(p)\]
\(p\) is the base number of a one-dimensional mathematical universe. In a base<br>Galois field, \(p\) must always be a prime number, otherwise the division operation<br>would be ill defined.
For example, if we’d set \(p=6\) and tried to find the multiplicative inverse of 2,<br>we’d get the following:
\[\begin{align}<br>(2 \cdot 0) \bmod 6 = 0 \\<br>(2 \cdot 1) \bmod 6 = 2 \\<br>(2 \cdot 2) \bmod 6 = 4 \\<br>(2 \cdot 3) \bmod 6 = 0 \\<br>(2 \cdot 4) \bmod 6 = 2 \\<br>(2 \cdot 5) \bmod 6 = 4 \\<br>\end{align}\]
There’s no solution with a result of 1. Since there’s at least one element for which a<br>multiplicative inverse doesn’t exist, you can’t create a field for \(p=6\) and thus<br>\(\text{GF}(6)\) can’t exist.
Another issue for \(p=6\) is that you can get a result of 0 when multiplying 2 non-zero<br>numbers:
\[2 \cdot 3 \pmod{6} = 6 \pmod{6} = 0\]
That’s behavior unbecoming of a proper field!
A Real World Example of a Base Galois Field
Since a base Galois field must have a prime number of elements, only \(\text{GF}(2)\) maps directly<br>to the zeros and ones of digital logic; all other fields have an odd number of elements.<br>Still, there are some real-world cases where these kind of Galois fields are used:<br>the Wikipedia article on Reed-Solomon error...