Channel Coding/Extension Field

1. Channel Coding
2. Reed–Solomon–Codes and Their Decoding
3. Extension Field

• Previous page
• Next page

• Previous page
• Next page

GF(2²) – Example of an extension field

In  "Example 2"  of the chapter  "Some Basics of Algebra"  it has already been shown that the  »finite set of numbers«  $\{0,\ 1,\ 2,\ 3\}$   ⇒   $q = 4$  does not satisfy the properties of a Galois field  $\rm GF(4)$.  Rather,  the following tables result for the  "addition modulo 4"  and the  "multiplication modulo 4":

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it q} = 4\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition: } \left[ \begin{array}{c|cccccc} + & 0 & 1 &2 & 3 \\ \hline 0 & 0 & 1 &2 & 3 \\ 1 & 1 & 2 &3 & 0 \\ 2 & 2 & 3 &0 & 1 \\ 3 & 3 & 0 &1 & 2 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplication: } \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 &2 & 3 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 0 & 2 & 0 & 2 \\ 3 & 0 & 3 & 2 & 1 \\ \end{array} \right] . $$

For  $z_i = 2$  there is no multiplicative inverse  ${\rm Inv_M}(z_i)$.  This can be seen from the fact that no single element  $z_i ∈ \{0,\ 1,\ 2,\ 3\}$  satisfies the condition  $2 · z_i = 1$.

On the other hand,  if we start from the binary Galois field  ${\rm GF}(2) = \{0,\ 1\}$  and extend it according to the equation

\[{\rm GF}(2^2)= \big\{k_0+k_1\cdot \alpha \ \big | \ k_0, k_1\in{\rm GF}(2) = \{ 0, 1\} \big \}\hspace{0.05cm}, \]

then the likewise  »finite set  $\{0,\ 1,\ \alpha,\ 1 + \alpha\}$«   ⇒   order is further  $q=4$.

Performing the arithmetic operations modulo  $p(\alpha) = \alpha^2 + \alpha + 1$  we get the following result:

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it p}(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1\!+\!\alpha & 1 \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1 & \alpha \end{array} \right] .$$

In this regard, it should be noted:

• The neutral elements of addition or multiplication are still  $N_{\rm A} = 0$  and  $N_{\rm M} = 1$.

• Since there is no difference between addition and subtraction in modulo arithmetic  $\alpha + \alpha = \alpha - \alpha = 0$.
• For all  $z_i$  thus holds:   The additive inverse of  $z_i$  is the element  $z_i$  itself.

• The entries in the multiplication table are obtained according to the following calculations:

\[\big [ \alpha \cdot (1+\alpha) \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) = (\alpha^2 + \alpha) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= 1\hspace{0.05cm},\]

\[\big [ \alpha \cdot \alpha \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) = (\alpha^2 ) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= 1+\alpha\hspace{0.05cm},\]

\[\big [ (1+\alpha) \cdot (1+\alpha) \big ] \hspace{0.15cm}{\rm mod} \hspace{0.15cm} p(\alpha) = (\alpha^2 + 1) \hspace{0.15cm}{\rm mod} \hspace{0.15cm} (\alpha^2 + \alpha + 1)= \alpha\hspace{0.05cm}.\]

• Thus, the multiplicative inverses exist for all elements except the zero element:

\[{\rm Inv_M}( 1) = 1 \hspace{0.05cm},\hspace{0.2cm}{\rm Inv_M}(\alpha) = 1+\alpha \hspace{0.05cm},\hspace{0.2cm}{\rm Inv_M}(1+\alpha) = \alpha \hspace{0.05cm}.\]

$\text{Intermediate result:}$ 

• The set  $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$  together with operations  "addition"  and  "multiplication"  modulo  $p(\alpha)= \alpha^2 + \alpha + 1$  represents a  "Galois field"  $($order  $q = 4)$.

• This Galois field, denoted by  $\rm GF(2^2) = GF(4)$  satisfies all the requirements mentioned in the  "previous chapter" .
  

