Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Blockfehlerwahrscheinlichkeit für RSC und BDD ==
 
== Blockfehlerwahrscheinlichkeit für RSC und BDD ==
 
<br>
 
<br>
Zur Fehlerwahrscheinlichkeitsberechnung  gehen wir vom gleichen Blockschaltbild wie im Kapitel [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung| Fehlerkorrektur nach Reed–Solomon–Codierung]] aus, wobei wir uns hier für den Codewortschätzer $(\underline {y} &#8594; \underline {z})$ auf [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#M.C3.B6gliche_Codewortsch.C3.A4tzer:_HD.E2.80.93MLD_bzw._BDD_.281.29| Bounded Distance Decoding]] (BDD) beschränken. Für <i>Maximum Likelihood Decoding</i> sind die Ergebnisse geringfügig besser.<br>
+
Zur Fehlerwahrscheinlichkeitsberechnung  gehen wir vom gleichen Modell wie im Kapitel&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung| "Fehlerkorrektur nach Reed–Solomon–Codierung"]]&nbsp; aus,&nbsp; wobei wir uns hier für den Codewortschätzer &nbsp; $(\underline {y} &#8594; \underline {z})$ &nbsp; auf&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#M.C3.B6gliche_Codewortsch.C3.A4tzer:_HD.E2.80.93MLD_bzw._BDD_.281.29| "Bounded Distance Decoding"]]&nbsp; $\rm (BDD)$&nbsp; beschränken.&nbsp; Für&nbsp; "Maximum Likelihood Decoding"&nbsp; sind die Ergebnisse geringfügig besser.<br>
  
[[Datei:P ID2564 KC T 2 6 S1 v2.png|center|frame|Systemmodell mit Reed–Solomon–Codierung, $m$–BSC und ''Bounded Distance Decoding''|class=fit]]
+
[[Datei:P ID2564 KC T 2 6 S1 v2.png|right|frame|Systemmodell mit Reed–Solomon–Codierung,&nbsp; $m$–BSC&nbsp; und&nbsp; Bounded Distance Decoding|class=fit]]
  
 
Die Blockfehlerwahrscheinlichkeit sei wie folgt definiert:
 
Die Blockfehlerwahrscheinlichkeit sei wie folgt definiert:
  
::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{\upsilon} \ne \underline{u})= { \rm Pr}( \underline{z} \ne \underline{c}) = { \rm Pr}( f >t) \hspace{0.05cm}.</math>
+
::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \ne \underline{u})= { \rm Pr}( \underline{z} \ne \underline{c}) = { \rm Pr}( f >t) \hspace{0.05cm}.</math>
  
Aufgrund der BDD&ndash;Annahme ergibt sich das gleiche einfache Ergebnis wie für die binären Blockcodes, nämlich die Wahrscheinlichkeit dafür, dass die Anzahl <i>f</i> der Fehler im Block (Empfangswort) größer ist als die Korrekturfähigkeit $t$ des Codes. Da  für die Zufallsgröße $f$ (Fehleranzahl) eine [[Stochastische_Signaltheorie/Binomialverteilung#Wahrscheinlichkeiten_der_Binomialverteilung| Binominalverteilung]] im Bereich $0 &#8804; f &#8804; n$ vorliegt, erhält man:
+
Aufgrund der BDD&ndash;Annahme ergibt sich das gleiche einfache Ergebnis wie für die binären Blockcodes,&nbsp; nämlich die Wahrscheinlichkeit dafür, dass  
 +
*die Anzahl&nbsp; $f$&nbsp; der Fehler im Block (Empfangswort) größer ist  
 +
 
 +
*als die Korrekturfähigkeit&nbsp; $t$&nbsp; des Codes.  
 +
 
 +
 
 +
Da  für die Zufallsgröße&nbsp; $f$&nbsp; $($Fehleranzahl in einem Block$)$&nbsp; eine&nbsp; [[Stochastische_Signaltheorie/Binomialverteilung#Wahrscheinlichkeiten_der_Binomialverteilung| "Binominalverteilung"]]&nbsp; im Bereich &nbsp; $0 &#8804; f &#8804; n$ &nbsp; vorliegt, erhält man:
  
 
::<math>{\rm Pr(Blockfehler)}  =
 
::<math>{\rm Pr(Blockfehler)}  =
 
\sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm}.</math>
 
\sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm}.</math>
  
Während aber im ersten Hauptkapitel stets $c_i &#8712; \rm GF(2)$ gegolten hat und damit die $f$ Übertragungsfehler jeweils Bitfehler waren, versteht man bei Reed&ndash;Solomon&ndash;Codierung unter einem Übertragungsfehler $(y_i \ne c_i)$ wegen $c_i &#8712; {\rm GF}(2^m)$ sowie $y_i &#8712; {\rm GF}(2^m)$ einen <i>Symbolfehler</i>. Damit ergeben sich folgende Unterschiede:
+
*Während aber im ersten Hauptkapitel stets&nbsp; $c_i &#8712; \rm GF(2)$&nbsp; gegolten hat und damit die&nbsp; $f$&nbsp; Übertragungsfehler jeweils&nbsp; '''Bitfehler''' waren,  
*Das diskrete Kanalmodell zur Beschreibung der binären Blockcodes ist der [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| ''Binary Symmetric Channel'']] (BSC). Jedes Bit $c_i$ eines Codewortes wird mit der Wahrscheinlichkeit $\varepsilon$ verfälscht $(y_i \ne c_i)$ und mit der Wahrscheinlichkeit $1-\varepsilon$  richtig übertragen $(y_i = c_i)$.<br>
+
 
 +
*versteht man bei Reed&ndash;Solomon&ndash;Codierung unter einem Übertragungsfehler&nbsp; $(y_i \ne c_i)$&nbsp; wegen&nbsp; $c_i &#8712; {\rm GF}(2^m)$&nbsp; sowie&nbsp; $y_i &#8712; {\rm GF}(2^m)$&nbsp; stets einen '''Symbolfehler'''.  
  
*Bei Reed&ndash;Solomon&ndash;Codierung muss man das BSC&ndash;Modell durch das $m$&ndash;BSC&ndash;Kanalmodell ersetzen. Ein Symbol $c_i$ wird mit der Wahrscheinlichkeit $\varepsilon_{\rm S}$ in ein anderes Symbol $y_i$ verfälscht (egal, in welches) und kommt mit der Wahrscheinlichkeit $1-\varepsilon_{\rm S}$ unverfälscht beim Empfänger an.<br><br>
+
Damit ergeben sich folgende Unterschiede:
 +
*Das diskrete Kanalmodell zur Beschreibung der binären Blockcodes ist der&nbsp; [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| ''Binary Symmetric Channel'']]&nbsp; (BSC). Jedes Bit&nbsp; $c_i$&nbsp; eines Codewortes wird mit der Wahrscheinlichkeit&nbsp; $\varepsilon$&nbsp; verfälscht&nbsp; $(y_i \ne c_i)$ und mit der Wahrscheinlichkeit&nbsp; $1-\varepsilon$&nbsp;  richtig übertragen&nbsp; $(y_i = c_i)$.<br>
 +
 
 +
*Bei Reed&ndash;Solomon&ndash;Codierung muss man das BSC&ndash;Modell durch das&nbsp; $m$&ndash;BSC&ndash;Kanalmodell ersetzen. Ein Symbol&nbsp; $c_i$&nbsp; wird mit der Wahrscheinlichkeit&nbsp; $\varepsilon_{\rm S}$&nbsp; in ein anderes Symbol&nbsp; $y_i$&nbsp; verfälscht (egal, in welches) und kommt mit der Wahrscheinlichkeit&nbsp; $1-\varepsilon_{\rm S}$&nbsp; unverfälscht beim Empfänger an.<br><br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 1:}$&nbsp;  
 
