Aufgaben:Aufgabe 2.11: RS–Decodierung nach „Erasures”

• Zurück zum Buch

${\rm GF}(2^3)$, dargestellt als Potenzen, Polynome und Koeffizientenvektoren

Wir betrachten hier ein Codier– und Decodiersystem entsprechend der  "Grafik im Theorieteil zu diesem Kapitel".  Anzumerken ist:

• Der Reed–Solomon–Code ist durch die Generatormatrix  $\mathbf{G}$  und die Prüfmatrix  $\mathbf{H}$  vorgegeben,  wobei alle Elemente aus dem Galoisfeld   $\rm GF(2^3) \ \backslash \ \{0\}$   stammen:

$${ \boldsymbol{\rm G}} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 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},$$

$${ \boldsymbol{\rm H}} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \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}.$$

• Alle Codesymbole   $c_i ∈ \{0, \, 1, \, \alpha, \, \alpha^2, \, \alpha^3, \, \alpha^4, \, \alpha^5, \, \alpha^6\}$   werden durch  $m = 3$  Bit dargestellt und über den Auslöschungskanal  $(m \rm –BEC)$  übertragen.  Ein Codesymbol wird bereits dann als Auslöschung  $\rm E$  markiert, wenn eines der drei Bit unsicher ist.

• Der  "Codewortfinder"  $\rm (CWF)$  hat die Aufgabe,  aus dem teilweise ausgelöschten Empfangswort  $\underline{y}$  das regenerierte Codewort   $\underline{z}$   zu erzeugen.  Dabei muss sichergestellt sein,  dass das Ergebnis   $\underline{z}$   tatsächlich ein gültiges Reed–Solomon–Codewort ist.

• Beinhaltet das Empfangswort   $\underline{y}$   zu viele Auslöschungen,  so gibt der Decoder eine Meldung der Art  „Symbol ist nicht decodierbar”  aus.  Es wird also nicht versucht,  das Codewort zu schätzen.  Wird  $\underline{z}$  ausgegeben, so ist dieses auch richtig:  $\underline{z} = \underline{c}$.

• Das gesuchte Informationswert  $\underline{v} = \underline{u}$  ergibt sich durch die inverse Coderfunktion  $\underline{v} = {\rm enc}^{-1}(\underline{z})$.  Mit der Generatormatrix   $\mathbf{G}$   lässt sich diese wie folgt realisieren:

$$\underline{c} = {\rm enc}(\underline{u}) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \underline{u} \cdot {\boldsymbol{\rm G}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{z} = {\rm enc}(\underline{v})= \underline{v} \cdot {\boldsymbol{\rm G}} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{v} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm enc}^{-1}(\underline{z}) = \underline{z} \cdot {\boldsymbol{\rm G}}^{\rm T}\hspace{0.05cm}.$$

Hinweise:

• Die Aufgabe bezieht sich auf das Kapitel  "Reed–Solomon–Decodierung beim Auslöschungskanal".

• Hinsichtlich des Codewortfinders verweisen wir insbesondere auf die Seiten 

• "Vorgehensweise ..."  und 
• "Lösung der Matrixgleichungen".

• Alle Berechnungen sind in  $\rm GF(2^3)$  durchzuführen.  Die obere Grafik beschreibt deren  $q = 8$  Elemente in Potenz–, Polynom– und Koeffizientenvektordarstellung.

Fragebogen

1 Geben Sie die Codeparameter des vorliegenden Reed–Solomon–Codes an.

$n \ = \ $

$k \ = \ $

$d_{\rm min} \ = \ $

2 Kann der Empfangsvektor   $\underline{y} = (0, \, 0, \, 0,\, 0, \, 0, \, 0, \, {\rm E})$   decodiert werden?

	JA.
	NEIN.

3 Kann der Empfangsvektor   $\underline{y} = (\rm E, \, E, \, 1, \, 1, \, 1, \, 1, \, 1)$   decodiert werden?

	JA.
	NEIN.

4 Welches Ergebnis liefert die Decodierung von   $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, 0)$?

	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = 0$.
	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = \alpha^3$.
	$z_0 = 1, \ z_1 = 0, \ z_2 = \alpha^3$.
	Die Decodierung führt zu keinem Ergebnis.