• In contrast to the Galois field  $\rm GF(3) = \{0, \ 1, \ 2\}$  with the property that  $q = 3$  is a prime number, $\rm GF(2^2)$  is called an extension field.

Reducible and irreducible polynomials

The polynomial  $p(\alpha)$  and thus the equation of determination  $p(\alpha) = 0$  must not be given arbitrarily. The polynomial used in the last section 

$$p(\alpha)= \alpha^2 + \alpha + 1$$

is suitable. Now we try another polynomial, namely  $p(\alpha)= \alpha^2 + 1$.

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm}{\it p}(\alpha)= \alpha^2 + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1 &1\!+\!\alpha \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1\!+\!\alpha & 0 \end{array} \right] .$$

The addition table is identical in both cases and also the multiplication tables differ only by the four entries in the two bottom rows and the two last columns:

• From  $p(\alpha) = 0$  now follows for the product  $\alpha \cdot \alpha = 1$  and the product  $(1 +\alpha) \cdot (1 +\alpha) $  gives the zero element. The mixed product is  $\alpha \cdot (1 +\alpha) = 1 +\alpha $.
  

• In the last row of the multiplication table and also in the last column there is now no "$1$"   ⇒   Concerning the condition  $p(\alpha)= \alpha^2 + 1= 0$  consequently the multiplicative inverse to  $1 +\alpha$  does not exist.
  

• But thus the finite set  $\{0, \ 1, \ \alpha, \ 1 + \alpha\}$ together with arithmetic operations modulo  $p(\alpha)= \alpha^2 + 1$  does not satisfy the conditions of an extension field either  $\rm GF(2^2) $.
  
  

$\text{Let us summarize:}$ 

From the binary Galois field  $\rm GF(2) = \{0, \ 1\}$  an extension field  $\rm GF(2^2)$  can be formulated with the aid of a polynomial of degree  $m = 2$  with binary coefficients:

\[p(x) = x^2 + k_1 \cdot x + k_0 \hspace{0.05cm}, \hspace{0.45cm}k_0\hspace{0.05cm},\hspace{0.1cm}k_1 \in \{0, 1\} \hspace{0.05cm}.\]

  Note:   The renaming of the variable  $\alpha$  to  $x$  has only formal meaning with regard to later sections.

• In the present case there is only one suitable polynomial  $p_1(x)= x^2 + x + 1$. All other possible polynomials of degree  $m = 2$, namely,

\[p_2(x) = x^2 + 1 \hspace{0.06cm} = (x+1) \cdot (x+1)\hspace{0.05cm},\]

\[p_3(x) =x^2 \hspace{0.76cm} = x \cdot x \hspace{0.05cm},\]

\[p_4(x) = x^2 + x = (x+1) \cdot x\hspace{0.05cm}, \]

can be factorized and do not yield extension fields.

• The polynomials  $p_2(x)$,  $p_3(x)$  and  $p_4(x)$  are called  "reducible".

• The conclusion is obvious that only  "irreducible polynomials"  such as  $p_1(x)$  are suitable for an extension fields

.

Interpretation of the new element "alpha"

We further consider the field  ${\rm GF}(2^2) = \{0, \ 1,\ \alpha,\ 1 + \alpha\}$  corresponding to the following two operational tables, based on the constraint  $p(\alpha)= \alpha^2 + \alpha + 1 = 0$  (irreducible ploynomial):

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm} p(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c|cccccc} + & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 1 & \alpha & 1\!+\!\alpha \\ 1 & 1 & 0 & 1\!+\!\alpha & \alpha \\ \alpha & \alpha & 1\!+\!\alpha & 0 & 1 \\ 1\!+\!\alpha & 1\!+\!\alpha & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 & \alpha & 1\!+\!\alpha \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & 1\!+\!\alpha \\ \alpha & 0 & \alpha & 1\!+\!\alpha & 1 \\ 1\!+\!\alpha & 0 & 1\!+\!\alpha & 1 & \alpha \end{array} \right] .$$

Transition from  ${\rm GF}(2)$  to  ${\rm GF}(2^2)$

But what is the meaning of the new element $\alpha$?

