Aufgaben:Aufgabe 2.11: RS–Decodierung nach „Erasures”: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(28 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Reed–Solomon–Decodierung beim Auslöschungskanal}}
 
{{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)$ in Potenz–, Polynom– u. Koeffizientenvektordarstellung]]
+
[[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– und Decodiersystem entsprechend der [[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. Anzumerken ist:
+
Wir betrachten hier ein Codier– und Decodiersystem entsprechend der  [[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"]].  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:
+
* 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}  
 
:$${ \boldsymbol{\rm G}} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  
 
\begin{pmatrix}
 
\begin{pmatrix}
Zeile 18: Zeile 18:
 
\end{pmatrix} \hspace{0.05cm}.$$
 
\end{pmatrix} \hspace{0.05cm}.$$
  
* Alle Codesymbole $c_i &#8712; \{0, \, 1, \, \alpha, \, \alpha^2, \, \alpha^3, \, \alpha^4, \, \alpha^5, \, \alpha^6\}$ werden durch $m = 3 \ \rm Bit$ dargestellt und über den grün hinterlegten Auslöschungskanal ($m$&ndash;BEC) übertragen. Ein Codesymbol wird bereits dann als Auslöschung (<i>Erasure</i>) E markiert, wenn eines der drei zugehörigen Bit unsicher ist.
+
* 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 <i>Codewortfinder</i> (CWF) hat die Aufgabe, aus dem teilweise ausgelöschten Empfangswort $\underline{y}$ das regenerierte Codewort $\underline{z}$ zu erzeugen. Dabei muss sicher gestellt sein, dass das Ergebnis $\underline{z}$ tatsächlich ein gültiges Reed&ndash;Solomon&ndash;Codewort ist.  
+
 
* Beinhaltet das Empfangswort $\underline{y}$ zu viele Auslöschungen, so gibt der Decoder eine Meldung der Art &bdquo;Symbol ist nicht decodierbar&rdquo; aus. Es wird also nicht versucht, das Codewort zu schätzen. Wird $\underline{z}$ ausgegeben, so ist dieses auch richtig: $\underline{z} = \underline{c}$.
+
* 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.
* Das gesuchte Informationswert $\underline{\upsilon} = \underline{u}$ ergibt sich durch die inverse Coderfunktion $\underline{\upsilon} = {\rm enc}^{-1}(\underline{z})$. Mit der Generatormatrix $\mathbf{G}$ lässt sich diese wie folgt realisieren:
+
 +
* 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}}
 
:$$\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{\upsilon})
+
\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{z} = {\rm enc}(\underline{v})
= \underline{\upsilon} \cdot {\boldsymbol{\rm G}}$$
+
= \underline{v} \cdot {\boldsymbol{\rm G}} \hspace{0.3cm}
:$$\Rightarrow \hspace{0.3cm} \underline{\upsilon} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm enc}^{-1}(\underline{z}) = \underline{z} \cdot {\boldsymbol{\rm G}}^{\rm T}\hspace{0.05cm}.$$
+
\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"]].
  
''Hinweise:''
+
* Hinsichtlich des Codewortfinders verweisen wir insbesondere auf die Seiten&nbsp;
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal| Reed&ndash;Solomon&ndash;Decodierung beim Auslöschungskanal]].
+
:*[[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Vorgehensweise_am_Beispiel_des_RSC_.287.2C_3.2C_5.298|"Vorgehensweise ..."]]&nbsp; und&nbsp;
* Hinsichtlich des <i>Codewortfinders</i> verweisen wir insbesondere auf die Seiten [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal#Vorgehensweise_am_Beispiel_des_RSC_.287.2C_3.2C_5.298| Vorgehensweise]] und [[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]].
+
:*[[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 $\rm GF(2^3)$ durchzuführen. Die obere Grafik beschreibt deren $q = 8$ Elemente in Potenz&ndash; Polynom&ndash; und Koeffizientenvektordarstellung.
+
 
 +
* 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.
  
  
Zeile 36: Zeile 47:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice
+
{Geben Sie die Codeparameter des vorliegenden Reed&ndash;Solomon&ndash;Codes an.
|type="[]"}
+
|type="{}"}
+ correct
+
$n \ = \ ${ 7 }
- false
+
$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.
  
{Input-Box Frage
+
{Welches Ergebnis liefert die Decodierung von &nbsp; $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, 0)$?
|type="{}"}
+
|type="()"}
$xyz \ = \ ${ 5.4 3% } $ab$
+
- $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>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  
+
'''(1)'''&nbsp; Die Spaltenanzahl der Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; gibt die Codelänge an: &nbsp; $n \ \underline{= 7}$.
'''(2)'''&nbsp;  
+
*Zum gleichen Ergebnis kommt man,&nbsp; wenn man von der Ordnung&nbsp; $q = 8$&nbsp; des Galoisfeldes ausgeht.&nbsp; Bei den Reed&ndash;Solomon&ndash;Codes gilt nämlich&nbsp; $n = q - 1$.
'''(3)'''&nbsp;  
+
'''(4)'''&nbsp;  
+
*Die Zeilenanzahl der Prüfmatrix ist gleich&nbsp; $n - k = 3 \ \Rightarrow \ k \ \underline{= 4}$.
'''(5)'''&nbsp;  
+
 
 +
*Von allen Reed&ndash;Solomon&ndash;Codes wird die&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Singleton.E2.80.93Schranke_und_minimale_Distanz| "Singleton&ndash;Schranke"]]&nbsp; erfüllt &nbsp; &#8658; &nbsp; $d_{\rm min} = n - k + 1 \ \underline{= 4}$.
 +
 
 +
