Aufgaben:Exercise 4.10: Union Bound

• Return to book

Signalraumkonstellationen mit $N=2$, $M=3$

Die so genannte „Union Bound” gibt eine obere Schranke für die Fehlerwahrscheinlichkeit eines nichtbinären Übertragungssystems $(M > 2)$ an. Die tatsächliche (mittlere) Fehlerwahrscheinlichkeit ist allgemein wie folgt gegeben:

$${\rm Pr}({ \cal E}) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} \sum\limits_{i = 0 }^{M-1} {\rm Pr}(m_i) \cdot {\rm Pr}({ \cal E}\hspace{0.05cm}|\hspace{0.05cm} m_i ) \hspace{0.05cm},$$

$$ {\rm Pr}({ \cal E}\hspace{0.05cm}|\hspace{0.05cm} m_i ) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} {\rm Pr} \left [ \bigcup_{k \ne i} { \cal E}_{ik}\right ] \hspace{0.05cm},\hspace{0.2cm}{ \rm wobei}\hspace{0.2cm} { \cal E}_{ik}\text{:} \ \ \boldsymbol{ r }{\rm \hspace{0.15cm}liegt \hspace{0.15cm}n\ddot{a}her \hspace{0.15cm}bei \hspace{0.15cm}}\boldsymbol{ s }_k {\rm \hspace{0.15cm}als \hspace{0.15cm}beim \hspace{0.15cm}Sollwert \hspace{0.15cm}}\boldsymbol{ s }_i \hspace{0.05cm}.$$

Die einfachere Union Bound liefert eine obere Schranke für die Verfälschungswahrscheinlichkeit unter der Voraussetzung, dass die Nachricht $m_i$ (bzw. das Signal $\boldsymbol{s}_i$) gesendet wurde:

$$p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_i} \hspace{-0.1cm} \ \ge \ \hspace{-0.1cm} {\rm Pr}({ \cal E}\hspace{0.05cm}|\hspace{0.05cm} \boldsymbol{ s }_i ) = {\rm Pr}({ \cal E}\hspace{0.05cm}|\hspace{0.05cm} m_i )\hspace{0.05cm},\ $$

$$ p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_i} \hspace{-0.1cm} \ = \ \hspace{-0.2cm}\sum\limits_{k = 0 ,\hspace{0.1cm} k \ne i}^{M-1}\hspace{-0.1cm} {\rm Pr}({ \cal E}_{ik}) = \hspace{-0.1cm}\sum\limits_{k = 0, \hspace{0.1cm} k \ne i}^{M-1}\hspace{-0.1cm}{\rm Q} \left ( \frac{d_{ik}/2}{\sigma_n} \right )\hspace{0.05cm}. $$

Dabei sind folgende Abkürzungen verwendet:

• ${\rm Q}(x)$ ist die komplementäre Gaußsche Fehlerfunktion,
• $d_{ik}$ bezeichnet den Abstand der Signalpunkte $\boldsymbol{s}_i$ und $\boldsymbol{s}_k$,
• $\sigma_n$ ist der Effektivwert (⇒ Wurzel aus der Varianz) des additiven weißen Gaußschen Rauschens.

Durch Mittelung über alle möglichen Signale $\boldsymbol{s}_i$ kommt man dann zur eigentlichen Union Bound:

$$p_{\rm UB} = \sum\limits_{i = 0 }^{M-1} {\rm Pr}(\boldsymbol{ s }_i) \cdot p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_i} \ge {\rm Pr}({ \cal E}) \hspace{0.05cm}.$$

Die Grafik zeigt drei verschiedene Signalraumkonstellationen mit jeweils $M = 3$ Signalpunkten $\boldsymbol{s}_0$, $\boldsymbol{s}_1$ und $\boldsymbol{s}_2$ im zweidimensionalen Raum $(N = 2)$. Die Basisfunktionen $\varphi_1(t)$ und $\varphi_2(t)$ sind geeignet normiert. Somit sind auch die Signalraumkoordinaten reine Zahlenwerte ohne Einheit:

$$\boldsymbol{ s }_1 = (-1, \hspace{0.1cm}+1)\hspace{0.05cm}, \hspace{0.2cm} \boldsymbol{ s }_2 = (+1, \hspace{0.1cm}+1)\hspace{0.05cm}.$$

Der Signalraumpunkt $\boldsymbol{s}_0$ in der Konfiguration A liegt so, dass $\boldsymbol{s}_0$, $\boldsymbol{s}_1$, $\boldsymbol{s}_2$ ein gleichseitiges Dreieck beschreiben. Bei der Konfiguration B und C gilt dagegen $\boldsymbol{s}_0 = (0, 0)$ bzw. $\boldsymbol{s}_0 = (0, \ –1)$. Verwenden Sie für alle Berechnungen den AWGN–Effektivwert $\sigma_n = 0.5$.

Hinweise:

• Die Aufgabe gehört zum Kapitel Approximation der Fehlerwahrscheinlichkeit.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
• Gegeben sind folgende Werte der komplementären Gaußschen Fehlerfunktion:

$${\rm Q}(1) \hspace{-0.1cm} \ \approx \ \hspace{-0.1cm} 0.159\hspace{0.05cm}, \hspace{0.2cm}{\rm Q}(\sqrt{2}) \approx 0.079\hspace{0.05cm}, \hspace{0.23cm}{\rm Q}(\sqrt{3}) \approx 0.042\hspace{0.05cm},$$

$${\rm Q}(2) \hspace{-0.1cm} \ \approx \ \hspace{-0.1cm} 0.023\hspace{0.05cm}, \hspace{0.2cm}{\rm Q}(2.14) \approx 0.016\hspace{0.05cm}, \hspace{0.1cm}{\rm Q}(\sqrt{5}) \approx 0.013 \hspace{0.05cm}.$$