• The polynomial  $p(\alpha)= \alpha^2 + \alpha + 1 $  has no zero in  ${\rm GF}(2) = \{0, \ 1\}$ . This further implies that  $\alpha$  can be neither  $0$  nor  $1$ .
  

• If  $\alpha= 0$  resp.   $\alpha= 1$, then moreover two of the four set elements  $\{0,\ 1,\ \alpha,\ 1 + \alpha\}$  would be identical respectively:   Either "$0$" and "$\alpha$" as well as "$1$" and "$1+\alpha$" or "$1$" and "$\alpha$" as well as "$0$" and "$1+\alpha$".

• Much more the one-dimensional field  ${\rm GF}(2)$  gets a second dimension by the introduction of the element  $\alpha$ . It is thus extended to the Galois field  ${\rm GF}(2^2)$  as shown in the accompanying diagram.

• The element  $\alpha$  has similar meaning as the imaginary unit  ${\rm j}$, by which one extends the set of real numbers under the constraint  ${\rm j}^2 + 1 = 0$  to the set of complex numbers.

$\text{Common representation of the binary extension field}\ \ {\rm GF}(2^2)\text{:}$

Due to the identity  $\alpha^2 = 1 + \alpha$, which follows from the constraint  $p(\alpha) = 0$ , one can write in the same way  ${\rm GF}(2^2) = \{0,\ 1,\ \alpha,\ \alpha^2\}$  where now the following operation tables hold:

$$ \begin{array}{c} {\rm modulo}\hspace{0.15cm} p(\alpha)= \alpha^2 + \alpha + 1\\ \end{array}\hspace{0.25cm} \Rightarrow\hspace{0.25cm} \left[ \begin{array}{c | cccccc} + & 0 & 1 & \alpha & \alpha^2 \\ \hline 0 & 0 & 1 & \alpha & \alpha^2 \\ 1 & 1 & 0 & \alpha^2 & \alpha \\ \alpha & \alpha & \alpha^2 & 0 & 1 \\ \alpha^2 & \alpha^2 & \alpha & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.5cm} \left[ \begin{array}{c | cccccc} \cdot & 0 & 1 & \alpha & \alpha^2 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & \alpha^2 \\ \alpha & 0 & \alpha &\alpha^2 & 1 \\ \alpha^2 & 0 & \alpha^2 & 1 & \alpha \end{array} \right] .$$

Polynomials over a finite field

$\text{Definition:}$  A  »polynomial«  in a finite field  ${\rm GF}(P)$,  where  $P$  denotes a prime number,  has the following form:

\[a(x) = \sum_{i = 0}^{m} a_i \cdot x^{i} = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}\text{...} \hspace{0.1cm} + a_m \cdot x^{m} \hspace{0.05cm}.\]

To note:

• All coefficients  $a_i $  are elements of the field:   $a_i \in {\rm GF}(P)$.
  

• If the leading coefficient  $a_m ≠ 0$, then  $m$  indicates the  »degree«  of the polynomial.

Let us consider a second polynomial with degree $M$,

\[b(x) = \sum_{i = 0}^{M} b_i \cdot x^{i} = b_0 + b_1 \cdot x + b_2 \cdot x^2 + \hspace{0.1cm}\text{...} \hspace{0.1cm} + b_M \cdot x^{M} \hspace{0.05cm},\]

then we get for the sum  (resp. difference)  and the product respectively in  ${\rm GF}(P)$:

\[a(x) \pm b(x) = \sum_{i = 0}^{{\rm max}\hspace{0.05cm}(m, \hspace{0.05cm}M)} \hspace{0.15cm}(a_i \pm b_i) \cdot x^{i} \hspace{0.05cm},\]

\[a(x) \cdot b(x) = \sum_{i = 0}^{m + M} \hspace{0.15cm}c_i \cdot x^{i}\hspace{0.05cm},\hspace{0.5cm} c_i = \sum_{j = 0}^{i}\hspace{0.15cm}a_j \cdot b_{i-j} \hspace{0.05cm}.\]

