Aufgaben:Aufgabe 1.12: Hard Decision vs. Soft Decision

• Zurück zum Buch

Blockfehlerrate des (7, 4, 3)-Codes bei Hard Decision und Soft Decision

Die Abbildung zeigt die Blockfehlerwahrscheinlichkeit für den (7, 4, 3)–Hamming–Code, wobei für den Empfänger zwei Varianten berücksichtigt sind:

• Bei Maximum–Likelihood–Detektion mit harten Entscheidungen (Hard Decision, HD), die im vorliegenden Fall (perfekter Code) auch durch Syndromdecodierung realisiert werden kann, ergibt sich die rote Kurve (Kreismarkierung).

• Der Kanal kann bei Hard Decision vereinfacht durch das BSC–Modell ersetzt werden. Der Zusammenhang zwischen dem BSC–Parameter $\varepsilon$ und dem AWGN–Quotienten $E_{\rm B}/N_{0}$ (in der Grafik verwendet) ist wie folgt gegeben:

$$\varepsilon = {\rm Q}\left ( \sqrt{2 \cdot R \cdot E_{\rm B}/N_0} \right ) \hspace{0.05cm}.$$

Hier bezeichnet Q(x) die komplementäre Gaußsche Fehlerfunktion und R die Coderate.

• Die grüne Kurve (Kreuze) zeigt die Blockfehlerwahrscheinlichkeit bei „weichen” Entscheidungen (Soft Decision, SD). Dieser Funktionsverlauf lässt sich nicht in geschlossen–mathematischer Form angeben. In der Grafik eingezeichnet ist eine in [Fri96] angegebene obere Schranke:

$$ {\rm Pr(Blockfehler)} \hspace{-0.15cm}\ \le \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{ 3 \cdot \frac{2 \cdot R \cdot E_{\rm B}}{N_0}} \right )+\\ \hspace{-0.15cm}\ + \ \hspace{-0.15cm}7 \cdot {\rm Q}\left ( \sqrt{ 4 \cdot \frac{2 \cdot R \cdot E_{\rm B}}{N_0}} \right ) + {\rm Q}\left ( \sqrt{ 7 \cdot \frac{2 \cdot R \cdot E_{\rm B}}{N_0}} \right ) \hspace{0.05cm}.$$

Der jeweils erste Faktor im Argument der Q–Funktion gibt die möglichen Hamming–Distanzen an: $i = 3, 4 {\rm und} 7$. Die Vorfaktoren berücksichtigen die Vielfachheiten $W_{3} = W_{4} = 7 {\rm und} W_{7} = 1$, und $R = 4/7$ beschreibt die Coderate. Für $10 · {\rm lg} \ E_{\rm B}/N_{0} > 8 \ {\rm dB}$ ist Pr(Blockfehler) kleiner als $10^{–5}$.

Hinweis:

Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes. Verwenden Sie für numerische Ergebnisse das folgende Berechnungsmodul:

Komplementäre Gaußsche Fehlerfunktion

Fragebogen

1

Wir betrachten bis einschließlich Teilaufgabe (4) stets Hard Decision. Welche Blockfehlerwahrscheinlichkeit besitzt der (7, 4, 3)–Hamming–Code?

$\varepsilon = 0.01: {\rm Pr(Blockfehler)}$ $\ \cdot 10^{-3} $

$\varepsilon = 0.001: {\rm Pr(Blockfehler)}$ $\ \cdot 10^{-5} $

2

Wie kann man die Fehlerwahrscheinlichkeit eines Hamming–Codes annähern?

	${\rm Pr(Blockfehler)} = n · (n–1)/2 · \varepsilon^2.$
	${\rm Pr(Blockfehler)} = n · \varepsilon^2.$
	${\rm Pr(Blockfehler)} = n · \varepsilon^n.$

3

Welcher Hamming–Code besitzt die kleinste Blockfehlerwahrscheinlichkeit bei konstantem BSC–Parameter $ \varepsilon$?

	der Hamming–Code (3, 1, 3) ⇒ Repetition Code (3, 1, 3),
	der Hamming–Code (7, 4, 3),
	der Hamming–Code (15, 11, 3).

