# What are some examples of additive inverses

## Some basics of algebra

1. Channel coding
2. Reed – Solomon codes and their decoding
3. Some basics of algebra

### # OVERVIEW OF THE SECOND MAIN CHAPTER #

This chapter covers the Reed – Solomon codesinvented by Irving Stoy Reed and Gustave Solomon in the early 1960s. In contrast to the binary block codes, these are based on a Galois field \$ {\ rm GF} (2 ^ m) \$ with \$ m> 1 \$. So you are working with multi-level symbols instead of binary characters (bits).

This chapter deals in detail with:

• The basics of linear algebra: set, group, ring, field, finite field,
• the definition of extension fields ⇒ \$ {\ rm GF} (2 ^ m) \$ and the associated operations,
• the meaning of irreducible polynomials and primitive elements,
• the description and implementation possibilities of a Reed-Solomon code,
• the error correction of such a code in the extinction channel (BEC),
• decoding with the help of the Error locator polynomials   ⇒   Bounded distance decoding (BDD),
• the block error probability of the Reed – Solomon codes and typical applications.

### Definition of a Galois field

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

\$ \ text {Definition:} \$ A \$ \ rm Galois field \$ \$ {\ rm GF} (q) \$ is a finite field with \$ q \$ elements \$ z_0 \$, \$ z_1 \$, ..., \$ z_ {q- 1} \$ if the eight statements listed below \$ \ rm (A) \$ ... \$ \ rm (H) \$ regarding addition (“\$ + \$”) And multiplication (“\$ \ Cdot \$”) apply.

• Addition and multiplication are to be understood as modulo \$ q \$.
• The \$ \ rm order \$ \$ q \$ specifies the number of elements of the Galois field.

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

\$ \ rm (A) \$ \$ {\ rm GF} (q) \$ is self-contained \$ \ 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 an addition-neutral element \$ N _ {\ rm A} \$, 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 multiplication-neutral element \$ N _ {\ rm M} \$, the so-called One 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.3 cm} z_j = N _ {\ rm M} = {1} \ hspace {0.05cm}. \]

\$ \ rm (D) \$ For every \$ z_i \$ there is one 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 every \$ z_i \$ with the exception of the zero element there is 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.15 cm} {\ 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) \$ This applies to addition and multiplication Commutative law \$ \ hspace {0.2cm} \ Rightarrow \ hspace {0.2cm} \ 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) \$ This applies to addition and multiplication in each case Associative law \$ \ hspace {0.2cm} \ Rightarrow \ hspace {0.2cm} \ 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) \$ This applies to the combination “addition - multiplication” Distributive law \$ \ hspace {0.2cm} \ Rightarrow \ hspace {0.2cm} \ 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 whether the eight criteria mentioned on the last page are met for the binary set of numbers \$ Z_2 = \ {0, 1 \} \$ ⇒ \$ q = 2 \$ (valid for the simple binary code), so that one can actually assume " \$ {\ rm GF} (2) \$ ”can speak. You can see the addition 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 recognizes from this representation:

• 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 fulfilled.
• The set \$ Z_2 \$ contains the zero element \$ (\ hspace {-0.05cm} N _ {\ rm A} = z_0 = 0) \$ and the single element \$ (\ hspace {-0.05cm} N _ {\ rm M} = z_1 = 1) \$ ⇒ the criteria \$ \ rm (B) \$ and \$ \ rm (C) \$ are fulfilled.
• The additive inverses \$ {\ rm Inv_A} (0) = 0 \$ and \$ {\ rm Inv_A} (1) = -1 \ {\ rm mod} \ 2 = 1 \$ exist and belong to \$ Z_2 \$.
• There is also the multiplicative inverse \$ {\ rm Inv_M} (1) = 1 \$ ⇒ the criteria \$ \ rm (D) \$ and \$ \ rm (E) \$ are fulfilled.
• The validity of the commutative law \$ \ rm (F) \$ in the set \$ Z_2 \$ can be seen from the symmetry with respect to the table diagonals.
• The criteria \$ \ rm (G) \$ and \$ \ rm (H) \$ are also met here ⇒ all eight criteria are met ⇒ \$ Z_2 = \ rm GF (2) \$.

\$ \ text {Example 1:} \$ The number set \$ Z_3 = \ {0, 1, 2 \} \$ ⇒ \$ q = 3 \$ fulfills all eight criteria and is therefore 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.25 cm} \ Rightarrow \ hspace {0.25cm} {\ rm GF} (3). \$\$

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