$\text{Example 1:}$    $a(x) = x^3 + x + 1$   and  $b(x) = x^2 + x + 1$  are valid.

In the binary Galois field    ⇒   ${\rm GF}(2)$  results according to the above equations for the sum,  difference and product of the two polynomials:

\[s(x) = a(x) + b(x) = x^3 + x^2 \hspace{0.05cm}, \]

\[d(x) = a(x) - b(x) = x^3 + x^2 = s(x)\hspace{0.05cm},\]

\[c(x) = a(x) \cdot b(x) =\sum_{i = 0}^{3 + 2} \hspace{0.15cm}c_i \cdot x^{i}\hspace{0.05cm},\hspace{0.5cm} c_i = \sum_{j = 0}^{i}\hspace{0.15cm}a_j \cdot b_{i-j} \hspace{0.05cm}.\]

With  $a_0 = a_1 = a_3 = b_0 = b_1 =b_2 = 1$   and   $a_2 = a_4 = a_5 = b_3 = b_4 =b_5 = 0$  we obtain:

\[c_0 = a_0 \cdot b_0 = 1 \cdot 1 = 1 \hspace{0.05cm},\]

\[c_1 = a_0 \cdot b_1 + a_1 \cdot b_0 = 1 \cdot 1 + 1 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_2 =a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0 = 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_3 = a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1 + a_3 \cdot b_0 = 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 0 \hspace{0.05cm},\]

\[c_4=a_0 \cdot b_4 + a_1 \cdot b_3 + \hspace{0.05cm}\text{...}\hspace{0.05cm}+ \hspace{0.05cm}a_4 \cdot b_0 =1 \cdot 0 + 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 1 \hspace{0.05cm},\]

\[c_5 = a_0 \cdot b_5 + a_1 \cdot b_4 + \hspace{0.05cm}\text{...}\hspace{0.05cm}+ \hspace{0.05cm} a_5 \cdot b_0 =1 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 + 0 \cdot 1= 1 \]

\[\Rightarrow \hspace{0.3cm} c(x) = x^5 + x^4 +1 \hspace{0.05cm}.\]

In the Galois field  ${\rm GF}(3)$  other results are obtained due to the modulo 3 operations:

\[s(x) = (x^3 + x + 1) + (x^2 + x + 1) = x^3 + x^2 + 2x + 2\hspace{0.05cm},\]

\[d(x) = (x^3 + x + 1) - (x^2 + x + 1) = x^3 + 2x^2 \hspace{0.05cm},\]

