Qual è la distanza di Hamming, e come faccio a determinare per uno schema di CRC?

Question

Mentre studiava per una classe in reti di computer, il prof ha parlato della distanza di Hamming tra le 2 parole codice valido in un codice di esempio. Ho letto di distanza di Hamming, e ha senso dal punto di vista di raccontare la distanza differenza tra 2 stringhe. Ad esempio:

Code Word 1 = 10110 

Il mittente invia parola di codice 1, e non v'è un errore introdotto, e il ricevitore riceve 10100. Così si vede che il 4 ° bit è stato danneggiato. Questo si tradurrebbe in lontananza una di Hamming di 1 perché:

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

Il XOR delle stringhe risultati 2 in un 1, quindi la distanza di Hamming è 1. Capisco che fino a quel momento. Ma poi il prof chiede:

• Qual è la distanza di Hamming del protocollo standard CRC-16 bit?
• Qual è la distanza di Hamming del protocollo standard CRC-32 bit?

Sono un po 'confuso, e chiedevo se qualcuno potesse aiutare. Grazie.

Answer 1

Probabilmente capito da ora, ma ciò che aveva chiesto era molto probabilmente il numero minimo di errori di bit che un codice CRC non rilevare. La risposta dipende dalla larghezza, il polinomio e la lunghezza del messaggio. Per esempio, il più noto CRC-32 polinomiale (0x1EDC6F41) ha una distanza di Hamming di 6 o superiore per i messaggi fino a 5.275 bit (Castaglioni, Bräuer, Herrmann: Ottimizzazione di Cyclic Redundancy-controllare i codici con 24 e 32 bit di parità, IEEE transazioni on Communications, vol 41 no 6, giugno 1993) che significa che è garantito per rilevare fino a 5 bit capovolte in un singolo messaggio di 5.275 bit o meno.

A proposito, la parola di codice include la somma di controllo, quindi il tuo esempio non è corretto.