• The reason for this is that there is no multiplicative inverse for the element \$ z_2 = 2 \$. For a Galois field the following should apply: \$ 2 \ cdot {\ rm Inv_M} (2) = 1 \$.
• In the multiplication table, however, 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 (initially without proof):} \$

• A Galois field \$ {\ rm GF} (q) \$ can only be formed as a "ring" of integers modulo \$ q \$ in the manner described here 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 number \$ P \$ and an integer \$ m \$, then the Galois field \$ {\ rm GF} (q) \$ can be found via an expansion field .

### Group, ring, body - basic algebraic terms

A few basic algebraic terms have already been mentioned on the first pages without their meanings being explained in more detail. This should now be made up for in a nutshell from the point of view of a communications engineer, whereby we mainly refer to the representation in [Fri96][1] and [KM + 08][2] Respectively. All in all:

\$ \ text {Definition:} \$ A \$ \ rm Galois field \$ \$ {\ rm GF} (q) \$ is a body (English:Field) with a limited number \$ (q) \$ of elements ⇒ finite body. Every body is a special case Rings (identical English name), which itself again as a special case of a Abelian group (English:Abelian Group) can be displayed.

Algebraic relationships between group, ring and body

The graphic shows step by step how the following subordinate quantities result from a set by defining addition, multiplication and division within this set \$ \ mathcal {M} \$:

• Abelian group \$ \ mathcal {G} \$ (English:Field ) ,
• Ring \$ \ mathcal {R} \$,
• Body \$ \ mathcal {K} \$ (English:Field \$ \ mathcal {F} \$),
• finite field \$ \ mathcal {F} _q \$ or Galois field \$ {\ rm GF} (q) \$.

The algebraic terms mentioned here are discussed in more detail on the next two pages.

• In order to understand the Reed – Solomon codes, however, this knowledge is not absolutely necessary.
• So you could jump straight to the chapter on extension bodies.

### Definition and examples of an algebraic group

For the general definitions of group (and later ring) we assume a set with an infinite number of 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 one additive link ("\$ + \$") defined between all elements, but only if the following properties are absolutely necessary:

• For all \$ z_i, z_j ∈ \ mathcal {G} \$, \$ (z_i + z_j) ∈ \ mathcal {G} \$ ⇒ Closure–Criterion for “\$ + \$”.
• There is always an element \$ N _ {\ rm A} ∈ \ mathcal {G} \$ that is neutral in terms of addition, so that for all \$ z_i ∈ \ mathcal {G} \$: \$ z_i + N _ {\ rm A} = z_i \$. For a group of numbers, \$ N _ {\ rm A} \ equiv 0 \$.
• For all \$ z_i ∈ \ mathcal {G} \$ there is also an inverse element with regard to the addition \$ {\ rm Inv_A} (z_i) ∈ \ mathcal {G} \$ with the property \$ z_i + {\ rm Inv_A} (z_i) = N _ {\ rm A} \$.
For a group of numbers, \$ {\ rm Inv_A} (z_i) = - z_i \$.
• For all \$ z_i, z_j, z_k ∈ \ mathcal {G} \$ the following applies: \$ z_i + (z_j + z_k) = (z_i + z_j) + z_k \$ ⇒ Associative law for “\$ + \$”.

If additionally for all \$ z_i, z_j ∈ \ mathcal {G} \$ the Commutative law \$ z_i + z_j = z_j + z_i \$ is fulfilled, one speaks of one commutative group or one Abelian group, named after the Norwegian mathematician 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, da
• for all \$ a ∈ \ mathcal {G} \$ and \$ b ∈ \ mathcal {G} \$ the sum \$ a + b \$ also belongs to \$ \ mathcal {G} \$ again,
• the associative law applies,
• with \$ N _ {\ rm A} = 0 \$ the neutral element of addition is contained in \$ \ mathcal {G} \$, and
• the additive inverse \$ {\ rm Inv_A} (a) = -a \$ exists for every \$ a \$.
Since the commutative law is also fulfilled, it is a Abelian group.

(2) The Set of natural numbers ⇒ \$ \ {0, 1, 2, \ text {...} \} \$ is not an algebraic group with regard to addition,

• since there is no additive inverse \$ {\ rm Inv_A} (z_i) = -z_i \$ for any single element \$ z_i \$.

