Difference between revisions of "Channel Coding/Reed-Solomon Decoding for the Erasure Channel"

From LNTwww
(11 intermediate revisions by 3 users not shown)
Line 8: Line 8:
 
== Blockschaltbild und Voraussetzungen zur RS–Fehlererkennung ==
 
== Blockschaltbild und Voraussetzungen zur RS–Fehlererkennung ==
 
<br>
 
<br>
Im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel|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 [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Erasure_Channel_.E2.80.93_BEC| BEC&ndash;Kanalmodell]] (<i>Binary Erasure Channel</i>), das ein unsicheres Bit als <i>Erasure</i> $\rm E$ (&bdquo;Auslöschung&rdquo;) markiert.<br>
+
Im Kapitel&nbsp; [[Channel_Coding/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel|Decodierung beim Binary Erasure Channel]]&nbsp; wurde für die binären Blockcodes gezeigt, welche Berechnungen der Decoder ausführen muss, um aus einem unvollständigen Empfangswort&nbsp; $\underline{y}$&nbsp; das gesendete Codewort&nbsp; $\underline{x}$&nbsp; bestmöglich decodieren zu können. Im Reed&ndash;Solomon&ndash;Kapitel haben wir&nbsp; $\underline{x}$&nbsp; in&nbsp; $\underline{c}$&nbsp; umbenannt. 
 +
 
 +
Zugrunde gelegt wird auch hier das&nbsp; [[Channel_Coding/Signal_classification#Binary_Erasure_Channel_.E2.80.93_BEC| BEC&ndash;Kanalmodell]]&nbsp; (<i>Binary Erasure Channel</i>&nbsp;), das ein unsicheres Bit als&nbsp; <i>Erasure</i>&nbsp; $\rm E$&nbsp; (&bdquo;Auslöschung&rdquo;) markiert. Im Gegensatz zu&nbsp; [[Channel_Coding/Signal_classification#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC]]&nbsp; (<i>Binary Symmetric Channel</i>&nbsp;) und&nbsp; [[Channel_Coding/Signal_classification#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN]]&nbsp; (<i>Additive White Gaussian Noise</i>&nbsp;) sind hier Bitfehler&nbsp; $(y_i &ne; c_i)$&nbsp; ausgeschlossen. Jedes  Bit eines Empfangswortes
 +
*stimmt also mit dem entsprechenden Bit des Codewortes überein&nbsp; $(y_i = c_i)$, oder
 +
*ist bereits als Auslöschung markiert&nbsp; $(y_i = \rm E)$.<br>
  
Im Gegensatz zu [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC]] (<i>Binary Symmetric Channel</i>) und [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN]] (<i>Additive White Gaussian Noise</i>) wurden hier Bitfehler $(y_i &ne; 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)$.<br>
 
  
 
[[File:P ID2544 KC T 2 4 S1 v2.png|center|frame|Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und Auslöschungskanal|class=fit]]
 
[[File:P ID2544 KC T 2 4 S1 v2.png|center|frame|Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und Auslöschungskanal|class=fit]]
  
Die Grafik zeigt das Blockschaltbild, das sich von dem Modell im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen|Decodierung linearer Blockcodes]] geringfügig unterscheidet:
+
Die Grafik zeigt das Blockschaltbild, das sich von dem Modell im Kapitel&nbsp; [[Channel_Coding/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen|Decodierung linearer Blockcodes]] geringfügig unterscheidet:
*Da Reed&ndash;Solomon&ndash;Codes lineare Blockcodes sind, stehen Informationswort $\underline{u}$ und Codewort $\underline{c}$ über die Generatormatrix $\boldsymbol{\rm G}$ und die folgende Gleichung in Zusammenhang:
+
*Da Reed&ndash;Solomon&ndash;Codes lineare Blockcodes sind, stehen auch hier Informationswort&nbsp; $\underline{u}$&nbsp; und Codewort&nbsp; $\underline{c}$&nbsp; über die Generatormatrix $\boldsymbol{\rm G}$ und die folgende Gleichung in Zusammenhang:
  
 
::<math>\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}}
 
::<math>\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}  
+
\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}, c_i, ...\hspace{0.05cm}, c_{n-1})
+
\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}.</math>
 
\hspace{0.05cm}.</math>
  
Line 29: Line 30:
 
\hspace{0.3cm} \Rightarrow  \hspace{0.3cm} n = 2^m - 1\hspace{0.05cm}. </math>
 