$\text{Beispiel 1:}$&nbsp;  
Wir gehen vom BSC&ndash;Parameter $\varepsilon = 0.1$ aus und betrachten Reed&ndash;Solomon&ndash;Codesymbole $c_i &#8712; {\rm GF}(2^8)$ &nbsp; &#8658; &nbsp;  $m = 8$, $q = 256$,  $n = 255$.  
+
Wir gehen vom BSC&ndash;Parameter&nbsp; $\varepsilon = 0.1$&nbsp; aus und betrachten Reed&ndash;Solomon&ndash;Codesymbole&nbsp; $c_i &#8712; {\rm GF}(2^8)$ &nbsp; &#8658; &nbsp;  $m = 8$, $q = 256$,&nbsp; $n = 255$.  
  
Für eine Symbolverfälschung $(y_i \ne c_i)$ genügt bereits ein falsches Bit. Oder anders ausgedrückt: Soll $y_i = c_i$ gelten, so müssen alle $m = 8$ Bit des Codesymbols richtig übertragen werden:
+
Für eine Symbolverfälschung&nbsp; $(y_i \ne c_i)$&nbsp; genügt bereits ein falsches Bit. Oder anders ausgedrückt: &nbsp; Soll&nbsp; $y_i = c_i$&nbsp; gelten, so müssen alle&nbsp; $m = 8$ Bit&nbsp; des Codesymbols richtig übertragen werden:
  
 
::<math>1 - \varepsilon_{\rm S} = (1 - \varepsilon)^m = 0.9^8 \approx 0.43
 
::<math>1 - \varepsilon_{\rm S} = (1 - \varepsilon)^m = 0.9^8 \approx 0.43
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
*Damit ergibt sich für das 8&ndash;BSC&ndash;Modell die Verfälschungswahrscheinlichkeit $\varepsilon_{\rm S}  &asymp; 0.57$.  
+
*Damit ergibt sich für das 8&ndash;BSC&ndash;Modell die Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon_{\rm S}  &asymp; 0.57$.  
*Mit der weiteren Annahme, dass die Verfälschung von $c_i  = \beta$ in jedes andere Symbol $y_i  = \gamma \ne \beta$ gleichwahrscheinlich ist, erhält man ${\rm Pr}(y_i  = \gamma\hspace{0.05cm}\vert \hspace{0.05cm}c_i  = \beta = 0.57/255 &asymp; 0.223\%$.}}<br>
+
*Mit der weiteren Annahme, dass die Verfälschung von&nbsp; $c_i  = \beta$&nbsp; in jedes andere Symbol&nbsp; $y_i  = \gamma \ne \beta$&nbsp; gleichwahrscheinlich ist, erhält man:
 +
:$${\rm Pr}(y_i  = \gamma\hspace{0.05cm}\vert \hspace{0.05cm}c_i  = \beta) = 0.57/255 &asymp; 0.223\%.$$}}<br>
  
 
== Anwendung der Reed–Solomon–Codierung bei binären Kanälen ==
 
== Anwendung der Reed–Solomon–Codierung bei binären Kanälen ==
 
<br>
 
<br>
Die Voraussetzungen für die folgende Berechnung der Blockfehlerwahrscheinlichkeit eines Systems mit Reed&ndash;Solomon&ndash;Codierung und Umsetzung auf Binärsymbole sind in der Grafik zusammenge-fasst:
+
Die Voraussetzungen für die folgende Berechnung der Blockfehlerwahrscheinlichkeit eines Systems mit Reed&ndash;Solomon&ndash;Codierung und Umsetzung auf Binärsymbole sind in der Grafik zusammengefasst:
*Angenommen wird eine (<i>n</i>, <i>k</i>)&ndash;Reed&ndash;Solomon&ndash;Codierung mit Symbolen aus GF(2<sup>m</sup>). Je kleiner die Coderate <i>R</i> = <i>k</i>/<i>n</i> ist, um so weniger Information kann bei fester Datenrate übertragen werden.<br>
+
*Angenommen wird eine&nbsp; $(n, k)$&ndash;Reed&ndash;Solomon&ndash;Codierung mit Symbolen aus&nbsp; $c_i &#8712; {\rm GF}(2^m)$. Je kleiner die Coderate&nbsp; $R=k/n$&nbsp; ist, um so weniger Information kann bei fester Datenrate übertragen werden.<br>
  
*Jedes Symbol wird durch <i>m</i> Bit binär dargestellt &nbsp;&#8658;&nbsp; <i>Binär&ndash;Mapping</i>. Ein Block (Codewort <u><i>c</i></u>) besteht somit aus <i>n</i> Symbolen bzw. aus <i>n</i> &middot; <i>m</i> Binärzeichen (Bit), die  in <u><i>c</i></u><sub>bin</sub> zusammengefasst sind.<br>
+
*Jedes Symbol wird durch&nbsp; $m$&nbsp; Bit binär dargestellt &nbsp; &#8658; &nbsp; <i>Binär&ndash;Mapping</i>. Ein Block&nbsp; $($Codewort &nbsp;$\underline {c} )$&nbsp; besteht somit aus&nbsp; $n$&nbsp; Symbolen bzw. aus&nbsp; $n \cdot m$&nbsp; Binärzeichen (Bit), die  in&nbsp;  $\underline {c}_{\rm bin} $&nbsp; zusammengefasst werden.<br>
  
*Vorausgesetzt wird  außerdem der [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang AWGN&ndash;Kanal,] gekennzeichnet durch den Parameter <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>. Entsprechend diesem Kanalmodell geschieht die Übertragung bipolar: &bdquo;0&rdquo;&nbsp;&#8596;&nbsp;&nbsp;&bdquo;+1&rdquo;,&nbsp;&bdquo;1&rdquo;&nbsp;&#8596;&nbsp;&nbsp;&bdquo;&ndash;1&rdquo;.<br>
+
*Vorausgesetzt wird  außerdem der&nbsp; [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang |AWGN&ndash;Kanal]], gekennzeichnet durch den Parameter&nbsp; $E_{\rm B}/N_0 $. Entsprechend diesem Kanalmodell geschieht die Übertragung bipolar: &nbsp; &bdquo;0&rdquo; &nbsp; &#8596; &nbsp; $+1$&nbsp; sowie  &bdquo;1&rdquo; &nbsp; &#8596; $-1$.  
  
*Der Empfänger trifft harte Entscheidungen (<i>Hard Decision</i>) auf Bitebene. Vor der Decodierung inclusive der Fehlerkorrektur werden die Binärsymbole wieder auf GF(2<sup>m</sup>)&ndash;Symbole umgesetzt.<br>
+
*Der Empfänger trifft harte Entscheidungen (<i>Hard Decision</i>&nbsp;) auf Bitebene. Vor der Decodierung inclusive der Fehlerkorrektur werden die Binärsymbole wieder auf&nbsp; ${\rm GF}(2^m)$&ndash;Symbole umgesetzt.<br>
  
:[[Datei:P ID2565 KC T 2 6 S2a v2.png|center|frame|Anwendung der Reed–Solomon–Codierung bei Binärkanälen|class=fit]]
 
  
 +
[[Datei:P ID2565 KC T 2 6 S2a v2.png|right|frame|Anwendung der Reed–Solomon–Codierung bei Binärkanälen|class=fit]]
 
Die auf der letzten Seite angegebene Gleichung (gültig für <i>Bounded Distance Decoding</i>),
 
Die auf der letzten Seite angegebene Gleichung (gültig für <i>Bounded Distance Decoding</i>),
 
+
::<math>{\rm Pr(Blockfehler)}  =
:<math>{\rm Pr(Blockfehler)}  =
 
 
\sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm},</math>
 
\sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm},</math>
  
