Exercise 5.4:Is the BSC Model Renewing?

Fehlerkorrelationsfunktion des BSC–Modells

Zur Beschreibung von digitalen Kanalmodellen werden vorwiegend benutzt:

die Fehlerabstandsverteilung (FAV)

$$V_a(k) = {\rm Pr}(a \ge k) = 1 - \sum_{\kappa = 1}^{k} {\rm Pr}(a = \kappa)\hspace{0.05cm},$$

die Fehlerkorrelationsfunktion (FKF)

$$\varphi_{e}(k) = {\rm E}[e_{\nu} \cdot e_{\nu + k}] \hspace{0.05cm}.$$

Für eine große Klasse von Kanalmodellen besteht ein einfacher Zusammenhang zwischen diesen Beschreibungsgrößen, nämlich

$$\varphi_{e}(k) = \left\{ \begin{array}{c} \varphi_{e}(0) \\ \sum_{\kappa = 1}^{k} {\rm Pr}(a = \kappa) \cdot \varphi_{e}(k - \kappa)\end{array} \right.\quad \begin{array}{*{1}c} f{\rm \ddot{u}r }\hspace{0.15cm}k = 0 \hspace{0.05cm}, \\ f{\rm \ddot{u}r }\hspace{0.15cm} k > 0 \hspace{0.05cm}.\\ \end{array}$$

Man nennt solche Kanalmodelle erneuernd. Sie zeichnen sich dadurch aus, dass bei ihnen die einzelnen Fehlerabstände statistisch voneinander unabhängig sind, so dass zur Generierung der Fehlerfolge der oft schnellere Weg über die Generierung der Fehlerabstände gegangen werden kann, wie in der Aufgabe 5.5 beschrieben wird.

In dieser Aufgabe soll überprüft werden, ob das BSC–Modell gemäß der oberen Grafik erneuernd ist. Die Fehlerkorrelationsfunktion $\varphi_e(k)$ ist in der unteren Grafik dargestellt. Die Wahrscheinlichkeiten der einzelnen Fehlerabstände sind beim BSC–Modell wie folgt gegeben:

$${\rm Pr}(a = k) = (1-p)^{k-1}\cdot p \hspace{0.05cm}.$$

Hinweise:

Die Aufgabe gehört zum Kapitel Binary Symmetric Channel (BSC).
Verwenden Sie für numerische Berechnungen den BSC–Parameter $p = 0.01$.
Die mittlere Fehlerwahrscheinlichkeit $p_{\rm M}$ hat dann den gleichen Wert.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

(1) Nach der allgemeinen Definition ist $\varphi_e(k = 0) = {\rm E}[e_{\nu}^2]$. Wegen $e_{\nu} ∈ \{0, 1\}$ gilt aber gleichzeitig $\varphi_e(k = 0) = {\rm E}[e_\nu]$, was der mittleren Fehlerwahrscheinlichkeit $p_{\rm M} = p$ entspricht ⇒ $\varphi_e(k = 0) \ \underline { = 0.01}$.

(2) Nach der allgemeinen FKF–Definition gilt unter Berücksichtigung des BSC–Modells:

$$\varphi_{e}(k = 1) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} {\rm E}[e_{\nu} \cdot e_{\nu + 1}]={\rm Pr}[e_{\nu} = 1 \cap e_{\nu + 1} = 1] = p \cdot p = p^2 \hspace{0.15cm}\underline {= 10^{-4}}\hspace{0.05cm}.$$

Zum gleichen Ergebnis kommt man über die nur für erneuernde Kanalmodelle gültige Gleichung:

$$\varphi_{e}(k = 1) = {\rm Pr}(a=1) \cdot \varphi_{e}(0) = p \cdot p = p^2 = 10^{-4}\hspace{0.05cm}.$$

Das bedeutet: Der FKF–Wert $\varphi_e(1)$ spricht nicht dagegen, dass das BSC–Modell erneuernd ist.

(3) Aus der Grafik erkennt man bereits, dass $\varphi_e(k = 2) = \varphi_e(k = 1) = 10^{–4}$ gelten wird. Die explizite Berechnung bestätigt dieses Ergebnis:

$$\varphi_{e}(k \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2) = {\rm Pr}[e_{\nu} = 1 \cap e_{\nu + 2} = 1] = {\rm Pr}[e_{\nu} = 1 \cap e_{\nu + 1} = 1 \cap e_{\nu + 2} = 1] + {\rm Pr}[e_{\nu} = 1 \cap e_{\nu + 1} = 0 \cap e_{\nu + 2} = 1] \hspace{0.05cm}.$$

