Galois Fields and Its Properties¶

Galois fields, named after Evariste Galois also known as Finite Field, is a mathematical concept in abstract algebra that deals with finite mathematical structures. It is a set of numbers that consists of a finite number of elements and has two operations, addition and multiplication, that follow specific rules. The rules for these operations ensure that the Galois Field remains closed, meaning that the result of any operation performed within the set will also be an element of the set.

The number of elements of a Galois field or finite field is called its order or, sometimes, its size. A finite field of order $q$ exists if and only if $q$ is a prime power $p^m$ (where $p$ is a prime number and $m$ is a positive integer). The Galois field is denoted as $GF(p^m)$. In a field of order $q=p^m$, adding $p$ copies of any element always results in zero; that is, the characteristic of the field is $p$.

Sometimes $GF(p)$ is called Galois fields and $GF(p^m)$ is called the extended Galois fields.

Properties of Galois Field¶

Finite Size: The most important property of a Galois Field is that it is finite. It has a specific number of elements, and it is not possible to add any more elements to it. The size of the field is represented by a prime number $p$.
Closure: The Galois Field remains closed under both addition and multiplication operations, meaning that the result of any operation performed within the set will always be an element of the set.
Commutative: The Galois Field is commutative under both addition and multiplication operations. This means that the order of elements does not matter in performing operations. For example, $a+b = b+a$ and $ab = ba$.
Associative: The Galois Field is associative under both addition and multiplication operations. This means that the grouping of elements in an operation does not matter. For example, $(a+b) + c = a + (b+c)$ and $(ab) * c = a * (bc)$.
Distributive: The Galois Field follows the distributive property. This means that multiplication distributes over addition, i.e., $a * (b + c) = a * b + a * c$.
Identity Elements: The Galois Field has two identity elements, 0 for addition and 1 for multiplication. Any element added with 0 is equal to the original element, and any element multiplied by 1 is equal to the original element.
Inverse Elements: Every element in the Galois Field has an inverse element under both addition and multiplication operations. The inverse element for addition is the negative of the original element, and the inverse element for multiplication is the reciprocal of the original element.

Binary Galois fields $GF(2^m)$ will be focused in the proceeding discussions.

Explicit Construction of $GF(p^m)$¶

For $m>1$, one first chooses an irreducible polynomial (or primitive polynomial) $P(x)$ of degree $m$. The elements of $GF(p^m)$ are the polynomials over $GF(p)$ whose degree is strictly less than $m$. The addition and subtraction are those of polynomials over $GF(p)$. The product of two elements is the remainder of the Euclidean division by $P(x)$ of the product. The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm. Usually the elements of $GF(p^m)$ is presented as polynomials in $\alpha$, where $P(\alpha)=0$.

There might be several possible choices for $P(x)$.

Field Symbols $\alpha ^i$¶

$\alpha ^i$ can be used to denote each individual element within $GF(p^m)$. $\alpha(x)$ is called the primitive element, often simply as $\alpha$. The consecutive powers of the primitive element $\alpha$ is taken until the field elements start to repeat.

Field Element Representations¶

Four representations are usually used:

Power Representation
Polynomial Representation
Vector Representation
Integer Representation

The following table demonstrates the four equivalent representations for $GF(2^4)$, where $\alpha = x$.

Power	Polynomial	Vector	Integer
0	0	(0000)	0
1	1	(0001)	1
$\alpha$	$x$	(0010)	2
$\alpha ^2$	$x ^2$	(0100)	4
$\alpha ^3$	$x ^3$	(1000)	8
$\alpha ^4$	$x+1$	(0011)	3
$\alpha ^5$	$x^2+x$	(0110)	6
$\alpha ^6$	$x^3+x^2$	(1100)	12
$\alpha ^7$	$x^3+x+1$	(1011)	11
$\alpha ^8$	$x^2+1$	(0101)	5
$\alpha ^9$	$x^3+x$	(1010)	10
$\alpha ^{10}$	$x^2+x+1$	(0111)	7
$\alpha ^{11}$	$x^3+x^2+x$	(1110)	14
$\alpha ^{12}$	$x^3+x^2+x+1$	(1111)	15
$\alpha ^{13}$	$x^3+x^2+1$	(1101)	13
$\alpha ^{14}$	$x^3+1$	(1001)	9