basiert auf dem <i>m</i>&ndash;BSC&ndash;Kanal. Ausgehend vom AWGN&ndash;Kanal kommt man
+
basiert auf dem $m$&ndash;BSC&ndash;Kanal. Ausgehend vom AWGN&ndash;Kanal (''Additive White Gaussian Noise '') kommt man
*mit dem [[komplementären Gaußschen Fehlerintegral Please add link and do not upload flash videos.]] Q(<i>x</i>) zum BSC&ndash;Parameter
+
*mit dem [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|komplementären Gaußschen Fehlerintegral]] ${\rm Q}(x)$ zum BSC&ndash;Parameter
  
 
::<math>\varepsilon = {\rm Q} \big (\sqrt{2 \cdot E_{\rm S}/N_0} \big )  
 
::<math>\varepsilon = {\rm Q} \big (\sqrt{2 \cdot E_{\rm S}/N_0} \big )  
Zeile 63: Zeile 73:
 
\hspace{0.05cm},</math>
 
\hspace{0.05cm},</math>
  
*und daraus zur Verfälschungswahrscheinlichkeit <i>&epsilon;</i><sub>S</sub> auf Symbolebene:
+
*daraus zur Verfälschungswahrscheinlichkeit $\varepsilon_{\rm S}$ auf Symbolebene:
  
 
::<math>\varepsilon_{\rm S} = 1 - (1 - \varepsilon)^m  
 
::<math>\varepsilon_{\rm S} = 1 - (1 - \varepsilon)^m  
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
{{Beispiel}}''':''' Für <i>R</i> = <i>k</i>/<i>n</i> = 239/255 = 0.9373, 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> = 7 dB &nbsp;&#8658;&nbsp; <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> &asymp; 5  und <i>n</i> = 2<sup>8</sup> &ndash; 1 &nbsp;&#8658;&nbsp; <i>m</i> = 8 erhält man für den Parameter <i>&epsilon;</i><sub>S</sub> des 8&ndash;BSC&ndash;Modells:
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 2:}$&nbsp; Man erhält mit
 +
*&nbsp;$R=k/n = 239/255 = 0.9373$,  
 +
*&nbsp;$10 \cdot \lg \ E_{\rm B}/N_0 = 7 \, \rm dB$ &nbsp; &#8658; &nbsp; $E_{\rm B}/N_0 &asymp; 5$,&nbsp; und
 +
*&nbsp; $n = 2^8-1&nbsp; &#8658; &nbsp; $m = 8$
  
:<math>\varepsilon = {\rm Q} \big (\sqrt{2 \cdot 0.9373 \cdot 5} \big ) =  {\rm Q} \big (3.06\big ) \approx 1.1 \cdot 10^{-3}
 
\hspace{0.05cm}</math>
 
  
:<math>\Rightarrow\hspace{0.3cm}  \varepsilon_{\rm S} = 1 - (1 - 1.1 \cdot 10^{-3})^8 = 1 - 0.9989^8 = 1 - 0.9912 \approx 0.88 \cdot 10^{-2}
+
für die Parameter&nbsp; $\varepsilon$&nbsp; des BSC&ndash;Modells&nbsp; sowie&nbsp; $\varepsilon_{\rm S}$&nbsp; des 8&ndash;BSC&ndash;Modells folgende Zahlenwerte:
\hspace{0.05cm}.</math>
 
  
Jedes einzelne Symbol wird also mit mehr als 99&ndash;prozentiger Wahrscheinlichkeit fehlerfrei übertragen.{{end}}<br>
+
:$$\varepsilon = {\rm Q} \big (\sqrt{2 \cdot 0.9373 \cdot 5} \big ) =  {\rm Q} \big (3.06\big ) \approx 1.1 \cdot 10^{-3}=0.11 \cdot \%$$
  
== Anwendung der Reed–Solomon–Codierung bei binären Kanälen (2) ==
+
:$$\Rightarrow\hspace{0.3cm}  \varepsilon_{\rm S} = 1 - (1 - 1.1 \cdot 10^{-3})^8 = 1 - 0.9989^8 = 1 - 0.9912 \approx 0.88 \cdot \%
<br>
+
\hspace{0.2cm}(\approx 8 \cdot \varepsilon)\hspace{0.05cm}.$$
Die folgende Grafik zeigt die in [Liv10]<ref>Liva, G.: ''Channel Coding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.</ref> angegebenen Blockfehlerwahrscheinlichkeiten in Abhängigkeit des AWGN&ndash;Quotienten 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>). Dargestellt sind die berechneten Kurvenverläufe Pr(<u><i>&upsilon;</i></u> &ne; <u><i>u</i></u>) für zwei verschiedene Reed&ndash;Solomon&ndash;Codes entsprechend den <i>Deep Space Standards</i> nach CCSDS (<i>Consultative Committee for Space Data Systems</i>), nämlich
 
  
*der RSC (255, 239,17)<sub>256</sub>, der bis zu <i>t</i> = 8 Fehler korrigieren kann,<br>
+
Jedes einzelne Symbol wird also mit mehr als $99$&ndash;prozentiger Wahrscheinlichkeit fehlerfrei übertragen.}}<br>
  
*der RSC (255, 223, 33)<sub>256</sub> mit höherer Korrekturfähigkeit (<i>t</i> = 16) aufgrund kleinerer Coderate.<br>
+
== BER der Reed–Solomon–Codierung bei binären Kanälen ==
 +
<br>
 +
Die folgende Grafik zeigt die in&nbsp; [Liv10]<ref name='Liv10'>Liva, G.: ''Channel Coding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.</ref>&nbsp; angegebenen Blockfehlerwahrscheinlichkeiten in Abhängigkeit des AWGN&ndash;Quotienten&nbsp; $10 \cdot \lg  \ E_{\rm B}/N_0$.
 +
[[Datei:P ID2566 KC T 2 6 S2b v1.png|righr|frame|Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge&nbsp; $n = 255$|class=fit]]
 +
Dargestellt sind die berechneten Kurvenverläufe&nbsp; ${ \rm Pr}( \underline{v} \ne \underline{u})$&nbsp; für zwei verschiedene Reed&ndash;Solomon&ndash;Codes entsprechend den <i>Deep Space Standards</i>&nbsp; nach CCSDS (<i>Consultative Committee for Space Data Systems</i>), nämlich
  
:[[Datei:P ID2566 KC T 2 6 S2b v1.png|Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge <i>n</i> = 255|class=fit]]<br>
+
*dem&nbsp; $\text{RSC (255, 239, 17)}_{256}$&nbsp; mit&nbsp; $R=0.9373$, der bis zu&nbsp; $t = 8$&nbsp; Fehler korrigieren kann, und<br>
 +
*dem&nbsp; $\text{RSC (255, 223, 33)}_{256}$&nbsp; mit höherer Korrekturfähigkeit&nbsp; $(t = 16)$&nbsp; aufgrund kleinerer Coderate.
  
Wir analysieren den in der Grafik gelb hinterlegten Punkt, gültig für
 
*den RSC (255, 239, 17)<sub>256</sub>, und<br>
 
  
*10&nbsp;&middot;&nbsp;lg&nbsp;<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>&nbsp;=&nbsp;7.1&nbsp;dB&nbsp;&#8658;&nbsp;<i>&epsilon;</i><sub>S</sub>&nbsp;=&nbsp;0.007.<br><br>
+
''Hinweis'': &nbsp; Die nachfolgend nur angedeutete Berechnung sollen Sie in der&nbsp; [[Aufgaben:Aufgabe_2.15:_RS-Blockfehlerwahrscheinlichkeit_bei_AWGN|Aufgabe 2.15]]&nbsp; für den&nbsp; $\text{RSC (7, 3, 5)}_{8}$&nbsp; &ndash; also für etwas übersichtlichere Parameter &ndash; vollständig durchführen.
 +
<br clear=all>  
 +
