Inhalt
Hamming-Codes werden verwendet, um Fehlerkorrekturinformationen in Datenströme einzufügen. Die Codes sind so konzipiert, dass ein Fehler nicht nur erkannt, sondern auch korrigiert wird. Das Hinzufügen von Fehlerkorrekturinformationen erhöht die Datenmenge, erhöht aber auch die Zuverlässigkeit der Kommunikation über Medien mit hohen Fehlerraten.
Die Implementierung der Hamming-Codierung kann kompliziert sein, sie kann jedoch sehr schnell mit arithmetischen Tricks auf Bitebene durchgeführt werden. Dies ermöglicht die Erstellung eines nützlichen und schnellen Fehlerkorrektursystems, das in eingebetteten Anwendungen verwendet werden kann.
Schritt 1
Erstellen Sie das Datenwort. Jedes Bit mit einer Position, die eine Zweierpotenz ist (erste, zweite, vierte usw.), muss für Paritätsinformationen reserviert werden. Verwenden Sie so lange, bis das Wort die Originaldaten und Paritätsbits enthält.
Beispiel:
1 1 0 1 0 0 1 0 wird zu _ _ 1 _ 1 0 1 _ 0 0 1 0
Die ursprünglichen Bits bleiben in derselben Reihenfolge, wurden jedoch verteilt, um die Paritätsbits einzufügen.
Schritt 2
Berechnen Sie das erste Paritätsbit. Beginnend mit dem ersten Bit wird ein Bit gelesen und dann ein Bit übersprungen und der Vorgang bis zum Ende wiederholt. In der Zwischenzeit wird die Anzahl der gefundenen gezählt. Paritätsbits zählen bei diesem Vorgang nicht.
Wenn die Anzahl der Einsen gerade ist, setzen Sie das erste Bit auf Null. Andernfalls setzen Sie es auf eins.
Beispiel:
Die Bits 1, 3, 5, 7, 9 und 11 von _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101 enthalten vier Einsen. Dies ist gerade, daher wird das erste Bit auf Null gesetzt: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Schritt 3
Berechnen Sie die verbleibenden Paritätsbits. Beginnend mit dem zweiten Bit werden zwei Bits gelesen und dann zwei Bits übersprungen und die Prozedur bis zum Ende wiederholt. Das vierte Bit liest vier Bits, überspringt weitere vier, beginnend mit Bit vier. Dem gleichen Muster folgen alle Paritätsbits, bis sie alle berechnet sind.
Beispiel:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 prüft _1, 01, 01, die drei Einsen enthalten, sodass Bit 2 auf eins gesetzt wird. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 prüft _101, 0, das zwei Einsen enthält, sodass Bit 4 auf Null gesetzt wird. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 prüft _0010, das nur eins enthält, also wird Bit 8 auf eins gesetzt.
Das Wort ist daher als 011010110010 codiert.
Schritt 4
Bestätige das Wort. Wenn ein Wort beschädigt ist, stimmen die Paritätsbits nicht mit den Erwartungen überein. Um zu bestätigen, dass das Wort nicht verfälscht ist, berechnen Sie einfach die Paritätsbits mit den Schritten zwei und drei. Wenn die Bits nicht gleich sind, notieren Sie ihre Positionen.
Schritt 5
Korrigieren Sie das falsche Bit. Wenn Sie falsche Paritätsbits finden, fügen Sie einfach die Positionen der Bits hinzu. Der Summenwert ist die Position des falschen Bits. Ändern Sie den Bitwert an dieser Position.
Wenn beispielsweise die falschen Paritätsbits eins und vier sind, wird der Fehler durch Ändern des Werts des fünften Bits korrigiert.