Exercise 1.09: Extended Hamming Code

• Return to book

$\text{(7, 4)}$–Hamming–Code (gelb hinterlegt)
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

1

Geben Sie die Coderaten von  $\mathcal{C}_{1}$  und  $\mathcal{C}_{2}$  an.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}R \ = \ $

2

Geben Sie die minimalen Distanzen von  $\mathcal{C}_{1}$  und  $\mathcal{C}_{2}$  an.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

3

Welches Format besitzt die Prüfmatrix  $\boldsymbol{\rm H}_{2}$  von  $\mathcal{C}_{2}$?

${\rm Spaltenzahl} \ = \ $

${\rm Zeilenzahl} \ = \ $

4

Leiten Sie aus der Codetabelle die Gleichung für das Codebit  $x_ {8} (= p_{4})$  ab. Welche Angabe ist richtig?

	$x_{8} = 0.$
	$x_{8} = x_{1}⊕x_{2}⊕x_{4}⊕x_{5}.$
	$x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$

5

Welche Aussagen gelten für  ${ \boldsymbol{\rm H}}_{2}$? Hinweis:  Richtig sind 3 von 4 Antworten.

	Die Zeile 1 lautet:   $1 1 0 1 1 0 0 0$.
	Die Zeile 2 lautet:   $0 1 1 1 0 1 0 0$.
	Die Zeile 3 lautet:   $0 0 0 0 1 1 1 1$.
	Die Zeile 4 lautet:   $1 1 1 1 1 1 1 1$.

6

Welche Umformung ist für die letzte Zeile von  ${ \boldsymbol{\rm H}}_{2}$  zulässig?

	$1 1 1 1 1 1 1 1 → 0 0 0 0 0 0 0 0,$
	$1 1 1 1 1 1 1 1 → 1 1 1 0 0 0 0 1,$
	$1 1 1 1 1 1 1 1 → 0 0 1 0 1 0 0 0.$

7

Geben Sie die zugehörige Generatormatrix  ${ \boldsymbol{\rm G}}_{2}$  an. Welche Aussagen treffen zu?

	${ \boldsymbol{\rm G}}_{2}$  hat gleiches Format wie die Matrix  ${ \boldsymbol{\rm G}}_{1}$ des  $\text{(7, 4)}$–Codes.
	${ \boldsymbol{\rm G}}_{2}$  beginnt wie ${ \boldsymbol{\rm G}}_{1}$  mit einer Diagonalmatrix  ${ \boldsymbol{\rm I}}_{4}$ .
	${ \boldsymbol{\rm G}}_{2}$  hat im betrachteten Beispiel das gleiche Format wie  ${ \boldsymbol{\rm H}}_{2}$ .

Musterlösung

Solution

(1)  Die entsprechende Gleichung für die Coderate lautet in beiden Fällen $R = k/n\text{:}$

• $\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.