Was ist ein Hamming-Code?
Ein Hamming-Code ist ein Verfahren zum Erkennen und Korrigieren von Fehlern in einer binären Übertragung. Dies geschieht durch die Einbeziehung zusätzlicher Binärziffern in die Sequenz, die zur Überprüfung verwendet werden, sowie eines Algorithmus, der die Erkennungslogik bereitstellt. Ein solcher Code ist in der Lage, zwei Fehler in einer beliebigen Folge von Bits zu finden und ein möglicherweise falsches Bit zu reparieren. Der Hamming-Code, auf den am häufigsten Bezug genommen wird, ist als Hamming (7, 4) bekannt, wobei die vier die ursprüngliche Anzahl von Startbits und die sieben die Gesamtanzahl von Bits in der Sequenz darstellen, nachdem die zusätzlichen Prüfbits enthalten wurden.
Die Technik erhielt ihren Namen von ihrem Schöpfer, Richard Hamming, der die Methode 1950 veröffentlichte. Die Funktionsweise des Hamming-Codes besteht darin, eine Folge von Bits zu nehmen und zusätzliche Prüfbits, die als Paritätsbits bezeichnet werden, in die Sequenz einzufügen. Die Prüfbits werden immer an einer Position injiziert, die eine Zweierpotenz ist, sodass eine beliebige Anzahl von Bits durch Einbeziehen zusätzlicher Paritätsbits überprüft werden kann. Dies kann fortgesetzt werden, bis sich das letzte der Sequenz hinzugefügte Paritätsbit in einer Position befindet, die eine Zweierpotenz ist, die kleiner oder gleich der Endposition in der Sequenz ist.
Wenn alle Paritätsbits vorhanden sind, sind die verbleibenden Positionen die tatsächlichen Datenbits. Bei dem Vier-Bit-Beispiel wären dann die Bitpositionen eins, zwei und vier die Paritätsbits, während die Positionen drei, fünf, sechs und sieben die Daten sind. Sobald diese Sequenz erstellt wurde, funktioniert die Logik des Hamming-Codes.
In einem Hamming-Code wird jedes der der Sequenz hinzugefügten Paritätsbits verwendet, um einige der Bitpositionen zu überprüfen, in deren Nähe sie sich befinden, einschließlich sich selbst. Das Paritätsbit in Position eins überprüft jede zweite Bitposition, die im Wesentlichen jede ungeradzahlige Position in der Sequenz ist. Das zweite Paritätsbit an Position zwei überprüft die Positionen zwei und drei, überspringt dann zwei Positionen, überprüft zwei weitere Positionen, überspringt zwei weitere und so weiter. Wenn an Position vier ein Paritätsbit vorhanden ist, prüft es auf ähnliche Weise die Positionen vier bis sieben, überspringt dann vier Positionen, prüft vier weitere und fährt fort. Jedes Paritätsbit in der Sequenz wird auf diese Weise während der gesamten Sequenz fortgesetzt.
Der Prozess, durch den ein Hamming-Code einen Fehler erkennt und korrigiert, besteht darin, die Bits in der Prüfsequenz für jede Paritätsprüfung zu addieren, von denen jedes eine gerade Zahl ergeben muss. Bei dem Sieben-Bit-Beispiel werden für die erste Paritätsprüfung die Bits eins, drei, fünf und sieben addiert. Wenn die Summe eine gerade Zahl ist, wird die Parität ausgecheckt. Wenn die Summe jedoch ungerade ist, liegt ein Fehler vor. Da sich die Paritätsprüfungen überlappen, werden zwei solche Fehler angezeigt. Wenn die Zwei-Paritäts-Bitpositionen, die keine geraden Summen ergeben, addiert werden, wird das zu korrigierende Bit angezeigt.
Berücksichtigen Sie im Sieben-Bit-Hamming-Codebeispiel, dass das Bit an Position fünf falsch ist. Die Summe der Bits an den Positionen eins, drei, fünf und sieben wird als ungerade Zahl ausgegeben, ebenso wie die Summe der Bits an den Positionen vier bis sieben. Dies zeigt an, dass die Paritätsprüfungen für die Prüfbits an Position eins und vier fehlgeschlagen sind. Wenn eins und vier addiert werden, ist die Summe fünf. Dies ist die Position für das falsche Bit in der Übertragung, das korrigiert werden muss.