Channel Coding/Reed-Solomon Decoding for the Erasure Channel

1. Channel Coding
2. Reed–Solomon–Codes und deren Decodierung
3. Reed-Solomon Decoding for the Erasure Channel

• Previous page
• Next page

• Previous page
• Next page

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)₈

Um die RS–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³ = 8. Allgemein gilt für das Informationswort u, das Codewort c und die Prüfmatrix H:

\[\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, ... , \alpha^6\} \hspace{0.05cm},\]

\[{ \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}. \]

• Der Empfangsvektor wird mit y = (α¹, 1, E, E, α², E, α⁵) vorgegeben. 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 z = (c₀, c₁, z₂, z₃, c₄, z₅, c₆) liefern soll mit z₂, z₃, z₅ ∈ GF(2³).
  

• Da das vom Decoder gefundene Codewort z aber auch ein gültiges Reed–Solomon–Codewort sein soll    ⇒    z ∈ C_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 z₂, z₃, z₅. 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)₈

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

• den Vektor z_E = (z₂, z₃, z₅) der ausgelöschten Symbole (Index E für Erasures),
  

• den Vektor z_K = (c₀, c₁, c₄, c₆) 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 ∈ GF(2^m) die additive Inverse 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  ⇒  z_K = (c₀, c₁, c₄, c₆) und basiert auf dem Polynom p(x) = x³ + 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 z_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 G zu υ = z · G^T = (α¹, 1, α³).

Aufgaben zum Kapitel

A2.11 RS–Decodierung nach „Erasures”