Aufgaben:Aufgabe 1.2: Einfacher binärer Kanalcode: Unterschied zwischen den Versionen

Aktuelle Version vom 6. Juni 2022, 14:44 Uhr

Verdeutlichung der Kanal(de)codierung

Die Grafik verdeutlicht die hier betrachtete Kanalcodierung $\mathcal{C}$:

Es gibt vier mögliche Informationsblöcke $\underline{u} = (u_{1},\ u_{2}, \text{...}\hspace{0.05cm} ,\ u_{k})$.

Jeder Informationsblock $\underline{u}$ wird eindeutig (erkennbar an der gleichen Farbe) dem Codewort $\underline{x}= (x_{1},\ x_{2}, \text{...}\hspace{0.05cm} ,\ x_{n})$ zugeordnet.

Aufgrund von Decodierfehlern $(0 → 1, \ 1 → 0)$ gibt es mehr als vier, nämlich 16 verschiedene Empfangsworte $\underline{y} = (y_{1},\ y_{2}, \text{...} \hspace{0.05cm} ,\ y_{n})$.

Ab Teilaufgabe (4) betrachten wir folgende Zuordnung:

$$\underline{u_0} = (0,\ 0) \leftrightarrow (0,\ 0,\ 0,\ 0) = \underline{x_0}\hspace{0.05cm},$$

$$\underline{u_1} = (0,\ 1) \leftrightarrow (0,\ 1,\ 0,\ 1) = \underline{x_1}\hspace{0.05cm},$$

$$\underline{u_2} = (1,\ 0) \leftrightarrow (1,\ 0,\ 1,\ 0) = \underline{x_2}\hspace{0.05cm},$$

$$\underline{u_3} = (1,\ 1) \leftrightarrow (1,\ 1,\ 1,\ 1) = \underline{x_3}\hspace{0.05cm}.$$

Hinweise:

Die Aufgabe gehört zum Kapitel "Zielsetzung der Kanalcodierung"

Bezug genommen wird insbesondere auf die Seiten

Fragebogen

$k \ = \ $

$n \ = \ $

$R \ = \ $

	Ja,
	Nein.

$ w_{\rm H} \ (\underline{x}_0) \ = \ $

$ w_{\rm H} \ (\underline{x}_1) \ = \ $

$ w_{\rm H} \ (\underline{x}_2) \ = \ $

$ w_{\rm H} \ (\underline{x}_3) \ = \ $

$ d_{\rm H} \ (\underline{x}_0, \underline{x}_1) \ = \ $

$ d_{\rm H} \ (\underline{x}_0, \underline{x}_3) \ = \ $

$ d_{\rm H} \ (\underline{x}_1, \underline{x}_2) \ = \ $

$ d_{\rm min} (\mathcal{C}) \ = \ $

Musterlösung

(1) Der Codeumfang ist hier zu $|\mathcal{C}| = 4$ gegeben.

Allgemein gilt $|\mathcal{C}|= 2^k$.
Daraus folgt $\underline{ k = 2}$.

(2) Jedes Codewort $\underline{x}$ ist eineindeutig einem Informationsblock $\underline{u}$ zugeordnet.

Durch Verfälschungen einzelner der insgesamt $n$ Bit eines Codewortes $\underline{x}$ ergeben sich die Empfangsworte $\underline{y}$.
Aus der Anzahl $(16 = 2^4)$ der möglichen Empfangsworte folgt $\underline{ n = 4}$.

(3) Die Coderate ist per Definition $R = k/n$. Mit den obigen Ergebnissen erhält man $\underline{R = 0.5}$.

(4) Richtig ist Ja: Ein systematischer Code zeichnet sich dadurch aus, dass jeweils die ersten $k$ Bit der Codeworte identisch sind mit dem Informationsblock.

(5) Das Hamming–Gewicht eines binären Codes ist gleich der algebraischen Summe $x_1 + x_2 + \text{...} + x_n$ über alle Codewortelemente. Damit gilt:

$$w_{\rm H}(\underline{x}_0) \hspace{0.15cm} \underline {= 0} \hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_1) \hspace{0.15cm} \underline {= 2} \hspace{0.05cm}, \hspace{0.3cm} w_{\rm H}(\underline{x}_2) \hspace{0.15cm} \underline {= 2}\hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_3) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm}.$$

