Qual è la distanza di hamming e come posso determinarla per uno schema CRC?

Question

Mentre studiavo per un corso in reti informatiche, il prof ha parlato della distanza di hamming tra 2 parole di codice valide in un codice di esempio. Ho letto di hamming distance, e ha senso dal punto di vista della differenza di distanza tra 2 stringhe. Per 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 

La 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 mi chiedevo se qualcuno potesse aiutare. Grazie.

Answer 1

Probabilmente lo avete capito, ma quello che ha chiesto era probabilmente il numero minimo di errori di bit che un codice CRC non avrebbe rilevato. La risposta dipende dalla larghezza, dal polinomio e dalla lunghezza del messaggio. Ad esempio, il polinomio CRC-32 più noto (0x1EDC6F41) ha una distanza di Hamming di 6 o superiore per messaggi fino a 5.275 bit (Castaglioni, Bräuer, Herrmann: Ottimizzazione dei codici di controllo di ridondanza ciclica con 24 e 32 bit di parità, IEEE Transactions on Communications, vol. 41 n. 6, giugno 1993), il che significa che è garantito il rilevamento di un massimo di 5 bit capovolti in un singolo messaggio di 5.275 bit o meno.

BTW, la parola codice include il checksum, quindi il tuo esempio non è corretto.