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

From LNTwww

$\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)$  gilt, also 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)$  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:



Fragebogen

1

Wie lautet der binäre Informationsblock im ersten Codierschritt?

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

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, \hspace{0.05cm} \text{...} \hspace{0.1cm} ,\ 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?

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

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


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 Lösungen zu 5 und 6 sind genau vertauscht.


(5)  Richtig ist der erste Lösungsvorschlag:

  • Dieser 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 auch 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.