Python Examples¶

Python library galois is used in the following examples. It can be installed as:

   pip install galois

In [2]:

import galois

gf16 = galois.GF(2**4)
print(gf16.properties)

print('--------------------------------------------')
print("All elements in different presentations:")
print(f"{0:>6} {0:>20} {0:>5}")
for ii in range(15):
    tmp_str = f'α^{ii}'
    print(f"{tmp_str:>6} {gf16._print_poly(gf16.primitive_element**ii):>20} {gf16.primitive_element**ii:>5}")

print('--------------------------------------------')
print('All primitive elements:')
print(gf16.primitive_elements)

Galois Field:
  name: GF(2^4)
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: x^4 + x + 1
  is_primitive_poly: True
  primitive_element: x
--------------------------------------------
All elements in different presentations:
     0                    0     0
   α^0                    1     1
   α^1                    α     2
   α^2                  α^2     4
   α^3                  α^3     8
   α^4                α + 1     3
   α^5              α^2 + α     6
   α^6            α^3 + α^2    12
   α^7          α^3 + α + 1    11
   α^8              α^2 + 1     5
   α^9              α^3 + α    10
  α^10          α^2 + α + 1     7
  α^11        α^3 + α^2 + α    14
  α^12    α^3 + α^2 + α + 1    15
  α^13        α^3 + α^2 + 1    13
  α^14              α^3 + 1     9
--------------------------------------------
All primitive elements:
[ 2  3  4  5  9 11 13 14]

In [3]:

print('Use different primitive element instead of X')
print('--------------------------------------------')
gf16_5 = galois.GF(2**4, primitive_element=5)
print(gf16_5.properties)

print('--------------------------------------------')
print("All elements in different presentations:")
print(f"{0:>6} {0:>20} {0:>5}")
for ii in range(15):
    tmp_str = f'α^{ii}'
    print(f"{tmp_str:>6} {gf16_5._print_poly(gf16_5.primitive_element**ii):>20} {gf16_5.primitive_element**ii:>5}")

# use galois repr_table
print('---------------------------------------------')
print('Using galois repr_table')
print(gf16_5.repr_table())

Use different primitive element instead of X
--------------------------------------------
Galois Field:
  name: GF(2^4)
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: x^4 + x + 1
  is_primitive_poly: True
  primitive_element: x^2 + 1
--------------------------------------------
All elements in different presentations:
     0                    0     0
   α^0                    1     1
   α^1              x^2 + 1     5
   α^2                    x     2
   α^3              x^3 + x    10
   α^4                  x^2     4
   α^5          x^2 + x + 1     7
   α^6                  x^3     8
   α^7        x^3 + x^2 + x    14
   α^8                x + 1     3
   α^9    x^3 + x^2 + x + 1    15
  α^10              x^2 + x     6
  α^11        x^3 + x^2 + 1    13
  α^12            x^3 + x^2    12
  α^13              x^3 + 1     9
  α^14          x^3 + x + 1    11
---------------------------------------------
Using galois repr_table
    Power           Polynomial         Vector      Integer
-------------- ------------------- -------------- ---------
      0                 0           [0, 0, 0, 0]      0
 (x^2 + 1)^0            1           [0, 0, 0, 1]      1
 (x^2 + 1)^1         x^2 + 1        [0, 1, 0, 1]      5
 (x^2 + 1)^2            x           [0, 0, 1, 0]      2
 (x^2 + 1)^3         x^3 + x        [1, 0, 1, 0]      10
 (x^2 + 1)^4           x^2          [0, 1, 0, 0]      4
 (x^2 + 1)^5       x^2 + x + 1      [0, 1, 1, 1]      7
 (x^2 + 1)^6           x^3          [1, 0, 0, 0]      8
 (x^2 + 1)^7      x^3 + x^2 + x     [1, 1, 1, 0]      14
 (x^2 + 1)^8          x + 1         [0, 0, 1, 1]      3
 (x^2 + 1)^9    x^3 + x^2 + x + 1   [1, 1, 1, 1]      15
 (x^2 + 1)^10        x^2 + x        [0, 1, 1, 0]      6
 (x^2 + 1)^11     x^3 + x^2 + 1     [1, 1, 0, 1]      13
 (x^2 + 1)^12       x^3 + x^2       [1, 1, 0, 0]      12
 (x^2 + 1)^13        x^3 + 1        [1, 0, 0, 1]      9
 (x^2 + 1)^14      x^3 + x + 1      [1, 0, 1, 1]      11