\[c(x) = (x^3 + x + 1) \cdot (x^2 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 + 2x +1\hspace{0.05cm}.\]

$\text{Definition:}$  A polynomial  $a(x)$  is called  »reducible«  if it can be represented as the product of two polynomials  $p(x)$  and  $q(x)$  each of lower degree:

\[a(x) = p(x) \cdot q(x) \hspace{0.05cm}.\]

If this factorization is not possible,  that is

\[a(x) = p(x) \cdot q(x) + r(x)\hspace{0.05cm},\hspace{0.5cm} r(x) \ne 0\]

holds,  then the polynomial is called an  »irreducible«  or  »prime«.

$\text{Example 2:}$  It holds  $b(x) = x^3 + x + 1$,  then  $p_1(x) = x^2 + x + 1$   and   $p_2(x) = x^2 + 1$   are valid.

The graph on the left illustrates the modulo 2 multiplication  $a(x)= b(x) \cdot p_1(x)$. The result is  $a(x) = x^5 + x^4 + 1$.

Example of polynomial multiplication and division

In the right part of the above graph, the modulo 2 division  $q(x)= a(x)/ p_2(x)$  is shown with the result  $q(x) = x^3 + x^2 + x + 1$.

• This leaves the remainder  $r(x) = x$.

• According to this calculation alone  $a(x) = x^5 + x^4 + 1$  could well be an irreducible polynomial.
  

• However,  the proof that the polynomial   $a(x) = x^5 + x^4 + 1$   is indeed irreducible would only be given if  $a(x)/p(x)$  yields a remainder for all

\[p(x) = \sum_{i = 0}^{m} a_i \cdot x^{i} = a_m \cdot x^{m} + a_{m-1} \cdot x^{m-1} + \hspace{0.1cm}\text{...} \hspace{0.1cm}+ a_2 \cdot x^2 + a_1 \cdot x + a_0 \hspace{0.05cm}.\]

This proof would require (almost)   $2^5 = 32$   divisions in the present example.

• Based on our left-hand calculation,  we can immediately see here that  $a(x)$  is certainly not an irreducible polynomial, 
  since e.g.   $a(x) = x^5 + x^4 + 1$   divided by   $p_1(x) = x^2 + x + 1$   yields the polynomial   $b(x) = x^3 + x + 1$   with no remainder.

Generalized definition of an extension field

We assume the following:

• A Galois field  ${\rm GF}(P)$, where  $P$  denotes a prime number,
  

• an irreducible polynomial  $p(x)$  over  ${\rm GF}(P)$  of degree  $m$:

\[p(x) = a_m \cdot x^{m} + a_{m-1} \cdot x^{m-1} + \hspace{0.1cm}\text{...} \hspace{0.1cm}+ a_2 \cdot x^2 + a_1 \cdot x + a_0 \hspace{0.05cm}, \hspace{0.3cm} a_i \in {\rm G}(P)\hspace{0.05cm}, \hspace{0.15cm}a_m \ne 0\hspace{0.05cm}. \]

With the above conditions generally applies:

$\text{Definition:}$  Let 

1. $P$  be a prime number,
2. $m$  be an integer, 
3. $p(x)$  be an irreducible polynomial of degree  $m$  and
4. $p(\alpha) = 0$  hold.

An  extension field  can then be described as follows:

\[{\rm GF}(P^m)= \Big\{ k_{m-1} \hspace{0.01cm}\cdot \hspace{0.02cm}\alpha^{m-1} \hspace{0.05cm}+ \hspace{0.05cm}\text{...} \hspace{0.05cm}+ \hspace{0.05cm}k_1 \hspace{0.01cm}\cdot \hspace{0.02cm} \alpha \hspace{0.05cm}+ \hspace{0.05cm} k_0\hspace{0.05cm} \Big{\vert}\hspace{0.02cm} \ k_i\in{\rm GF}(P) = \{ 0, 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, P-1\}\Big \}.\]

• The addition and multiplication in this extension field then corresponds to polynomial addition and polynomial multiplication modulo  $p(\alpha)$.
  

• So:  A Galois field  ${\rm GF}(q)$  with  $q$  elements can be specified whenever the element number can be written in the form  $q = P^m$ 
  $(P$  denotes a prime number,  $m$  be integer$)$.

Possible Galois fields  ${\rm GF}(q)$  for  $q ≤ 64$

The diagram shows for which $q$–values a Galois field can be constructed. For the shaded values no finite field can be given.

Further it is to be noted:

1. The yellow highlighted positions  $q=P$   ⇒   $m = 1$  mark sets of numbers  $\{0,\ 1,\hspace{0.05cm}\text{ ...} \hspace{0.05cm},\ q- 1\}$  with Galois properties, see section  "Definition of a Galois Field".
   
2. Other background colors mark extension fields with  $q=P^m$,   $m ≥ 2$.  For  $q ≤ 64$  these are based on the primes  $2$,  $3$,  $5$,  $7$.
   
3. Highlighted in red are binary fields   ⇒   $q=2^m$,   $m ≥ 1$, which will be considered in more detail in the next section.
4. All other extension fields are labeled in blue.
   

Binary extension fields – Primitive polynomials

Irreducible and primitive polynomials

In the following we consider binary extension fields with  $q$  elements:

\[q = 2^m \hspace{0.15cm}(m \ge 2) \hspace{0.3cm} \Rightarrow\hspace{0.3cm} q = 4,\ 8,\ 16, 32,\ 64,\ \text{...}\]

• In the table all irreducible polynomials of the Galois field  ${\rm GF}(2)$  are given for  $2 ≤ m ≤ 6$.

• The polynomials in columns 2 and 3 are not only irreducible,  but additionally also primitive.
  

• Primitive polynomials also provide the basis for the  "Realization of pseudo–noise generators".
  

Before we turn to the definition of a primitive polynomial,  we shall first mention the peculiarities of  "primitive elements"  using the example of

\[{\rm GF}(q) = \{\hspace{0.05cm}z_0 = 0,\hspace{0.1cm} z_1 = 1,\hspace{0.05cm} \text{...}\hspace{0.05cm} , \hspace{0.05cm}z_{q-1}\}.\]

The element  $z_i = \beta$  is then called  »primitive« ,

• if the power  $\beta^{\hspace{0.05cm}i}$  modulo  $q$  for the first time for  $i = q-1$  leads to the result  "$1$"  so that
  

• $\beta^{\hspace{0.05cm}i}$  for  $1 ≤ i ≤ q- 1$  yields exactly the elements  $z_1$, ... , $z_{q-1}$  i.e. all elements of  ${\rm GF}(q)$  except the zero element  $z_0 = 0$.
  

$\text{Example 3:}$  From the number set  $Z_5 = \{0,\ 1,\ 2,\ 3,\ 4\}$,  the numbers  "$2$"  and  "$3$"  are primitive elements because of

\[2^1 \hspace{-0.1cm} = \hspace{-0.1cm} 2\hspace{0.05cm},\hspace{0.2cm} 2^2 = 4\hspace{0.05cm},\hspace{0.2cm} 2^3 = 8 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},\hspace{0.2cm} 2^4 = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},\]

