Error Probability and Application Areas

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.

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 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.