Aufgabe 2.15Z: Nochmals RS-Blockfehlerwahrscheinlichkeit

Wahrscheinlichkeiten der Binominalverteilung

Bei Verwendung eines Reed–Solomon–Codes mit der Korrekturfähigkeit $t$ und Bounded Distance Decoding (BDD) erhält man mit

der Codewortlänge $n$ und
der Symbolverfälschungswahrscheinlichkeit $\epsilon_{\rm S}$

für die Blockfehlerwahrscheinlichkeit:

$${\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}.$$

In dieser Aufgabe soll die Blockfehlerwahrscheinlichkeit für den $\rm RSC \, (7, \, 3, \, 5)_8$ und verschiedene $\epsilon_{\rm S}$–Werte berechnet und angenähert werden. Obige Gleichung erinnert an die Biomialverteilung. Die Grafik zeigt die Wahrscheinlichkeiten der Binomialverteilung für die Parameter $n = 7$ (Codewortlänge) und $\epsilon_{\rm S} = 0.25$ (Symbolverfälschungswahrscheinlichkeit).

Hinweise:

Die Aufgabe gehört zum Kapitel Fehlerwahrscheinlichkeit und Anwendungsgebiete.
Zur Kontrolle können Sie das interaktive Applet Gegenüberestellung von Binomialverteilung vs. Poissonverteilung benutzen.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

$\epsilon_{\rm S} = 0.1 \text{:} \hspace{0.2cm} \rm Pr(Blockfehler) \ = \ $

$\ \cdot 10^{-2}$

$\epsilon_{\rm S} = 0.01 \text{:} \hspace{0.2cm} \rm Pr(Blockfehler) \ = \ $

$\ \cdot 10^{-5}$

$\rm Näherung \text{:} \hspace{0.2cm} Pr(Blockfehler) \ = \ $

$\ \cdot 10^{-5}$

$\epsilon_{\rm S} = 10^{-3} \text{:} \hspace{0.2cm} \rm Pr(Blockfehler) \ = \ $

$\ \cdot 10^{-8}$

${\rm Pr(Blockfehler)} = 10^{-10} \text{:} \hspace{0.2cm} \epsilon_{\rm S} \ = \ $

$\ \cdot 10^{-4}$

Musterlösung

(1) Für den $\rm RSC \, (7, \, 3, \, 5)_8$ ergibt sich wegen $d_{\rm min} = 5 \ \Rightarrow \ t = 2$ für die Blockfehlerwahrscheinlichkeit:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{f = 3}^{7} {7 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{7-f} =$$

$$\hspace{2.875cm} \ = \ \hspace{-0.15cm} {7 \choose 3} \cdot 0.1^3 \cdot 0.9^4 + {7 \choose 4} \cdot 0.1^4 \cdot 0.9^3 + {7 \choose 5} \cdot 0.1^5 \cdot 0.9^2+$$

$$ \hspace{2.875cm} \ + \ \hspace{-0.15cm} {7 \choose 6} \cdot 0.1^6 \cdot 0.9+ {7 \choose 7} \cdot 0.1^7 \hspace{0.05cm}.$$

Nach dieser Berechnung müssten fünf Terme berücksichtigt werden. Da aber auch

$${\rm Pr(Blockfehler)} = \sum_{f = 0}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} = 1$$

gilt, kommt man über den nachfolgenden Rechenweg schneller zum Erfolg:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - \big [ {7 \choose 0} \cdot 0.9^7 + {7 \choose 1} \cdot 0.1 \cdot 0.9^6 + {7 \choose 2} \cdot 0.1^2 \cdot 0.9^5 \big ] =$$

$$\hspace{2.875cm} \ = \ \hspace{-0.15cm}1 - \big [ 0.4783 + 0.3720 + 0.1240 \big ] \hspace{0.15cm} \underline{= 0.0257} \hspace{0.05cm}.$$

(2) Analog zur Teilaufgabe erhält man hier:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - \big [ 0.99^7 + 7 \cdot 0.01 \cdot 0.99^6 + 21 \cdot 0.01^2 \cdot 0.99^5 \big ] =$$

$$\hspace{2.875cm} \ = \ \hspace{-0.15cm}1 - \big [ 0.9321 + 0.0659 + 0.0020 \big ] \approx 0 \hspace{0.05cm}.$$

Das bedeutet: Für die Wahrscheinlichkeit $\epsilon_{\rm S} = 0.01$ ist die vereinfachte Rechnung sehr fehleranfällig, weil sich für den Klammerausdruck ein Wert nahezu $1$ ergibt. Die vollständige Rechnung ergibt hier:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {7 \choose 3} \cdot 0.01^3 \cdot 0.99^4 + {7 \choose 4} \cdot 0.01^4 \cdot 0.99^3 + {7 \choose 5} \cdot 0.01^5 \cdot 0.99^2+$$

$$\hspace{2.875cm} \ = \ \hspace{-0.15cm} {7 \choose 6} \cdot 0.01^6 \cdot 0.99+ {7 \choose 7} \cdot 0.01^7 =$$

$$\hspace{2.875cm} \ = \ \hspace{-0.15cm} 10^{-6} \cdot \big [ 33.6209 + 0.3396 + 0.0021 + ... \big ] \hspace{0.15cm} \underline{ \approx 3.396 \cdot 10^{-5}} \hspace{0.05cm}.$$

(3) Aus der Musterlösung zur Teilaufgabe (2) kann das Ergebnis direkt abgelesen werden:

$${\rm Pr(Blockfehler)} \hspace{0.15cm} \underline{ \approx 3.362 \cdot 10^{-5}} \hspace{0.05cm}.$$

Der relative Fehler beträgt ca. $-1\%$. Das Minuszeichen zeigt an, dass es sich hier nur um eine Näherung handelt und nicht um eine Schranke: Der Näherungswert ist etwas kleiner als der tatsächliche Wert.

(4) Beschränkt man sich auf den relevanten Term $(f = 3)$, so ergibt sich für $\epsilon_{\rm S} = 0.001$:

$${\rm Pr(Blockfehler)} \approx {7 \choose 3} \cdot [10^{-3}]^3 \cdot 0.999^4 \hspace{0.15cm} \underline{ \approx 3.49 \cdot 10^{-8}} \hspace{0.05cm}.$$

Der relative Fehler beträgt hier nur noch etwa $-0.1\%$.

(5) Entsprechend der hergeleiteten Näherung gilt für den betrachteten Code:

$${\rm Pr(Blockfehler)} \approx {7 \choose 3} \cdot {\varepsilon_{\rm S}}^3 = 35 \cdot {\varepsilon_{\rm S}}^3$$

$$\Rightarrow \hspace{0.3cm} {\rm Pr(Blockfehler)} = 10^{-10}: \hspace{0.4cm} {\varepsilon_{\rm S}} = \big ( \frac{10^{-10}}{35} \big )^{1/3} = 2.857^{1/3} \cdot 10^{-4} \hspace{0.15cm} \underline{ \approx 1.42 \cdot 10^{-4}}\hspace{0.05cm}.$$