Reed-Solomon Decoding for the Erasure Channel

From LNTwww
< Channel Coding
Revision as of 10:45, 23 November 2017 by Guenter (talk | contribs)

Blockschaltbild und Voraussetzungen


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)$.
Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und Auslöschungskanal

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 entsprechend den Ausführungen in Kapitel 2.3 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 z2, z3, z5. Bei eindeutiger Lösung – und nur bei einer solchen – ist die Decodierung erfolgreich und man kann dann mit Sicherheit sagen, dass tatsächlich c = z gesendet wurde.

Die Beschreibung wird auf der nächsten Seite fortgesetzt.

Lösung der Matrixgleichungen am Beispiel des RSC (7, 3, 5)8


Gefunden werden muss also das zulässige Codewort z, das die Bestimmungsgleichung H · zT = 0T erfüllt. Zweckmäßigerweise spalten wir dazu den Vektor z in zwei Teilvektoren auf, nämlich in

  • den Vektor zE = (z2, z3, z5) der ausgelöschten Symbole (Index E für Erasures),
  • den Vektor zK = (c0, c1, c4, c6) der bekannten Symbole (Index K für Korrekt).

Mit den zugehörigen Teilmatrizen (jeweils mit nk = 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 zi ∈ GF(2m) die additive Inverse InvA(zi) (= –zi) = zi 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  ⇒  zK = (c0, c1, c4, c6) und basiert auf dem Polynom p(x) = x3 + x + 1, das zu folgenden Potenzen in α führt:

\[\alpha^3 \hspace{-0.15cm} = \hspace{-0.15cm}\alpha + 1\hspace{0.05cm}, \hspace{0.4cm} \alpha^4 = \alpha^2 + \alpha\hspace{0.05cm}, \hspace{0.4cm} \alpha^5 = \alpha^2 + \alpha + 1\hspace{0.05cm}, \hspace{0.4cm} \alpha^6 = \alpha^2 + 1\hspace{0.05cm},\] \[\alpha^7 \hspace{-0.15cm} = \hspace{-0.15cm} 1\hspace{0.05cm}, \hspace{1.12cm} \alpha^8 = \alpha^1 \hspace{0.05cm}, \hspace{1.19cm} \alpha^9 = \alpha^2 \hspace{0.05cm}, \hspace{1.9cm} \alpha^{10} = \alpha^3 = \alpha + 1\hspace{0.05cm},\hspace{0.1cm} ...\]

Damit lautet die Matrizengleichung zur Bestimmung des gesuchten Vektors zE:

\[\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 G zu υ = z · GT = (α1, 1, α3).

Aufgaben zum Kapitel


A2.11 RS–Decodierung nach „Erasures”

Zusatzaufgaben:2.11 Erasure–Kanal für Symbole