Aufgaben:Aufgabe 2.11: RS–Decodierung nach „Erasures”: Unterschied zwischen den Versionen
Aus LNTwww
(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)$ | + | [[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 | + | 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 ∈ \{0, \, 1, \, \alpha, \, \alpha^2, \, \alpha^3, \, \alpha^4, \, \alpha^5, \, \alpha^6\}$ werden durch $m = 3 | + | * 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 | + | |
− | * 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}$. | + | * 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. |
− | * Das gesuchte Informationswert $\underline{ | + | |
+ | * 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}} | :$$\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{ | + | \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{z} = {\rm enc}(\underline{v}) |
− | = \underline{ | + | = \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 [[Kanalcodierung/Reed%E2%80%93Solomon%E2%80%93Decodierung_beim_Ausl%C3%B6schungskanal| "Reed–Solomon–Decodierung beim Auslöschungskanal"]]. | ||
− | + | * Hinsichtlich des Codewortfinders verweisen wir insbesondere auf die Seiten | |
− | + | :*[[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Vorgehensweise_am_Beispiel_des_RSC_.287.2C_3.2C_5.298|"Vorgehensweise ..."]] und | |
− | * Hinsichtlich des | + | :*[[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– Polynom– und Koeffizientenvektordarstellung. | + | |
+ | * Alle Berechnungen sind in $\rm GF(2^3)$ durchzuführen. Die obere Grafik beschreibt deren $q = 8$ Elemente in Potenz–, Polynom– und Koeffizientenvektordarstellung. | ||
Zeile 36: | Zeile 47: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {Geben Sie die Codeparameter des vorliegenden Reed–Solomon–Codes an. |
− | |type=" | + | |type="{}"} |
− | + | + | $n \ = \ ${ 7 } |
− | - | + | $k \ = \ ${ 4 } |
+ | $d_{\rm min} \ = \ ${ 4 } | ||
+ | |||
+ | {Kann der Empfangsvektor $\underline{y} = (0, \, 0, \, 0,\, 0, \, 0, \, 0, \, {\rm E})$ decodiert werden? | ||
+ | |type="()"} | ||
+ | + JA. | ||
+ | - NEIN. | ||
+ | |||
+ | {Kann der Empfangsvektor $\underline{y} = (\rm E, \, E, \, 1, \, 1, \, 1, \, 1, \, 1)$ decodiert werden? | ||
+ | |type="()"} | ||
+ | + JA. | ||
+ | - NEIN. | ||
− | { | + | {Welches Ergebnis liefert die Decodierung von $\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, 0)$? |
− | |type="{}"} | + | |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 $\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)''' | + | '''(1)''' Die Spaltenanzahl der Prüfmatrix $\mathbf{H}$ gibt die Codelänge an: $n \ \underline{= 7}$. |
− | '''(2)''' | + | *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$. |
− | '''(3)''' | + | |
− | '''(4)''' | + | *Die Zeilenanzahl der Prüfmatrix ist gleich $n - k = 3 \ \Rightarrow \ k \ \underline{= 4}$. |
− | '''(5)''' | + | |
+ | *Von allen Reed–Solomon–Codes wird die [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Singleton.E2.80.93Schranke_und_minimale_Distanz| "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 ⇒ <b><u>JA</u></b>. | ||
+ | *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$ ⇒ <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–$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 <u>Lösungsvorschlag 2</u>. | ||
+ | |||
+ | |||
+ | |||
+ | '''(5)''' Richtig ist der <u>Lösungsvorschlag 4</u>. 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$. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category:Aufgaben zu Kanalcodierung|^2.4 | + | [[Category:Aufgaben zu Kanalcodierung|^2.4 RS–Decodierung bei Auslöschungen^]] |
Aktuelle Version vom 20. Oktober 2022, 16:46 Uhr
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
- Alle Berechnungen sind in $\rm GF(2^3)$ durchzuführen. Die obere Grafik beschreibt deren $q = 8$ Elemente in Potenz–, Polynom– und Koeffizientenvektordarstellung.
Fragebogen
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$.