\[3^1 \hspace{-0.1cm} = \hspace{-0.1cm} 3\hspace{0.05cm},\hspace{0.2cm} 3^2 = 9\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4\hspace{0.05cm},\hspace{0.2cm} 3^3 = 27 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2\hspace{0.05cm},\hspace{0.2cm} 3^4 = 81 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\]

• On the other hand,  "$4$"  is not a primitive element,  because already  $4^2 = 1$:

\[4^1 = 4\hspace{0.05cm},\hspace{0.2cm} 4^2 = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},\hspace{0.2cm} 4^3 = 64 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4\hspace{0.05cm},\hspace{0.2cm} 4^4 = 256 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm}.\]

$\text{Definition:}$  An irreducible polynomial is called at the same time a  »primitive polynomial« 
    if the root  $\alpha$  with respect to the polynomial  $p(x)$  is a primitive element of  ${\rm GF}(q)$.  Then holds

\[{\rm GF}(q) = \{\hspace{0.1cm}\alpha^{-\infty} = 0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0} = 1,\hspace{0.05cm}\hspace{0.2cm} \alpha\hspace{0.05cm},\hspace{0.2cm} \alpha^{2},\hspace{0.2cm} \text{...} \hspace{0.1cm} , \hspace{0.2cm}\alpha^{q-2}\hspace{0.1cm}\}\hspace{0.05cm}. \]

• All polynomials given in the second column of the above table are both irreducible and primitive.

• If  $p_1(x)$  is a primitive polynomial,  then the polynomial reciprocal   $p_2 (x) = x^m \cdot p_1(x^{-1})$   to it is also primitive.

• All polynomials in the third column are reciprocal to the polynomial in the second column.  For example,  for  $m = 3$:

\[p_1(x) = x^3 + x + 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}p_2(x) = x^3 \cdot \big[x^{-3} + x^{-1} + 1 \big]= x^3 + x^2 + 1 \hspace{0.05cm}.\]

• The irreducible polynomials of column 4,  on the other hand,  are not primitive;  they play only a minor role in describing error correction procedures.
  

$\text{Example 4:}$  For clarification of these statements we consider exemplarily

• the Galois field  $\rm GF(2^3) = GF(8)$,  as well as
  

• the polynomial  $p(x) = x^3 + x + 1$.
  
  

From the condition   $p(\alpha) = 0$   we obtain in  $\rm GF(2^3)$  further:

\[\alpha^3 + \alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}\alpha^3 = \alpha + 1 \hspace{0.05cm},\]

