Kann jemand mit eigenen Worten erklären, was Double Bit Error Detection ist und wie man es ableitet? Ein Beispiel für beschädigte Daten und wie das Doppelbit erkannt wird, wäre wünschenswert.
Ich kann eine Einzelbitfehlerkorrektur mit Paritätsbits durchführen und das umgedrehte Bit korrigieren. Wenn ich jetzt die Double Bit Error Detection erreiche, verstehe ich, dass es ein zusätzliches DED-Bit gibt, das irgendwie mit der geraden oder ungeraden Parität der Bitsequenz zusammenhängt. Allerdings bin ich verloren.
Was ich gelesen habe: http://en.wikipedia.org/wiki/Error_detection_and_correction
Video zum Hamming-Code: http://www.youtube.com/watch?v=JAMLuxdHH8o
Ein Hamming-Code ist eine besondere Art von Fehlerkorrekturcode (ECC), der die Korrektur von Einzelbitfehlern in Codewörtern ermöglicht. Solche Codes werden in Datenübertragungs- oder Datenspeichersystemen verwendet, in denen es nicht möglich ist, Wiederholungsmechanismen zu verwenden, um die Daten wiederherzustellen, wenn Fehler erkannt werden. Diese Art der Fehlerbehebung wird auch als Vorwärtsfehlerkorrektur (FEC) bezeichnet.
Konstruieren eines Hamming-Codes, um beispielsweise ein 4-Bit-Datenwort zu schützen
Hamming-Codes sind relativ einfach zu konstruieren, da sie auf Paritätslogik basieren. Jedes Prüfbit ist ein Paritätsbit für eine bestimmte Teilmenge der Datenbits, und sie sind so angeordnet, dass das Muster der Paritätsfehler direkt die Position des Bitfehlers anzeigt.
Es sind drei Prüfbits erforderlich, um vier Datenbits zu schützen (der Grund dafür wird in Kürze ersichtlich), was insgesamt 7 Bits im codierten Wort ergibt. Wenn Sie die Bitpositionen eines 8-Bit-Wortes binär nummerieren, sehen Sie, dass es eine Position gibt, die keine "1" in ihrer Spalte hat, drei Positionen, die jeweils eine einzelne "1" haben, und vier Positionen, die zwei haben oder mehr "1".
Wenn die vier Datenbits A, B, C und D heißen und unsere drei Prüfbits X, Y und Z sind, platzieren wir sie so in den Spalten, dass die Prüfbits in den Spalten mit einer „1“ und den Daten sind Bits befinden sich in den Spalten mit mehr als einer "1". Das Bit an Position 0 wird nicht verwendet.
Bit position: 7 6 5 4 3 2 1 0
in binary: 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
Bit: A B C X D Y Z -
Das Prüfbit X wird gesetzt oder gelöscht, so dass alle Bits mit einer „1“ in der obersten Reihe – A, BC und X – gerade Parität haben. In ähnlicher Weise ist das Prüfbit Y das Paritätsbit für alle Bits mit einer "1" in der zweiten Reihe (A, B und D), und das Prüfbit Z ist das Paritätsbit für alle Bits mit einer "1". " in der dritten Reihe (A, C und D).
Jetzt werden alle sieben Bits – das Codewort – übertragen (oder gespeichert), normalerweise neu geordnet, sodass die Datenbits in ihrer ursprünglichen Reihenfolge erscheinen: ABCDXY Z. Wenn sie später empfangen (oder abgerufen) werden, werden die Datenbits genauso durchgereicht Codierungsprozess wie zuvor, wodurch drei neue Prüfbits X', Y' und Z' erzeugt werden. Wenn die neuen Prüfbits mit den empfangenen Prüfbits XOR-verknüpft werden, tritt eine interessante Sache auf. Wenn die empfangenen Bits keinen Fehler enthalten, ist das Ergebnis des XOR ausschließlich Nullen. Wenn es jedoch einen einzelnen Bitfehler in einem der sieben empfangenen Bits gibt, ist das Ergebnis des XOR eine Drei-Bit-Zahl ungleich Null, die als "Syndrom" bezeichnet wird und direkt die Position des Bitfehlers anzeigt, wie in der obigen Tabelle definiert. Wenn das Bit in dieser Position umgedreht wird, wird das ursprüngliche 7-Bit-Codewort perfekt rekonstruiert.
Ein paar Beispiele sollen dies verdeutlichen. Nehmen wir an, dass die Datenbits alle Null sind, was auch bedeutet, dass alle Prüfbits ebenfalls Null sind. Wenn Bit "B" im empfangenen Wort gesetzt ist, dann sind die neu berechneten Prüfbits X'Y'Z' (und das Syndrom) 110, was die Bitposition für B ist. Wenn Bit "Y" im empfangenen Wort gesetzt ist Wort, dann sind die neu berechneten Prüfbits "000" und das Syndrom ist "010", was die Bitposition für Y ist.
Hamming-Codes werden mit größeren Codewörtern effizienter. Grundsätzlich benötigen Sie genügend Prüfbits, um alle Datenbits plus die Prüfbits plus eins aufzuzählen. Daher können vier Prüfbits bis zu 11 Datenbits schützen, fünf Prüfbits können bis zu 26 Datenbits schützen und so weiter. Schließlich kommen Sie an den Punkt, an dem Sie bei 8 Datenbytes (64 Bits) mit einem Paritätsbit in jedem Byte genügend Paritätsbits haben, um stattdessen ECC mit den 64 Datenbits durchzuführen.
Unterschiedliche (aber gleichwertige) Hamming-Codes
Bei einer bestimmten Anzahl N von Prüfbits gibt es 2 N äquivalente Hamming-Codes, die konstruiert werden können, indem jedes Prüfbit willkürlich so ausgewählt wird, dass es entweder eine "gerade" oder eine "ungerade" Parität innerhalb seiner Gruppe von Datenbits hat. Solange der Codierer und der Decodierer die gleichen Definitionen für die Prüfbits verwenden, bleiben alle Eigenschaften des Hamming-Codes erhalten.
Manchmal ist es nützlich, die Prüfbits so zu definieren, dass ein codiertes Wort aus lauter Nullen oder reinen Einsen immer als Fehler erkannt wird.
Was passiert, wenn mehrere Bits in einem Hamming-Codewort umgedreht werden?
Mehrbitfehler in einem Hamming-Code verursachen Probleme. Zwei-Bit-Fehler werden immer als Fehler erkannt, aber das falsche Bit wird von der Korrekturlogik umgedreht, was zu Kauderwelsch führt. Wenn mehr als zwei Bits fehlerhaft sind, kann das empfangene Codewort als gültig erscheinen (aber anders als das Original), was bedeutet, dass der Fehler erkannt werden kann oder nicht.
In jedem Fall kann die Fehlerkorrekturlogik nicht zwischen Einzelbitfehlern und Mehrfachbitfehlern unterscheiden, und daher kann man sich nicht auf die korrigierte Ausgabe verlassen.
Erweitern eines Hamming-Codes zum Erkennen von Doppelbitfehlern
Jeder einzelne Fehler korrigierende Hamming-Code kann erweitert werden, um Doppelbitfehler zuverlässig zu erkennen, indem dem gesamten codierten Wort ein weiteres Paritätsbit hinzugefügt wird. Diese Art von Code wird SECDED-Code (Einzelfehlerkorrektur, Doppelfehlererkennung) genannt. Es kann immer einen Doppelbitfehler von einem Einzelbitfehler unterscheiden und erkennt mehr Arten von Mehrbitfehlern als ein reiner Hamming-Code.
Es funktioniert so: Alle gültigen Codewörter haben (mindestens) eine Hamming-Distanz 3 voneinander entfernt. Die "Hamming-Distanz" zwischen zwei Wörtern ist definiert als die Anzahl von Bits an entsprechenden Positionen, die unterschiedlich sind. Jeder Einzelbitfehler ist um eins von einem gültigen Wort entfernt, und der Korrekturalgorithmus wandelt das empfangene Wort in das nächste gültige um.
Wenn ein Doppelfehler auftritt, wird die Parität des Wortes nicht beeinflusst, aber der Korrekturalgorithmus korrigiert immer noch das empfangene Wort, das Abstand zwei von dem ursprünglich gültigen Wort, aber Abstand eins von einem anderen gültigen (aber falschen) Wort ist. Dies geschieht durch Umdrehen eines Bits, das eines der fehlerhaften Bits sein kann oder nicht. Jetzt hat das Wort entweder ein oder drei Bits umgedreht, und der ursprüngliche Doppelfehler wird jetzt vom Paritätsprüfer erkannt.
Beachten Sie, dass dies auch dann funktioniert, wenn das Paritätsbit selbst an einem Einzelbit- oder Doppelbitfehler beteiligt ist. Es ist nicht schwer, alle Kombinationen auszuarbeiten.
Andi aka
Mike John
Russell McMahon
Russell McMahon
Russell McMahon