Aufgabe 2.07: Reed–Solomon–Code (7, 3, 5) zur Basis 8

$\rm GF(2^3)$–Darstellung als Potenzen, Polynome, Vektoren

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)$ keine Bits, sondern Symbole darstellen;

erzeugt ein Codewort $\underline{c} = (c_0, \, c_1,\hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6)$ der Länge $n = 7$ mit Codesymbolen $c_i$ ebenfalls aus dem Galoisfeld $\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 \hspace{0.05cm} \text{...} $$

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, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$ erzeugt, im zweiten Schritt dann aus dem Informationsblock $\underline{u} = (u_3, \, u_4, \, u_5)$ die Symbole $(c_7, \hspace{0.05cm} \text{...} \hspace{0.1cm} , 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, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$ erhält man, indem in das Polynom $u(x)$ alle Elemente $x$ 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 gehört zum Kapitel "Definition und Eigenschaften von Reed–Solomon–Codes".

Die "Aufgabe 2.8" ist ähnlich strukturiert wie diese, aber zur Generierung eines Codewortes $\underline{c}$ wird dann die Generatormatrix $\mathbf{G}$ herangezogen.

Fragebogen

Musterlösung

(1) Richtig ist der Lösungsvorschlag 2:

Alle Informationssymbole entstammen hier dem Galoisfeld $\rm GF(2^3)$. In Binärschreibweise wird jedes Symbol durch drei Bit dargestellt.

Aufgrund des RS–Codeparameters $k = 3$ besteht ein Informationsblock aus drei Informationssymbolen: $\underline{u} = (u_0, \, u_1, \, u_2)$.

Dementsprechend beinhaltet der binäre Informationsblock $\underline{u}_{\rm bin}$ genau $3 \cdot 3 = 9$ Bit.

(2) Entsprechend der Tabelle auf der Angabenseite besteht folgender Zusammenhang zwischen dem Koeffizientenvektor und der Exponentialdarstellung:

$$(110) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_0 = \alpha^{4}\hspace{0.05cm},\hspace{0.6cm} (001) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_1 = \alpha^{0} = 1\hspace{0.05cm},\hspace{0.6cm} (011) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_2 = \alpha^{3}\hspace{0.05cm}. $$

Richtig sind also die Lösungsvorschläge 1, 4 und 5.

Der Informationsblock im ersten Codierschritt lautet: $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$.

(3) In Polynomdarstellung ergibt sich für den Informationsblock $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$:

$$u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2 = \alpha^{4} + x + \alpha^{3}\cdot x^2 \hspace{0.05cm}. $$

Richtig ist demnach der Lösungsvorschlag 3.

Der erste Lösungsvorschlag kann schon allein deshalb nicht stimmen, da der Polynomgrad höchstens $2$ sein kann, wenn alle Informations– und Codesymbole aus $\rm GF(2^3)$ entstammen.

(4) Für die Codesymbole erhält man mit der Polynomdarstellung entsprechend der Angabenseite:

$$c_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{0} = 1) = \alpha^{4} + 1 + \alpha^{3}\cdot 1^2 = (110) + (001) + (011)= (100) = \alpha^{2} \hspace{0.05cm},$$

$$c_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{1}) = \alpha^{4} + \alpha + \alpha^{5}= (110) + (010) + (111) = (011) = \alpha^{3} \hspace{0.05cm},$$

$$c_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{2}) = \alpha^{4} + \alpha^{2} + \alpha^{7}= (110) + (100) + (001) = (011) = \alpha^{3} \hspace{0.05cm},$$

$$c_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{3}) = \alpha^{4} + \alpha^{3} + \alpha^{9}= (110) + (011) + (100) = (001) = 1 \hspace{0.05cm},$$

$$c_4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{4}) = \alpha^{4} + \alpha^{4} + \alpha^{11} = \alpha^{4} \hspace{0.05cm},$$

$$c_5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{5}) = \alpha^{4} + \alpha^{5} + \alpha^{13}= (110) + (111) + (101) = (100) = \alpha^{2} \hspace{0.05cm},$$

$$c_6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{6}) = \alpha^{4} + \alpha^{6} + \alpha^{15}= (\alpha^{2} + \alpha) + (\alpha^2 +1) + \alpha = 1 \hspace{0.05cm}.$$

Richtig sind also die Lösungsvorschläge 1, 2, 3, 4, 7.

Die angegebenen Lösungen zu 5 und 6 sind genau vertauscht.

(5) Richtig ist der erste Lösungsvorschlag:

Es ergibt sich aus dem Ergebnis der Teilaufgabe (4) und der Zuordnung

$$\alpha^2 ↔ 100, \ \alpha^3 ↔ 011, \ \alpha^3 ↔ 011, \ 1 ↔ 001, \ \alpha^4 ↔ 110, \ \alpha^2 ↔ 100, \ 1 ↔ 001. $$

Der letzte Lösungsvorschlag kann schon allein deshalb nicht stimmen, da das binäre Codewort aus $n \cdot m = 7 \cdot 3 = 21$ Bit bestehen muss.

Selbst wenn Sie in der Teilaufgabe (4) nur das Ergebnis $c_0 = \alpha^2$ ermittelt haben, so wissen Sie schon, dass hier der Vorschlag 2 nicht der richtige sein kann.

(6) Die Aussagen 1, 3, 4 sind richtig:

Die Bit 10, ... , 18 der Eingangssequenz sind alle $0$ und damit auch die Informationssymbole $u_0, \ u_1, \ u_2 ∈ \rm GF(2^3)$.

Dementsprechend ist auch $u(x) = 0$, so dass alle Codesymbole $c_i = u(x = \alpha^i)$ dem Nullsymbol entsprechen $($Index: $0 ≤ i ≤ 6)$.

Die binäre Codefolge besteht somit aus $n \cdot m = 21$ Nullen.

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

	$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$.

	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 $\underline{c}_{\rm bin} ∈ \rm GF(2)$ besteht aus 21 Nullen.

	$\underline{u}_{\rm bin} = (110)$,
	$\underline{u}_{\rm bin} = (110_\|001_\|011)$,
	$\underline{u}_{\rm bin} = (110_\|001_\|0)$.

	$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$.

	$\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} = 100_\|111_\|0$.