Wir analysieren den in der Grafik gelb hinterlegten Punkt, gültig für den&nbsp; $\text{RSC (255, 239, 17)}_{256}$&nbsp; und&nbsp; $10 \cdot \lg  \ E_{\rm B}/N_0 = 7.1 \,\rm dB$ &nbsp; &#8658; &nbsp; $\varepsilon = 0.007$. Die dazugehörige Blockfehlerwahrscheinlichkeit ergibt sich entsprechend der Grafik zu
  
Die dazugehörige Blockfehlerwahrscheinlichkeit ergibt sich entsprechend der Grafik zu
+
::<math>{\rm Pr(Blockfehler)}  =
 
 
:<math>{\rm Pr(Blockfehler)}  =
 
 
\sum_{f =9}^{255} {255 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{255-f}\approx 10^{-4} \hspace{0.05cm}.</math>
 
\sum_{f =9}^{255} {255 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{255-f}\approx 10^{-4} \hspace{0.05cm}.</math>
  
Dominant ist hierbei der erste Term (für <i>f</i> = 9), der bereits etwa 80% ausmacht:
+
Dominant ist hierbei der erste Term&nbsp; $($für&nbsp; $f=9)$, der bereits etwa&nbsp; $80\%$&nbsp; ausmacht:
  
:<math>{255 \choose 9} \approx 1.1 \cdot 10^{16}\hspace{0.05cm},\hspace{0.15cm}
+
::<math>{255 \choose 9} \approx 1.1 \cdot 10^{16}\hspace{0.05cm},\hspace{0.15cm}
 
\varepsilon_{\rm S}^9 \approx 4 \cdot 10^{-20}\hspace{0.05cm},\hspace{0.15cm}
 
\varepsilon_{\rm S}^9 \approx 4 \cdot 10^{-20}\hspace{0.05cm},\hspace{0.15cm}
 
(1 -\varepsilon_{\rm S})^{246} \approx 0.18  
 
(1 -\varepsilon_{\rm S})^{246} \approx 0.18  
Zeile 108: Zeile 121:
 
Dies soll als Beleg dafür gelten, dass man die Summation schon nach wenigen Termen abbrechen darf.<br>
 
Dies soll als Beleg dafür gelten, dass man die Summation schon nach wenigen Termen abbrechen darf.<br>
  
Die hier nur angedeutete Berechnung sollen Sie in der Aufgabe A2.15 für den RSC (7, 3, 5)<sub>8</sub> &ndash; also für etwas übersichtlichere Parameter &ndash; vollständig durchführen.<br>
 
 
== Anwendung der Reed–Solomon–Codierung bei binären Kanälen (3) ==
 
<br>
 
 
Die in der Grafik dargestellten Ergebnisse kann man wie folgt zusammenfassen:
 
Die in der Grafik dargestellten Ergebnisse kann man wie folgt zusammenfassen:
*Für kleines <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> (des AWGN&ndash;Kanals) sind die Reed&ndash;Solomon&ndash;Codes völlig ungeeignet. Beide Codes liegen für 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>  < 6 dB über der Vergleichskurve für uncodierte Übertragung.<br>
+
*Für kleines&nbsp; $E_{\rm B}/N_0$&nbsp; (des AWGN&ndash;Kanals) sind die Reed&ndash;Solomon&ndash;Codes völlig ungeeignet. Beide Codes liegen für&nbsp; $10 \cdot \lg \ E_{\rm B}/N_0 < 6 \,\rm dB$&nbsp; über der (schwarzen) Vergleichskurve für uncodierte Übertragung.<br>
  
*Die Berechung für den RSC (255, 223, 33)<sub>256</sub> unterscheidet sich von obiger Rechnung nur in der unteren Summationsgrenze (<i>f</i><sub>min</sub> = 17) und   (wegen <i>R</i>&nbsp;=&nbsp;0.8745) durch ein etwas größeres <i>&epsilon;</i><sub>S</sub>.<br>
+
*Die Berechung für den&nbsp; $\text{RSC (255, 223, 33)}_{256}$&nbsp; unterscheidet sich von obiger Rechnung nur in der unteren Summationsgrenze&nbsp; $(f_{\rm min} = 17)$&nbsp; und durch ein etwas größeres&nbsp; $\varepsilon_{\rm S}$ &nbsp;$($wegen &nbsp;$R = 0.8745)$.<br>
  
*Dieser (<i>t</i> = 16)&ndash;Code ist für BER = 10<sup>&ndash;6</sup> auch nur weniger als 1 dB besser als der durch grüne Kreuze gekennzeichnete Code mit <i>t</i> = 8. Die Ergebnisse beider Codes sind eher enttäuschend.<br>
+
*Dieser &bdquo;rote&rdquo; Code&nbsp; $($mit&nbsp; $t = 16)$&nbsp; ist für&nbsp; $\rm BER = 10^{-6}$&nbsp; auch nur um etwa&nbsp; $1 \, \rm dB$&nbsp; besser als der durch grüne Kreuze gekennzeichnete Code mit&nbsp; $t = 8$. Die Ergebnisse beider Codes sind also eher enttäuschend.<br>
  
:[[Datei:P ID2582 KC T 2 6 S2b v1.png|center|frame|Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge <i>n</i> = 255|class=fit]]
 
  
Allgemein gilt:
+
{{BlaueBox|TEXT= 
*Reed&ndash;Solomon&ndash;Codes sind beim gedächtnislosen Binärkanal (AWGN&ndash;Kanal) nicht sehr gut. Beide Codes liegen mehr als 4 dB von der informationstheoretischen [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#AWGN.E2.80.93Kanalkapazit.C3.A4t_f.C3.BCr_bin.C3.A4re_Eingangssignale Shannon&ndash;Grenze] entfernt.<br>
+
$\text{Fazit:}$&nbsp;
 +
*Reed&ndash;Solomon&ndash;Codes sind beim gedächtnislosen Binärkanal (AWGN&ndash;Kanal) nicht sehr gut. Beide Codes liegen mehr als&nbsp; $4 \, \rm dB$&nbsp; von der informationstheoretischen&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#AWGN.E2.80.93Kanalkapazit.C3.A4t_f.C3.BCr_bin.C3.A4re_Eingangssignale| Shannon&ndash;Grenze]]&nbsp; entfernt.<br>
  
*Reed&ndash;Solomon&ndash;Codes sind dagegen sehr wirkungsvoll bei so genannten [http://www.lntwww.de/Digitalsignal%C3%BCbertragung/B%C3%BCndelfehlerkan%C3%A4le#Kanalmodell_nach_Gilbert.E2.80.93Elliott_.281.29 Bündelfehlerkanälen.] Sie werden deshalb vorwiegend bei Fadingkanälen, Speichersysteme, usw. eingesetzt.<br><br>
+
*Reed&ndash;Solomon&ndash;Codes sind dagegen sehr wirkungsvoll bei so genannten&nbsp; [[Digitalsignal%C3%BCbertragung/B%C3%BCndelfehlerkan%C3%A4le| Bündelfehlerkanälen]]. Sie werden deshalb vorwiegend bei Fadingkanälen, Speichersysteme, usw. eingesetzt.<br>
 +
*Die Reed&ndash;Solomon&ndash;Codes sind nicht perfekt. Welche Konsequenzen sich daraus ergeben, wird in der&nbsp; [[Aufgaben:Aufgabe_2.16:_Entscheidungskriterien_bei_BDD|Aufgabe 2.16]]&nbsp; behandelt.}}<br>
  
<b>Hinweis:</b> Die Reed&ndash;Solomon&ndash;Codes sind nicht perfekt. Welche Konsequenzen sich daraus ergeben, wird in der Aufgabe A2.16 behandelt.<br>
+
== Typische Anwendungen mit Reed–Solomon–Codierung==
 +
<br>
 +
[[Datei:P ID2575 KC T 2 6 S3a v2.png|right|frame|Codeschema mit Kaskadierung|class=fit]]
 +
Reed&ndash;Solomon&ndash;Codierung wird häufig entsprechend der Grafik zusammen mit einem <i>inneren Code</i>&nbsp; in kaskadierter Form angewandt.
  
== Typische Anwendungen mit Reed–Solomon–Codierung (1) ==
+
*Der innere Code ist fast immer ein Binärcode und in der Satelliten&ndash; und Mobilkommunikation oft ein Faltungscode.
<br>
+
Reed&ndash;Solomon&ndash;Codierung wird häufig entsprechend der Grafik zusammen mit einem <i>inneren Code</i> in kaskadierter Form angewandt. Der innere Code ist fast immer ein Binärcode und in der Satelliten&ndash; und Mobilkommunikation oft ein Faltungscode. Will man nur die Reed&ndash;Solomon&ndash;Codierung/Decodierung untersuchen, so ersetzt man in einer Simulation die grau hinterlegten Komponenten durch einen einzigen Block, den man <i>Super Channel</i> nennt.<br>
+
*Will man nur die Reed&ndash;Solomon&ndash;Codierung/Decodierung untersuchen, so ersetzt man in einer Simulation die grau hinterlegten Komponenten durch einen einzigen Block, den man &bdquo;Super Channel&rdquo; nennt.<br>
 +
<br clear=all>
 +
Besonders effizient ist ein solches&nbsp; <b>verkettetes</b> &nbsp;(englisch: <i>concatenated</i>) <b>Codiersystem</b>, wenn zwischen den beiden Codierern ein Interleaver geschaltet ist, um Bündelfehler weiter zu entspreizen.<br>
  
[[Datei:P ID2575 KC T 2 6 S3a v2.png|center|frame|Codeschema mit Kaskadierung|class=fit]]
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 3:}$&nbsp; Die Grafik zeigt beispielhaft einen solchen Interleaver, wobei wir uns auf eine&nbsp; $20 &times; 4$&ndash;Matrix beschränken. In der Praxis sind diese Matrizen deutlich größer.<br>
  
Besonders effizient ist ein solches <b>verkettetes</b> (englisch: <i>concatenated</i>) <b>Codiersystem</b>, wenn zwischen den beiden Codierern ein Interleaver geschaltet ist, um Bündelfehler weiter zu entspreizen.<br>
+
[[Datei:P ID2579 KC T 2 6 S3b v2.png|right|frame|Interleaver–Matrix für&nbsp; $20 &times; 4$ Symbole|class=fit]]
  
{{Beispiel}}''':''' Die Grafik zeigt beispielhaft einen solchen Interleaver, wobei wir uns auf eine 20 &times; 4 Matrix beschränken. In der Praxis sind diese Matrizen deutlich größer.<br>
 
  
[[Datei:P ID2579 KC T 2 6 S3b v2.png|Interleaver–Matrix für 20x4 Symbole|class=fit]]<br>
 
  
 
Der Interleaver wird zeilenweise beschrieben und spaltenweise ausgelesen (blaue Beschriftung). Beim De&ndash;Interleaver  (grüne Beschriftung) ist die Reihenfolge genau umgekehrt.
 
Der Interleaver wird zeilenweise beschrieben und spaltenweise ausgelesen (blaue Beschriftung). Beim De&ndash;Interleaver  (grüne Beschriftung) ist die Reihenfolge genau umgekehrt.
 
*Die Reed&ndash;Solomon&ndash;Symbole werden also nicht fortlaufend an den inneren Coder weitergeleitet, sondern entsprechend der angegebenen Reihenfolge als Symbol 1, 21, 41, 61, 2, 22, usw. .<br>
 
*Die Reed&ndash;Solomon&ndash;Symbole werden also nicht fortlaufend an den inneren Coder weitergeleitet, sondern entsprechend der angegebenen Reihenfolge als Symbol 1, 21, 41, 61, 2, 22, usw. .<br>
  
*Auf dem Kanal wird ein zusammenhängender Bereich (hier die Symbole 22, 42, 62, 3, 23 &#8658; rot umrandetes Rechteck) zerstört, z. B. durch einen Kratzer auf dem Kanal &bdquo;Speichermedium&rdquo;.<br>
+
*Auf dem Kanal wird ein zusammenhängender Bereich (hier die Symbole 42, 62, 3, 23, 43, 63, 4, 24 &nbsp; &#8658; &nbsp;  um das unten rot umrandete Rechteck) zerstört, zum Beispiel durch einen Kratzer auf dem Kanal &bdquo;Speichermedium&rdquo;.<br>
  
*Nach dem De&ndash;Interleaving ist die Symbolreihenfolge wieder 1, 2, 3, ... Man erkennt an den rot umrandeten Kreisen, dass nun dieses Fehlerbündel weitgehend &bdquo;aufgebrochen&rdquo; wurde.{{end}}<br>
+
*Nach dem De&ndash;Interleaving ist die Symbolreihenfolge wieder 1, 2, 3, ... &nbsp; &nbsp; Man erkennt an den rot umrandeten Kreisen, dass nun dieses Fehlerbündel weitgehend &bdquo;aufgebrochen&rdquo; wurde.}}
  
== Typische Anwendungen mit Reed–Solomon–Codierung (2) ==
 
<br>
 
Eine sehr weit verbreitete Anwendung von Reed&ndash;Solomon&ndash;Codierung &ndash; und zudem die kommerziell erfolgreichste &ndash; ist die <b>Compact Disc</b> (CD), deren Fehlerkorrekturmechanismus bereits im [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_einf.C3.BChrende_Beispiele_.283.29 Kapitel 1.1] dieses Buches beschrieben wurde. Hier ist der innere Code ebenfalls ein Reed&ndash;Solomon&ndash;Code, und das verkette Codiersystem lässt sich wie folgt beschreiben:
 
*Beide Kanäle des Stereo&ndash;Audiosignals werden mit je 44.1 kHz abgetastet und jeder einzelne Abtastwert wird mit 32 Bit (4 Byte) digital dargestellt.<br>
 
  
*Die Gruppierung von 6 Samples ergibt einen Rahmen (192 Bit) und damit 24 Codesymbole aus dem Galoisfeld  GF(2<sup>8</sup>). Jedes Codesymbol entspricht somit genau einem Byte.<br>
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 4:}$&nbsp; Eine sehr weit verbreitete Anwendung von Reed&ndash;Solomon&ndash;Codierung &ndash; und zudem die kommerziell erfolgreichste &ndash; ist die <i>Compact Disc</i>&nbsp; $\rm (CD)$, deren Fehlerkorrekturmechanismus bereits im&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Die_.E2.80.9EGeschlitzte_CD.E2.80.9D_.E2.80.93_eine_Demonstration_des_LNT_der_TUM| Einführungkapitel]]&nbsp; dieses Buches beschrieben wurde. Hier ist der innere Code ebenfalls ein Reed&ndash;Solomon&ndash;Code, und das verkette Codiersystem lässt sich wie folgt beschreiben:
 +
