Channel Coding/Some Basics of Algebra

1. Channel Coding
2. Reed–Solomon–Codes and Their Decoding
3. Some Basics of Algebra

• Previous page
• Next page

• Previous page
• Next page

# OVERVIEW OF THE SECOND MAIN CHAPTER #

This chapter discusses the  »Reed-Solomon codes«,  invented in the early 1960s by  $\text{Irving Stoy Reed}$  and  $\text{Gustave Solomon}$.  Unlike binary block codes,  these codes are based on a Galois field   ${\rm GF}(2^m)$   with  $m > 1$.  So they work with multi-level symbols instead of binary characters  ("bits").

Specifically,  this chapter covers:

• The basics of  »linear algebra«:   »set«,   »group«,   »ring«,   »field«,  finite field«,

• the definition of  »extension fields«   ⇒   ${\rm GF}(2^m)$  and the corresponding operations,

• the meaning of  »irreducible polynomials«   and  »primitive elements«,

• the  »description and realization possibilities«   of a Reed-Solomon code,

• the error correction of such a code at the  »binary ersaure channel«   $\rm (BEC)$,

• the decoding using the  »Error Locator Polynomial   ⇒   "Bounded Distance Decoding"   $\rm (BDD)$,

• the  »block error probability«   of Reed-Solomon codes  and   »typical applications«.

Definition of a Galois field

Before we can turn to the description of  Reed–Solomon codes,  we need some basic algebraic notions.  We begin with the properties of the Galois field   ${\rm GF}(q)$,  named after the Frenchman  $\text{Évariste Galois}$, whose biography is rather unusual for a mathematician.

$\text{Definition:}$  A   $\rm Galois\:field$  ${\rm GF}(q)$  is a  $\text{finite field}$  with  $q$  elements  $z_0$,  $z_1$,  ... ,  $z_{q-1}$, if the eight statements listed below  $\rm (A)$  ...  $\rm (H)$  with respect to  "addition"   ⇒   "$+$"   and  "multiplication"  ⇒  "$\hspace{0.05cm}\cdot \hspace{0.05cm}$"   are true.

• Addition and multiplication are to be understood here modulo  $q$ .

• The  $\rm order$  $q$  indicates the number of elements of the Galois field.

$\text{Criteria of a Galois field:}$ 

$\rm (A)$  ${\rm GF}(q)$  is closed $\hspace{0.2cm}\Rightarrow \hspace{0.2cm}\rm Closure$:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_j \in {\rm GF}(q)\text{:} \hspace{0.25cm}(z_i + z_j)\in {\rm GF}(q),\hspace{0.15cm}(z_i \cdot z_j)\in {\rm GF}(q) \hspace{0.05cm}. \]

$\rm (B)$  There is a neutral element  $N_{\rm A}$  with respect to addition,  the so-called  "zero element" $\hspace{0.2cm}\Rightarrow \hspace{0.2cm}\rm Identity \ for \ "\hspace{-0.05cm}+\hspace{0.05cm}"$:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i + z_j = z_i \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm A} = \text{ 0} \hspace{0.05cm}.\]

$\rm (C)$  There is a neutral element  $N_{\rm M}$  with respect to multiplication,  the so-called  "identity element" $\hspace{0.2cm}\Rightarrow \hspace{0.2cm}\rm Identity \ for \ "\hspace{-0.05cm}·\hspace{0.05cm}"$:

\[\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i \cdot z_j = z_i \hspace{0.3cm}\Rightarrow \hspace{0.3cm} z_j = N_{\rm M} = {1} \hspace{0.05cm}. \]

$\rm (D)$  For each  $z_i$  there exists an  "additive inverse"   ${\rm Inv_A}(z_i)$ $\hspace{0.2cm}\Rightarrow \hspace{0.2cm}\rm Inverse \ for \ "\hspace{-0.05cm}+\hspace{0.05cm}"$:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {0} \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{short:}\hspace{0.3cm} {\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}. \]

$\rm (E)$  For each  $z_i$  except the zero element,  there exists the  "multiplicative inverse"   ${\rm Inv_M}(z_i)$ $\hspace{0.2cm}\Rightarrow \hspace{0.2cm}\rm Inverse \ for \ "\hspace{-0.05cm}\cdot\hspace{0.05cm}"$:

\[\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A}, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {1}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{short:}\hspace{0.3cm} {\rm Inv_M}(z_i) = z_i^{-1} \hspace{0.05cm}. \]