4

Welcher numerische Zusammenhang besteht zwischen dem BSC–Parameter $\varepsilon$ und dem AWGN–Quotienten $E_{\rm B}/N_{0}$?

$\varepsilon = 0.01: \ \ 10 · {\rm lg} \ E_{\rm B}/N_{0} $ $\ \rm dB$

$\varepsilon = 0.001: \ \ 10 · {\rm lg} \ E_{\rm B}/N_{0} $ $\ \rm dB$

5

Welcher Gewinn (in dB) ist durch Soft Decision (SD) zu erzielen, wenn die Blockfehlerwahrscheinlichkeit den Wert $10^{–5}$ nicht überschreiten soll?

$\ 10 · \ {\rm lg} \ G_{\rm SD} $ = $ \ \rm dB$

Musterlösung

Musterlösung

(1)  Jeder Hamming–Code ist perfekt und weist eine minimale Distanz von $d_{\rm min} = 3$ auf. Deshalb kann ein Bitfehler im Codewort korrigiert werden, während zwei Bitfehler stets zu einer Fehlentscheidung des Codewortes führen ⇒ Parameter $t = 1$. Damit ergibt sich für die Blockfehlerwahrscheinlichkeit:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - {\rm Pr(kein\hspace{0.15cm} Blockfehler)} - {\rm Pr(ein\hspace{0.15cm} Blockfehler)} = \\ \hspace{-0.15cm}\ = \ \hspace{-0.15cm}1 - (1 - \varepsilon)^7 - 7 \cdot \varepsilon \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$

