Reed-Solomon Decoding for the Erasure Channel

From LNTwww
< Channel Coding
Revision as of 17:22, 14 January 2017 by Ayush (talk | contribs) (Die Seite wurde neu angelegt: „ {{Header |Untermenü=Reed–Solomon–Codes und deren Decodierung |Vorherige Seite=Definition und Eigenschaften von Reed–Solomon–Codes |Nächste Seite=Fe…“)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Blockschaltbild und Voraussetzungen zu Kapitel 2.4


Im Kapitel 1.5 wurde für die binären Blockcodes gezeigt, welche Berechnungen der Decoder ausführen muss, um aus einem unvollständigen Empfangswort y das gesendete Codewort x bestmöglich decodieren zu können. Zugrunde gelegt war dabei das BEC–Kanalmodell (Binary Erasure Channel), das ein unsicheres Bit als Erasure E („Auslöschung”) markiert.

Im Gegensatz zu BSC (Binary Symmetric Channel) und AWGN (Additive White Gaussian Noise) wurden hier Bitfehler (yixi) ausgeschlossen. Jedes Bit eines Empfangswortes stimmt also mit dem entsprechenden Bit des Codewortes überein (yi = xi) oder ist bereits als Auslöschung markiert (yi = E).

Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und Auslöschungskanal

Die Grafik zeigt das Blockschaltbild, das sich von dem Modell in Kapitel 1.5 geringfügig unterscheidet:

  • Da Reed–Solomon–Codes lineare Blockcodes sind, stehen Informationswort u und Codewort c über die Generatormatrix 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 Informations– 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 ci 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 λmm · λ wird ein Codesymbol ci ausgelöscht (yi = E) und es gilt Pr(yi = ci) = 1 – λm. Näheres zur Umrechnung der beiden Modelle finden Sie in Aufgabe Z2.11.

Im Folgenden beschäftigen wir uns ausschließlich mit dem Block Codewortfinder (CWF), der aus dem Empfangsvektor y den Vektor <nobr>zCRS</nobr> gewinnt:

  • Falls die Anzahl e der Auslöschungen in Vektor y hinreichend klein ist, lässt sich das gesamte Codewort mit Sicherheit (z = c) finden.
  • Sind zuviele Symbole des Empfangswortes 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 2.5 Anwendung findet, eine Fehlentscheidung (zc) ausgeschlossen ⇒ Blockfehlerwahrscheinlichkeit Pr(zc) = 0 ⇒ Pr(υu) = 0. Das rekonstruierte Informationswort ergibt sich gemäß dem Blockschaltbild (gelbe Hinterlegung) zu υ = enc–1(z). Mit der Generatormatrix 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}. \]