(6) Die Hamming–Distanz zwischen zwei Codeworten kann hier nur die Werte $2$ und $4$ annehmen:

$$d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_1) \hspace{0.15cm} \underline {= 2}\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_2) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_3) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm},$$

$$ d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_2) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_2, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}.$$

(7) Aus dem Ergebnis der Teilaufgabe (6) folgt $d_{\rm min}(\mathcal{C}) \hspace{0.15cm}\underline{= 2}$.

Allgemein gilt für diese Größe:

$$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.$$

@@ Zeile 2: / Zeile 2: @@
 }}
-[[Datei:|right|]]
+[[Datei:P_ID2381__KC_A_1_2.png|right|frame|Verdeutlichung der Kanal(de)codierung]]
+Die Grafik verdeutlicht die hier betrachtete Kanalcodierung&nbsp; $\mathcal{C}$:
+*Es gibt vier mögliche Informationsblöcke&nbsp; $\underline{u} = (u_{1},\ u_{2}, \text{...}\hspace{0.05cm} ,\ u_{k})$.
+*Jeder Informationsblock&nbsp; $\underline{u}$&nbsp; wird eindeutig&nbsp; (erkennbar an der gleichen Farbe)&nbsp; dem Codewort&nbsp; $\underline{x}= (x_{1},\ x_{2}, \text{...}\hspace{0.05cm}  ,\ x_{n})$&nbsp; zugeordnet.
+*Aufgrund von Decodierfehlern&nbsp; $(0 → 1, \ 1 → 0)$&nbsp; gibt es mehr als vier,&nbsp; nämlich 16 verschiedene Empfangsworte&nbsp; $\underline{y} = (y_{1},\ y_{2}, \text{...} \hspace{0.05cm} ,\ y_{n})$.
+Ab Teilaufgabe&nbsp; '''(4)'''&nbsp; betrachten wir folgende Zuordnung:
+:$$\underline{u_0} = (0,\ 0) \leftrightarrow (0,\ 0,\ 0,\ 0) = \underline{x_0}\hspace{0.05cm},$$
+:$$\underline{u_1} = (0,\ 1) \leftrightarrow (0,\ 1,\ 0,\ 1) = \underline{x_1}\hspace{0.05cm},$$
+:$$\underline{u_2} = (1,\ 0) \leftrightarrow (1,\ 0,\ 1,\ 0) = \underline{x_2}\hspace{0.05cm},$$
+:$$\underline{u_3} = (1,\ 1) \leftrightarrow (1,\ 1,\ 1,\ 1) = \underline{x_3}\hspace{0.05cm}.$$
+Hinweise:
+*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung|"Zielsetzung der Kanalcodierung"]]
+*Bezug genommen wird insbesondere auf die Seiten&nbsp;
+:*[[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Blockschaltbild_und_Voraussetzungen|"Blockschaltbild und Voraussetzungen"]],
+:*[[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|"Einige wichtige Definitionen zur Blockcodierung"]].
@@ Zeile 10: / Zeile 35: @@
 {Aus wievielen Binärsymbolen besteht ein Informationsblock?
 |type="{}"}