*Beide Kanäle des Stereo&ndash;Audiosignals werden mit je&nbsp; $\text{44.1 kHz}$&nbsp; abgetastet und jeder einzelne Abtastwert wird mit&nbsp; $32$&nbsp; Bit (vier Byte) digital dargestellt.<br>
 +
 
 +
*Die Gruppierung von sechs Samples ergibt einen Rahmen&nbsp; $(192$&nbsp; Bit$)$ und damit&nbsp; $24$&nbsp; Codesymbole aus dem Galoisfeld&nbsp; $\rm GF(2^8)$. Jedes Codesymbol entspricht somit genau einem Byte.<br>
  
*Der erste Reed&ndash;Solomon&ndash;Code mit der Rate <i>R</i><sub>1</sub> = 24/28 liefert 28 Byte, die einem Interleaver der Größe 28 &middot; 109 Byte zugeführt werden. Das Auslesen erfolgt (kompliziert) diagonal.<br>
+
*Der erste Reed&ndash;Solomon&ndash;Code mit der Rate&nbsp; $R_1 = 24/28$&nbsp; liefert&nbsp; $28$&nbsp; Byte, die einem Interleaver der Größe&nbsp; $28 &times; 109$&nbsp; Byte zugeführt werden. Das Auslesen erfolgt (kompliziert) diagonal.<br>
  
