Contents
Blockschaltbild und Voraussetzungen zur RS–Fehlererkennung
Im Kapitel Decodierung beim Binary Erasure Channel wurde für die binären Blockcodes gezeigt, welche Berechnungen der Decoder ausführen muss, um aus einem unvollständigen Empfangswort $\underline{y}$ das gesendete Codewort $\underline{x}$ bestmöglich decodieren zu können. Zugrunde gelegt war dabei das BEC–Kanalmodell (Binary Erasure Channel), das ein unsicheres Bit als Erasure $\rm E$ („Auslöschung”) markiert.
Im Gegensatz zu BSC (Binary Symmetric Channel) und AWGN (Additive White Gaussian Noise) wurden hier Bitfehler $(y_i ≠ x_i)$ ausgeschlossen. Jedes Bit eines Empfangswortes
- stimmt also mit dem entsprechenden Bit des Codewortes überein $(y_i = x_i)$, oder
- ist bereits als Auslöschung markiert $(y_i = \rm E)$.
Die Grafik zeigt das Blockschaltbild, das sich von dem Modell im Kapitel Decodierung linearer Blockcodes geringfügig unterscheidet:
- Da Reed–Solomon–Codes lineare Blockcodes sind, stehen Informationswort $\underline{u}$ und Codewort $\underline{c}$ über die Generatormatrix $\boldsymbol{\rm G}$ und die folgende Gleichung in Zusammenhang:
- \[\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} {\rm mit} \hspace{0.3cm}\underline {u} = (u_0, u_1, ... \hspace{0.05cm}, u_i, ...\hspace{0.05cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm} \underline {c} = (c_0, c_1, ... \hspace{0.05cm}, c_i, ...\hspace{0.05cm}, c_{n-1}) \hspace{0.05cm}.\]
- Für die einzelnen Symbole von Informationsblock und Codewort gilt bei Reed–Solomon–Codierung:
- \[u_i \in {\rm GF}(q)\hspace{0.05cm},\hspace{0.2cm}c_i \in {\rm GF}(q)\hspace{0.3cm}{\rm mit}\hspace{0.3cm} q = n+1 = 2^m \hspace{0.3cm} \Rightarrow \hspace{0.3cm} n = 2^m - 1\hspace{0.05cm}. \]
- Jedes Codesymbol $c_i$ wird somit mit $m ≥ 2$ Binärsymbolen (Bit) dargestellt. Zum Vergleich: Für die binären Blockcodes gilt $q=2$, $m=1$ und die Codewortlänge $n$ ist frei wählbar.
- Bei Codierung auf Symbolebene muss das BEC–Modell zum $m$–BEC–Modell erweitert werden. Mit der Wahrscheinlichkeit $\lambda_m ≈ m \cdot\lambda$ wird ein Codesymbol $c_i$ ausgelöscht $(y_i = \rm E)$ und es gilt ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$. Näheres zur Umrechnung der beiden Modelle finden Sie in der Aufgabe 2.11Z.
Im Folgenden beschäftigen wir uns ausschließlich mit dem Block Codewortfinder (CWF), der aus dem Empfangsvektor $\underline{y}$ den Vektor $\underline{z} ∈ \mathcal{C}_{\rm RS}$ gewinnt:
- Falls die Anzahl $e$ der Auslöschungen in Vektor $\underline{y}$ hinreichend klein ist, lässt sich das gesamte Codewort mit Sicherheit $(\underline{z}=\underline{c})$ finden.
- Sind zuviele Symbole des Empfangswortes $\underline{y}$ ausgelöscht, meldet der Decoder, dass dieses Wort nicht decodierbar ist. Eventuell wird dann die Codesequenz noch einmal gesendet.
Beim Auslöschungskanal ($m$–BEC) ist also im Gegensatz zum $m$–BSC, der im Kapitel Fehlerkorrektur nach Reed–Solomon–Codierung Anwendung findet, eine Fehlentscheidung $(\underline{z} \ne \underline{c})$ ausgeschlossen ⇒ Blockfehlerwahrscheinlichkeit ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$ ⇒ ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$. Das rekonstruierte Informationswort ergibt sich gemäß dem Blockschaltbild (gelbe Hinterlegung) zu $\underline{v} = {\rm enc}^{-1}(\underline{z})$. Mit der Generatormatrix $\boldsymbol{\rm G}$ kann hierfür auch geschrieben werden:
- \[\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline {z} = \underline {\upsilon} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline {\upsilon} = \underline {z} \cdot { \boldsymbol{\rm G}}^{\rm T} \hspace{0.05cm}. \]
Vorgehensweise am Beispiel des RSC (7, 3, 5)8
Um die Reed–Solomon–Decodierung beim Auslöschungskanal so einfach wie möglich darstellen zu können, gehen wir von einer konkreten Aufgabenstellung aus: Verwendet wird ein Reed–Solomon–Code mit den Parametern $n= 7$, $k= 3$ und $q= 2^3 = 8$.
Somit gilt für das Informationswort $\underline{u}$ und das Codewort $\underline{c}$:
- \[\underline {u} = (u_0, u_1, u_2) \hspace{0.05cm},\hspace{0.15cm} \underline {c} = (c_0, c_1, c_2,c_3,c_4,c_5,c_6)\hspace{0.05cm},\hspace{0.15cm} u_i, c_i \in {\rm GF}(2^3) = \{0, 1, \alpha, \alpha^2, \text{...}\hspace{0.05cm} , \alpha^6\} \hspace{0.05cm},\]
und die Prüfmatrix $\boldsymbol{\rm H}$ lautet:
- \[{ \boldsymbol{\rm H}} = \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}\\ 1 & \alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2} & \alpha^{6} & \alpha^{3} \end{pmatrix}\hspace{0.05cm}. \]
Beispielhaft wird vom Empfangsvektor $\underline {y} = (\alpha, \hspace{0.03cm} 1, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}\alpha^2,{\rm E}, \hspace{0.03cm}\alpha^5)$ ausgegangen. Dann gilt:
- Da der Auslöschungskanal keine Fehler produziert, sind dem Decoder vier der Codesymbole bekannt:
- \[c_0 = \alpha^1 \hspace{0.05cm},\hspace{0.2cm} c_1 = 1 \hspace{0.05cm},\hspace{0.2cm} c_4 = \alpha^2 \hspace{0.05cm},\hspace{0.2cm} c_6 = \alpha^5 \hspace{0.05cm}.\]
- Es ist offensichtlich, dass der Block „Codewortfinder” – im Blockschaltbild mit CWF bezeichnet – einen Vektor der Form $\underline {z} = (c_0, \hspace{0.03cm}c_1, \hspace{0.03cm}z_2, \hspace{0.03cm}z_3,\hspace{0.03cm}c_4,\hspace{0.03cm}z_5,\hspace{0.03cm}c_6)$ liefern soll mit $z_2,\hspace{0.03cm}z_3,\hspace{0.03cm}z_5 \in \rm GF(2^3)$.
- Da das vom Decoder gefundene Codewort $\underline {z}$ aber auch ein gültiges Reed–Solomon–Codewort sein soll ⇒ $\underline {z} ∈ \mathcal{C}_{\rm RS}$, muss aber ebenso gelten:
- \[{ \boldsymbol{\rm H}} \cdot \underline {z}^{\rm T} = \underline {0}^{\rm T} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \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}\\ 1 & \alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2} & \alpha^{6} & \alpha^{3} \end{pmatrix} \cdot \begin{pmatrix} c_0\\ c_1\\ z_2\\ z_3\\ c_4\\ z_5\\ c_6 \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ 0\\ 0 \end{pmatrix} \hspace{0.05cm}. \]
- Daraus ergeben sich vier Gleichungen für die Unbekannten $z_2$, $z_3$ $z_5$. Bei eindeutiger Lösung – und nur bei einer solchen – ist die Decodierung erfolgreich und man kann dann mit Sicherheit sagen, dass tatsächlich $\underline {c} = \underline {z} $ gesendet wurde.
Lösung der Matrixgleichungen am Beispiel des RSC (7, 3, 5)8
Gefunden werden muss also das zulässige Codewort $\underline {z}$, das die Bestimmungsgleichung $\boldsymbol{\rm H} \cdot \underline {z}^{\rm T} $ erfüllt. Zweckmäßigerweise spalten wir dazu den Vektor $\underline {z}$ in zwei Teilvektoren auf, nämlich in
- den Vektor $\underline {z}_{\rm E} = (z_2, z_3, z_5)$ der ausgelöschten Symbole (Index „E” für Erasures),
- den Vektor $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$ der bekannten Symbole (Index „K” für Korrekt).
Mit den zugehörigen Teilmatrizen (jeweils mit $n-k = 4$ Zeilen)
- \[{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^5 \\ \alpha^4 & \alpha^6 & \alpha^{3} \\ \alpha^6 & \alpha^2 & \alpha^{1} \\ \alpha^1 & \alpha^{5} & \alpha^{6} \end{pmatrix} \hspace{0.05cm},\hspace{0.4cm} { \boldsymbol{\rm H}}_{\rm K} \begin{pmatrix} 1 & \alpha^1 & \alpha^4 & \alpha^6\\ 1 & \alpha^2 & \alpha^1 & \alpha^{5}\\ 1 & \alpha^3 & \alpha^{5} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^{2} & \alpha^{3} \end{pmatrix}\]
lautet somit die Bestimmungsgleichung:
- \[{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} + { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} = \underline {0}^{\rm T} \hspace{0.5cm} \Rightarrow \hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} = - { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}. \]
Da für alle Elemente $z_i ∈ {\rm GF}(2^m)$ die additive Inverse ${\rm Inv_A}(z_i)= (- z_i) = z_i$ ist, gilt in gleicher Weise
- \[{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} = { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 & \alpha^1 & \alpha^4 & \alpha^6\\ 1 & \alpha^2 & \alpha^1 & \alpha^{5}\\ 1 & \alpha^3 & \alpha^{5} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^{2} & \alpha^{3} \end{pmatrix} \cdot \begin{pmatrix} \alpha^1\\ 1\\ \alpha^{2}\\ \alpha^{6} \end{pmatrix} = \hspace{0.15cm}... \hspace{0.15cm}= \begin{pmatrix} \alpha^3\\ \alpha^{4}\\ \alpha^{2}\\ 0 \end{pmatrix} \hspace{0.05cm}.\]
Die rechte Gleichungsseite ergibt für das betrachtete Beispiel ⇒ $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$ und basiert auf dem Polynom $p(x) = x^3 + x +1$, das zu folgenden Potenzen (in $\alpha$) führt:
- \[\alpha^3 =\alpha + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^4 = \alpha^2 + \alpha\hspace{0.05cm}, \hspace{0.3cm} \alpha^5 = \alpha^2 + \alpha + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^6 = \alpha^2 + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^7 \hspace{-0.15cm} = \hspace{-0.15cm} 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^8 = \alpha^1 \hspace{0.05cm}, \hspace{0.3cm} \alpha^9 = \alpha^2 \hspace{0.05cm}, \hspace{0.3cm} \alpha^{10} = \alpha^3 = \alpha + 1\hspace{0.05cm},\hspace{0.1cm} \text{...}\]
Damit lautet die Matrizengleichung zur Bestimmung des gesuchten Vektors $\underline {z}_{\rm E}$:
- \[\begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^5 \\ \alpha^4 & \alpha^6 & \alpha^{3} \\ \alpha^6 & \alpha^2 & \alpha^{1} \\ \alpha^1 & \alpha^{5} & \alpha^{6} \end{pmatrix} \cdot \begin{pmatrix} z_2\\ z_3\\ z_5 \end{pmatrix} \stackrel{!}{=} \begin{pmatrix} \alpha^3\\ \alpha^{4}\\ \alpha^{2}\\ 0 \end{pmatrix} \hspace{0.05cm}. \]
Löst man diese Matrizengleichung (am einfachsten per Programm), so erhält man
- \[z_2 = \alpha^2\hspace{0.05cm},\hspace{0.25cm}z_3 = \alpha^1\hspace{0.05cm},\hspace{0.25cm}z_5 = \alpha^5 \hspace{0.5cm} \Rightarrow \hspace{0.5cm}\underline {z} = \left ( \hspace{0.05cm} \alpha^1, \hspace{0.05cm}1, \hspace{0.05cm}\alpha^2, \hspace{0.05cm}\alpha^1, \hspace{0.05cm}\alpha^2, \hspace{0.05cm}\alpha^5, \hspace{0.05cm}\alpha^5 \hspace{0.05cm}\right ) \hspace{0.05cm}.\]
Das Ergebnis ist richtig, wie die folgenden Kontrollrechnungen zeigen:
- \[\alpha^2 \cdot \alpha^2 + \alpha^3 \cdot \alpha^1 + \alpha^5 \cdot \alpha^5 \hspace{-0.15cm} = \hspace{-0.15cm} \alpha^4 + \alpha^4 + \alpha^{10} = \alpha^{10} = \alpha^3\hspace{0.05cm},\]
- \[\alpha^4 \cdot \alpha^2 + \alpha^6 \cdot \alpha^1 + \alpha^3 \cdot \alpha^5 \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha^2 + 1) + (1) + (\alpha) = \alpha^{2} + \alpha = \alpha^4\hspace{0.05cm},\]
- \[\alpha^6 \cdot \alpha^2 + \alpha^2 \cdot \alpha^1 + \alpha^1 \cdot \alpha^5 \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha) + (\alpha + 1) + (\alpha^2 + 1) = \alpha^{2} \hspace{0.05cm},\]
- \[\alpha^1 \cdot \alpha^2 + \alpha^5 \cdot \alpha^1 + \alpha^6 \cdot \alpha^5 \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha + 1) + (\alpha^2 + 1) + (\alpha^2 + \alpha) = 0\hspace{0.05cm}.\]
Das zugehörige Informationswort erhält man mit der Generatormatrix $\boldsymbol{\rm G}$ zu $\underline {v} = \underline {z} \cdot \boldsymbol{\rm G}^{\rm T} = (\alpha^1,\hspace{0.05cm}1,\hspace{0.05cm}\alpha^3)$.
Aufgaben zum Kapitel
Aufgabe 2.11: RS–Decodierung nach „Erasures”
Aufgabe 2.11Z: Erasure–Kanal für Symbole