\hspace{0.3cm} \Rightarrow  \hspace{0.3cm} n = 2^m - 1\hspace{0.05cm}. </math>
  
*Jedes Codesymbol $c_i$ wird somit mit $m &#8805; 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.<br>
+
*Jedes Codesymbol&nbsp; $c_i$&nbsp; wird somit mit&nbsp; $m &#8805; 2$&nbsp; Binärsymbolen (Bit) dargestellt. Zum Vergleich: &nbsp; Für die binären Blockcodes gilt&nbsp; $q=2$,&nbsp; $m=1$&nbsp; und die Codewortlänge&nbsp; $n$&nbsp; ist frei wählbar.<br>
  
*Bei Codierung auf Symbolebene muss das BEC&ndash;Modell zum $m$&ndash;BEC&ndash;Modell erweitert werden. Mit der Wahrscheinlichkeit $\lambda_m  &asymp; 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]].<br>
+
*Bei Codierung auf Symbolebene muss das BEC&ndash;Modell zum&nbsp; $m$&ndash;BEC&ndash;Modell erweitert werden. Mit der Wahrscheinlichkeit&nbsp; $\lambda_m  &asymp; m \cdot\lambda$&nbsp; wird ein Codesymbol&nbsp; $c_i$&nbsp; ausgelöscht&nbsp; $(y_i = \rm E)$&nbsp; und es gilt&nbsp; ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$. Näheres zur Umrechnung der beiden Modelle finden Sie in der&nbsp; [[Aufgaben:Aufgabe_2.11Z:_Erasure–Kanal_für_Symbole|Aufgabe 2.11Z]].<br>
  
  
Im Folgenden beschäftigen wir uns ausschließlich mit dem Block  <i>Codewortfinder</i> (CWF), der aus dem Empfangsvektor $\underline{y}$ den Vektor $\underline{z} &#8712; \mathcal{C}_{\rm RS}$ gewinnt:
+
Im Folgenden beschäftigen wir uns nur mit dem Block&nbsp; <i>Codewortfinder</i> (CWF), der aus dem Empfangsvektor&nbsp; $\underline{y}$&nbsp; den Vektor&nbsp; $\underline{z} &#8712; \mathcal{C}_{\rm RS}$&nbsp; 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.<br>
+
*Falls die Anzahl&nbsp; $e$&nbsp; der Auslöschungen im Vektor&nbsp; $\underline{y}$&nbsp; hinreichend klein ist, lässt sich das gesamte Codewort mit Sicherheit&nbsp; $(\underline{z}=\underline{c})$&nbsp;   finden.<br>
  
*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.<br><br>
+
*Sind zuviele Symbole des Empfangswortes&nbsp; $\underline{y}$&nbsp; ausgelöscht, meldet der Decoder, dass dieses Wort nicht decodierbar ist und sendet eventuell die Sequenz noch einmal.<br><br>
  
Beim Auslöschungskanal ($m$&ndash;BEC) ist also im Gegensatz zum $m$&ndash;BSC, der im Kapitel [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung|Fehlerkorrektur nach Reed–Solomon–Codierung]] Anwendung findet,  eine Fehlentscheidung $(\underline{z} \ne \underline{c})$ ausgeschlossen &nbsp; &#8658; &nbsp; Blockfehlerwahrscheinlichkeit ${\rm Pr}(\underline{z}\ne\underline{c})  = 0$ &nbsp; &#8658; &nbsp; ${\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:
+
Beim Auslöschungskanal&nbsp; ($m$&ndash;BEC)&nbsp; ist im Gegensatz zum &nbsp;$m$&ndash;BSC, der im Kapitel&nbsp; [[Channel_Coding/Fehlerkorrektur_nach_Reed–Solomon–Codierung|Fehlerkorrektur nach Reed–Solomon–Codierung]]&nbsp; Anwendung findet,  eine Fehlentscheidung&nbsp; $(\underline{z} \ne \underline{c})$&nbsp; ausgeschlossen &nbsp; &#8658; &nbsp; Blockfehlerwahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{z}\ne\underline{c})  = 0$ &nbsp; &#8658; &nbsp; ${\rm Pr}(\underline{v}\ne\underline{u})  = 0$.  
 +
*Das rekonstruierte Informationswort ergibt sich gemäß dem Blockschaltbild (gelbe Hinterlegung) zu&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$.  
 +
*Mit der Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; kann hierfür auch geschrieben werden:
  
 
::<math>\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}
 
::<math>\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}
Line 48: Line 51:
 
