Aufgabe 1.09: Erweiterter Hamming–Code
und $\text{(8, 4)}$–Erweiterung (grün)
Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind.
- Die ersten vier Bit eines jeden Codewortes $\underline{x}$ sind gleich dem jeweiligen Informationswort $\underline{u}$ (schwarze Schrift).
- Danach folgen $m = n- k$ Prüfbit (rote Schrift).
Der systematische $\text{(7, 4)}$–Hamming–Code wurde bereits in Aufgabe 1.6 sowie Aufgabe 1.7 behandelt. Prüfmatrix und Generatormatrix dieses Codes sind wie folgt gegeben:
- $${ \boldsymbol{\rm H}}_1 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},$$
- $${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
Im weiteren Verlauf der Aufgabe wird dieser (gelb hinterlegte) Code $\mathcal{C}_{1}$ genannt.
Die rechte Spalte in obiger Tabelle gibt einen Blockcode mit den Parametern $n = 8$ und $k = 4$ an, der in der Literatur meist als „Erweiterter Hamming–Code” bezeichnet wird. Wir nennen diesen (grün hinterlegten) Code im Folgenden $\mathcal{C}_{2}$ und bezeichnen dessen Prüfmatrix mit ${ \boldsymbol{\rm H}}_{2}$ und die dazugehörige Generatormatrix mit ${ \boldsymbol{\rm G}}_{2}$ .
Die Fragen zu dieser Aufgabe beziehen sich auf
- die Coderate,
- die minimale Distanz zwischen zwei Codeworten,
- die Prüfmatrix und die Generatormatrix des erweiterten $\text{(8, 4)}$–Hamming–Codes.
Hinweise:
- Die Aufgabe gehört zum Kapitel Allgemeine Beschreibung linearer Blockcodes.
- Beachten Sie bei der Lösung, dass $\mathcal{C}_{1}$ und $\mathcal{C}_{2}$ jeweils systematische Codes sind.
- Die folgende Aufgabe 1.9Z behandelt die Erweiterung von Codes in etwas allgemeinerer Form.
Fragebogen
Musterlösung
- $\mathcal{C}_{1} \text{:} \ n = 7, k = 4\ ⇒ \ R = 4/7 \underline {= 0.571},$
- $\mathcal{C}_{2} \text{:} \ n = 8, k = 4 \ ⇒ \ R = 4/8 \underline { =0.5}.$
(2) Die minimale Distanz des (7, 4, 3)–Hamming–Codes $\mathcal{C}_{1}$ beträgt $d_{\rm min} \underline{= 3}$, was allein schon aus der Namensgebung ablesbar ist.
- Aus der Tabelle auf der Angabenseite ist ersichtlich, dass für den erweiterten Hamming–Code $d_{\rm min} \underline{= 4}$ gilt.
- $\mathcal{C}_{2}$ bezeichnet man deshalb in der Literatur auch als einen (8, 4, 4)–Blockcode.
(3) Die Prüfmatrix ${ \boldsymbol{\rm H}}$ besteht im Allgemeinen aus $n$ Spalten und $m = n – k$ Zeilen, wobei $m$ die Anzahl der Prüfgleichungen angibt.
- Beim (7, 4, 3)–Hamming–Code ist ${ \boldsymbol{\rm H}}$ eine 3 × 7–Matrix.
- Für den erweiterten Hamming–Code ⇒ Code $\mathcal{C}_{2}$ gilt demgegenüber $\underline{n = 8}$ (Spaltenzahl) und $\underline{m = 4}$ (Zeilenzahl).
(4) Aus der Codetabelle auf der Angabenseite erkennt man, dass allein Antwort 3 richtig ist.
- Das Prüfbit $p_{4}$ ist so zu bestimmen, dass die Modulo–2–Summe über alle Bits des Codewortes den Wert $0$ ergibt.
(5) Anzumerken ist zunächst, dass die Angabe der Prüfmatrix nie eindeutig ist, schon allein deshalb, weil die Reihenfolge der Prüfgleichungen vertauschbar ist.
- Unter Berücksichtigung des Hinweises, dass nur eine der vorgegebenen Zeilen falsch ist, ist ${ \boldsymbol{\rm H}}_{2}$ allerdings eindeutig bestimmt:
- $${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
- Richtig sind also die Aussagen 1, 2 und 4. Die Zeilen dieser Prüfmatrix stehen in dieser Reihenfolge für die vier Prüfgleichungen:
- $$ x_1\oplus x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$
- $$x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$
- $$ x_1 \oplus x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},$$
- $$ x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0 \hspace{0.05cm}.$$
(6) Richtig ist die Antwort 2:
- Zu diesem Ergebnis kommt man, wenn man die letzte Zeile durch die Modulo–2–Summe über alle vier Zeilen ersetzt, was erlaubt ist.
- Der Vorschlag 1 stellt keine Prüfgleichung dar.
- Der Vorschlag 3 steht für die Prüfgleichung $x_{3}⊕x_{5} = 0$, was auch nicht den Gegebenheiten entspricht.
Entsprechend dem richtigen Lösungsvorschlag 2 wird dagegen die Prüfgleichung
- $$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$
durch folgende neue Prüfgleichung ersetzt:
- $$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
Die modifizierte Prüfmatrix lautet nun:
- $${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
(7) Nach dieser Matrixmanipulation liegt ${ \boldsymbol{\rm H}}_{2}$ in der für systematische Codes typischen Form vor:
- $${ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} m = 4 {\rm :}\hspace{0.3cm}{ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_4 \right) \hspace{0.05cm}.$$
Damit lautet die Generatormatrix:
- $${ \boldsymbol{\rm G_{2}}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 &1\\ 0 &1 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
Richtig sind also die Aussagen 2 und 3:
- ${ \boldsymbol{\rm G}}_{2}$ beginnt wie ${ \boldsymbol{\rm G}}_{1}$ (siehe Angabenblatt) mit einer Diagonalmatrix ${ \boldsymbol{\rm I}}_{4}$ , hat aber im Gegensatz zu ${ \boldsymbol{\rm G}}_{1}$ nun 8 Spalten.
- Im vorliegenden Fall $n = 8, k = 4 \ ⇒ \ m = 4$ sind sowohl ${ \boldsymbol{\rm G}}_{2}$ als auch ${ \boldsymbol{\rm H}}_{2}$ jeweils 4×8–Matrizen.
