Was ist der hamming-Abstand, und wie Ermittle ich ihn für ein CRC-Schema?

Während des Studiums für eine Klasse in computer-Netzwerken, der Prof. Sprach über die hamming-Distanz zwischen 2 gültige code-Wörter in einem Beispielcode. Ich habe gelesen, über die hamming-Distanz, und es macht Sinn aus der Perspektive sagen, der Unterschied Abstand zwischen 2 Saiten. Zum Beispiel:

Code Word 1 = 10110

Sendet der Absender code-Wort 1, und es wird ein Fehler eingeführt, und der Empfänger erhält 10100. Sie sehen also, dass das 4. bit wurde beschädigt. Dies hätte zur Folge, dass eine hamming-Distanz von 1, da:

Valid Code Word: 10110
Error Code Word: 10100
                 -----
XOR              00010

Dem XOR des 2 strings Ergebnisse in eine 1, so ist die hamming-Distanz ist 1. Ich verstehe es bis zu diesem Punkt. Dann aber der prof fragt:

  • Was ist die hamming-Distanz der standard CRC-16-bit-Protokoll?
  • Was ist die hamming-Distanz der standard CRC-32-bit-Protokoll?

Ich bin ein wenig verwirrt, und Frage mich, wenn jemand helfen könnte. Danke.

InformationsquelleAutor naivedeveloper | 2010-09-27
  1. 4

    Haben Sie wahrscheinlich es mittlerweile herausgefunden, aber was er fragte, war wahrscheinlich die minimale Anzahl von bit-Fehlern, die ein CRC-code nicht erkennen. Die Antwort hängt von der Breite, die Polynom-und die Länge der Nachricht. Zum Beispiel, die beste bekannte CRC-32-Polynom (0x1EDC6F41) hat eine Hamming-Distanz von 6 oder besser für Nachrichten von bis zu 5,275 bits (Castaglioni, Bräuer, Hermann: Optimierung von Cyclic-Redundancy-Check-Codes mit 24 und 32 Parity-Bit, IEEE Transactions on Communications, vol 41 no 6, Juni 1993), das heißt es ist garantiert, um zu erkennen, bis zu 5 Gekippte bits in einer einzelnen Nachricht von 5,275 bits oder weniger.

    BTW, das code-Wort enthält die Prüfsumme, also dein Beispiel ist falsch.

    • Der Teil über die bekanntesten Polynom ist falsch. Das Polynom 0x741B8CD7 hat Hamming-Distanz von 6 bis zu 16360 bits und Hamming-Distanz von 4 bis zu 114663 bits. [Philip Koopman, 32-Bit Cyclic Redundancy Codes for Internet Applications]
    • Wohl die beste wäre einfach zu finden: Koopman ' s website. Es scheint sich um eine der meisten up-to-date-Orte für CRC-performance.
    InformationsquelleAutor DES
Schreibe einen Kommentar