/ Informationstheorie

Hamming-Distanz

Aus der minimalen Hamming-Distanz d eines Blockcodes folgen Erkennbar = d − 1 Fehler und Korrigierbar = ⌊(d − 1) / 2⌋ Fehler.

Hamming-Distanz

01 · Eingabe

Hamming-Distanz berechnen

Aus der minimalen Hamming-Distanz d eines Blockcodes folgen Erkennbar = d − 1 Fehler und Korrigierbar = ⌊(d − 1) / 2⌋ Fehler.

Lösen für

Erkennbar = d - 1

d Hamming-Distanz

Worum geht es?

Die Hamming-Distanz d zwischen zwei Bitstrings ist die Anzahl der Positionen, an denen sich die beiden Strings unterscheiden. Die minimale Hamming-Distanz eines Blockcodes ist das Minimum dieser Distanz über alle Paare gültiger Codewörter.

Aus dieser Größe folgt direkt, wie robust der Code ist:

Erkennbar = d − 1 Bitfehler
Korrigierbar = ⌊(d − 1) / 2⌋ Bitfehler

Die Formel

Formel Hamming-Distanz

Erkennbar    = d − 1
Korrigierbar = ⌊(d − 1) / 2⌋

Umstellung:
    d = Erkennbar + 1

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
d	Hamming-Distanz	—	Minimale Hamming-Distanz des Codes.
Erkennbar	Erkennbare Fehler	—	Anzahl sicher erkennbarer Bitfehler.

Minimal-Beispiel

Code mit d = 3:

Rechnung d = 3

Erkennbar    = 3 − 1 = 2
Korrigierbar = ⌊2 / 2⌋ = 1

Ein einfacher Hamming(7,4)-Code erkennt also 2 Fehler und korrigiert 1.

Praxis-Beispiele

Beispiel 1 — Paritätsbit

Einfaches Paritätsbit liefert d = 2:

Rechnung Parität

Erkennbar    = 1
Korrigierbar = 0

Beispiel 2 — Erweiterter Hamming-Code

Erweiterter Hamming-Code mit d = 4:

Rechnung d = 4

Erkennbar    = 3
Korrigierbar = ⌊3 / 2⌋ = 1

Beispiel 3 — Gewünschte Fehlerkorrektur

Du willst 2 Bitfehler korrigieren können:

Rechnung Mindest-d

⌊(d − 1) / 2⌋ ≥ 2
⇒ d ≥ 5