*Der Interleaver verteilt zusammenhängende Bytes großräumig über die gesamte Disk. Dadurch werden so genannte Bursts &bdquo;aufgelöst&rdquo;, die zum Beispiel durch Kratzer auf der CD herrühren.<br>
+
*Der Interleaver verteilt zusammenhängende Bytes großräumig über die gesamte Disk. Dadurch werden so genannte Bursts &bdquo;aufgelöst&rdquo;, die zum Beispiel durch Kratzer auf der&nbsp; $\rm CD$&nbsp; herrühren.<br>
  
*Zusammen mit dem zweiten Reed&ndash;Solomon&ndash;Code (Rate <i>R</i><sub>2</sub> = 28/32) ergibt sich eine Gesamtrate von <i>R</i> = (24/28) &middot; (28/32) = 3/4. Beide Codes können jeweils <i>t</i> = 2 Symbolfehler korrigieren.<br>
+
*Zusammen mit dem zweiten Reed&ndash;Solomon&ndash;Code&nbsp; $($Rate $R_2 =   28/32)$&nbsp; ergibt sich eine Gesamtrate von&nbsp; $R = (24/28) &middot; (28/32) = 3/4$. Beide Codes können jeweils&nbsp; $t = 2$&nbsp; Symbolfehler korrigieren.<br>
  
*Beide RS&ndash;Komponentencodes (28, 24, 5) und (32, 28, 5) basieren jeweils auf dem Galoisfeld GF(2<sup>8</sup>), was eigentlich eine Codelänge <i>n</i> = 255 bedeuten würde.<br>
+
*Die beiden Komponentencodes&nbsp; $\text{RSC (28, 24, 5)}$&nbsp; und&nbsp; $\text{RSC (32, 28, 5)}$&nbsp; basieren jeweils auf dem Galoisfeld&nbsp; $\rm GF(2^8)$, was eigentlich die Codelänge&nbsp; $n = 255$&nbsp; bedeuten würde.<br>
  
*Die hier benötigten kürzeren Komponentencodes ergeben sich aus aus dem RSC (255, 251, 5)<sub>256</sub> durch <i>Shortening</i>. Man sieht, dass dadurch die minimale Distanz <i>d</i><sub>min</sub> = 5 nicht verändert wird.<br>
+
*Die hier benötigten kürzeren Komponentencodes ergeben sich aus aus dem&nbsp; $\text{RSC (255, 251, 5)}_{256}$&nbsp; durch <i>Shortening</i> &nbsp; &rArr; &nbsp; siehe&nbsp; [[Aufgaben:Aufgabe_1.09Z:_Erweiterung_und/oder_Punktierung|Aufgabe 1.9Z]]. Durch diese Maßnahme wird aber die minimale Distanz&nbsp; $d_{\rm min}= 5$&nbsp; nicht verändert.<br>
  
*Mit der anschließenden Eight&ndash;to&ndash;Fourteen&ndash;Modulation und weiterer Kontrollsymbole kommt man schließlich zur endgültigen Coderate 192/588 &asymp; 0.326 der CD&ndash;Daten-komprimierung.<br><br>
+
*Mit der anschließenden&nbsp; [https://de.wikipedia.org/wiki/Eight-to-Fourteen-Modulation Eight&ndash;to&ndash;Fourteen&ndash;Modulation]&nbsp; und weiterer Kontrollsymbole kommt man schließlich zur endgültigen Coderate&nbsp; $ R = 192/588 &asymp; 0.326$&nbsp; der CD&ndash;Datenkomprimierung.<br><br>
  
Auf der Seite [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Die_.E2.80.9EGeschlitzte_CD.E2.80.9D_.E2.80.93_eine_Demonstration_des_LNT_der_TUM Geschlitzte CD] kann man sich anhand eines Audio&ndash;Beispiels von der Korrekturfähigkeit dieser <i>cross&ndash;interleaved Reed&ndash;Solomon&ndash;Codierung</i> überzeugen, aber auch deren Grenzen erkennen.<br>
+
Auf der Seite&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Die_.E2.80.9EGeschlitzte_CD.E2.80.9D_.E2.80.93_eine_Demonstration_des_LNT_der_TUM |Geschlitzte CD]]&nbsp; kann man sich anhand eines Audio&ndash;Beispiels von der Korrekturfähigkeit dieser <i>cross&ndash;interleaved Reed&ndash;Solomon&ndash;Codierung</i>&nbsp; überzeugen, aber auch deren Grenzen erkennen.}}<br>
  
 
== Aufgaben zum Kapitel==
 
== Aufgaben zum Kapitel==
 
<br>
 
<br>
[[Aufgaben:2.15 Pr(υ ≠ u) vs. EB/N0|A2.15 Pr(υ ≠ u) vs. EB/N0]]
+
[[Aufgaben:Aufgabe_2.15:_RS-Blockfehlerwahrscheinlichkeit_bei_AWGN|Aufgabe 2.15: RS-Blockfehlerwahrscheinlichkeit bei AWGN]]
  
[[Zusatzaufgaben:2.15 Nochmals Pr(υ ≠ u) für BDD]]
+
[[Aufgaben:Aufgabe_2.15Z:_Nochmals_RS-Blockfehlerwahrscheinlichkeit|Aufgabe 2.15Z: Nochmals RS-Blockfehlerwahrscheinlichkeit]]
  
[[Aufgaben:2.16 BDD–Entscheidungskriterien|A2.16 BDD–Entscheidungskriterien]]
+
[[Aufgaben:Aufgabe_2.16:_Entscheidungskriterien_bei_BDD|Aufgabe 2.16: Entscheidungskriterien bei BDD]]
  
 
==Quellenverzeichnis==
 
==Quellenverzeichnis==

Aktuelle Version vom 31. Oktober 2022, 17:47 Uhr

Blockfehlerwahrscheinlichkeit für RSC und BDD


Zur Fehlerwahrscheinlichkeitsberechnung gehen wir vom gleichen Modell wie im Kapitel  "Fehlerkorrektur nach Reed–Solomon–Codierung"  aus,  wobei wir uns hier für den Codewortschätzer   $(\underline {y} → \underline {z})$   auf  "Bounded Distance Decoding"  $\rm (BDD)$  beschränken.  Für  "Maximum Likelihood Decoding"  sind die Ergebnisse geringfügig besser.

Systemmodell mit Reed–Solomon–Codierung,  $m$–BSC  und  Bounded Distance Decoding

Die Blockfehlerwahrscheinlichkeit sei wie folgt definiert:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \ne \underline{u})= { \rm Pr}( \underline{z} \ne \underline{c}) = { \rm Pr}( f >t) \hspace{0.05cm}.\]

Aufgrund der BDD–Annahme ergibt sich das gleiche einfache Ergebnis wie für die binären Blockcodes,  nämlich die Wahrscheinlichkeit dafür, dass

  • die Anzahl  $f$  der Fehler im Block (Empfangswort) größer ist
  • als die Korrekturfähigkeit  $t$  des Codes.


Da für die Zufallsgröße  $f$  $($Fehleranzahl in einem Block$)$  eine  "Binominalverteilung"  im Bereich   $0 ≤ f ≤ n$   vorliegt, erhält man:

\[{\rm Pr(Blockfehler)} = \sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm}.\]
  • Während aber im ersten Hauptkapitel stets  $c_i ∈ \rm GF(2)$  gegolten hat und damit die  $f$  Übertragungsfehler jeweils  Bitfehler waren,
  • versteht man bei Reed–Solomon–Codierung unter einem Übertragungsfehler  $(y_i \ne c_i)$  wegen  $c_i ∈ {\rm GF}(2^m)$  sowie  $y_i ∈ {\rm GF}(2^m)$  stets einen Symbolfehler.