Reed Solomon (RS) Coding¶

RS codes are BCH codes which are a subset of cyclic block codes. Cyclic block codes are a subset of linear block codes which are a subset of block codes which are a subset of error correction codes in general. Therefore, RS codes are the great, great grandchildren of block codes. RS codes are very efficient random and burst error correcting codes.

RS Encoder¶

The parity-check information $CK(x)$ is obtained from the message information $M(x)$ by the modulo-$g(x)$ function (generator function).

$$CK(x)=x^{n-k}M(x)\ mod\ g(x)$$

where $x^{n-k}$ is the displacement shift, $M(x)$ is the message, $g(x)$ is the generator that is $n-k$ degree. The code word is:

$$C(x)=x^{n-k}M(x)+CK(x)$$

Polynomial Definations¶

Message $M(x)$ consists of message symbols $M_i$:

$$M(x)=M_{k-1}x^{k-1}+M_{k-2}x^{k-2}+...+M_1x+M_0$$

Generator $g(x)$ consists of generator symbols:

$$g(x)=x^{2t}+g_{2t-1}x^{2t-1}+...+g_1x+g_0$$

where $n-k=2t$.

Parity check $CK(x)$ consists of parity-check symbols $CK_i$:

$$CK(x)=CK_{n-k-1}x^{n-k-1}+CK_{n-k-2}x^{n-k-2}+...+CK_1x+CK_0$$

Code word $C(x)$ consists of code word symbols $C_i$:

$$C(x) = x^{n-k}M(x)+CK(x)=M_{k-1}x^{n-1}+...+M_0x^{n-k}+CK_{n-k-1}x^{n-k-1}+...+CK_0$$

$(n,k)$ RS Codes¶

Given the Galois Fields $GF(p^m)$, a set of RS codes with varying error correction capabilities, block lengths, and rates can be constructed. A $(n,k)$ RS code is defined given the following values:

$p$ (almost always 2)
m
n
primitive polynomial $P(x)$ of $GF(p^m)$
primitive element $\alpha(x)$ (almost always $\alpha(x)=x$)
any primitive element of $\alpha ^ G$
first consecutive root (FCR) for determining $g(x)$

A primitive RS code has the following parameters over $GF(p^m)$:

block length: $n=p^m-1$ (units are symbols)
parity-check length: $n-k=2t$ (units are symbols)
minimum distance: $d_{min}=2t+1$ (units are symbols)

Generator Polynomial $g(x)$¶

The generator $g(x)$ for a primitive RS code can be determined as:

$$g(x)=\prod_{i=FCR}^{FCR+2t-1}\left[x+\left(\alpha^G\right)^i\right]=\sum_{j=0}^{2t}g_jx^j=x^{2t}+g_{2t-1}x^{2t-1}+...+g_1x+g_0$$

CCSDS RS Code Generators¶

CCSDS RS code is based on $GF(2^8)$. The general characteristics are:

$n=2^8-1=255$
$P(x)=x^8+x^7+x^2+x+1$
$t = 16$ for $(255, 223)$ RS code and $t=8$ for $(255,239)$ RS code

The code generator $g(x)$ shall be:

$$g(x)=\prod_{i=128-t}^{127+t}(x-\alpha^{11i})$$

Python scripts to obtain $g(x)$:

In [4]:

gf_rs = galois.GF(2**8, irreducible_poly='x^8 + x^7 + x^2 + x +1', primitive_element=173)  # α^11 is 173

