Exercise 1.6: (7, 4) Hamming Code
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:
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
Musterlösung
