Exercise 2.12: Decoding at RSC (7, 4, 4) to Base 8
Wir analysieren den Peterson–Algorithmus, der im Theorieteil zu Kapitel 2.5 ausführlich dargelegt ist. Vorausgesetzt wird der Reed–Solomon–Code mit den Parametern $n = 7, \ k = 4$ und $d_{\rm min} = 4$, wobei alle Codesymbole aus $\rm GF(2^3)$ stammen und alle Rechenoperationen in $\rm GF(2^3)$ durchzuführen sind.
Die Prüfmatrix dieses Codes lautet:
- $${ \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}.$$
Im Schritt (A) des hier betrachteten Decodier–Algorithmuses muss das Syndrom $\underline{s} = \underline{y} \cdot \mathbf{H}^{\rm T}$ berechnet werden. Für das hier vorausgesetzte Empfangswort $\underline{y} = (\alpha^1, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha, \, 0)$ ergibt sich das Syndrom zu $\underline{s} = (\alpha^4, \, \alpha^5, \, \alpha^6)$, wie in Aufgabe Z.12 noch gezeigt wird.
Danach müssen die ELP–Koeffizientenvektoren gemäß der nebenstehenden Abbildung aufgestellt und ausgewertet werden, wobei die Belegung davon abhängt, ob man von $r = 1, \ r = 2$ oder $r = 3$ Symbolfehlern im Empfangswort ausgeht.
Sind für die angenommene Symbolfehlerzahl $r$ alle Gleichungen ${\it \underline{\Lambda}}_l \cdot \underline{s}^{\rm T} = 0$ erfüllt, so weist das Empfangswort $\underline{y}$ tatsächlich genau $r$ Symbolfehler auf.
Die weiteren Schritte können Sie dem Theorieteil entnehmen:
- Schritt (C): Lokalisierung der Fehlerpositionen,
- Schritt (D): Ermittlung der Fehlerwerte.
Hinweise:
- Die Aufgabe bezieht sich auf das Kapitel Fehlerkorrektur nach Reed–Solomon–Codierung.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
(2) Entsprechend der Grafik auf der Angabenseite besitzt der Vektor ${\it \underline{\Lambda}}_l$ hier $L = n - k \ \underline{= 3}$ Elemente.
(3) Es gibt nur die beiden ELP–Koeffizientenvektoren ${\it \underline{\Lambda}}_1 = (\lambda_0, \, 1, \, 0)$ und ${\it \underline{\Lambda}}_2 = (0, \, \lambda_0, \, 1) \ \Rightarrow \ l_{\rm max} \ \underline{= 2}$.
(4) Aus ${\it \underline{\Lambda}}_1$ und ${\it \underline{\Lambda}}_2$ ergeben sich zwei skalare Bestimmungsgleichungen ${\it \underline{\Lambda}}_l \cdot \underline{s}^{\rm T} = 0$. für den Parameter $\lambda_0$:
- $$\lambda_0 \cdot \alpha^4 + \alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_0 \cdot \alpha^4 = -\alpha^5 = \alpha^5 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_0 = \alpha \hspace{0.05cm},$$
- $$\lambda_0 \cdot \alpha^5 + \alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_0 = \alpha \hspace{0.05cm}.$$
Das Gleichungssystem ist eindeutig lösbar ⇒ Antwort JA.
(5) Mit dem Ergebnis der Teilaufgabe (4) ⇒ $\lambda_0 = \alpha$ erhält man für das Error Locator Polynom
- $${\it \Lambda}(x)=x \cdot \big ({\it \lambda}_0 + x \big ) =x \cdot \big (\alpha + x )$$
- $$\Rightarrow \hspace{0.3cm} {\it \Lambda}(\alpha^0 )\hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 \cdot \big ( \alpha + 1 \big ) = \alpha + 1 \ne 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}{\rm Keine\hspace{0.15cm} Nullstelle}\hspace{0.05cm},$$
- $$\hspace{1cm} {\it \Lambda}(\alpha^1)\hspace{-0.15cm} \ = \ \hspace{-0.15cm}\alpha \cdot \big (\alpha + \alpha\big ) = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}{ \boldsymbol{\rm Nullstelle}}\hspace{0.05cm}.$$
Verfälscht wurde also das Symbol an der Position 1 ⇒ Lösungsvorschlag 2. Da die Berechnung in der Teilaufgabe (4) unter der Bedingung $r = 1$ erfolgte, wurden alle anderen Symbole richtig übertragen:
- $$\underline {e} = (0, e_1, 0, 0, 0, 0, 0)\hspace{0.05cm}. $$
- $$(0, e_1, 0, 0, 0, 0, 0) \cdot \begin{pmatrix} 1 & 1 & 1 \\ \alpha^1 & \alpha^2 & \alpha^3 \\ \alpha^2 & \alpha^4 & \alpha^6 \\ \alpha^3 & \alpha^6 & \alpha^9 \\ \alpha^4 & \alpha^8 & \alpha^{12} \\ \alpha^5 & \alpha^{10} & \alpha^{15} \\ \alpha^6 & \alpha^{12} & \alpha^{18} \end{pmatrix} \hspace{0.15cm}\stackrel{!}{=} \hspace{0.15cm} \begin{pmatrix} \alpha^4\\ \alpha^5\\ \alpha^6 \end{pmatrix} $$
- $$\Rightarrow \hspace{0.3cm} e_1 \cdot \alpha = \alpha^4\hspace{0.05cm},\hspace{0.4cm} e_1 \cdot \alpha^2 = \alpha^5\hspace{0.05cm},\hspace{0.4cm} e_1 \cdot \alpha^3 = \alpha^6\hspace{0.05cm}. $$
Die Lösung führt stets zum Ergebnis $e_1 = \alpha^3$ ⇒ Antwort 2. Mit dem Empfangswort $\underline{y} = (\alpha^1, \, 0, \, \alpha^3, \, 0, \, 1, \, \alpha^1, \, 0)$ erhält man das Decodierergebnis $\underline{z} = (\alpha^1, \, \alpha^3, \, \alpha^3, \, 0, \, 1, \, \alpha^1, \, 0)$.
(7) Analog zur Teilaufgabe (4) lautet nun das Gleichungssystem:
- $$\lambda_0 \cdot \alpha^2 + \alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_0 = \alpha^2 \hspace{0.05cm},$$
- $$\lambda_0 \cdot \alpha^4 + \alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_0 = \alpha \hspace{0.05cm}.$$
Die beiden Lösungen widersprechen sich. Bei der Übertragung müssen also mindestens zwei Symbole verfälscht worden sein und die Decodierung versagt ⇒ Antwort NEIN. Man müsste nun einen neuen Versuch gemäß dem roten Schema $(r = 2)$ starten.