Aufgaben:Exercise 1.6: (7, 4) Hamming Code

• Return to book

Tabelle des (7, 4)–Hamming–Codes

1962 hat Richard Wesley Hamming eine Klasse binärer Blockcodes angegeben, die sich durch die Anzahl m der zugeführten Prüfbits unterscheiden. Die Codewortlänge ist bei diesen Codes stets $n = 2^m – 1$ und das Informationswort besteht aus $k = n – m$ Bit:

• m = 2: (3, 1) Hamming–Code, ⇒ RC (3, 1),
• m = 3: (7, 4) Hamming–Code,
• m = 4: (15, 11) Hamming–Code,
• m = 5: (31, 26) Hamming–Code, usw.

Im Verlaufe dieser Aufgabe gibt es Fragen

• zum Codeumfang |C|,
• zur Coderate R, und
• zur minimalen Distanz $d_{\rm min}$

dieser Codeklasse. Weiterhin soll geklärt werden, ob der für diese Aufgabe durch seine Codetabelle $\underline{u}_{\rm i} ⇒ \underline{x}_{\rm i}$ gegebene (7, 4)–Hamming–Code systematisch ist, und ob es sich um einen

so genannten „perfekten Code” handelt. Der Laufindex kann hierbei die Werte $i = 1, ... , 2^k =16$ annehmen.

Hinweis :

Die Aufgabe bezieht sich auf das Kapitel Beispiele binärer Blockcodes. Genaueres zu den Hamming–Codes finden Sie auf folgenden Seiten:

• Hamming–Codes (1),
• Hamming–Codes (2),
• Einige Eigenschaften des (7, 4, 3)–Hamming–Codes.

Für diesen Hamming–Code wurden andere Prüfgleichungen herangezogen als im Theorieteil. Deshalb unterscheiden sich auch die Codetabellen. In der Aufgabe 1.07, bei der der gleiche Code verwendet wird, ist das Schaubild der Prüfgleichungen angegeben.

Man spricht von einem perfekten Code, wenn folgende Bedingung erfüllt ist:

$$2^k = \frac{2^n} {\sum_{f=0}^t {n \choose f}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$

Hierbei bezeichnet t die Anzahl der korrigierbaren Fehler. Bei ungerader Minimaldistanz $d_{rm\ min}$ gilt:

$$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$

Die Interpretation zu dieser Bedingung finden Sie in der Musterlösung zu dieser Aufgabe.

Fragebogen

1

Geben Sie die Kenngrößen des gegebenen Codes C an:

$\ |C|$ =

$\ k$ =

$\ n$ =

$\ R$ =

2

Handelt es sich um einen systematischen Code?

	Ja,
	Nein.

3

Wie groß ist die minimale Distanz zwischen zwei beliebigen Codeworten?

$ \ d_{\rm min}$ =

4

Wieviele Übertragungsfehler können erkannt (e) bzw. korrigiert (t) werden?

$ \ e$ =

$ \ t$ =

5

Ist der hier betrachtete Hamming–Code perfekt?

	Ja,
	Nein.

6

Welche Aussagen gelten hinsichtlich eines perfekten Codes?

	Ein perfekter Code führt stets zu Pr(Blockfehler) = 0.
	Alle Empfangsworte y sind einem gültigen Codewort zuordbar.
	Bei perfekten Codes ist die minimale Hamming–Distanz ungerade.

7

Welche der nachfolgend genannten Codes sind perfekt?

	(15,11)–Hamming–Code,
	(63,57)–Hamming–Code,
	(3,1)–Repetition Code,
	(4,1)–Repetition Code,
	(5,1)–Repetition Code.

Musterlösung

Solution

1. 2. 3. 4. 5. 6. 7.