5 Welches Ergebnis liefert die Decodierung von   $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, E)$?

	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = 0, \ z_6 = 1$.
	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = \alpha^3, \ z_6 = 1$.
	$z_0 = 1, \ z_1 = 0, \ z_2 = \alpha^3, \ z_6 = 1$.
	Die Decodierung führt zu keinem Ergebnis.

Musterlösung

Musterlösung

(1)  Die Spaltenanzahl der Prüfmatrix  $\mathbf{H}$  gibt die Codelänge an:   $n \ \underline{= 7}$.

• Zum gleichen Ergebnis kommt man,  wenn man von der Ordnung  $q = 8$  des Galoisfeldes ausgeht.  Bei den Reed–Solomon–Codes gilt nämlich  $n = q - 1$.

• Die Zeilenanzahl der Prüfmatrix ist gleich  $n - k = 3 \ \Rightarrow \ k \ \underline{= 4}$.

• Von allen Reed–Solomon–Codes wird die  "Singleton–Schranke"  erfüllt   ⇒   $d_{\rm min} = n - k + 1 \ \underline{= 4}$.

• Es handelt sich also um den Reed–Solomon–Code  $(7, \, 4, \, 4)_8$.

(2)  Eine Decodierung ist sicher möglich,  so lange die Anzahl  $e$  der Auslöschungen kleiner ist als die Minimaldistanz  $d_{\rm min}$.  Diese Bedingung ist hier erfüllt   ⇒   JA.

• Nachdem bei allen RS–Codes das Nullwort zulässig ist und jedes andere Codewort mindestens vier Symbole ungleich „$0$” beinhaltet,  ist bereits ohne Rechnung sicher,  dass das Nullwort gesendet wurde.

• Die formale Rechnung bestätigt dieses Ergebnis:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} =\begin{pmatrix} 0\\ 0\\ 0\end{pmatrix} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \begin{pmatrix} \alpha^6\\ \alpha^{5}\\ \alpha^{4}\end{pmatrix} \cdot z_6 = \begin{pmatrix} 0\\ 0\\ 0\end{pmatrix} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} z_6 = 0\hspace{0.05cm}. $$

(3)  Auch hier ist  $e = 2$  kleiner als  $d_{\rm min} = 4$   ⇒   JA.

• Da auch  $(1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$  ein gültiges Codewort ist,  erwarten wir bei der formalen Überprüfung  $z_0 = 1$  und  $z_1 = 1$.

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}\begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4}\end{pmatrix} \cdot\begin{pmatrix} 1\\ 1\\ 1\\ 1\\ 1\end{pmatrix}=\begin{pmatrix} \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6\\ \alpha^4 + \alpha^6 + \alpha^1 + \alpha^{3} + \alpha^{5}\\ \alpha^6 + \alpha^2 + \alpha^{5} + \alpha^{1} + \alpha^{4} \end{pmatrix}$$

$$\Rightarrow \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \begin{pmatrix}(100) + (011) + (110) + (111) + (101)\\ (110) + (101) + (010) + (011) + (111)\\ (101) + (100) + (111) + (010) + (110) \end{pmatrix} =\begin{pmatrix} (011)\\ (101)\\ (010)\end{pmatrix} = \begin{pmatrix} \alpha^3\\ \alpha^6\\ \alpha^1\end{pmatrix}\hspace{0.05cm}. $$

• Bei dieser Berechnung wurde zwischen der Polynomdarstellung und der Koeffizientendarstellung auf der Angabenseite variiert.  Damit lautet das Gleichungssystem:

$$\begin{pmatrix}(001) + (010) \\(001) + (100)\\(001) + (011) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1\end{pmatrix} =\begin{pmatrix} (011)\\ (101)\\ (010)\end{pmatrix} \hspace{0.25cm} \Rightarrow \hspace{0.25cm} \begin{pmatrix}(001) + (010) \\(001) + (100)\\(000) + (111) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1\end{pmatrix} =\begin{pmatrix} (011)\\ (101)\\ (111)\end{pmatrix}\hspace{0.05cm}.$$

• Die zweite Form ergibt sich,  wenn man die dritte Zeile aus der Modulo–$2$–Summe der Zeilen 2 und 3 ersetzt.

• Aus der letzten Zeile folgt nun  $z_1 = 1$  und die Zeilen 1 und 2 lauten dann:

