Exercise 4.10: Union Bound

Signalraumkonstellationen mit $N=2$ und $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$ Signalraumpunkten $\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 $\rm A$ liegt so, dass $\boldsymbol{s}_0$, $\boldsymbol{s}_1$, $\boldsymbol{s}_2$ ein gleichseitiges Dreieck beschreiben. *Bei den Konfigurationen $\rm B$ und $\rm C$ gilt dagegen $\boldsymbol{s}_0 = (0, 0)$ bzw. $\boldsymbol{s}_0 = (0, \ -1)$.

Hinweise:

Die Aufgabe gehört zum Kapitel Approximation der Fehlerwahrscheinlichkeit.
Verwenden Sie für alle Berechnungen den AWGN–Effektivwert $\sigma_n = 0.5$.

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

	Konfiguration $\rm A$,
	Konfiguration $\rm B$,
	Konfiguration $\rm C$.

$p_{\rm UB} \ = \ $

$\ \%$

$p_{\rm UB} \ = \ $

$\ \%$

$p_{\rm UB} \ = \ $

$\ \%$

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