Exercise 1.09: Extended Hamming Code
Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind. Die ersten vier Bit eines jeden Codewortes x geben das jeweilige Informationswort u wider (schwarze Schrift). Danach folgen $m = n – k$ Prüfbit (rote Schrift).
- Der systematische (7, 4)–Hamming–Code wurde bereits in Aufgabe 1.6 sowie Aufgabe 1.07 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 $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 „erweiteter Hamming–Code” bezeichnet wird. Wir nennen diesen (grün hinterlegten) Code im Folgenden $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 (8, 4)–Hamming–Codes.
Hinweis :
Die Aufgabe gehört zu Kapitel Allgemeine Beschreibung linearer Blockcodes. Beachten Sie bei der Lösung, dass $C_{1}$ und $C_{2}$ jeweils systematische Codes sind. Die nachfolgende Aufgabe 1.09Z behandelt die Erweiterung von Codes in etwas allgemeinerer Form.
Fragebogen
Musterlösung
- $C_{1} : n = 7, k = 4 ⇒ R = 4/7 \underline {= 0.571},$
- $C_{2} : n = 8, k = 4 ⇒ R = 4/8 \underline { =0.5}.$
(2) Die minimale Distanz des (7, 4, 3)–Hamming–Codes $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. $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 $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 \hspace{-0.3cm} \ \oplus \ \hspace{-0.25cm} x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.3cm} x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$
- $$ x_1 \hspace{-0.3cm} \ \oplus \ \hspace{-0.25cm} x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},\hspace{0.3cm} 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 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.