Fragebogen

1

Welche der drei Konfigurationen führt zur kleinsten Fehlerwahrscheinlichkeit (zumindest nach der Union Bound–Näherung)?

	Konfiguration A,
	Konfiguration B,
	Konfiguration C.

2

Berechnen Sie die „gemittelte Union Bound” ($p_{\rm UB}$) für die Konfiguration A.

$p_{\rm UB} \ = \ $ $\ \%$

3

Berechnen Sie die „gemittelte Union Bound” ($p_{\rm UB}$) für die Konfiguration B.

$p_{\rm UB} \ = \ $ $\ \%$

4

Berechnen Sie die „gemittelte Union Bound” ($p_{\rm UB}$) für die Konfiguration C.

$p_{\rm UB} \ = \ $ $\ \%$

5

Wie müsste der Rauscheffektivwert $\sigma_n$ bei Konfiguration A verändert werden, damit sich die gleiche Union Bound wie in (4) ergibt?

$\sigma_n \ = \ $

Musterlösung

Solution

(1)  Die Punkte $\boldsymbol{s}_1$ und $\boldsymbol{s}_2$ sind für alle Konfigurationen gleich. Die kleinste Fehlerwahrscheinlichkeit ergibt sich, wenn $\boldsymbol{s}_0$ von $\boldsymbol{s}_1$ und $\boldsymbol{s}_2$ am weitesten entfernt liegt. Dies ist bei der Konfiguration C der Fall   ⇒   Lösungsvorschlag 3.

(2)  Bei der Konfiguration A ist der Abstand zwischen allen Punkten gleich: $d_{01} = d_{02} = d_{12} = 2$. Deshalb muss zur Berechnung der Union Bound nicht über alle Symbole gemittelt werden, und es gilt, da zum Beispiel $\boldsymbol{s}_0$ mit gleicher Wahrscheinlichkeit in das Symbol $\boldsymbol{s}_1$ bzw. $\boldsymbol{s}_2$ verfälscht wird:

$${\rm Pr}({ \cal E}) \le p_{\rm UB} = 2 \cdot {\rm Q} \left ( \frac{d_{ik}/2}{\sigma_n} \right ) = 2 \cdot {\rm Q}(2) \approx 2 \cdot 0.023 \hspace{0.1cm}\hspace{0.15cm}\underline {= 4.6\%} \hspace{0.05cm}. $$

(3)  Hier unterscheiden sich die Verfälschungswahrscheinlichkeiten für die einzelnen Symbole. Wurde $\boldsymbol{s}_0$ gesendet, so gilt mit $d_{01} = d_{02} = 2^{0.5}$ und $\sigma = 0.5$:

$$p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_0} = 2 \cdot {\rm Q} \left ( \frac{\sqrt{2}/2}{0.5} \right ) = 2 \cdot {\rm Q}(\sqrt{2}) = 2 \cdot 0.079 = 0.158 \hspace{0.05cm}. $$

Dagegen sind die beiden anderen bedingten Wahrscheinlichkeiten kleiner

$$p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_1} = p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_2} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} {\rm Q} \left ( \frac{{2}/2}{0.5} \right )+{\rm Q} \left ( \frac{\sqrt{2}/2}{0.5} \right )= {\rm Q}(2) +{\rm Q}(\sqrt{2}) = 0.023 + 0.079 = 0.102 \hspace{0.05cm}.$$

Durch Mittelung erhält man für die Union Bound unter Berücksichtigung der unterschiedlichen Abstände:

$$p_{\rm UB} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} {1}/{3} \cdot \left [ p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_0} + p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_1} +p_{{\rm UB}\hspace{0.05cm}| \hspace{0.05cm}\boldsymbol{ s }_2}\right ]= {1}/{3} \cdot \left [ 2 \cdot {\rm Q}(\sqrt{2})+ 2 \cdot ({\rm Q}({2}) + {\rm Q}(\sqrt{2})) \right ] = {1}/{3} \cdot \left [ 4 \cdot {\rm Q}(\sqrt{2})+ 2 \cdot {\rm Q}({2}) \right ] $$

$$ \Rightarrow \hspace{0.3cm} p_{\rm UB} = {1}/{3} \cdot \left [ 4 \cdot 0.079+ 2 \cdot 0.023 \right ] \hspace{0.1cm}\hspace{0.12cm}\underline {\approx 12.1\% } \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_{\rm UB}\ge {\rm Pr}({ \cal E})\hspace{0.05cm}.$$

(4)  Diese Konfiguration wird durch folgende Gleichungen beschrieben:

$$d_{01} = d_{02} = \sqrt{2^2 + 1^2}= \sqrt{5} \approx 2.24\hspace{0.2cm}, d_{12} = 2$$

$$\Rightarrow \hspace{0.3cm} p_{\rm UB} = {1}/{3} \cdot \left [ 4 \cdot {\rm Q}(\sqrt{5})+ 2 \cdot {\rm Q}({2}) \right ] = {1}/{3} \cdot \left [ 4 \cdot 0.013+ 2 \cdot 0.023 \right ]\hspace{0.1cm}\hspace{0.15cm}\underline {\approx 3.2\%} \hspace{0.05cm}. $$

(5)  Es soll gelten:

$$p_{\rm UB} = 2 \cdot {\rm Q}\left ( {1}/{\sigma_n} \right ) = 0.032 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Q}\left ( {1}/{\sigma_n} \right ) = 0.016\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {1}/{\sigma_n} \approx 2.14 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\hspace{0.1cm}\hspace{0.15cm}\sigma_n \hspace{0.15cm}\underline {\approx 0.467}\hspace{0.05cm}. $$