$\rm (F)$  For addition and multiplication applies in each case the  "$\rm Commutative \ Law$":

\[\forall \hspace{0.15cm} z_i,\hspace{0.15cm} z_j \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i + z_j = z_j + z_i ,\hspace{0.15cm}z_i \cdot z_j = z_j \cdot z_i \hspace{0.05cm}.\]

$\rm (G)$  For addition and multiplication applies in each case the  "$\rm Associative \ Law$":

\[\forall \hspace{0.15cm} z_i,\hspace{0.1cm} z_j ,\hspace{0.1cm} z_k \in {\rm GF}(q)\text{:} \hspace{0.25cm}(z_i + z_j) + z_k = z_i + (z_j + z_k ),\hspace{0.15cm}(z_i \cdot z_j) \cdot z_k = z_i \cdot (z_j \cdot z_k ) \hspace{0.05cm}.\]

$\rm (H)$  For the combination  "addition – multiplication"  holds the  "$\rm Distributive \ Law$":

\[\forall \hspace{0.15cm} z_i,\hspace{0.15cm} z_j ,\hspace{0.15cm} z_k \in {\rm GF}(q)\text{:} \hspace{0.25cm}(z_i + z_j) \cdot z_k = z_i \cdot z_k + z_j \cdot z_k \hspace{0.05cm}.\]

Examples and properties of Galois fields

We first check that for the binary number set  $Z_2 = \{0, 1\}$   ⇒   $q=2$   $($valid for the simple binary code$)$

• the eight criteria mentioned in the last section are met,

• so that we can indeed speak of  "${\rm GF}(2)$".

You can see the addition table and multiplication table below:

$$Z_2 = \{0, 1\}\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{Addition: } \left[ \begin{array}{c|cccccc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right] \hspace{-0.1cm} ,\hspace{0.25cm}\text{Multiplication: } \left[ \begin{array}{c|cccccc} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array} \right]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm GF}(2) . $$

One can see from this representation:

1. Each element of the addition and multiplication table of  $Z_2$  is again  $z_0 = 0$  or  $z_0 = 1$   ⇒   the criterion  $\rm (A)$  is satisfied.
   
2. The set  $Z_2$  contains the zero element  $(\hspace{-0.05cm}N_{\rm A} = z_0 = 0)$  and the one element $(\hspace{-0.05cm}N_{\rm M} = z_1 = 1)$  ⇒   the criteria  $\rm (B)$  and  $\rm (C)$  are satisfied.
   
3. The additive inverses  ${\rm Inv_A}(0) = 0$  and  ${\rm Inv_A}(1) = -1 \ {\rm mod}\ 2 = 1$  exist and belong to  $Z_2$   ⇒   the criterion  $\rm (D)$  is satisfied.
4. Similarly, the multiplicative inverse  ${\rm Inv_M}(1) = 1$   ⇒   the criterion  $\rm (E)$  is satisfied.
   
5. The validity of the commutative law  $\rm (F)$  in the set  $Z_2$  can be recognized by the symmetry with respect to the table diagonals.
6. The criteria  $\rm (G)$  and  $\rm (H)$  are also satisfied here  ⇒   all eight criteria are satisfied  ⇒   $Z_2 = \rm GF(2)$.
   

$\text{Example 1:}$  The number set  $Z_3 = \{0, 1, 2\}$   ⇒   $q = 3$  satisfies all eight criteria and is thus a Galois field  $\rm GF(3)$:

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

$\text{Example 2:}$  In contrast,  the number set  $Z_4 = \{0, 1, 2, 3\}$   ⇒   $q = 4$  is  »not«  a Galois field.

• The reason for this is that here is no multiplicative inverse to the element  $z_2 = 2$.  For a Galois field it would have to be true:   $2 \cdot {\rm Inv_M}(2) = 1$.

• But in the multiplication table there is no entry with  "$1$"  in the third row and third column  $($each valid for the multiplicand  $z_2 = 2)$.

$$Z_4 = \{0, 1, 2, 3\}\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]\hspace{0.25cm} \Rightarrow\hspace{0.25cm}\text{no }{\rm GF}(4) . $$

$\text{Generalization (without proof for now):}$

• A Galois field  ${\rm GF}(q)$  can be formed in the manner described here as  $\text{ring}$  of integer sizes modulo  $q$  only if  $q$  is a prime number:  
      $q = 2$,  $q = 3$,  $q = 5$,  $q = 7$,  $q = 11$, ...
  