-$k \ = \ $ { 2 3% }
+$k \ = \ $ { 2 }
-{Wie groß ist die Codewortlänge ''n''?
+{Wie groß ist die Codewortlänge&nbsp; $n$?
 |type="{}"}
-$n \ = \ $ { 4 3% } $\  \rm$
+$n \ = \ $ { 4 }
 {Wie groß ist die Coderate?
 |type="{}"}
-$R \ = \ $ { 0.5 3% } $\  \rm$
+$R \ = \ $ { 0.5 3% }
-{Multiple-Choice Frage
+{Ist der hier vorgegebene Code systematisch?
-|type="[]"}
+|type="()"}
-- Falsch
++ Ja,
-+ Richtig
+- Nein.
-{Input-Box Frage
+{Geben Sie die Hamming–Gewichte aller Codeworte an.
 |type="{}"}
-$\alpha$ = { 0.3 }
+$ w_{\rm H} \  (\underline{x}_0) \ = \ $ { 0. }
+$ w_{\rm H} \  (\underline{x}_1) \ = \ $ { 2 }
+$ w_{\rm H} \  (\underline{x}_2) \ = \ $ { 2 }
+$ w_{\rm H} \  (\underline{x}_3) \ = \ $ { 4 }
-{Input-Box Frage
+{Geben Sie die Hamming–Distanzen zwischen folgenden Codeworten an.
 |type="{}"}
-$\alpha$ = { 0.3 }
+$ d_{\rm H} \  (\underline{x}_0, \underline{x}_1) \ = \ $ { 2 }
+$ d_{\rm H} \  (\underline{x}_0, \underline{x}_3) \ = \ $ { 4 }
+$ d_{\rm H} \  (\underline{x}_1, \underline{x}_2) \ = \ $ { 4 }
-{Input-Box Frage
+{Wie groß ist die minimale Hamming–Distanz des betrachteten Codes&nbsp; $\mathcal{C}$?
 |type="{}"}
-$\alpha$ = { 0.3 }
+$ d_{\rm min}  (\mathcal{C}) \ = \ $ { 2 }
@@ Zeile 46: / Zeile 73: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''1.'''
+'''(1)'''&nbsp; Der Codeumfang ist hier zu&nbsp; $|\mathcal{C}| = 4$&nbsp; gegeben.
-'''2.'''
+*Allgemein gilt&nbsp; $|\mathcal{C}|= 2^k$.
-'''3.'''
+*Daraus folgt&nbsp; $\underline{ k = 2}$.
-'''4.'''
-'''5.'''
-'''6.'''
-'''7.'''
+'''(2)'''&nbsp; Jedes Codewort &nbsp;  $\underline{x}$ &nbsp;  ist eineindeutig einem Informationsblock&nbsp;   $\underline{u}$&nbsp;  zugeordnet.
+*Durch Verfälschungen einzelner der insgesamt&nbsp;  $n$&nbsp;   Bit eines Codewortes&nbsp;  $\underline{x}$&nbsp; ergeben sich die Empfangsworte&nbsp;    $\underline{y}$.
+*Aus der Anzahl&nbsp; $(16 = 2^4)$&nbsp; der möglichen Empfangsworte folgt&nbsp; $\underline{ n = 4}$.
+'''(3)'''&nbsp; Die Coderate ist per Definition&nbsp; $R = k/n$.&nbsp; Mit den obigen Ergebnissen erhält man&nbsp; $\underline{R = 0.5}$.
+'''(4)'''&nbsp; Richtig ist&nbsp; <u>Ja</u>:&nbsp; Ein systematischer Code zeichnet sich dadurch aus,&nbsp; dass jeweils die ersten&nbsp; $k$&nbsp; Bit der Codeworte identisch sind mit dem Informationsblock.
+'''(5)'''&nbsp;  Das Hamming–Gewicht eines binären Codes ist gleich der algebraischen Summe&nbsp; $x_1 + x_2 + \text{...} + x_n$&nbsp; über alle Codewortelemente.&nbsp; Damit gilt:
+:$$w_{\rm H}(\underline{x}_0) \hspace{0.15cm} \underline {= 0} \hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_1) \hspace{0.15cm} \underline {= 2} \hspace{0.05cm}, \hspace{0.3cm} w_{\rm H}(\underline{x}_2) \hspace{0.15cm} \underline {= 2}\hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_3) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm}.$$
+'''(6)'''&nbsp; Die Hamming–Distanz zwischen zwei Codeworten kann hier nur die Werte&nbsp; $2$&nbsp; und&nbsp; $4$&nbsp; annehmen:
+:$$d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_1) \hspace{0.15cm} \underline {= 2}\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_2) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_3) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm},$$
+:$$ d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_2) \hspace{0.15cm} \underline {= 4}\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_2, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}.$$
+'''(7)'''&nbsp; Aus dem Ergebnis der Teilaufgabe&nbsp; '''(6)'''&nbsp; folgt&nbsp; $d_{\rm min}(\mathcal{C}) \hspace{0.15cm}\underline{= 2}$.
+*Allgemein gilt für diese Größe:
+:$$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.$$
 {{ML-Fuß}}