Was ist die Hamming-Distanz, und wie kann ich es für ein CRC-Schema bestimmen?
-
25-09-2019 - |
Frage
Während für eine Klasse in Computer-Netzwerken zu studieren, sprach der prof über die Hamming-Distanz zwischen zwei gültigen Codeworten in einem Beispielcode. Ich habe über Hamming-Distanz zu lesen, und es macht Sinn, aus der Perspektive die Differenz Abstand zwischen zwei Saiten zu erzählen. Zum Beispiel:
Code Word 1 = 10110
Der Sender sendet Codewort 1, und es ist ein Fehler eingeführt, und der Empfänger erhält 10100. Sie sehen also, dass das vierte Bit beschädigt wurde. Dies würde in der eine Hamming-Distanz von 1, weil:
Valid Code Word: 10110
Error Code Word: 10100
-----
XOR 00010
Die XOR der 2 Strings Ergebnisse in einem 1, so dass die Hamming-Distanz ist 1. Ich kann es verstehen, bis zu diesem Punkt. Aber dann die prof fragt:
- Was ist die Hamming-Distanz von dem Standard-CRC-16-Bit-Protokoll?
- Was ist die Hamming-Distanz von dem Standard-CRC-32-Bit-Protokoll?
Ich bin ein wenig verwirrt, und frage mich, ob jemand helfen könnte. Danke.
Lösung
Sie es vermutlich jetzt herausgefunden, aber was er gefragt waren höchstwahrscheinlich die minimale Anzahl der Bitfehler, dass ein CRC-Code nicht erkennen. Die Antwort hängt von der Breite, das Polynom und der Länge der Nachricht. Zum Beispiel bekannt, dass die besten CRC-32-Polynom (0x1EDC6F41) eine Hamming-Distanz von 6 oder besser für Nachrichten von bis zu 5.275 Bits (Castaglioni, Bräuer, Herrmann: Optimierung der Cyclic Redundancy-Check Codes mit 24 und 32 Parity Bits, IEEE Transactions on Communications, vol 41 no 6 Juni 1993), was bedeutet, ist gewährleistet, zu erfassen, bis zu 5 gekippt Bits in einer einzelnen Nachricht von 5.275 Bits oder weniger.
BTW, das Codewort enthält die Prüfsumme, so dass Ihr Beispiel nicht korrekt ist.