Fehlerwahrscheinlichkeit und Anwendungsgebiete

Aus LNTwww
Wechseln zu:Navigation, Suche

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 (yz) auf Bounded Distance Decoding (BDD) beschränken. Für Maximum Likelihood Decoding sind die Ergebnisse geringfügig besser.

Systemmodell mit RSC, m–BSC und BDD

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 ≤ fn 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 ci ∈ GF(2) gegolten hat und damit die f Übertragungsfehler jeweils Bitfehler waren, versteht man bei Reed–Solomon–Codierung unter einem Übertragungsfehler (yi ≠ ci) wegen ci ∈ GF(2m) bzw. yi ∈ GF(2m) einen Symbolfehler. Damit ergeben sich folgende Unterschiede:

  • Das diskrete Kanalmodell zur Beschreibung der binären Blockcodes ist der Binary Symmetric Channel (BSC). Jedes Bit ci eines Codewortes wird mit der Wahrscheinlichkeit ε verfälscht (yi ≠ ci) und mit der Wahrscheinlichkeit 1 – ε richtig übertragen (yi = ci).
  • Bei Reed–Solomon–Codierung muss das BSC–Modell durch das m–BSC–Kanalmodell ersetzt werden. Ein Symbol ci wird mit der Wahrscheinlichkeit εS in ein anderes Symbol yi 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 ci ∈ GF(28)   ⇒   m = 8, q = 256, n = 255. Für eine Symbolverfälschung (yi ≠ ci) genügt bereits ein falsches Bit. Oder anders ausgedrückt: Soll yi = ci 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 ci = β in jedes andere Symbol yi = γβ gleichwahrscheinlich ist, erhält man Pr(yi = γ | ci = β) = 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(2m). 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 cbin zusammengefasst sind.
  • Vorausgesetzt wird außerdem der AWGN–Kanal, gekennzeichnet durch den Parameter EB/N0. 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(2m)–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 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 EB/N0 = 7 dB  ⇒  EB/N0 ≈ 5 und n = 28 – 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][1] angegebenen Blockfehlerwahrscheinlichkeiten in Abhängigkeit des AWGN–Quotienten 10 · lg (EB/N0). 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)256, der bis zu t = 8 Fehler korrigieren kann,
  • der RSC (255, 223, 33)256 mit höherer Korrekturfähigkeit (t = 16) aufgrund kleinerer Coderate.
Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge n = 255

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

  • den RSC (255, 239, 17)256, und
  • 10 · lg EB/N0 = 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)8 – 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 EB/N0 (des AWGN–Kanals) sind die Reed–Solomon–Codes völlig ungeeignet. Beide Codes liegen für 10 · lg EB/N0 < 6 dB über der Vergleichskurve für uncodierte Übertragung.
  • Die Berechung für den RSC (255, 223, 33)256 unterscheidet sich von obiger Rechnung nur in der unteren Summationsgrenze (fmin = 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.
Blockfehlerwahrscheinlichkeit zweier Reed–Solomon–Codes der Länge n = 255

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.

Typische Anwendungen mit Reed–Solomon–Codierung (1)


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.

Codeschema mit Kaskadierung

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

: 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 20x4 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 22, 42, 62, 3, 23 ⇒ rot umrandetes Rechteck) zerstört, z. B. 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.


Typische Anwendungen mit Reed–Solomon–Codierung (2)


Eine sehr weit verbreitete Anwendung von Reed–Solomon–Codierung – und zudem die kommerziell erfolgreichste – ist die Compact Disc (CD), deren Fehlerkorrekturmechanismus bereits im Kapitel 1.1 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 44.1 kHz abgetastet und jeder einzelne Abtastwert wird mit 32 Bit (4 Byte) digital dargestellt.
  • Die Gruppierung von 6 Samples ergibt einen Rahmen (192 Bit) und damit 24 Codesymbole aus dem Galoisfeld GF(28). Jedes Codesymbol entspricht somit genau einem Byte.
  • Der erste Reed–Solomon–Code mit der Rate R1 = 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 CD herrühren.
  • Zusammen mit dem zweiten Reed–Solomon–Code (Rate R2 = 28/32) ergibt sich eine Gesamtrate von R = (24/28) · (28/32) = 3/4. Beide Codes können jeweils t = 2 Symbolfehler korrigieren.
  • Beide RS–Komponentencodes (28, 24, 5) und (32, 28, 5) basieren jeweils auf dem Galoisfeld GF(28), was eigentlich eine Codelänge n = 255 bedeuten würde.
  • Die hier benötigten kürzeren Komponentencodes ergeben sich aus aus dem RSC (255, 251, 5)256 durch Shortening. Man sieht, dass dadurch die minimale Distanz dmin = 5 nicht verändert wird.
  • Mit der anschließenden Eight–to–Fourteen–Modulation und weiterer Kontrollsymbole kommt man schließlich zur endgültigen Coderate 192/588 ≈ 0.326 der CD–Daten-komprimierung.

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


A2.15 Pr(υ ≠ u) vs. EB/N0

Zusatzaufgaben:2.15 Nochmals Pr(υ ≠ u) für BDD

A2.16 BDD–Entscheidungskriterien

Quellenverzeichnis

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