Longueur des données par rapport à la longueur du CRC

L'efficacité d'un CRC dépend de plusieurs facteurs. Vous devez non seulement sélectionner la taille du CRC, mais aussi le polynôme générateur à utiliser. Il existe des compromis complexes et non intuitifs selon:

• attendue taux d'erreur de bits du canal.
• si les erreurs ont tendance à se produire en rafales ou ont tendance à être étalées (l'éclatement est commun)
• La longueur des données à protéger - longueur maximale longueur minimale et distribution.

Le livre de Redondance Cyclique Code Polynominal de Sélection Pour les Réseaux Embarqués, par Philippe Koopman et Tridib Chakravarty, édité dans la procédure de 2004 de la Conférence Internationale sur la Fiabilité des Systèmes et des Réseaux donne une très bonne vue d'ensemble et fait plusieurs recommandations. Il fournit également une bibliographie pour plus de compréhension.

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

je pense que la taille du CRC a plus à voir avec le caractère unique d'un CRC dont vous avez besoin au lieu de la taille des données d'entrée. Cela est lié à l'usage particulier et le nombre d'articles sur lesquels vous calculez un CRC.

le CRC devrait être choisi spécifiquement pour la longueur des messages, il ne s'agit pas seulement d'une question de la taille du CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

le choix de la longueur du CRC par rapport à la taille du fichier est principalement pertinent dans les cas où l'on est plus susceptible d'avoir une entrée qui diffère de l'entrée "correcte" de trois bits ou moins que d'avoir une entrée qui est massivement différente. Étant donné deux entrées qui sont massivement différentes, la possibilité d'une fausse correspondance sera d'environ 1/256 avec la plupart des formes de valeur de contrôle 8 bits (y compris CRC), 1/65536 avec la plupart des formes de valeur de contrôle 16 bits (y compris CRC), etc. L'avantage du CRC vient de son traitement des intrants qui sont très similaires.

avec un CRC 8-bit dont le polynôme génère deux périodes de longueur 128, la fraction d'erreurs simples, doubles ou triples dans un paquet plus court que celui qui passe inaperçu ne sera pas 1/256--elle sera nulle. De même avec un CRC de 16 bits de période 32768, en utilisant des paquets de 32768 bits ou moins.

si les paquets sont plus longs que la période CRC, cependant, alors une erreur à deux bits ne sera pas détectée si la distance entre les bits erronés sont un multiple de la période CRC. Bien que cela ne puisse pas sembler être un scénario très probable, un CRC8 sera un peu plus mauvais pour détecter les erreurs à double bits dans les paquets longs que pour détecter les erreurs "paquet totalement brouillé". Si les erreurs à deux bits sont le deuxième mode de défaillance le plus courant (après les erreurs à un seul bit), ce serait mauvais. Si quelque chose qui corrompt certaines données est susceptible de corrompre une grande partie de celui-ci, cependant, le comportement inférieur de CRCs avec des erreurs de double bits peut être un non-problème.

Voici une belle évaluation "réelle" du CRC-N http://www.backplane.com/matt/crc64.html

j'utilise le CRC-32 et la comparaison de la taille des fichiers et je N'ai jamais, dans les milliards de fichiers vérifiés, rencontré une collision correspondante du CRC-32 et de la taille des fichiers. Mais je sais que certains existent, quand ils ne sont pas délibérément forcés d'exister. (Piraté astuces/exploits)

lorsque vous faites une comparaison, vous devriez également vérifier "taille des données". Vous aurez rarement une collision de données de taille, avec un CRC assorti, dans les bonnes tailles.

les données manipulées intentionnellement, pour simuler une correspondance, est généralement fait en ajoutant des données supplémentaires jusqu'à ce que le CRC correspond à une cible. Toutefois, il en résulte une taille de données qui ne correspond plus. Tenter de forcer, ou de faire un cycle à travers des données aléatoires, ou séquentielles, de la même taille exacte, laisserait un taux de collision très étroit.

vous pouvez aussi avoir des collisions à l'intérieur de la taille des données, juste par les limites génériques des formules utilisées, et contraintes d'utilisation des bits / octets et des systèmes de base-ten, qui dépend des valeurs à virgule flottante, qui sont tronquées et tronquées.

le point que vous voudriez penser à aller plus grand, c'est quand vous commencez à voir beaucoup de collisions qui ne peuvent pas être "confirmées" comme "originales". (Lorsqu'ils ont tous les deux la même taille de données, et (lorsqu'ils sont testés à l'envers, ils ont un CRC correspondant. Arrière/octet ou à l'inverse, les forets, ou peu-de compensations)

dans tous les cas, il ne devrait jamais être utilisé comme la seule forme de comparaison, seulement pour un rapide formulaire de comparaison, pour l'indexation.

vous pouvez utiliser un CRC-8 pour indexer l'ensemble de l'internet, et diviser tout en N-catagories. Vous voulez ces collisions. Maintenant, avec ces pré-triés, vous n'avez qu'à vérifier un des n-répertoires, à la recherche de "file-size", ou "reverse-CRC", ou toute autre comparaison que vous pouvez faire à ce plus petit ensemble de données, rapide...

faire un CRC-32 avant et arrière sur le même bloc de données est plus fiable que utiliser le CRC-64 dans une seule direction. (Ou un MD5, d'ailleurs.)