Reed-Solomon Decoding for the Erasure Channel

From LNTwww
< Channel Coding
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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. Im Reed–Solomon–Kapitel haben wir  $\underline{x}$  in  $\underline{c}$  umbenannt.

Zugrunde gelegt wird auch hier 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 ) sind hier Bitfehler  $(y_i ≠ c_i)$  ausgeschlossen. Jedes Bit eines Empfangswortes

  • stimmt also mit dem entsprechenden Bit des Codewortes überein  $(y_i = c_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 auch hier 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}\text{ ... }\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm} \underline {c} = (c_0, c_1, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, c_i, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, 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 nur 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 im 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 und sendet eventuell die Sequenz noch einmal.

Beim Auslöschungskanal  ($m$–BEC)  ist 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 hier 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 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$  und  $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 „$\rm E$” für Erasures ),
  • den Vektor  $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$  der bekannten Symbole  (Index „$\rm 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.45cm}... \hspace{0.45cm}= \begin{pmatrix} \alpha^3\\ \alpha^{4}\\ \alpha^{2}\\ 0 \end{pmatrix} \hspace{0.05cm}.\]
  • Die rechte Gleichungsseite ergibt sich 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 = \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 = (\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 = (\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 = (\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