Channel Coding/Error Probability and Application Areas

1. Channel Coding
2. Reed–Solomon–Codes und deren Decodierung
3. Error Probability and Application Areas

• Previous page
• Next page

• Previous page
• Next page

Blockfehlerwahrscheinlichkeit für RSC und BDD

Zur Fehlerwahrscheinlichkeitsberechnung gehen wir vom gleichen Blockschaltbild wie im Kapitel 2.5 aus, wobei wir uns hier für den Codewortschätzer (y → z) auf Bounded Distance Decoding (BDD) beschränken. Für Maximum Likelihood Decoding sind die Ergebnisse geringfügig besser.

Die Blockfehlerwahrscheinlichkeit sei wie folgt definiert:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{\upsilon} \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, 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) 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 Kapitel 1 stets c_i ∈ GF(2) gegolten hat und damit die f Übertragungsfehler jeweils Bitfehler waren, versteht man bei Reed–Solomon–Codierung unter einem Übertragungsfehler (y_i ≠ c_i) wegen c_i ∈ GF(2^m) bzw. y_i ∈ GF(2^m) 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 ε verfälscht (y_i ≠ c_i) und mit der Wahrscheinlichkeit 1 – ε richtig übertragen (y_i = c_i).
  

• Bei Reed–Solomon–Codierung muss das BSC–Modell durch das m–BSC–Kanalmodell ersetzt werden. Ein Symbol c_i wird mit der Wahrscheinlichkeit ε_S in ein anderes Symbol y_i verfälscht (egal, in welches) und kommt mit der Wahrscheinlichkeit 1 – ε_S unverfälscht beim Empfänger an.
  
  

: Wir gehen vom BSC–Parameter ε = 0.1 aus und betrachten Reed–Solomon–Codesymbole c_i ∈ GF(2⁸)   ⇒   m = 8, q = 256, n = 255. Für eine Symbolverfälschung (y_i ≠ 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 ε_S ≈ 0.57. Mit der Annahme, dass die Verfälschung von c_i = β in jedes andere Symbol y_i = γ ≠ β gleichwahrscheinlich ist, erhält man Pr(y_i = γ | c_i = β) = 0.57/255 ≈ 0.223%.

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

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

• Angenommen wird eine (n, k)–Reed–Solomon–Codierung mit Symbolen aus 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 c) besteht somit aus n Symbolen bzw. aus n · m Binärzeichen (Bit), die in c_bin zusammengefasst sind.
  

• Vorausgesetzt wird außerdem der AWGN–Kanal, gekennzeichnet durch den Parameter E_B/N₀. Entsprechend diesem Kanalmodell geschieht die Übertragung bipolar: „0” ↔  „+1”, „1” ↔  „–1”.
  

• Der Empfänger trifft harte Entscheidungen (Hard Decision) auf Bitebene. Vor der Decodierung inclusive der Fehlerkorrektur werden die Binärsymbole wieder auf GF(2^m)–Symbole umgesetzt.
  

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 kommt man

• mit dem komplementären Gaußschen Fehlerintegral Q(x) zum BSC–Parameter

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

• und daraus zur Verfälschungswahrscheinlichkeit ε_S auf Symbolebene:

\[\varepsilon_{\rm S} = 1 - (1 - \varepsilon)^m \hspace{0.05cm}.\]

: Für R = k/n = 239/255 = 0.9373, 10 · lg E_B/N₀ = 7 dB  ⇒  E_B/N₀ ≈ 5 und n = 2⁸ – 1  ⇒  m = 8 erhält man für den Parameter ε_S des 8–BSC–Modells:

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

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

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

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

Die folgende Grafik zeigt die in [Liv10] angegebenen Blockfehlerwahrscheinlichkeiten in Abhängigkeit des AWGN–Quotienten 10 · lg (E_B/N₀). Dargestellt sind die berechneten Kurvenverläufe Pr(υ ≠ u) für zwei verschiedene Reed–Solomon–Codes entsprechend den Deep Space Standards nach CCSDS (Consultative Committee for Space Data Systems), nämlich

• der RSC (255, 239,17)₂₅₆, der bis zu t = 8 Fehler korrigieren kann,
  

• der RSC (255, 223, 33)₂₅₆ mit höherer Korrekturfähigkeit (t = 16) aufgrund kleinerer Coderate.
  

Wir analysieren den in der Grafik gelb hinterlegten Punkt, gültig für

• den RSC (255, 239, 17)₂₅₆, und
  

• 10 · lg E_B/N₀ = 7.1 dB ⇒ ε_S = 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 hier nur angedeutete Berechnung sollen Sie in der Aufgabe A2.15 für den RSC (7, 3, 5)₈ – also für etwas übersichtlichere Parameter – vollständig durchführen.

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

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

• Für kleines E_B/N₀ (des AWGN–Kanals) sind die Reed–Solomon–Codes völlig ungeeignet. Beide Codes liegen für 10 · lg E_B/N₀ < 6 dB über der Vergleichskurve für uncodierte Übertragung.
  

• Die Berechung für den RSC (255, 223, 33)₂₅₆ unterscheidet sich von obiger Rechnung nur in der unteren Summationsgrenze (f_min = 17) und (wegen R = 0.8745) durch ein etwas größeres ε_S.
  

• Dieser (t = 16)–Code ist für BER = 10^–6 auch nur weniger als 1 dB besser als der durch grüne Kreuze gekennzeichnete Code mit t = 8. Die Ergebnisse beider Codes sind eher enttäuschend.
  

Allgemein gilt:

• Reed–Solomon–Codes sind beim gedächtnislosen Binärkanal (AWGN–Kanal) nicht sehr gut. Beide Codes liegen mehr als 4 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.
  
  

Hinweis: Die Reed–Solomon–Codes sind nicht perfekt. Welche Konsequenzen sich daraus ergeben, wird in der Aufgabe A2.16 behandelt.