• But if the order  $q$  can be expressed in the form  $q = P^m$  with a prime  $P$  and integer  $m$,  the Galois field  ${\rm GF}(q)$  can be found via an  $\text{extension field}$. 

Group, ring, field - basic algebraic concepts

In the first sections,  some basic algebraic terms have already been mentioned,  without their meanings having been explained in more detail.  This is to be made up now in all shortness from view of a communication engineer, whereby we mainly refer to the representation in  [Fri96]  and  [KM+08].  To summarize:

$\text{Definition:}$ 

• A  $\rm Galois\, field$  ${\rm GF}(q)$ is a  "field"  with a finite number  $(q)$  of elements   ⇒   »finite field«. 

• Each field is again a special case of a  "ring",  which itself can be represented again as a special case of an  "Abelian group".

Algebraic relations between group, ring and field

The diagram illustrates step by step how the following subordinate sets arise from a set  $\mathcal{M}$  by definition of addition, multiplication and division:

• Abelian group  $\mathcal{G}$ ,
• ring  $\mathcal{R}$,
• field  $\mathcal{F}$,
• finite field  $\mathcal{F}_q$  or Galois field  ${\rm GF}(q)$.

In the next two sections, the algebraic terms mentioned here will be discussed in more detail.

• For understanding the Reed–Solomon codes, however, this knowledge is not absolutely necessary.

• So you could jump directly to the chapter  "Extension Field" .
  

Definition and examples of an algebraic group

For the general definitions of  "group"  (and later  "ring")  we assume a set with infinitely many elements:

\[\mathcal{M} = \{\hspace{0.1cm}z_1,\hspace{0.1cm} z_2,\hspace{0.1cm} z_3 ,\hspace{0.1cm}\text{ ...} \hspace{0.1cm}\}\hspace{0.05cm}. \]

$\text{Definition:}$  A  $\text{algebraic group}$  $(\mathcal{G}, +)$  is an  (arbitrary)  subset  $\mathcal{G} ⊂ \mathcal{M}$  together with an additive linkage  $($"$+$"$)$  defined between all elements,  but only if the following properties are necessarily satisfied:

1. For all  $z_i, z_j ∈ \mathcal{G}$  holds  $(z_i + z_j) ∈ \mathcal{G}$   ⇒   "Closure–criterion for  $+$".
   
2. There is always a neutral element  $N_{\rm A} ∈ \mathcal{G}$  with respect to addition,  so that for all  $z_i ∈ \mathcal{G}$ holds:   $z_i +N_{\rm A} = z_i$.  Given a group of numbers:   $N_{\rm A} \equiv 0$.
   
3. For all  $z_i ∈ \mathcal{G}$  there is an inverse element  ${\rm Inv_A}(z_i) ∈ \mathcal{G}$  with respect to addition:  $z_i + {\rm Inv_A}(z_i)= N_{\rm A} $.  For a number group:  ${\rm Inv_A}(z_i) =- z_i$.
   
4. For all  $z_i, z_j, z_k ∈ \mathcal{G}$  holds:  $z_i + (z_j + z_k)= (z_i + z_j) + z_k$   ⇒   "Associative law  for  $+$".
   
5. If in addition for all  $z_i, z_j ∈ \mathcal{G}$  the  "commutative law"  $z_i + z_j= z_j + z_i$  is satisfied,  one speaks of a  "commutative group"  or an  "Abelian group",  named after the Norwegian mathematician  $\text{Niels Hendrik Abel}$.

$\text{Examples of algebraic groups:}$

(1)  The  "set of rational numbers"  is defined as the set of all quotients  $I/J$  with integers  $I$  and  $J ≠ 0$.

This set is a group  $(\mathcal{G}, +)$  with respect to addition,  since

• for all  $a ∈ \mathcal{G}$  and  $b ∈ \mathcal{G}$  also the sum  $a+b$  belongs to  $\mathcal{G}$ ,
  
• the associative law applies,
  
• with  $ N_{\rm A} = 0$  the neutral element of the addition is contained in  $\mathcal{G}$  and
  
• it exists for each  $a$  the additive inverse  ${\rm Inv_A}(a) = -a$ .
  

Since moreover the commutative law is fulfilled,  it is an  "abelian group".

