Deshalb mag ich in diesem Sommer Projekt arbeiten Fehler in einer Nachrichtenübertragung zu korrigieren unter Verwendung von Hamming-Code, aber ich kann nicht herausfinden, wie es wirklich funktioniert. Ich habe viele Artikel online gelesen, aber ich verstehe den Algorithmus nicht wirklich. Kann das jemand in einfachen Worten erklären?Wie eine Nachricht korrigieren Hamming-Code mit
Danke.
Es geht um Hamming distance.
Der Hamming-Abstand zwischen zwei Basis-2-Werten ist die Anzahl der Bits, bei denen sie sich unterscheiden. Wenn Sie also A senden, aber ich B empfange, dann ist die Hamming-Distanz zwischen A und B die Anzahl der Bits, die gesendet werden müssen.
Hamming-Codes sind nützlich, wenn die Bits in jedem Codewort irgendwie übertragen werden separat. Es ist uns egal, ob sie seriell oder parallel sind, aber sie werden nicht zum Beispiel in einen analogen Wert kombiniert, der mehrere Bits repräsentiert, oder nach der Codierung komprimiert/verschlüsselt.
Somit wird jedes Bit unabhängig (zufällig mit einer festen Wahrscheinlichkeit), entweder korrekt empfangen, oder umgedreht. Unter der Annahme, dass die Übertragung ziemlich zuverlässig ist, werden die meisten Bits korrekt empfangen. So sind Fehler in einer kleinen Anzahl von Bits wahrscheinlicher, und gleichzeitige Fehler in großen Anzahlen von Bits sind unwahrscheinlich.
Also zielt ein Hamming-Code in der Regel darauf ab, 1-Bit-Fehler zu korrigieren und/oder 2-Bit-Fehler zu erkennen (siehe Wikipedia-Artikel für Details zu den beiden Haupttypen). Codes, die größere Fehler korrigieren/erkennen, können konstruiert werden, aber AFAIK werden nicht so oft verwendet.
Der Code funktioniert, indem die Codepunkte im "Hamming-Raum" gleichmäßig verteilt werden, was mathematisch der metrische Raum ist, der aus allen Werten der relevanten Wortgröße mit Hamming-Abstand als Metrik besteht. Stellen Sie sich vor, dass jeder Codepunkt von einer kleinen "Pufferzone" mit ungültigen Werten umgeben ist. Wenn ein Wert empfangen wird, der kein Codepunkt ist, muss ein Fehler aufgetreten sein, da immer nur gültige Codepunkte übertragen werden.
Wenn ein Wert in der Pufferzone empfangen wird, dann unter der Annahme, dass ein 1-Bit-Fehler aufgetreten ist, muss der übertragene Wert Abstand 1 vom empfangenen Wert sein. Da die Codepunkte jedoch verteilt sind, schließt nur ein Codepunkt. Es wird also auf diesen Codepunkt "korrigiert", weil ein 1-Bit-Fehler wahrscheinlicher ist als der größere Fehler, der für jeden anderen Codepunkt erforderlich wäre, um den empfangenen Wert zu erzeugen. In Wahrscheinlichkeit ausgedrückt ist die bedingte Wahrscheinlichkeit, dass Sie den nahegelegenen Codepunkt gesendet haben, größer als die bedingte Wahrscheinlichkeit, dass Sie einen anderen Codepunkt senden, da ich den Wert erhalten habe, den ich gemacht habe. Ich nehme an, dass Sie das nahe liegende mit einer gewissen Sicherheit gesendet haben, basierend auf der Zuverlässigkeit der Übertragung und der Anzahl der Bits in jedem Wort.
Wenn ein ungültiger Wert empfangen wird, der von zwei Codepunkten gleich weit entfernt ist, kann ich nicht sagen, dass einer wahrscheinlicher als der andere ist. Ich erkenne den Fehler, kann ihn aber nicht korrigieren.
Offensichtlich werden 3-Bit-Fehler nicht durch einen SECDED-Hamming-Code korrigiert. Der empfangene Wert ist weiter von dem Wert, den Sie tatsächlich gesendet haben, als an einem anderen Codepunkt, und ich korrigiere irrtümlicherweise den Wert auf den falschen Wert. Entweder brauchen Sie entweder eine zuverlässige Übertragung, die Sie nicht interessieren, oder Sie benötigen eine höhere Fehlererkennung (z. B. eine CRC über die gesamte Nachricht).
The wikipedia article erklärt es ganz gut.
Wenn Sie nicht über einen bestimmten Aspekt des Algorithmus verstehen, dann müssen Sie (oder Detail) Ihre Frage neu zu formulieren, so dass jemand Ihren spezifischen Teil des Problems adressieren kann. Insbesondere
aus Wikipedia wird der Algorithmus wie folgt: