Aufgabe 1.09: Erweiterter Hamming–Code

• Zurück zum Buch

$\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 Codewörter,

• 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 drei von vier 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

Musterlösung

(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 acht 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.