Aufgaben:Aufgabe 1.2: Einfacher binärer Kanalcode: Unterschied zwischen den Versionen
Zeile 7: | Zeile 7: | ||
*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. | *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 4, nämlich 16 verschiedene Empfangsworte $\underline{y} = (y_{1}, y_{2}, \text{...} \hspace{0.05cm} , y_{n})$. | *Aufgrund von Decodierfehlern $(0 → 1, \ 1 → 0)$ gibt es mehr als 4, nämlich 16 verschiedene Empfangsworte $\underline{y} = (y_{1}, y_{2}, \text{...} \hspace{0.05cm} , y_{n})$. | ||
+ | |||
+ | |||
Ab Teilaufgabe (4) betrachten wir folgende Zuordnung: | 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_0} = (0, 0) \leftrightarrow (0, 0, 0, 0) = \underline{x_0}\hspace{0.05cm},$$ | ||
Zeile 58: | Zeile 60: | ||
{Wie groß ist die minimale Hamming–Distanz des betrachteten Codes $\mathcal{C}$? | {Wie groß ist die minimale Hamming–Distanz des betrachteten Codes $\mathcal{C}$? | ||
|type="{}"} | |type="{}"} | ||
− | $ d_{\rm min} | + | $ d_{\rm min} (\mathcal{C}) \ = \ $ { 2 } |
Zeile 65: | Zeile 67: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Der Codeumfang ist hier zu |C| = 4 gegeben. Allgemein gilt |C| = | + | '''(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 <u>Ja</u>. 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 + ... + x_n über alle Codewortelemente. Damit gilt: | + | '''(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}.$$ | :$$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: | + | '''(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}_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}.$$ | :$$ 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}.$$ | :$$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}.$$ | ||
Version vom 28. November 2017, 13:24 Uhr
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 4, 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 Blockschaltbild und Voraussetzungen und Einige wichtige Definitionen zur Blockcodierung.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
(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}.$$