(2)  The  "set of natural numbers"   ⇒   $\{0, 1, 2, \text{...}\}$  is not an algebraic group with respect to addition,
          since for no single element  $z_i$  there exists the additive inverse  ${\rm Inv_A}(z_i) = -z_i$ .

(3)  The  "bounded set of natural numbers"   ⇒   $\{0, 1, 2, \text{...}\hspace{0.05cm}, q\hspace{-0.05cm}-\hspace{-0.05cm}1\}$  on the other hand then satisfies the conditions on a group  $(\mathcal{G}, +)$,
          if one defines the addition modulo  $q$.

(4)  On the other hand,  $\{1, 2, 3, \text{...}\hspace{0.05cm},q\}$  is not a group because the neutral element of addition  $(N_{\rm A} = 0)$  is missing.

Definition and examples of an algebraic ring

According to the  $\text{overview graphic}$ 

• one gets from the group  $(\mathcal{G}, +)$ 

• by defining a second arithmetic operation  "multiplication"  ("$\cdot$")  to the  "ring"  $(\mathcal{R}, +, \cdot)$. 

So you need a multiplication table as well as an addition table for this.

$\text{Definition:}$  A  $\text{algebraic ring}$   $(\mathcal{R}, +, \cdot)$   is a subset  $\mathcal{R} ⊂ \mathcal{G} ⊂ \mathcal{M}$  together with two arithmetic operations defined in this set,

• addition  ("$+$") 
• and multiplication  ("$·$"). 

The following properties must be satisfied:

1. In terms of addition,  the ring  $(\mathcal{R}, +, \cdot)$  is an  $\text{Abelian group}$  $(\mathcal{G}, +)$.
   
2. In addition,  for all  $z_i, z_j ∈ \mathcal{R}$  also  $(z_i \cdot z_j) ∈ \mathcal{R}$   ⇒   "Closure criterion for  $\cdot$".
   
3. There is always also a neutral element  $N_{\rm M} ∈ \mathcal{R}$  with respect to multiplication,  so that for all  $z_i ∈ \mathcal{R}$  holds:   $z_i \cdot N_{\rm M} = z_i$.  For a number group:  $N_{\rm M} \equiv 1$.
   
4. For all  $z_i, z_j, z_k ∈ \mathcal{R}$  holds:   $z_i + (z_j + z_k)= (z_i + z_j) + z_k$   ⇒   "Associative law  for  $\cdot $".
   
5. For all  $z_i, z_j, z_k ∈ \mathcal{R}$ holds:   $z_i \cdot (z_j + z_k) = z_i \cdot z_j + z_i \cdot z_k$   ⇒   "Distributive law  for  $\cdot $".

Further the following agreements shall hold:

• A ring  $(\mathcal{R}, +, \cdot)$  is not necessarily commutative.  If in fact the  "commutative law"  also holds for all elements  $z_i, z_j ∈ \mathcal{R}$  with respect to multiplication  $(z_i \cdot z_j= z_j \cdot z_i)$  then it is called in the technical literature a  »commutative ring«.

• Exists for each element  $z_i ∈ \mathcal{R}$  except  $N_{\rm A}$  $($neutral element of addition,  zero element$)$  an element  ${\rm Inv_M}(z_i)$  inverse with respect to multiplication such that  $z_i \cdot {\rm Inv_M}(z_i) = 1$  holds, then there is a  »division ring«.
  

• The ring is  »free of zero divisors«  if from  $z_i \cdot z_j = 0$  follows necessarily  $z_i = 0$  or  $z_j = 0$.  In abstract algebra,  a zero divisor of a ring is an element  $z_i$ different from the zero element if there exists an element  $z_j \ne 0$  such that the product  $z_i \cdot z_j = 0$ .
  

• A commutative ring free of zero divisors is called  »integral domain«.
  
  

$\text{Conclusion:}$  Comparing the definitions of  $\text{group}$,  "ring"  (see above), $\text{field}$  and  $\text{Galois field}$,  we recognize that a  »Galois field«  ${\rm GF}(q)$

1. is a finite field with  $q$  elements,
   
2. is at the same time a  "commutative division ring",  and
   
3. also describes an  "integral domain".

Exercises for the chapter

Exercise 2.1: Group, Ring, Field

Exercise 2.1Z: Which Tables Describe Groups?

Exercise 2.2: Properties of Galois Fields

Exercise 2.2Z: Galois Field GF(5)