Efficacité de détection des erreurs (CRC, somme de contrôle, etc.)

Question

J'ai une situation hypothétique d'envoi d'unités de données, chacune des mille octets. Le taux de défaillance est rare, mais lorsqu'une erreur se produit, il est moins susceptible d'être une erreur de bit unique et plus susceptible d'être une erreur en quelques bits d'affilée.

Au début, j'ai pensé à utiliser une somme de contrôle, mais apparemment, cela peut manquer des erreurs de bits plus grandes qu'un seul bit. Un contrôle de parité ne fonctionnera pas non plus, donc le CRC pourrait être la meilleure option.

L'utilisation d'une vérification de redondance cyclique sur mille octets est-elle efficace? Ou y a-t-il d'autres méthodes qui fonctionneraient mieux?

Answer 1

Les contrôles de redondance cyclique (CRC) sont populaires Plus précisément En raison de leur efficacité pour détecter les erreurs de plusieurs bits avec une précision garantie.

Il existe différentes conceptions pour générer des polynômes CRC où le compromis est la précision par rapport à la complexité informatique. Dans votre cas, vous pouvez choisir celui "le plus rapide" qui répond à vos exigences pour l'exactitude.

Vous voudrez peut-être commencer par cet article Wikipedia sur le Contrôle de redondance cyclique.

Answer 2

CRC est couvert d'une autre question ici
Quand CRC est-il plus approprié à utiliser que MD5 / Sha1?
Il convient pour détecter les erreurs aléatoires et facile à implémenter.

Answer 3

Il est normal d'utiliser un CRC. Je ne suis pas certain de ce que vous entendez par «efficacité», mais je pense que parfois le CRC est implémenté en matériel (par exemple sur la carte Ethernet). Sinon, vous pouvez trouver des implémentations «optimisées» (à l'aide d'une table de recherche).

Answer 4

Quelle est la taille de vos secteurs de disque? Probablement au moins 512 octets. Et CRC est un schéma séculaire pour le disque de niveau matériel ECC.

Les algorithmes polynomiaux CRC d'origine sont assez efficaces pour un petit nombre d'erreurs de bits. La précision exacte est mathématiquement calculable. Le CRC est également très efficace à faire dans le matériel où un nombre relativement faible de portes et de registres de décalage peuvent gérer le travail à la volée.