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

• Return to book

$\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 Definition und Eigenschaften von Reed–Solomon–Codes.
• 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

Wie lautet der binäre Informationsblock im ersten Codierschritt?

	$\underline{u}_{\rm bin} = (110)$,
	$\underline{u}_{\rm bin} = (110001011)$,
	$\underline{u}_{\rm bin} = (1100010)$.

2

Wie lauten die Informationssymbole im ersten Codierschritt?

	$u_0 = \alpha^4$,
	$u_0 = 0$,
	$u_1 = \alpha^6$,
	$u_1 = \alpha^0$,
	$u_2 = \alpha^3$,
	$u_2 = \alpha^2$.

3

Wie lautet der Informationsblock als Polynom $u(x)$?

	$u(x) = \alpha^3 \cdot x + x^2 + \alpha^4 \cdot x^3$,
	$u(x) = \alpha^3 + x + \alpha^4 \cdot x^2$,
	$u(x) = \alpha^4 + x + \alpha^3 \cdot x^2$.

4

Wie lauten die Codesymbole $c_0, \ ... \ , \ c_6$ für den ersten Codierschritt.

	$c_0 = \alpha^2$,
	$c_1 = \alpha^3$,
	$c_2 = \alpha^3$,
	$c_3 = 1$,
	$c_4 = \alpha^2$,
	$c_5 = \alpha^4$,
	$c_6 = 1$.

5

Wie lautet das binäre Codewort? Genau ein Vorschlag ist richtig.

	$\underline{c}_{\rm bin} = 100_|011_|011_|001_|110_|100_|001$,
	$\underline{c}_{\rm bin} = 011_|011_|001_|110_|100_|001_|100$,
	$\underline{c}_{\rm bin} = 1001110$.

6

Welche Aussagen gelten für den zweiten Codierschritt?

	Es gilt $u_0 = u_1 = u_2 = 0$.
	Es gilt $u(x) = 1$.
	Das Codewort $\underline{c} ∈ \rm GF(2^3)$ besteht aus sieben Nullsymbolen.
	Das binäre Codewort besteht aus 21 Nullen.

Musterlösung

Solution

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