/ Informationstheorie

Hamming-Code Prüfbits

Anzahl Prüfbits r für m Datenbits im (m+r,m)-Hamming-Code: kleinstes r mit 2^r ≥ m + r + 1.

01 · Eingabe

Hamming-Code Prüfbits berechnen

Anzahl Prüfbits r für m Datenbits im (m+r,m)-Hamming-Code: kleinstes r mit 2^r ≥ m + r + 1.

r: 2^r >= m + r + 1

m Datenbits

Bit

Worum geht es?

Beim Hamming-Code werden m Datenbits durch r Prüfbits zu einem Codewort der Länge m + r ergänzt. Damit jede Bitposition (inklusive der Prüfbits selbst) eindeutig durch die Prüfbits adressierbar ist, muss gelten:

2^r ≥ m + r + 1

Gesucht ist das kleinste r, das diese Ungleichung erfüllt.

Die Formel

Formel Prüfbits

r: kleinstes r mit 2^r ≥ m + r + 1

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
m	Datenbits	Bit	Anzahl Nutzdaten-Bits.
r	Prüfbits	Bit	Benötigte Prüfbits für (m+r,m)-Code.

Minimal-Beispiel

4 Datenbits (klassischer (7,4)-Code):

Rechnung m = 4

r = 1: 2^1 = 2  < 4 + 1 + 1 = 6   ✗
r = 2: 2^2 = 4  < 4 + 2 + 1 = 7   ✗
r = 3: 2^3 = 8  ≥ 4 + 3 + 1 = 8   ✓
⇒ r = 3

Ergebnis: 3 Prüfbits — (7,4)-Hamming-Code.

Praxis-Beispiele

Beispiel 1 — 8 Datenbits

Rechnung m = 8

r = 4: 2^4 = 16 ≥ 8 + 4 + 1 = 13  ✓
⇒ r = 4  ⇒ (12,8)-Code

Beispiel 2 — 16 Datenbits

Rechnung m = 16

r = 5: 2^5 = 32 ≥ 16 + 5 + 1 = 22 ✓
⇒ r = 5  ⇒ (21,16)-Code

Beispiel 3 — 64 Datenbits

Rechnung m = 64

r = 7: 2^7 = 128 ≥ 64 + 7 + 1 = 72 ✓
⇒ r = 7  ⇒ (71,64)-Code

Der relative Overhead sinkt mit wachsendem m: bei 4 Datenbits 75 %, bei 64 Datenbits nur noch knapp 11 %.