$$(1)\hspace{0.3cm}z_0 + (010) \cdot 1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (011)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}z_0 = (001) = 1\hspace{0.05cm},$$

$$(2)\hspace{0.3cm}z_0 + (100) \cdot 1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (101)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}z_0 = (001) = 1\hspace{0.05cm}. $$

• Beide Gleichungen führen zum gleichen Ergebnis  $z_0 = 1, \ z_1 = 1$.  Die Decodierung ist erfolgreich.

(4)  Die Decodierung passiert auf folgenden Schritten:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}\begin{pmatrix} \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4}\end{pmatrix} \cdot\begin{pmatrix} 0\\ 1\\ \alpha\\ 0\end{pmatrix}=\begin{pmatrix} \alpha^4 + \alpha^6\\ \alpha^1 + \alpha^{4}\\ \alpha^5 + \alpha^2 \end{pmatrix}=\begin{pmatrix}(110) + (101)\\(010) + (110)\\(111) + (100) \end{pmatrix} =\begin{pmatrix} (011)\\ (100)\\ (011)\end{pmatrix} \hspace{0.05cm},$$

$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}\begin{pmatrix} 1 & \alpha^1 & \alpha^2\\ 1 & \alpha^2 & \alpha^4\\ 1 & \alpha^3 & \alpha^6\end{pmatrix} \cdot\begin{pmatrix} z_0\\ z_1\\ z_2\end{pmatrix}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\begin{pmatrix}(001) &(010) &(100)\\(001) &(100) &(110)\\(001) &(011) &(101) \end{pmatrix} \cdot\begin{pmatrix} z_0\\ z_1\\ z_2\end{pmatrix}=\begin{pmatrix} (011)\\ (100)\\ (011)\end{pmatrix} \hspace{0.05cm}. $$

• Wir ersetzen nun die Zeile 2 durch die Modulo–2–Summe der Zeilen 1 und 2 sowie die Zeile 3 durch die Modulo–2–Summe der Zeilen 1 und 3:

$$\begin{pmatrix}(001) &(010) &(100)\\(000) &(110) &(010)\\(000) &(001) &(001) \end{pmatrix} \cdot\begin{pmatrix} z_0\\ z_1\\ z_2\end{pmatrix}=\begin{pmatrix} (011)\\ (111)\\ (000)\end{pmatrix} \hspace{0.05cm}.$$

• Aus der letzten Zeile folgt  $z_1 + z_2 = 0 \ \Rightarrow \ z_2 = z_1$.  Eingesetzt in die zweite Zeile dieser Matrixgleichung erhält man:

$$\big[(110) + (010)\big] \cdot z_1 = (100) \cdot z_1 = (111) \hspace{0.2cm} \Rightarrow \hspace{0.2cm}\alpha^2 \cdot z_1 = \alpha^5\hspace{0.2cm}\Rightarrow \hspace{0.2cm}z_1 \hspace{0.1cm}\underline{= \alpha^3}\hspace{0.05cm},\hspace{0.2cm}z_2 \hspace{0.1cm}\underline{= \alpha^3} \hspace{0.05cm}. $$

• Mit diesem Ergebnis folgt aus der ersten Matrixzeile:

$$z_0 + \big[(010) + (100)\big] \cdot z_1 = z_0 + (110) \cdot z_1 = (011) $$

$$\Rightarrow \hspace{0.2cm} z_0 + \alpha^4 \cdot \alpha^3 = z_0 + 1 = \alpha^3 \hspace{0.2cm} \Rightarrow \hspace{0.2cm}z_0 = \alpha^3 + 1 = ( \alpha + 1) +1\hspace{0.15cm} \underline{= \alpha}\hspace{0.05cm}.$$

• Richtig ist demnach der  Lösungsvorschlag 2.

(5)  Richtig ist der Lösungsvorschlag 4.   Begründung:

• Aus den drei bekannten Symbolen  $0, \, 1, \, \alpha$  kann man nicht vier Informationssymbole gewinnen.

• Die  $\mathbf{H}$–Matrix dieses  $(7, \, 4, \, 4)_8$–Codes hat genau  $n - k = 3$  Zeilen.

• Man hat damit auch nur drei Gleichungen.  Benötigen würde man aber vier Gleichungen für die Unbekannten  $z_0, \ z_1, \ z_2$  und  $z_6$.