*Es handelt sich also um den Reed&ndash;Solomon&ndash;Code&nbsp; $(7, \, 4, \, 4)_8$.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Eine Decodierung ist sicher möglich,&nbsp; so lange die Anzahl&nbsp; $e$&nbsp; der Auslöschungen kleiner ist als die Minimaldistanz&nbsp; $d_{\rm min}$.&nbsp; 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,&nbsp; ist bereits ohne Rechnung sicher,&nbsp; 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&nbsp; $(1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$&nbsp; ein gültiges Codewort ist,&nbsp; erwarten wir bei der formalen Überprüfung&nbsp; $z_0 = 1$&nbsp; und&nbsp; $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.&nbsp; 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,&nbsp; wenn man die dritte Zeile aus der Modulo&ndash;$2$&ndash;Summe der Zeilen 2 und 3 ersetzt.
 +
 +
*Aus der letzten Zeile folgt nun&nbsp; $z_1 = 1$&nbsp; 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&nbsp; $z_0 = 1, \ z_1 = 1$.&nbsp; 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&nbsp; $z_1 + z_2 = 0 \ \Rightarrow \ z_2 = z_1$.&nbsp; 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&nbsp; <u>Lösungsvorschlag 2</u>.
 +
 
 +
 
 +
 
 +
'''(5)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 4</u>. &nbsp; Begründung:
 +
* Aus den drei bekannten Symbolen&nbsp; $0, \, 1, \, \alpha$&nbsp; kann man nicht vier Informationssymbole gewinnen.
 +
 
 +
* Die&nbsp; $\mathbf{H}$&ndash;Matrix dieses&nbsp; $(7, \, 4, \, 4)_8$&ndash;Codes hat genau&nbsp; $n - k = 3$&nbsp; Zeilen.
 +
 +
*Man hat damit auch nur drei Gleichungen.&nbsp; Benötigen würde man aber vier Gleichungen für die Unbekannten&nbsp; $z_0, \ z_1, \ z_2$&nbsp; und&nbsp; $z_6$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^2.4 Reed–Solomon–Decodierung beim Auslöschungskanal^]]
+
[[Category:Aufgaben zu  Kanalcodierung|^2.4 RS–Decodierung bei Auslöschungen^]]

Aktuelle Version vom 20. Oktober 2022, 16:46 Uhr

${\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:

  • Hinsichtlich des Codewortfinders verweisen wir insbesondere auf die Seiten 
  • 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

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