== Vorgehensweise am Beispiel des RSC (7, 3, 5)<sub>8</sub> ==
 
== Vorgehensweise am Beispiel des RSC (7, 3, 5)<sub>8</sub> ==
 
<br>
 
<br>
Um die Reed&ndash;Solomon&ndash;Decodierung beim Auslöschungskanal so einfach wie möglich darstellen zu können, gehen wir von einer konkreten Aufgabenstellung aus: Verwendet wird ein Reed&ndash;Solomon&ndash;Code mit den Parametern $n= 7$, $k= 3$ und $q= 2^3 = 8$.  
+
Um die Reed&ndash;Solomon&ndash;Decodierung beim Auslöschungskanal so einfach wie möglich darstellen zu können, gehen wir von einer konkreten Aufgabenstellung aus:  
 +
 
 +
Verwendet wird ein Reed&ndash;Solomon&ndash;Code mit den Parametern&nbsp; $n= 7$,&nbsp; $k= 3$&nbsp; und&nbsp; $q= 2^3 = 8$.  
  
Somit gilt für das Informationswort $\underline{u}$ und das Codewort $\underline{c}$:
+
Somit gilt für das Informationswort&nbsp; $\underline{u}$&nbsp; und das Codewort&nbsp; $\underline{c}$:
  
 
::<math>\underline {u} = (u_0, u_1, u_2) \hspace{0.05cm},\hspace{0.15cm}
 
::<math>\underline {u} = (u_0, u_1, u_2) \hspace{0.05cm},\hspace{0.15cm}
Line 57: Line 62:
 
\hspace{0.05cm},</math>
 
\hspace{0.05cm},</math>
  
und die Prüfmatrix $\boldsymbol{\rm H}$ lautet:
+
und die Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; lautet:
  
 
::<math>{ \boldsymbol{\rm H}} =  
 
::<math>{ \boldsymbol{\rm H}} =  
Line 67: Line 72:
 
\end{pmatrix}\hspace{0.05cm}. </math>
 
\end{pmatrix}\hspace{0.05cm}. </math>
  
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:
+
Beispielhaft wird hier vom  Empfangsvektor&nbsp; $\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)$&nbsp; ausgegangen. Dann gilt:
 
*Da der Auslöschungskanal keine Fehler produziert, sind dem Decoder vier der Codesymbole bekannt:
 
*Da der Auslöschungskanal keine Fehler produziert, sind dem Decoder vier der Codesymbole bekannt:
  
Line 76: Line 81:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
*Es ist offensichtlich, dass der Block &bdquo;Codewortfinder&rdquo; &ndash; im Blockschaltbild mit '''CWF''' bezeichnet &ndash; 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)$.<br>
+
*Es ist offensichtlich, dass der Block &bdquo;Codewortfinder&rdquo; &ndash; im Blockschaltbild mit&nbsp; '''CWF'''&nbsp; bezeichnet &ndash; einen Vektor der Form&nbsp; $\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)$&nbsp; liefern soll mit&nbsp; $z_2,\hspace{0.03cm}z_3,\hspace{0.03cm}z_5 \in \rm GF(2^3)$.<br>
  
*Da das vom Decoder gefundene Codewort $\underline {z}$ aber auch ein gültiges Reed&ndash;Solomon&ndash;Codewort  sein soll &nbsp; &#8658; &nbsp; $\underline {z} &#8712; \mathcal{C}_{\rm RS}$, muss aber ebenso gelten:
+
*Da das vom Decoder gefundene Codewort&nbsp; $\underline {z}$&nbsp; aber auch ein gültiges Reed&ndash;Solomon&ndash;Codewort  sein soll &nbsp; &#8658; &nbsp; $\underline {z} &#8712; \mathcal{C}_{\rm RS}$, muss ebenso gelten:
  
 
::<math>{ \boldsymbol{\rm H}} \cdot \underline {z}^{\rm T} = \underline {0}^{\rm T}  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
::<math>{ \boldsymbol{\rm H}} \cdot \underline {z}^{\rm T} = \underline {0}^{\rm T}  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
Line 103: Line 108:
 
\hspace{0.05cm}. </math>
 
\hspace{0.05cm}. </math>
  