and thus for the powers  $\alpha^{i}$  of the root for  $i ≥ 4$:

\[\alpha^4 = \alpha \cdot \alpha^3 = \alpha \cdot (\alpha + 1) = \alpha^2 + \alpha \hspace{0.05cm},\]

\[\alpha^5 = \alpha^2 \cdot \alpha^3 = \alpha^2 \cdot (\alpha + 1) = \alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1 \hspace{0.05cm},\]

\[\alpha^6 = \alpha^3 \cdot \alpha^3 = (\alpha + 1) \cdot (\alpha + 1) = \alpha^2 + \alpha + \alpha + 1= \alpha^2 + 1 \hspace{0.05cm},\]

\[\alpha^7 = \alpha^4 \cdot \alpha^3 = (\alpha^2 + \alpha) \cdot (\alpha + 1) = \alpha^3 + \alpha^2 + \alpha^2 + \alpha = \alpha + 1 + \alpha = 1 = \alpha^0 \hspace{0.05cm}.\]

$\text{Example 5:}$  The elements  $z_0$,  $z_1$, ... ,  $z_7$  of the Galois field  $\rm GF(2^3)$  can be represented according to the adjacent table as follows:

Elements of  $\rm GF(2^3)$  in three different representations

• as powers of  $\alpha$   ⇒   »exponent representation«,
  

• as polynomials of the form  $k_2 \cdot \alpha^2 + k_1 \cdot \alpha + k_0$  with binary coefficients  $k_2$,  $k_1$,  $k_0$   ⇒   »polynomial representation«,
  

• as vectors of coefficients  $(k_2, \ k_1, \ k_0)$   ⇒   »coefficient representation«.
  
  

⇒   For addition  (or subtraction)  of two elements polynomial and vector representation are equally suitable,
where the components are to be added  $\text{modulo 2}$,  for example:

\[z_5 + z_7 =(\alpha^2 + \alpha) + (\alpha^2 + 1) = \alpha + 1 = \alpha^3 = z_4 \hspace{0.05cm},\]

\[{\rm oder}\hspace{0.15cm} z_5 + z_7 =(110) + (101) = (011) = z_4 \hspace{0.05cm},\]

\[\hspace{0.15cm} z_1 + z_2 + z_3 =(001) + (010) + (100)= (111) = z_6 \hspace{0.05cm}.\]

⇒   For multiplications,  the exponent representation is well suited,  as the following examples show:

$\rm GF(2^3)$  in 3D representation

\[z_3 \cdot z_4 =\alpha^2 \cdot \alpha^3 = \alpha^{2+3}= \alpha^{5} = z_6 \hspace{0.05cm},\]

\[z_0 \cdot z_5 =\alpha^{-\infty} \cdot \alpha^4 = \alpha^{-\infty} = z_0 \hspace{0.05cm},\]

\[z_5 \cdot z_7 = \alpha^4 \cdot \alpha^6 = \alpha^{10}= \alpha^{7} \cdot \alpha^{3} = 1 \cdot \alpha^{3}= z_4 \hspace{0.05cm}.\]

It can be seen that the exponents result modulo  $q-1$  $($in this example modulo  $7)$.

⇒   The bottom graph shows the finite extension field  $\rm GF(2^3)$  in a three-dimensional representation:

• The axes are labeled  $\alpha^0 =1$,  $\alpha^1$  and  $\alpha^2$.

• The  $2^3 = 8$  points in the three-dimensional space are labeled with the coefficient vectors.

• The assignment of the coefficients  $k_2$,  $k_1$,  $k_0$  to the axes is made clear by color.

Exercises for the chapter

Exercise 2.3: Reducible and Irreducible Polynomials

Exercise 2.3Z: Polynomial Division

Exercise 2.4: GF(2 to the Power of 2) Representation Forms

Exercise 2.4Z: Finite and Infinite Fields

Exercise 2.5: Three Variants of GF(2 power 4)

Exercise 2.5Z: Some Calculations about GF(2 power 3)

Exercise 2.6: GF(P power m). Which P, which m?