Aufgaben:Exercise 1.09: Extended Hamming Code

• Return to book

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

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

1 Geben Sie die Coderaten von $C_{1}$ und $C_{2}$ an.

$\C_{1}: \ \ \ R$ =

$\C_{2}: \ \ \ R$ =

2 Geben Sie die minimalen Distanzen von $C_{1}$ und $C_{2}$ an.

$\C_{1}: \ \ \ d_{\rm min}$ =

$\C_{2}: \ \ \ d_{\rm min}$ =

3 Welches Format besitzt die Prüfmatrix von $C_{2}$?

$\ { \boldsymbol{\rm H}}_{2}{\rm :} \ \ \ {\rm Spaltenzahl}$ =

$\ { \boldsymbol{\rm H}}_{2}{\rm :} \ \ \ {\rm Zeilenzahl}$ =

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

	$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 erste Zeile lautet: $1 1 0 1 1 0 0 0$.
	Die zweite Zeile lautet: $0 1 1 1 0 1 0 0$.
	Die dritte Zeile lautet: $0 0 0 0 1 1 1 1$.
	Die letzte Zeile 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. 2. 3. 4. 5. 6. 7.