Quelle est la distance de Hamming et comment la déterminer pour un système CRC ?

StackOverflow https://stackoverflow.com/questions/3800788

  •  25-09-2019
  •  | 
  •  

Question

Alors qu'il étudiait pour un cours sur les réseaux informatiques, le professeur a parlé de la distance de Hamming entre 2 mots de code valides dans un exemple de code.J'ai lu des articles sur la distance de jambon, et cela a du sens du point de vue de la différence de distance entre 2 cordes.Par exemple:

Code Word 1 = 10110

L'expéditeur envoie le mot de code 1, une erreur est introduite et le destinataire reçoit 10100.Vous voyez donc que le 4ème bit a été corrompu.Cela entraînerait une distance de Hamming de 1 car :

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

Le XOR des 2 chaînes donne un 1, donc la distance de Hamming est de 1.Je le comprends jusque-là.Mais alors le prof demande :

  • Quelle est la distance de Hamming du protocole standard CRC-16 bits ?
  • Quelle est la distance de Hamming du protocole standard CRC-32 bits ?

Je suis un peu confus et je me demandais si quelqu'un pouvait m'aider.Merci.

Était-ce utile?

La solution

Vous l'avez probablement déjà compris, mais ce qu'il a demandé était très probablement le nombre minimum d'erreurs binaires qu'un code CRC ne détecterait pas.La réponse dépend de la largeur, du polynôme et de la longueur du message.Par exemple, le polynôme CRC-32 le plus connu (0x1EDC6F41) a une distance de Hamming de 6 ou mieux pour des messages allant jusqu'à 5 275 bits (Castaglioni, Bräuer, Herrmann :Optimisation des codes de contrôle de redondance cyclique avec 24 et 32 ​​bits de parité, IEEE Transactions on Communications, vol 41 no 6, juin 1993), ce qui signifie qu'il est garanti de détecter jusqu'à 5 bits inversés dans un seul message de 5 275 bits ou moins.

BTW, le mot de code inclut la somme de contrôle, donc votre exemple est incorrect.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top