Exercise 2.12Z: Reed-Solomon Syndrome Calculation

Umrechnungstabellen für das Galoisfeld $\rm GF(2^3)$

Wie in der Aufgabe 2.12 betrachten wir den Reed–Solomon–Code $(7, \, 4, \, 4)_8$, der auf dem Galoisfeld ${\rm GF}(q)$ mit $q = 8 = 2^3$ basiert. Die Grafik zeigt die zugehörige Umrechnungstabelle.

Gegeben sind die möglichen Codesymbole in Exponentendarstellung (Potenzen von $\alpha$) sowie in Polynom– und Koeffizientenvektordarstellung.

Vorgegeben ist das Empfangswort $\underline{y} = (\alpha, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$. Anhand des Syndroms

$$\underline {s} = (s_0, s_1, s_2) = \underline {y} \cdot { \boldsymbol{\rm H }}^{\rm T}$$

soll überprüft werden, ob einzelne Symbole des Empfangsvektors $\underline{y}$ bei der Übertragung verfälscht wurden. Gegeben ist hierzu die Prüfmatrix $\mathbf{H}$ des betrachteten Codes und deren Transponierte:

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 & \alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ 1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4} \end{pmatrix} \hspace{0.05cm},\hspace{0.4cm} { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 & 1 & 1 \\ \alpha^1 & \alpha^2 & \alpha^3 \\ \alpha^2 & \alpha^4 & \alpha^6 \\ \alpha^3 & \alpha^6 & \alpha^2 \\ \alpha^4 & \alpha^1 & \alpha^{5} \\ \alpha^5 & \alpha^{3} & \alpha^{1} \\ \alpha^6 & \alpha^{5} & \alpha^{4} \end{pmatrix} \hspace{0.05cm}.$$

Hinweise:

Die Aufgabe bezieht auf die Seite Schritt (A): Auswertung des Syndroms beim BDD des Kapitels „Fehlercodierung nach Reed–Solomon–Codierung”.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

Umrechnungstabellen für das Galoisfeld $\rm GF(2^3)$

(1) Die entsprechende Gleichung zur Syndromberechnung lautet:

$$\underline {s} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (s_0, s_1, s_2) = \begin{pmatrix} \alpha,0, \alpha^3,0, 1, \alpha,0 \end{pmatrix}\cdot \begin{pmatrix} 1 & 1 & 1 \\ \alpha^1 & \alpha^2 & \alpha^3 \\ \alpha^2 & \alpha^4 & \alpha^6 \\ \alpha^3 & \alpha^6 & \alpha^2 \\ \alpha^4 & \alpha^1 & \alpha^{5} \\ \alpha^5 & \alpha^{3} & \alpha^{1} \\ \alpha^6 & \alpha^{5} & \alpha^{4} \end{pmatrix} \hspace{0.05cm}.$$

Das erste Element ergibt sich zu

$$s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^2 + 1 \cdot \alpha^4 + \alpha \cdot \alpha^5= \alpha + \alpha^5 + \alpha^4+ \alpha^6$$

$$\Rightarrow\hspace{0.3cm} s_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (\alpha) + (\alpha^2 + \alpha+ 1)+ (\alpha^2 + \alpha) + + (\alpha^2 + 1) = \alpha^2 + \alpha = \alpha^4\hspace{0.05cm}.$$

Richtig ist der Lösungsvorschlag 1.

(2) Entsprechend gilt für das zweite Syndromelement entsprechend dem der Lösungsvorschlag 2:

$$s_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^4 + 1 \cdot \alpha^1 + \alpha \cdot \alpha^3= \alpha + \alpha^7 + \alpha+ \alpha^4= 1 + \alpha^4 = \alpha^2 + \alpha + 1 = \alpha^5 \hspace{0.05cm}.$$

(3) Zur Berechnung von $s_2$ muss mit der letzten Matrixspalte multipliziert werden:

$$s_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot 1 + \alpha^3 \cdot \alpha^6 + 1 \cdot \alpha^5 + \alpha \cdot \alpha^1= \alpha + \alpha^2 + \alpha^5 + \alpha^2=\alpha^5 + \alpha = (\alpha^2 + \alpha + 1) + \alpha = \alpha^2 + 1 = \alpha^5 \hspace{0.05cm}.$$

Richtig ist der Lösungsvorschlag 3.

(4) Aufgrund des errechneten Syndroms $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6) ≠ 0$ beinhaltet das Empfangswort mindestens einen Symbolfehler ⇒ $r > 0$. Da der vorliegende Reed–Solomon–Code $(7, \, 4, \, 4)_8 \ \Rightarrow \ d_{\rm min} = 4$ auch nicht mehr als $t = ⌊d_{\rm min}/2⌋ = 1$ Fehler korrigieren kann und das Empfangswort gemäß der Angabe tatsächlich decodiert werden kann, gilt $\underline{r = 1}$.

	$s_0 = \alpha^4$,
	$s_0 = \alpha^5$,
	$s_0 = \alpha^6$,
	$s_0 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.

	$s_1 = \alpha^4$,
	$s_1 = \alpha^5$,
	$s_1 = \alpha^6$,
	$s_1 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.

	$s_2 = \alpha^4$,
	$s_2 = \alpha^5$,
	$s_2 = \alpha^6$,
	$s_2 = 0, \, 1, \, \alpha, \, \alpha^2$ oder $\alpha^3$.