(3) The limited natural number set ⇒ \$ \ {0, 1, 2, \ text {...} \ hspace {0.05cm}, q-1 \} \$ on the other hand then fulfills the conditions for a group \$ (\ mathcal {G}, +) \$,

• if one defines the addition modulo \$ q \$.

(4) In contrast, \$ \ {1, 2, 3, \ text {...} \ hspace {0.05cm}, q \} \$ is not a group, since the neutral element of the addition \$ (N _ {\ rm A} = 0) \$ is missing.

### Definition and examples of an algebraic ring

According to the overview graphic, one comes from the group \$ (\ mathcal {G}, +) \$ by defining a second arithmetic operation - the multiplication ("\$ \ cdot \$") - to the ring \$ (\ mathcal {R}, +, \ cdot ) \$. In addition to an addition table, you also need a multiplication 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 met:

• With regard to addition, the ring \$ (\ mathcal {R}, +, \ cdot) \$ is an Abelian group \$ (\ mathcal {G}, +) \$.
• In addition, for all \$ z_i, z_j ∈ \ mathcal {R} \$ also \$ (z_i \ cdot z_j) j \ mathcal {R} \$ ⇒ Closure–Criterion for “\$ \ cdot \$”.
• There is always an element \$ N _ {\ rm M} ∈ \ mathcal {R} \$ that is neutral with regard to the multiplication, so that for all \$ z_i ∈ \ mathcal {R} \$: \$ z_i \ cdot N _ {\ rm M} = z_i \$.
In a group of numbers, \$ N _ {\ rm M} = 1 \$.
• For all \$ z_i, z_j, z_k ∈ \ mathcal {R} \$ the following applies: \$ z_i + (z_j + z_k) = (z_i + z_j) + z_k \$ ⇒ Associative law for “\$ \ cdot \$”.
• For all \$ z_i, z_j, z_k ∈ \ mathcal {R} \$ the following applies: \$ z_i \ cdot (z_j + z_k) = z_i \ cdot z_j + z_i \ cdot z_k \$ ⇒ Distributive law for “\$ \ cdot \$”.

The following agreements should also apply:

• A ring \$ (\ mathcal {R}, +, \ cdot) \$ is not necessarily commutative. In fact, this also applies to all elements \$ z_i, z_j ∈ \ mathcal {R} \$ das Commutative law \$ z_i \ cdot z_j = z_j \ cdot z_i \$ with regard to the multiplication, this is what one speaks of a in the specialist literature commutative ring.
• If for each element \$ z_i ∈ \ mathcal {R} \$ with the exception of \$ N _ {\ rm A} \$ (neutral element of addition, zero element) there is an inverse element \$ {\ rm Inv_M} (z_i) \$ with regard to multiplication, see above that \$ z_i \ cdot {\ rm Inv_M} (z_i) = 1 \$ applies, then a Division ring (English: Division ring) in front.
• The ring is zero divider free (English: free of zero devisors), if \$ z_i \ cdot z_j = 0 \$ necessarily follows \$ z_i = 0 \$ or \$ z_j = 0 \$. In abstract algebra, a zero divisor of a ring is an element \$ z_i \$ that is different from the zero element if there is an element \$ z_j \ ne 0 \$ such that the product \$ z_i \ cdot z_j = 0 \$.
• A commutative zero-divisor ring is called a Integrity ring orHealth scope (English:Integral Domain) designated.

\$ \ text {Conclusion:} \$

If one compares the definitions of group, ring (see above), body and Galois field, one recognizes that a Galois field \$ {\ rm GF} (q) \$

• a finite bodyField ) with \$ q \$ elements,
• at the same time as Commutative Division Ring can be understood, and also
• an integrity area Integral Domain ) describes.

### Exercises for the chapter

Exercise 2.1: group, ring, body

Exercise 2.1Z: Which tables describe groups?

Exercise 2.2: Properties of Galois fields

Exercise 2.2Z: Galois field GF (5)

### Bibliography

1. ^ Friedrichs, B .: Channel Coding - Basics and Applications in Modern Communication Systems. Berlin - Heidelberg: Springer, 1996.
2. ↑ Kötter, R .; Mayer, T .; Tüchler, M .; Schreckbach, F .; Brauchle, J .: Channel coding. Lecture manuscript, Chair of Telecommunications, Technical University of Munich, 2008.