Der erste Term lautet beim BSC-Modell mit den bedingten Wahrscheinlichkeiten (nur erste Ordnung erforderlich):

$${\rm Pr}[1\hspace{0.1cm}1 \hspace{0.1cm} 1] \hspace{-0.1cm} \ = \ \hspace{-0.1cm}{\rm Pr}[e_{\nu +2} = 1 \hspace{0.1cm}|\hspace{0.1cm} e_{\nu + 1} = 1] \cdot {\rm Pr}[e_{\nu +1} = 1 \hspace{0.1cm}|\hspace{0.1cm} e_{\nu } = 1] \cdot {\rm Pr}[ e_{\nu } = 1]=p \cdot p \cdot p = p^3\hspace{0.05cm}.$$

Entsprechend gilt für den zweiten Term:

$${\rm Pr}[1\hspace{0.1cm}0 \hspace{0.1cm} 1] \hspace{-0.1cm} \ = \ \hspace{-0.1cm}{\rm Pr}[e_{\nu +2} = 1 \hspace{0.1cm}|\hspace{0.1cm} e_{\nu + 1} = 0] \cdot {\rm Pr}[e_{\nu +1} = 0 \hspace{0.1cm}|\hspace{0.1cm} e_{\nu } = 1] \cdot {\rm Pr}[ e_{\nu } = 1]=p \cdot (1-p) \cdot p = p^2 -p^3\hspace{0.05cm}.$$

$$\Rightarrow \hspace{0.3cm} \varphi_{e}(k = 2) = {\rm Pr}[1\hspace{0.1cm}1 \hspace{0.1cm} 1] + {\rm Pr}[1\hspace{0.1cm}0 \hspace{0.1cm} 1] = (p^3) + (p^2 -p^3)= p^2\hspace{0.15cm}\underline { = 10^{-4}}\hspace{0.05cm}.$$

Mit der nur für erneuernde Kanalmodelle gültigen Gleichung erhält man:

$$\varphi_{e}(k = 2) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} {\rm Pr}(a=1) \cdot \varphi_{e}(k= 1) + {\rm Pr}(a=2) \cdot \varphi_{e}(k= 0)= p \cdot p^2 + (1-p) \cdot p \cdot p = p^2 \hspace{0.05cm}.$$

Auch dieses Ergebnis spricht also nicht dagegen, dass das BSC–Modell erneuernd ist.

(4) Die bisherigen Ergebnisse lassen schon darauf schließen, dass das BSC–Modell erneuernd ist. Und auch die Tatsache, dass hier die einzelnen Fehlerabstände statistisch unabhängig voneinander sind, spricht für diese These. Als letzten Beweis zeigen wird, dass die Gleichung

$$\varphi_{e}(k) = \sum_{\kappa = 1}^{k} {\rm Pr}(a = \kappa) \cdot \varphi_{e}(k - \kappa)= \varphi_{e}(0) \cdot {\rm Pr}(a = k)+ \sum_{\kappa = 1}^{k-1} \varphi_{e}(k - \kappa) \cdot {\rm Pr}(a = \kappa)$$

das richtige Ergebnis liefert, wenn $\varphi_e(0) = p$ und $\varphi_e(1) = \ \text{...} \ = \varphi_e(k–1) = p^2$ eingesetzt wird. Man erhält

$$\varphi_{e}(k) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} p \cdot (1-p)^{k-1} \cdot p + p^2 \cdot \sum_{\kappa = 1}^{k-1} (1-p)^{\kappa-1} \cdot p =p^2 \cdot (1-p)^{k-1} + p^3 \cdot \sum_{\kappa = 0}^{k-2} (1-p)^{\kappa}\hspace{0.05cm}.$$

Mit der Summenformel einer geometrischen Reihe

$$\sum_{\kappa = 0}^{n} x^{\kappa} = \frac{1 - x^{n+1}}{1 - x}\hspace{0.05cm},$$

lässt sich dieser Ausdruck wie folgt darstellen:

$$\varphi_{e}(k) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} p^2 \cdot (1-p)^{k-1} + p^3 \cdot \frac{1 - (1-p)^{k-1}}{1 - (1-p)}= p^2 \cdot \left [ (1-p)^{k-1} + 1 - (1-p)^{k-1} \right ] = p^2\hspace{0.05cm}.$$

Das bedeutet: Das BSC–Modell ist tatsächlich erneuernd ⇒ Lösungsvorschlag 1.

	Das BSC–Modell ist erneuernd.
	Das BSC–Modell ist nicht erneuernd.