Quelltext der Seite Aufgaben:Aufgabe 2.11: RS–Decodierung nach „Erasures”

{{quiz-Header|Buchseite=Kanalcodierung/Reed–Solomon–Decodierung beim Auslöschungskanal}}

[[Datei:P_ID2542__KC_A_2_11_neu.png|right|frame|${\rm GF}(2^3)$, dargestellt als  Potenzen, Polynome und Koeffizientenvektoren]]
Wir betrachten hier ein Codier&ndash; und Decodiersystem entsprechend der&nbsp; [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung| "Grafik im Theorieteil zu diesem Kapitel"]].&nbsp; Anzumerken ist:
* Der Reed&ndash;Solomon&ndash;Code ist durch die Generatormatrix&nbsp; $\mathbf{G}$&nbsp; und die Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; vorgegeben,&nbsp; wobei alle Elemente aus dem Galoisfeld &nbsp; $\rm GF(2^3) \ \backslash \ \{0\}$ &nbsp; 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 &nbsp; $c_i &#8712; \{0, \, 1, \, \alpha, \, \alpha^2, \, \alpha^3, \, \alpha^4, \, \alpha^5, \, \alpha^6\}$ &nbsp; werden durch&nbsp; $m = 3$&nbsp; Bit  dargestellt und über den Auslöschungskanal&nbsp; $(m \rm &ndash;BEC)$&nbsp; übertragen.&nbsp; Ein Codesymbol wird bereits dann als Auslöschung&nbsp; $\rm E$&nbsp; markiert, wenn eines der drei Bit unsicher ist.

* Der&nbsp; "Codewortfinder"&nbsp; $\rm (CWF)$&nbsp; hat die Aufgabe,&nbsp; aus dem teilweise ausgelöschten Empfangswort&nbsp; $\underline{y}$&nbsp; das regenerierte Codewort &nbsp; $\underline{z}$ &nbsp; zu erzeugen.&nbsp; Dabei muss sichergestellt sein,&nbsp; dass das Ergebnis &nbsp; $\underline{z}$ &nbsp; tatsächlich ein gültiges Reed&ndash;Solomon&ndash;Codewort ist.
 
* Beinhaltet das Empfangswort &nbsp; $\underline{y}$ &nbsp; zu viele Auslöschungen,&nbsp; so gibt der Decoder eine Meldung der Art&nbsp; &bdquo;Symbol ist nicht decodierbar&rdquo;&nbsp; aus. &nbsp;Es wird also nicht versucht,&nbsp; das Codewort zu schätzen.&nbsp; Wird&nbsp; $\underline{z}$&nbsp; ausgegeben, so ist dieses auch richtig:&nbsp; $\underline{z} = \underline{c}$.

* Das gesuchte Informationswert&nbsp; $\underline{v} = \underline{u}$&nbsp; ergibt sich durch die inverse Coderfunktion&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$.&nbsp; Mit der Generatormatrix &nbsp; $\mathbf{G}$ &nbsp; 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&nbsp; [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal| "Reed&ndash;Solomon&ndash;Decodierung beim Auslöschungskanal"]].

* Hinsichtlich des Codewortfinders verweisen wir insbesondere auf die Seiten&nbsp; 
:*[[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Vorgehensweise_am_Beispiel_des_RSC_.287.2C_3.2C_5.298|"Vorgehensweise ..."]]&nbsp; und&nbsp; 
:*[[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal#L.C3.B6sung_der_Matrixgleichungen_am_Beispiel_des_RSC_.287.2C_3.2C_5.298| "Lösung der Matrixgleichungen"]].

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



===Fragebogen===
<quiz display=simple>
{Geben Sie die Codeparameter des vorliegenden Reed&ndash;Solomon&ndash;Codes an.
|type="{}"}
$n \ = \ ${ 7 }
$k \ = \ ${ 4 }
$d_{\rm min} \ = \ ${ 4 }

{Kann der Empfangsvektor &nbsp; $\underline{y} = (0, \, 0, \, 0,\, 0, \, 0, \, 0, \, {\rm E})$ &nbsp; decodiert werden?
|type="()"}
+ JA.
- NEIN.

{Kann der Empfangsvektor &nbsp; $\underline{y} = (\rm E, \, E, \, 1, \, 1, \, 1, \, 1, \, 1)$ &nbsp; decodiert werden?
|type="()"}
+ JA.
- NEIN.

{Welches Ergebnis liefert die Decodierung von &nbsp; $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, 0)$?
|type="()"}
- $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.

{Welches Ergebnis liefert die Decodierung von &nbsp; $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, E)$?
|type="()"}
- $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.
</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; 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&ndash;Solomon&ndash;Codes gilt nämlich $n = q - 1$. 
*Die Zeilenanzahl der Prüfmatrix ist gleich $n - k = 3 \ \Rightarrow \ k \ \underline{= 4}$. 
*Von allen Reed&ndash;Solomon&ndash;Codes wird die [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Singleton.E2.80.93Schranke_und_minimale_Distanz| Singleton&ndash;Schranke]] erfüllt &nbsp; &#8658; &nbsp; $d_{\rm min} = n - k + 1 \ \underline{= 4}$. 
*Es handelt sich also um den Reed&ndash;Solomon&ndash;Code $(7, \, 4, \, 4)_8$.



'''(2)'''&nbsp; 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 &nbsp;&#8658;&nbsp; <b><u>JA</u></b>. 
*Nachdem bei allen RS&ndash;Codes das Nullwort zulässig ist und jedes andere Codewort mindestens vier Symbole ungleich &bdquo;$0$&rdquo; 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)'''&nbsp; Auch hier ist&nbsp; $e = 2$&nbsp; kleiner als&nbsp; $d_{\rm min} = 4$ &nbsp; &#8658; &nbsp; <b><u>JA</u></b>. 
*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&ndash;$2$&ndash;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)'''&nbsp; 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&ndash;$2$&ndash;Summe der Zeilen 1 und 2 sowie die Zeile 3 durch die Modulo&ndash;$2$&ndash;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 <u>Lösungsvorschlag 2</u>.



'''(5)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 4</u>. &nbsp; Begründung:
* Aus den drei bekannten Symbolen $0, \, 1, \, \alpha$ kann man nicht vier Informationssymbole gewinnen.
* Die $\mathbf{H}$&ndash;Matrix dieses $(7, \, 4, \, 4)_8$&ndash;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$.
{{ML-Fuß}}



[[Category:Aufgaben zu  Kanalcodierung|^2.4 RS–Decodierung bei Auslöschungen^]]