Der Hamming-Code gehört zu der Gruppe der fehlerkorrigierenden Codes. Er wird eingesetzt, um Daten vor Übertragungsfehlern zu schützen. Er wurde von Richard Hamming im Jahr 1950 entwickelt und ist nach ihm benannt.
Um Fehler erkennen zu können, müssen zusätzliche Bits (Redundanzbits) in den Code eingefügt werden. Die führt zu einer Erhöhung der Redundanz.
Aufbau:
- k Informationsbits: Die eigentlichen Daten, die übertragen werden sollen.
- r Redundanzbits: Die zusätzlichen Bits, die zur Fehlerkorrektur verwendet werden.
- n Gesamtbits: Die Gesamtzahl der Bits in einem Hamming-Codewort (n = k + r).
Fehlerkorrektur:
Der Hamming-Code kann einzelne Bitfehler in einem Codewort erkennen und korrigieren. Dies geschieht durch die Verwendung einer Paritätsprüfung.
- Paritätsbits: Die Redundanzbits werden verwendet, um die Parität (gerade oder ungerade Anzahl von 1-Bits) in bestimmten Bitpositionen des Codeworts zu überprüfen.
- Fehlererkennung: Wenn die Parität an einer bestimmten Position nicht mit der berechneten Parität übereinstimmt, liegt ein Fehler in einem der Datenbits vor.
- Fehlerkorrektur: Durch die Analyse der Paritätsbits kann die Position des fehlerhaften Bits bestimmt und korrigiert werden.
| Dezimalzahl | Hamming Code |
|---|---|
| 0 | 0000000 |
| 1 | 0000111 |
| 2 | 0011001 |
| 3 | 0011110 |
| 4 | 0101010 |
| 5 | 0101101 |
| 6 | 0110011 |
| 7 | 0110100 |
| 8 | 1001011 |
| 9 | 1001100 |
Der Hamming Code in der Tabelle ändert bei jedem Übergang jeweils mindestens 3 Bit.
Hamming-Distanz:
Die Hamming-Distanz zwischen zwei Codewörtern ist die Anzahl der Bits, die sich in den beiden Codewörtern unterscheiden. Der Hamming-Code kann alle Fehler mit einer Hamming-Distanz von 1 korrigieren.
Vorteile:
- Effektive Fehlerkorrektur: Der Hamming-Code kann einzelne Bitfehler effizient erkennen und korrigieren.
- Einfache Implementierung: Der Hamming-Code ist relativ einfach zu implementieren und kann in verschiedenen Hardware- und Softwaresystemen verwendet werden.
- Geringer Overhead: Der Hamming-Code fügt nur einen geringen Overhead an Redundanzbits zu den Daten hinzu.
Nachteile:
- Korrekturgrenze: Der Hamming-Code kann nur Fehler mit einer Hamming-Distanz von 1 korrigieren.
- Erhöhte Komplexität: Der Hamming-Code ist komplexer als einfache Codes wie der ASCII-Code.