Fehlerkorrektur-Codes: Funktionsweise und Hamming-Code
Fehlererkennung und Fehlerkorrektur
Fehlerkorrektur-Codes dienen nicht nur dazu, das Vorhandensein eines Fehlers zu erkennen, sondern informieren auch darüber, welche Binärziffern oder Stellen betroffen sind, um deren Werte gezielt zu korrigieren. Diese Codes werden vor allem in Situationen eingesetzt, in denen eine erneute Übertragung der Nachricht bei Fehlern nicht möglich ist oder wenn Übertragungssysteme eine hohe Fehlerrate aufweisen.
In Systemen mit einer niedrigen Fehlerquote und der Möglichkeit zur erneuten Anforderung sind sie weniger gebräuchlich, da die Menge der erforderlichen redundanten Stellen zur Korrektur mehrerer Bit-Fehler im Vergleich zur Länge des zu übermittelnden Wortes sehr groß ist.
Der Hamming-Code
Einer der am häufigsten verwendeten Fehlerkorrektur-Codes ist der Hamming-Code. Hierbei werden mehrere Paritätsbits für jedes Wort eingefügt. Wenn die Anzahl der Paritätsbits korrekt gewählt ist, lässt sich die Position des aufgetretenen Fehlers bestimmen und somit korrigieren. Jedes Paritätsbit deckt eine spezifische Gruppe von Informationsbits ab.
Prinzipien des Hamming-Codes
Der grundlegende Aufbau eines Hamming-Codes zur Korrektur von Ein-Bit-Fehlern bei einem Binärcode von N Bits umfasst folgende Schritte:
- Jedem Wort aus N Binärstellen werden K zusätzliche Bits hinzugefügt, um ein Codewort der Länge N + K zu erzeugen.
- Die Paritätsbits werden nicht am Ende angefügt, sondern an Positionen eingefügt, die Zweierpotenzen entsprechen (1, 2, 4, 8, 16, etc.).
- Die zusätzlichen Stellen werden so generiert, dass die K Paritätsbits ein binäres Wort bilden, das die Position des fehlerhaften Bits angibt oder eine Null liefert, falls kein Fehler vorliegt.
- Jedes Paritätsbit kann in mehr als eine Paritätsberechnung einbezogen werden.
Mathematische Grundlage
Wenn ein Wort der Länge N + K übertragen wird und die Möglichkeit eines Fehlers in einer der N + K Stellen sowie der Fall „kein Fehler“ existiert (insgesamt N + K + 1 Fälle), muss die Ungleichung 2K ≥ N + K + 1 erfüllt sein, um alle Fälle darstellen zu können. Ein Hamming-Code gilt als optimal, wenn er die Gleichung N = 2K - K - 1 erfüllt.