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

• Zurück zum Buch

${\rm GF}(2^3)$ in Potenz–, Polynom– u. Koeffizientenvektordarstellung

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 \ \rm Bit$ dargestellt und über den grün hinterlegten Auslöschungskanal ($m$–BEC) übertragen. Ein Codesymbol wird bereits dann als Auslöschung (Erasure) E markiert, wenn eines der drei zugehörigen Bit unsicher ist.
• Der Codewortfinder (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–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{\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:

$$\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}) = \underline{\upsilon} \cdot {\boldsymbol{\rm G}}$$

$$\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}.$$

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 Spalten 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 Zeilenzahl 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.

(4) 

(5)