*Daraus ergeben sich vier Gleichungen für die Unbekannten $z_2$, $z_3$ $z_5$. Bei eindeutiger Lösung &ndash; und nur bei einer solchen &ndash; ist die Decodierung erfolgreich und man kann dann mit Sicherheit sagen, dass tatsächlich $\underline {c} =  \underline {z} $ gesendet wurde.<br><br>
+
*Daraus ergeben sich vier Gleichungen für die Unbekannten&nbsp; $z_2$,&nbsp; $z_3$&nbsp; und &nbsp;$z_5$. Bei eindeutiger Lösung &ndash; und nur bei einer solchen &ndash; ist die Decodierung erfolgreich und man kann dann mit Sicherheit sagen, dass tatsächlich&nbsp; $\underline {c} =  \underline {z} $&nbsp; gesendet wurde.<br><br>
  
  
Line 109: Line 114:
 
== Lösung der Matrixgleichungen am Beispiel des RSC (7, 3, 5)<sub>8</sub> ==
 
== Lösung der Matrixgleichungen am Beispiel des RSC (7, 3, 5)<sub>8</sub> ==
 
<br>
 
<br>
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
+
Gefunden werden muss also das zulässige Codewort&nbsp; $\underline {z}$, das die Bestimmungsgleichung&nbsp; $\boldsymbol{\rm H} \cdot \underline {z}^{\rm T} $&nbsp; erfüllt. Zweckmäßigerweise spalten wir dazu den Vektor&nbsp; $\underline {z}$&nbsp; in zwei Teilvektoren auf, nämlich in
*den Vektor $\underline {z}_{\rm E} = (z_2, z_3, z_5)$ der ausgelöschten Symbole (Index &bdquo;E&rdquo; für <i>Erasures</i>),<br>
+
*den Vektor&nbsp; $\underline {z}_{\rm E} = (z_2, z_3, z_5)$&nbsp; der ausgelöschten Symbole&nbsp; (Index &bdquo;$\rm E$&rdquo; für <i>Erasures</i>&nbsp;),<br>
  
*den Vektor $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$ der bekannten Symbole (Index &bdquo;K&rdquo; für <i>Korrekt</i>).<br><br>
+
*den Vektor&nbsp; $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$&nbsp; der bekannten Symbole&nbsp; (Index &bdquo;$\rm K$&rdquo; für <i>Korrekt</i>&nbsp;).<br><br>
  
Mit den zugehörigen Teilmatrizen (jeweils mit $n-k = 4$ Zeilen)
+
Mit den zugehörigen Teilmatrizen (jeweils mit&nbsp; $n-k = 4$&nbsp; Zeilen)
  
 
::<math>{ \boldsymbol{\rm H}}_{\rm E} =  
 
::<math>{ \boldsymbol{\rm H}}_{\rm E} =  
Line 139: Line 144:
 
{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}.  </math>
 
{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}.  </math>
  
Da für alle Elemente $z_i &#8712; {\rm GF}(2^m)$ die [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes |additive Inverse]] ${\rm Inv_A}(z_i)= (- z_i) = z_i$ ist, gilt in gleicher Weise
+
*Da für alle Elemente&nbsp; $z_i &#8712; {\rm GF}(2^m)$&nbsp; die&nbsp; [[Channel_Coding/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes |additive Inverse]]&nbsp; ${\rm Inv_A}(z_i)= (- z_i) = z_i$&nbsp; ist, gilt in gleicher Weise
  
 
::<math>{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} =  
 
::<math>{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} =  
Line 154: Line 159:
 
\alpha^{2}\\
 
\alpha^{2}\\
 
\alpha^{6}
 
\alpha^{6}
\end{pmatrix} = \hspace{0.15cm}... \hspace{0.15cm}=   
+
\end{pmatrix} = \hspace{0.45cm}... \hspace{0.45cm}=   
 
\begin{pmatrix}
 
\begin{pmatrix}
 
\alpha^3\\
 
\alpha^3\\
Line 163: Line 168:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Die rechte Gleichungsseite ergibt für das betrachtete Beispiel &nbsp; &#8658; &nbsp; $\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:
+
*Die rechte Gleichungsseite ergibt sich für das betrachtete Beispiel &nbsp; &#8658; &nbsp; $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$&nbsp; und basiert auf dem Polynom&nbsp; $p(x) = x^3 + x +1$, das zu folgenden Potenzen $($in&nbsp; &nbsp;$\alpha)$&nbsp; führt:
  
 
::<math>\alpha^3 =\alpha + 1\hspace{0.05cm},
 
::<math>\alpha^3 =\alpha + 1\hspace{0.05cm},
Line 174: Line 179:
 
\hspace{0.3cm} \alpha^{10} = \alpha^3 =  \alpha + 1\hspace{0.05cm},\hspace{0.1cm} \text{...}</math>
 
