Aufgaben:Exercise 1.09: Extended Hamming Code

• Return to book

(7, 4) Hamming–Code
und (8, 4) Erweiterung

Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind.

• Die ersten vier $\rm 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 (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 „erweiteter 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 (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.09Z 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 (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.