Exercise 2.07: Reed-Solomon Code (7, 3, 5) to Base 8

From LNTwww
Revision as of 23:30, 15 December 2017 by Hussain (talk | contribs)

$\rm GF(2^3)$ in Exponential–, Polynom– und Koeffizientendarstellung

Der hier betrachtete Reed–Solomon–Code mit der Bezeichnung $\rm RSC \, (7, \, 3, \, 5)_8$

  • codiert einen Informationsblock $\underline{u} = (u_0, \, u_1, \, u_2)$ von $k = 3$ Symbolen, wobei $u_0, \, u_1, \, u_2 ∈ \rm GF(2^3)$ gilt,
  • erzeugt ein Codewort $\underline{c} = (c_0, \, c_1, \, ... \, , \ , c_6)$ der Länge $n = 7$ mit Codesymbolen $c_i$ ebenfalls aus $\rm GF(2^3)$,
  • besitzt die freie Distanz $d_{\rm min} = n - k + 1 = 5$, so dass bis zu $e = 4$ Symbolfehler erkannt und bis zu $t = 2$ Symbolfehler korrigiert werden können.


Die Elemente des zugrunde liegenden Galoisfeldes lauten:

$${\rm GF}(2^3) = \{\hspace{0.1cm} 0\hspace{0.05cm},\hspace{0.1cm} 1 \hspace{0.05cm},\hspace{0.1cm} \alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm},\hspace{0.1cm} \alpha^{3} \hspace{0.05cm},\hspace{0.1cm} \alpha^{4} \hspace{0.05cm},\hspace{0.1cm} \alpha^{5} \hspace{0.05cm},\hspace{0.1cm} \alpha^{6} \hspace{0.1cm}\}\hspace{0.05cm}. $$

Diese Elemente lassen sich entsprechend der Grafik auch als Polynome oder als Koeffizientenvektoren darstellen. Man erkennt aus obiger Tabelle, dass alle $u_i ∈ \rm GF(2^3)$ und alle $c_i ∈ \rm GF(2^3)$ auch durch $m = 3 \ \rm Bit$ charakterisiert werden können, zum Beispiel $\alpha^4$ durch „$110$”. Sie sollen in dieser Aufgabe für die binäre Eingangsfolge

$$110 \hspace{0.09cm}001\hspace{0.09cm} 011\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 111 \, ... $$

den Codiervorgang nachvollziehen. Beachten Sie dabei:

  • Der Reed–Solomon–Coder arbeitet blockweise. Im ersten Codierschritt werden aus den drei ersten Informationssymbolen die Codesymbole $c_0, \ ... \, c_6$ erzeugt, im zweiten Schritt dann aus dem Informationsblock $\underline{u} = (u_3, \, u_4, \, u_5)$ die Symbole $(c_7, \ ... \ , \ c_{13})$ des zweiten Codewortes, usw.
  • Man beschreibt den Informationsblock $\underline{u}$ durch das Polynom $u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2$ vom Grad 2. Allgemein ergibt sich für das Galoisfeld $\rm GF(2^m)$ der Grad des Polynoms zu $m - 1$.
  • Die Codesymbole $c_0, \ ... \ , \ c_6$ erhält man, indem in das Polynom $u(x)$ für $x$ alle Elemente von $\rm GF(2^3)$ mit Ausnahme des Nullelementes eingesetzt werden:
$${\rm GF}(2^3)\hspace{-0.01cm}\setminus \hspace{-0.01cm}\{ 0\} = \{\hspace{0.1cm}\alpha^{0}\hspace{0.05cm},\hspace{0.1cm} \alpha^1\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm},\hspace{0.1cm} \alpha^{3} \hspace{0.05cm},\hspace{0.1cm} \alpha^{4} \hspace{0.05cm},\hspace{0.1cm} \alpha^{5} \hspace{0.05cm},\hspace{0.1cm} \alpha^{6} \hspace{0.1cm}\}\hspace{0.05cm}. $$

Formal lässt sich der $\rm RSC \, (7, \, 3, \, 5)_8$ wie folgt beschreiben:

$$C_{\rm RS} = \Big \{ \underline {c} = \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}u(\alpha^{2})\hspace{0.1cm} \big ) \hspace{0.1cm} \big | \hspace{0.2cm} u(x) = \sum_{i = 0}^{2} u_i \cdot x^{i}\hspace{0.05cm},\hspace{0.2cm} u_i \in {\rm GF}(2^3) \Big \} \hspace{0.05cm}.$$

Hinweise:

  • Die vorliegende Aufgabe behandelt die Thematik des Kapitels ....
  • Die Aufgabe A2.8 ist ähnlich strukturiert wie diese. Zur Generierung eines Codewortes $\underline{c}$ soll dann aber die Generatormatrix $\mathbf{G}$ herangezogen werden.


Fragebogen

1

Multiple-Choice

correct
false

2

Input-Box Frage

$xyz \ = \ $

$ab$


Musterlösung

(1)  (2)  (3)  (4)  (5)