\hspace{0.3cm} \alpha^{10} = \alpha^3 =  \alpha + 1\hspace{0.05cm},\hspace{0.1cm} \text{...}</math>
  
Damit lautet die Matrizengleichung zur Bestimmung des gesuchten Vektors $\underline {z}_{\rm E}$:
+
*Damit lautet die Matrizengleichung zur Bestimmung des gesuchten Vektors&nbsp; $\underline {z}_{\rm E}$:
  
 
::<math>\begin{pmatrix}
 
::<math>\begin{pmatrix}
Line 195: Line 200:
 
\hspace{0.05cm}. </math>
 
\hspace{0.05cm}. </math>
  
Löst man diese Matrizengleichung (am einfachsten per Programm), so erhält man
+
*Löst man diese Matrizengleichung (am einfachsten per Programm), so erhält man
  
 
::<math>z_2 = \alpha^2\hspace{0.05cm},\hspace{0.25cm}z_3 = \alpha^1\hspace{0.05cm},\hspace{0.25cm}z_5 = \alpha^5
 
::<math>z_2 = \alpha^2\hspace{0.05cm},\hspace{0.25cm}z_3 = \alpha^1\hspace{0.05cm},\hspace{0.25cm}z_5 = \alpha^5
Line 201: Line 206:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Das Ergebnis ist richtig, wie die folgenden Kontrollrechnungen zeigen:  
+
*Das Ergebnis ist richtig, wie die folgenden Kontrollrechnungen zeigen:  
  
::<math>\alpha^2 \cdot \alpha^2 + \alpha^3 \cdot \alpha^1 + \alpha^5 \cdot \alpha^5 \hspace{-0.15cm}  = \hspace{-0.15cm}
+
::<math>\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},</math>
 
\alpha^4 + \alpha^4 + \alpha^{10} = \alpha^{10} = \alpha^3\hspace{0.05cm},</math>
::<math>\alpha^4 \cdot \alpha^2 + \alpha^6 \cdot \alpha^1 + \alpha^3 \cdot \alpha^5 \hspace{-0.15cm}  = \hspace{-0.15cm}
+
::<math>\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},</math>
 
(\alpha^2 + 1) + (1) + (\alpha) = \alpha^{2} + \alpha = \alpha^4\hspace{0.05cm},</math>
::<math>\alpha^6 \cdot \alpha^2 + \alpha^2 \cdot \alpha^1 + \alpha^1 \cdot \alpha^5 \hspace{-0.15cm}  = \hspace{-0.15cm}
+
::<math>\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},</math>
 
(\alpha) + (\alpha + 1) + (\alpha^2 + 1) = \alpha^{2} \hspace{0.05cm},</math>
::<math>\alpha^1 \cdot \alpha^2 + \alpha^5 \cdot \alpha^1 + \alpha^6 \cdot \alpha^5 \hspace{-0.15cm}  = \hspace{-0.15cm}
+
::<math>\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}.</math>
 
(\alpha + 1) + (\alpha^2 + 1) + (\alpha^2 + \alpha) = 0\hspace{0.05cm}.</math>
  
Das zugehörige Informationswort erhält man mit der [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| 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)$.<br>
+
*Das zugehörige Informationswort erhält man mit der&nbsp; [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Generatormatrix]]&nbsp; $\boldsymbol{\rm G}$&nbsp; zu&nbsp; $\underline {v} = \underline {z} \cdot \boldsymbol{\rm G}^{\rm T} = (\alpha^1,\hspace{0.05cm}1,\hspace{0.05cm}\alpha^3)$.<br>
  
 
== Aufgaben zum Kapitel ==
 
== Aufgaben zum Kapitel ==
Line 218: Line 223:
 
[[Aufgaben:2.11_RS–Decodierung_nach_„Erasures”|Aufgabe 2.11: RS–Decodierung nach „Erasures”]]
 
[[Aufgaben:2.11_RS–Decodierung_nach_„Erasures”|Aufgabe 2.11: RS–Decodierung nach „Erasures”]]
  
[[Aufgaben:2.11Z_Erasure–Kanal_für_Symbole|Zusatzaufgabe 2.11Z: Erasure–Kanal für Symbole]]
+
[[Aufgaben:2.11Z_Erasure–Kanal_für_Symbole|Aufgabe 2.11Z: Erasure–Kanal für Symbole]]
  
 
{{Display}}
 
{{Display}}

Revision as of 16:30, 13 October 2020

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