Damit ergeben sich folgende Unterschiede:

  • Das diskrete Kanalmodell zur Beschreibung der binären Blockcodes ist der  Binary Symmetric Channel  (BSC). Jedes Bit  $c_i$  eines Codewortes wird mit der Wahrscheinlichkeit  $\varepsilon$  verfälscht  $(y_i \ne c_i)$ und mit der Wahrscheinlichkeit  $1-\varepsilon$  richtig übertragen  $(y_i = c_i)$.
  • Bei Reed–Solomon–Codierung muss man das BSC–Modell durch das  $m$–BSC–Kanalmodell ersetzen. Ein Symbol  $c_i$  wird mit der Wahrscheinlichkeit  $\varepsilon_{\rm S}$  in ein anderes Symbol  $y_i$  verfälscht (egal, in welches) und kommt mit der Wahrscheinlichkeit  $1-\varepsilon_{\rm S}$  unverfälscht beim Empfänger an.

$\text{Beispiel 1:}$  Wir gehen vom BSC–Parameter  $\varepsilon = 0.1$  aus und betrachten Reed–Solomon–Codesymbole  $c_i ∈ {\rm GF}(2^8)$   ⇒   $m = 8$, $q = 256$,  $n = 255$.

Für eine Symbolverfälschung  $(y_i \ne c_i)$  genügt bereits ein falsches Bit. Oder anders ausgedrückt:   Soll  $y_i = c_i$  gelten, so müssen alle  $m = 8$ Bit  des Codesymbols richtig übertragen werden:

\[1 - \varepsilon_{\rm S} = (1 - \varepsilon)^m = 0.9^8 \approx 0.43 \hspace{0.05cm}.\]
  • Damit ergibt sich für das 8–BSC–Modell die Verfälschungswahrscheinlichkeit  $\varepsilon_{\rm S} ≈ 0.57$.
  • Mit der weiteren Annahme, dass die Verfälschung von  $c_i = \beta$  in jedes andere Symbol  $y_i = \gamma \ne \beta$  gleichwahrscheinlich ist, erhält man:
$${\rm Pr}(y_i = \gamma\hspace{0.05cm}\vert \hspace{0.05cm}c_i = \beta) = 0.57/255 ≈ 0.223\%.$$


Anwendung der Reed–Solomon–Codierung bei binären Kanälen


Die Voraussetzungen für die folgende Berechnung der Blockfehlerwahrscheinlichkeit eines Systems mit Reed–Solomon–Codierung und Umsetzung auf Binärsymbole sind in der Grafik zusammengefasst:

  • Angenommen wird eine  $(n, k)$–Reed–Solomon–Codierung mit Symbolen aus  $c_i ∈ {\rm GF}(2^m)$. Je kleiner die Coderate  $R=k/n$  ist, um so weniger Information kann bei fester Datenrate übertragen werden.
  • Jedes Symbol wird durch  $m$  Bit binär dargestellt   ⇒   Binär–Mapping. Ein Block  $($Codewort  $\underline {c} )$  besteht somit aus  $n$  Symbolen bzw. aus  $n \cdot m$  Binärzeichen (Bit), die in  $\underline {c}_{\rm bin} $  zusammengefasst werden.
  • Vorausgesetzt wird außerdem der  AWGN–Kanal, gekennzeichnet durch den Parameter  $E_{\rm B}/N_0 $. Entsprechend diesem Kanalmodell geschieht die Übertragung bipolar:   „0”   ↔   $+1$  sowie „1”   ↔ $-1$.
  • Der Empfänger trifft harte Entscheidungen (Hard Decision ) auf Bitebene. Vor der Decodierung inclusive der Fehlerkorrektur werden die Binärsymbole wieder auf  ${\rm GF}(2^m)$–Symbole umgesetzt.


Anwendung der Reed–Solomon–Codierung bei Binärkanälen

Die auf der letzten Seite angegebene Gleichung (gültig für Bounded Distance Decoding),

\[{\rm Pr(Blockfehler)} = \sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm},\]

basiert auf dem $m$–BSC–Kanal. Ausgehend vom AWGN–Kanal (Additive White Gaussian Noise ) kommt man

\[\varepsilon = {\rm Q} \big (\sqrt{2 \cdot E_{\rm S}/N_0} \big ) = {\rm Q} \big (\sqrt{2 \cdot R \cdot E_{\rm B}/N_0} \big ) \hspace{0.05cm},\]
  • daraus zur Verfälschungswahrscheinlichkeit $\varepsilon_{\rm S}$ auf Symbolebene:
\[\varepsilon_{\rm S} = 1 - (1 - \varepsilon)^m \hspace{0.05cm}.\]

$\text{Beispiel 2:}$  Man erhält mit

  •  $R=k/n = 239/255 = 0.9373$,
  •  $10 \cdot \lg \ E_{\rm B}/N_0 = 7 \, \rm dB$   ⇒   $E_{\rm B}/N_0 ≈ 5$,  und
  •   $n = 2^8-1$   ⇒   $m = 8$


für die Parameter  $\varepsilon$  des BSC–Modells  sowie  $\varepsilon_{\rm S}$  des 8–BSC–Modells folgende Zahlenwerte:

$$\varepsilon = {\rm Q} \big (\sqrt{2 \cdot 0.9373 \cdot 5} \big ) = {\rm Q} \big (3.06\big ) \approx 1.1 \cdot 10^{-3}=0.11 \cdot \%$$
$$\Rightarrow\hspace{0.3cm} \varepsilon_{\rm S} = 1 - (1 - 1.1 \cdot 10^{-3})^8 = 1 - 0.9989^8 = 1 - 0.9912 \approx 0.88 \cdot \% \hspace{0.2cm}(\approx 8 \cdot \varepsilon)\hspace{0.05cm}.$$

Jedes einzelne Symbol wird also mit mehr als $99$–prozentiger Wahrscheinlichkeit fehlerfrei übertragen.


BER der Reed–Solomon–Codierung bei binären Kanälen


Die folgende Grafik zeigt die in  [Liv10][1]  angegebenen Blockfehlerwahrscheinlichkeiten in Abhängigkeit des AWGN–Quotienten  $10 \cdot \lg \ E_{\rm B}/N_0$.

Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge  $n = 255$

Dargestellt sind die berechneten Kurvenverläufe  ${ \rm Pr}( \underline{v} \ne \underline{u})$  für zwei verschiedene Reed–Solomon–Codes entsprechend den Deep Space Standards  nach CCSDS (Consultative Committee for Space Data Systems), nämlich

  • dem  $\text{RSC (255, 239, 17)}_{256}$  mit  $R=0.9373$, der bis zu  $t = 8$  Fehler korrigieren kann, und
  • dem  $\text{RSC (255, 223, 33)}_{256}$  mit höherer Korrekturfähigkeit  $(t = 16)$  aufgrund kleinerer Coderate.


Hinweis:   Die nachfolgend nur angedeutete Berechnung sollen Sie in der  Aufgabe 2.15  für den  $\text{RSC (7, 3, 5)}_{8}$  – also für etwas übersichtlichere Parameter – vollständig durchführen.
Wir analysieren den in der Grafik gelb hinterlegten Punkt, gültig für den  $\text{RSC (255, 239, 17)}_{256}$  und  $10 \cdot \lg \ E_{\rm B}/N_0 = 7.1 \,\rm dB$   ⇒   $\varepsilon = 0.007$. Die dazugehörige Blockfehlerwahrscheinlichkeit ergibt sich entsprechend der Grafik zu

