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.