$$\varepsilon = 0.01:\hspace{0.2cm} {\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - 0.99^7 - 7 \cdot 0.01 \cdot 0.99^6= \\ \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - 0.932065 - 0.065904\hspace{0.15cm}\underline{\approx 2.03 \cdot 10^{-3}}\hspace{0.05cm},\\ \varepsilon = 0.001:\hspace{0.2cm} {\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - 0.999^7 - 7 \cdot 0.001 \cdot 0.999^6= \\ \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - 0.993021 - 0.006958\hspace{0.15cm}\underline{\approx 2.09 \cdot 10^{-5}}\hspace{0.05cm}.$$

(2)  Ein jeder $(n, k, 3)$ Hamming–Code kann nur einen Bitfehler korrigieren. Damit gilt allgemein für den BSC–Kanal mit der Codewortlänge n:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - (1 - \varepsilon)^n - n \cdot \varepsilon \cdot (1 - \varepsilon)^{n-1}=\\ \hspace{3.3cm}\ = \ \hspace{-0.15cm} 1 - \left [ 1 - {n \choose 1}\cdot \varepsilon + {n \choose 2}\cdot \varepsilon^2 - \hspace{0.05cm}... \hspace{0.05cm} \right ] -\\ \hspace{6.8cm}\ . \ \hspace{0.18cm} - \left [ n \cdot \varepsilon \cdot \left ( 1 - {{n-1} \choose 1}\cdot \varepsilon + {{n-1} \choose 2}\cdot \varepsilon^2 - \hspace{0.05cm}... \hspace{0.05cm}\right ) \right ] \hspace{0.05cm}.$$

Bei Vernachlässigung aller Terme mit $\varepsilon^3, \varepsilon^4, ...$ erhält man:

$${\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} n \cdot \varepsilon - {n \choose 2}\cdot \varepsilon^2 - n \cdot \varepsilon + n \cdot \varepsilon {{n-1} \choose 1}\cdot \varepsilon + \hspace{0.05cm}... \hspace{0.05cm} =\\ \hspace{4.3cm}\ = \ \hspace{-0.15cm} -1/2 \cdot n \cdot (n-1)\cdot \varepsilon^2 + n \cdot (n-1)\cdot \varepsilon^2 = n \cdot (n-1)/2 \cdot \varepsilon^2 \hspace{0.05cm}.$$

⇒ Richtig ist Lösungsvorschlag 1. Für den (7, 4, 3)–Hamming–Code ergibt sich somit:

$${\rm Pr(Blockfehler)} \le \left\{ \begin{array}{c} 2.1 \cdot 10^{-3}\\ 2.1 \cdot 10^{-5} \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r}\hspace{0.15cm} \varepsilon = 10^{-2} \\ {\rm f\ddot{u}r}\hspace{0.15cm} \varepsilon = 10^{-3} \\ \end{array} \hspace{0.05cm}.$$

Durch Vergleich mit dem Ergebnis der Teilaufgabe (1) erkennt man die Gültigkeit dieser Näherung. Diese ist um so besser, je kleiner die BSC–Verfälschungswahrscheinlichkeit $\varepsilon$ ist.

(3)  Die Ergebnisse der Teilaufgabe 2) lassen sich wie folgt zusammenfassen:

$${\rm Pr(Blockfehler)} = \left\{ \begin{array}{l} 3 \cdot \varepsilon^2 \\ 21 \cdot \varepsilon^2\\ 105 \cdot \varepsilon^2\\ \end{array} \right.\quad \begin{array}{*{1}l} {\rm f\ddot{u}r}\hspace{0.15cm} n = 3 \\ {\rm f\ddot{u}r}\hspace{0.15cm} n = 7 \\ {\rm f\ddot{u}r}\hspace{0.15cm} n = 15 \\ \end{array} \hspace{0.05cm}.$$

Richtig ist Antwort 1. Die geringste Blockfehlerwahrscheinlichkeit besitzt natürlich der Hamming–Code mit der geringsten Rate $R = 1/3$, also mit der größten relativen Redundanz.

(4)  Bei Hard Decision gilt mit der komplementären Gaußschen Fehlerfunktion Q(x):

$$\varepsilon = {\rm Q}\left ( \sqrt{2 \cdot R \cdot E_{\rm B}/N_0} \right )\hspace{0.3cm} \Rightarrow \hspace{0.3cm} E_{\rm B}/N_0 = \frac{[{\rm Q}^{-1}(\varepsilon)]^2}{2R}$$

$$ \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 = 20 \cdot {\rm lg} \hspace{0.1cm}[{\rm Q}^{-1}(\varepsilon)] - 10 \cdot {\rm lg} \hspace{0.1cm} (2R) \hspace{0.05cm}.$$

Daraus erhält man mit $\varepsilon = 0.01 ⇒ {\rm Q}^{–1}(\varepsilon) = 2.33:$

$$10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 = 20 \cdot {\rm lg} \hspace{0.1cm}(2.33) - 10 \cdot {\rm lg} \hspace{0.1cm} (8/7) = 7.35\,{\rm dB} - 0.58\,{\rm dB}\hspace{0.15cm}\underline{\approx 6.77\,{\rm dB}}\hspace{0.05cm}.$$

In analoger Weise ergibt sich für $\varepsilon = 0.001 ⇒ {\rm Q}^{–1}(\varepsilon) ≈ 3.09$.

$$10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 = 20 \cdot {\rm lg} \hspace{0.1cm}(3.09) - 0.58\,{\rm dB}\hspace{0.15cm}\underline{\approx 9.22\,{\rm dB}}\hspace{0.05cm}.$$

(5)  Wir beziehen uns auf die Blockfehlerwahrscheinlichkeit $10^{–5}$. Nach dem Ergebnis der Teilaufgabe (2) darf dann die BSC–Verfälschungswahrscheinlichkeit nicht größer sein als

$$\varepsilon = \sqrt{\frac{10^{-5}}{21}} = 6.9 \cdot 10^{-4} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Q}^{-1}(\varepsilon) = 3.2 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 = 9.52\,{\rm dB}\hspace{0.05cm}.$$

Mit Soft Decision genügen laut Angabe $8 {\rm dB} ⇒ 10 · {\rm lg} G_{\rm SD} = 1.52 {\rm dB}$.