ts = [8, 16]
fcr = [128 - x for x in ts]

gxs = [galois.Poly([1], field=gf_rs), galois.Poly([1], field=gf_rs)]
for it, t in enumerate(ts):
    for ii in range(2*t):
        gxs[it] = gxs[it] * galois.Poly([1, gf_rs.primitive_element**(fcr[it]+ii)], field=gf_rs)
    print(f'Generator for t={t}:')
    print(gxs[it].coefficients())

# use reed-solomon in galois
print('------------------------------------')
print('Use ReedSolomon module in galois:')
rs8 = galois.ReedSolomon(n=255, k=239, field=gf_rs, c=fcr[0])
print(f'Generator for t=8, (255, 239):')
print(rs8.generator_poly.coeffs)
rs16 = galois.ReedSolomon(n=255, k=223, field=gf_rs, c=fcr[1])
print(f'Generator for t=16, (255, 223):')
print(rs16.generator_poly.coeffs)

Generator for t=8:
[  1 165 105  27 159 104 152 101  74 101 152 104 159  27 105 165   1]
Generator for t=16:
[  1  91 127  86  16  30  13 235  97 165   8  42  54  86 171  32 113  32
 171  86  54  42   8 165  97 235  13  30  16  86 127  91   1]
------------------------------------
Use ReedSolomon module in galois:
Generator for t=8, (255, 239):
[  1 165 105  27 159 104 152 101  74 101 152 104 159  27 105 165   1]
Generator for t=16, (255, 223):
[  1  91 127  86  16  30  13 235  97 165   8  42  54  86 171  32 113  32
 171  86  54  42   8 165  97 235  13  30  16  86 127  91   1]

Encoding Example of RS(15,9)¶

In [5]:

import numpy as np

rs_15_9 = galois.ReedSolomon(15, 9)
gf_rs_15_9 = rs_15_9.field
print(gf_rs_15_9.properties)

# generate randome symbols
msg = gf_rs_15_9.Random(rs_15_9.k)
print(msg)

cw = rs_15_9.encode(msg)
print(cw)

# using literal method
print('-----------------------------')
print('Using polynomials to encode')
print(f'Generator polynomial is {rs_15_9.generator_poly}')
# make polynomial from msg
len_parity = 6
shift_poly = galois.Poly([1 if x==0 else 0 for x in range(len_parity+1)], field=gf_rs_15_9)

msg_poly = galois.Poly(msg) * shift_poly
ck_poly = msg_poly % rs_15_9.generator_poly

cw_poly = np.concat((msg, ck_poly.coeffs))
print('Encoded codeword using msg(x) % g(x):')
print(cw_poly)

Galois Field:
  name: GF(2^4)
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: x^4 + x + 1
  is_primitive_poly: True
  primitive_element: x
[ 9  0 10 12 12  3  4  3  2]
[ 9  0 10 12 12  3  4  3  2 12 13  2  6  6  6]
-----------------------------
Using polynomials to encode
Generator polynomial is x^6 + 7x^5 + 9x^4 + 3x^3 + 12x^2 + 10x + 12
Encoded codeword using msg(x) % g(x):
[ 9  0 10 12 12  3  4  3  2 12 13  2  6  6  6]

RS Decoder¶

To be added.

Decoding Example of RS(15, 9)¶

In [16]:

print(f'Corrupt the first symbol of {cw}')
cw[0] ^= 13
print('Corrupted codeword:')
print(cw)

dec_m, num_corr = rs_15_9.decode(cw, errors=True)
print('Decoded message:')
print(dec_m)
print(f'Corrected errors: {num_corr}')
print(f'Equality against original message: {np.array_equal(msg, dec_m)}')

Corrupt the first symbol of [ 9  0 10 12 12  3  4  3  2 12 13  2  6  6  6]
Corrupted codeword:
[ 4  0 10 12 12  3  4  3  2 12 13  2  6  6  6]
Decoded message:
[ 9  0 10 12 12  3  4  3  2]
Corrected errors: 1
Equality against original message: True

Comments

Galois Field and Reed-Solomon Coding