Exercise 1.5: SPC (5, 4) and BEC Model

Mögliche Codeworte des $\rm SPC \ (5, 4)$

Für diese Aufgabe wird vorausgesetzt:

Der Single Parity–check Code mit den Parametern $k = 4$ und $n = 5$ ⇒ SPC (5, 4) fügt zu den Informationsbits $u_{1}$, ... , $u_{4}$ ein Prüfbit $p$ hinzu, so dass in jedem Codewort $\underline{x}$ eine gerade Anzahl von Einsen vorkommt:

$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$

$$ u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$

Der Binary Erasure Channel (BEC) – mit binären Eingangswerten $x_{i} \in \{0, \ 1\}$ und ternärem Ausgang $y_{i} \in \{0, 1, \rm E\}$ führt mit Wahrscheinlichkeit $\lambda = 0.1$ zu einer Auslöschung (englisch: Erasure), abgekürzt mit $\rm E$.
Weiterhin gilt ${\rm Pr}(y_{i} = x_{i}) = 1 – \lambda = 0.9$. Ein echter Übertragungsfehler wird ausgeschlossen:

$$ {\rm Pr} [(x_i = 0)\cap (y_i = 1)] = {\rm Pr} [(x_i = 1)\cap (y_i = 0)] = 0\hspace{0.05cm}.$$

Der Zusammenhang zwischen dem Informationswort $\underline{u}$ und dem Codewort $\underline{x}$ ist durch die obige Tabelle gegeben. Aus dem Empfangswort $\underline{y}$ wird durch Maximum–Likelihood–Entscheidung der Vektor $\underline{v}$ der Informationsbits an der Sinke gebildet, der möglichst mit dem Informationswort $\underline{u}$ übereinstimmen sollte.

Es gelte die folgende Nomenklatur:

$$\underline{u} \ \in \ \{\underline{u}_0, \underline{u}_1,\hspace{0.15cm} \text{...} \hspace{0.2cm}, \underline{u}_{15}\} \hspace{0.05cm},$$

$$ \underline{v} \ \in \ \{\underline{v}_0, \underline{v}_1, \hspace{0.15cm}\text{...} \hspace{0.2cm}, \underline{v}_{15}, \underline{\rm E}\} \hspace{0.05cm}.$$

Das Ergebnis $\underline{v} =\underline{\rm E} = {\rm (E, E, E, E)}$ kennzeichnet dabei, dass aufgrund zu vieler Auslöschungen eine Decodierung des Codewortes nicht möglich ist.

Hinweise:

Die Aufgabe gehört zum Kapitel Beispiele binärer Blockcodes.
Bezug genommen wird auch auf das Kapitel Kanalmodelle und Entscheiderstrukturen.
Die Prüfbits von $u_{0}$, $u_{4}$ und $u_{13}$ sollen in der Teilaufgabe (1) ermittelt werden.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

$\underline{u} = \underline{u_{0}}\text{:}\hspace{0.4cm}p \ = \ $

$\underline{u} = \underline{u_{4}}\text{:}\hspace{0.4cm}p \ = \ $

$\underline{u} = \underline{u_{13}}\text{:}\hspace{0.25cm}p \ = \ $

	$ \underline{u}_{0}$,
	$ \underline{u}_{4}$,
	$ \underline{u}_{13}$.

	$\underline{u}_{0}$,
	$\underline{u}_{4}$,
	$\underline{u}_{13}$.

$\ {\rm Pr} (\underline{y} = \underline{x}) \ = \ $

$\ \%$

$\ {\rm Pr} (\underline{v} = \underline{u}) \ = \ $

$\ \%$

$\ {\rm Pr} (\underline{\upsilon} = {\rm {\underline{ E}}}) \ = \ $

$\ \%$

Musterlösung

Solution

(1) Das Prüfbit $p$ wird beim Single Parity–check Code so bestimmt, dass die Summe aller Einsen im Codewort $\underline{x} = (u_{1}, u_{2}, ... , u_{4}, p)$ geradzahlig ist. Beispielsweise erhält man:

$$\underline{u}_0 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (0, 0, 0, 0) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 0} \hspace{0.05cm},$$

$$ \underline{u}_4 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (0, 1, 0, 0) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}_4 = (0, 1, 0, 0, 1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 1} \hspace{0.05cm},$$

$$\underline{u}_{13} \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (1, 1, 0, 1) \hspace{0.15cm} \Rightarrow \hspace{0.15cm} \underline{x}_{13} = (1, 1, 0, 1, 1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 1} \hspace{0.05cm}.$$

(2) Richtig ist die Antwort 1:

Aufgrund der Tatsache, dass die Anzahl der Einsen geradzahlig sein muss, ist das ausgelöschte Prüfbit $p = 0$. Gesendet wurde also $\underline{u}_{0}$.

(3) Richtig ist die Antwort 2:

Nach gleichen Überlegungen wie in der letzten Teilaufgabe kommt man für $\underline{y} = (0, {\rm E}, 0, 0, 1)$ zum Ergebnis

$$\underline{x} = \underline{x}_{4} = (0, 1, 0, 0, 1) ⇒ \underline{u}_{4} = (0, 1, 0, 0).$$

(4) Das Ereignis $\underline{y} = \underline{x}$ tritt nur dann auf, wenn durch den BEC–Kanal keines der $n = 5$ Codebits ausgelöscht wird:

$${\rm Pr}(\underline{y} = \underline{x}) = (1 - \lambda)^5 = 0.9^5 \hspace{0.15cm} \underline{= 59.1\%} \hspace{0.05cm}.$$

(5) Das Ereignis $v = u$ tritt dann auf,

wenn alle Codebits richtig übertragen werden ⇒ ${\rm Pr}(\underline{y} = \underline{x})$,
aber auch dann, wenn nur ein Codebit ausgelöscht wird. Entsprechend der Binominalverteilung gibt es hierfür 5 Möglichkeiten:

$${\rm Pr}(\underline{v} = \underline{u}) \hspace{-0.1cm}\ = \ \hspace{-0.1cm} {\rm Pr}(\underline{y} = \underline{x}) + 5 \cdot (1 - \lambda)^4 \cdot \lambda = 0.591 + 5 \cdot 0.656^4 \cdot 0.1 \hspace{0.15cm} \underline{= 91.9 \%} \hspace{0.05cm}.$$

(6) Aufgrund des BEC–Modells ist die Verfälschung eines Codewortes <$\underline{x}$ per se ausgeschlossen, da keines der Bit von $0 → 1$ bzw. von $1 → 0$ verfälscht werden kann. Vielmehr gilt:

$${\rm Pr}(\underline{v} = \underline{u}) + {\rm Pr}(\underline{v} = {\rm\underline{ E}}) = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr}(\underline{v} = {\rm\underline{ E}}) = 1 - {\rm Pr}(\underline{v} = \underline{u}) \hspace{0.15cm} \underline{= 8.1\%} \hspace{0.05cm}.$$