\[{\rm Pr(Blockfehler)} = \sum_{f =9}^{255} {255 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{255-f}\approx 10^{-4} \hspace{0.05cm}.\]

Dominant ist hierbei der erste Term  $($für  $f=9)$, der bereits etwa  $80\%$  ausmacht:

\[{255 \choose 9} \approx 1.1 \cdot 10^{16}\hspace{0.05cm},\hspace{0.15cm} \varepsilon_{\rm S}^9 \approx 4 \cdot 10^{-20}\hspace{0.05cm},\hspace{0.15cm} (1 -\varepsilon_{\rm S})^{246} \approx 0.18 \hspace{0.15cm} \Rightarrow \hspace{0.15cm} {\rm Pr}(f = 9) \approx 8 \cdot 10^{-5} \hspace{0.05cm}.\]

Dies soll als Beleg dafür gelten, dass man die Summation schon nach wenigen Termen abbrechen darf.

Die in der Grafik dargestellten Ergebnisse kann man wie folgt zusammenfassen:

  • Für kleines  $E_{\rm B}/N_0$  (des AWGN–Kanals) sind die Reed–Solomon–Codes völlig ungeeignet. Beide Codes liegen für  $10 \cdot \lg \ E_{\rm B}/N_0 < 6 \,\rm dB$  über der (schwarzen) Vergleichskurve für uncodierte Übertragung.
  • Die Berechung für den  $\text{RSC (255, 223, 33)}_{256}$  unterscheidet sich von obiger Rechnung nur in der unteren Summationsgrenze  $(f_{\rm min} = 17)$  und durch ein etwas größeres  $\varepsilon_{\rm S}$  $($wegen  $R = 0.8745)$.
  • Dieser „rote” Code  $($mit  $t = 16)$  ist für  $\rm BER = 10^{-6}$  auch nur um etwa  $1 \, \rm dB$  besser als der durch grüne Kreuze gekennzeichnete Code mit  $t = 8$. Die Ergebnisse beider Codes sind also eher enttäuschend.


$\text{Fazit:}$ 

  • Reed–Solomon–Codes sind beim gedächtnislosen Binärkanal (AWGN–Kanal) nicht sehr gut. Beide Codes liegen mehr als  $4 \, \rm dB$  von der informationstheoretischen  Shannon–Grenze  entfernt.
  • Reed–Solomon–Codes sind dagegen sehr wirkungsvoll bei so genannten  Bündelfehlerkanälen. Sie werden deshalb vorwiegend bei Fadingkanälen, Speichersysteme, usw. eingesetzt.
  • Die Reed–Solomon–Codes sind nicht perfekt. Welche Konsequenzen sich daraus ergeben, wird in der  Aufgabe 2.16  behandelt.


Typische Anwendungen mit Reed–Solomon–Codierung


Codeschema mit Kaskadierung

Reed–Solomon–Codierung wird häufig entsprechend der Grafik zusammen mit einem inneren Code  in kaskadierter Form angewandt.

  • Der innere Code ist fast immer ein Binärcode und in der Satelliten– und Mobilkommunikation oft ein Faltungscode.
  • Will man nur die Reed–Solomon–Codierung/Decodierung untersuchen, so ersetzt man in einer Simulation die grau hinterlegten Komponenten durch einen einzigen Block, den man „Super Channel” nennt.


Besonders effizient ist ein solches  verkettetes  (englisch: concatenated) Codiersystem, wenn zwischen den beiden Codierern ein Interleaver geschaltet ist, um Bündelfehler weiter zu entspreizen.

$\text{Beispiel 3:}$  Die Grafik zeigt beispielhaft einen solchen Interleaver, wobei wir uns auf eine  $20 × 4$–Matrix beschränken. In der Praxis sind diese Matrizen deutlich größer.

Interleaver–Matrix für  $20 × 4$ Symbole


Der Interleaver wird zeilenweise beschrieben und spaltenweise ausgelesen (blaue Beschriftung). Beim De–Interleaver (grüne Beschriftung) ist die Reihenfolge genau umgekehrt.

  • Die Reed–Solomon–Symbole werden also nicht fortlaufend an den inneren Coder weitergeleitet, sondern entsprechend der angegebenen Reihenfolge als Symbol 1, 21, 41, 61, 2, 22, usw. .
  • Auf dem Kanal wird ein zusammenhängender Bereich (hier die Symbole 42, 62, 3, 23, 43, 63, 4, 24   ⇒   um das unten rot umrandete Rechteck) zerstört, zum Beispiel durch einen Kratzer auf dem Kanal „Speichermedium”.
  • Nach dem De–Interleaving ist die Symbolreihenfolge wieder 1, 2, 3, ...     Man erkennt an den rot umrandeten Kreisen, dass nun dieses Fehlerbündel weitgehend „aufgebrochen” wurde.


$\text{Beispiel 4:}$  Eine sehr weit verbreitete Anwendung von Reed–Solomon–Codierung – und zudem die kommerziell erfolgreichste – ist die Compact Disc  $\rm (CD)$, deren Fehlerkorrekturmechanismus bereits im  Einführungkapitel  dieses Buches beschrieben wurde. Hier ist der innere Code ebenfalls ein Reed–Solomon–Code, und das verkette Codiersystem lässt sich wie folgt beschreiben:

  • Beide Kanäle des Stereo–Audiosignals werden mit je  $\text{44.1 kHz}$  abgetastet und jeder einzelne Abtastwert wird mit  $32$  Bit (vier Byte) digital dargestellt.
  • Die Gruppierung von sechs Samples ergibt einen Rahmen  $(192$  Bit$)$ und damit  $24$  Codesymbole aus dem Galoisfeld  $\rm GF(2^8)$. Jedes Codesymbol entspricht somit genau einem Byte.
  • Der erste Reed–Solomon–Code mit der Rate  $R_1 = 24/28$  liefert  $28$  Byte, die einem Interleaver der Größe  $28 × 109$  Byte zugeführt werden. Das Auslesen erfolgt (kompliziert) diagonal.
  • Der Interleaver verteilt zusammenhängende Bytes großräumig über die gesamte Disk. Dadurch werden so genannte Bursts „aufgelöst”, die zum Beispiel durch Kratzer auf der  $\rm CD$  herrühren.
  • Zusammen mit dem zweiten Reed–Solomon–Code  $($Rate $R_2 = 28/32)$  ergibt sich eine Gesamtrate von  $R = (24/28) · (28/32) = 3/4$. Beide Codes können jeweils  $t = 2$  Symbolfehler korrigieren.
  • Die beiden Komponentencodes  $\text{RSC (28, 24, 5)}$  und  $\text{RSC (32, 28, 5)}$  basieren jeweils auf dem Galoisfeld  $\rm GF(2^8)$, was eigentlich die Codelänge  $n = 255$  bedeuten würde.
  • Die hier benötigten kürzeren Komponentencodes ergeben sich aus aus dem  $\text{RSC (255, 251, 5)}_{256}$  durch Shortening   ⇒   siehe  Aufgabe 1.9Z. Durch diese Maßnahme wird aber die minimale Distanz  $d_{\rm min}= 5$  nicht verändert.
  • Mit der anschließenden  Eight–to–Fourteen–Modulation  und weiterer Kontrollsymbole kommt man schließlich zur endgültigen Coderate  $ R = 192/588 ≈ 0.326$  der CD–Datenkomprimierung.

Auf der Seite  Geschlitzte CD  kann man sich anhand eines Audio–Beispiels von der Korrekturfähigkeit dieser cross–interleaved Reed–Solomon–Codierung  überzeugen, aber auch deren Grenzen erkennen.


Aufgaben zum Kapitel


Aufgabe 2.15: RS-Blockfehlerwahrscheinlichkeit bei AWGN

Aufgabe 2.15Z: Nochmals RS-Blockfehlerwahrscheinlichkeit

Aufgabe 2.16: Entscheidungskriterien bei BDD

Quellenverzeichnis

  1. Liva, G.: Channel Coding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.