Quelle est une alternative plus rapide à un CRC?

27

Je fais une transmission de données d'un dsPIC à un PC et je fais un CRC 8 bits à chaque bloc de 512 octets pour m'assurer qu'il n'y a pas d'erreurs. Avec mon code CRC activé, j'obtiens environ 33 Ko / s, sans lui j'obtiens 67 Ko / s.

Quels sont les autres algorithmes de détection d'erreurs à vérifier qui seraient plus rapides?

FigBug
la source
5
Comment le CRC est-il mis en œuvre? Au niveau du bit? Passez ensuite à une méthode basée sur une table. Bytewise? Considérez l'espace, la complexité et le compromis temporel impliqués dans l'augmentation de la taille de la table à, disons, 16 bits (qui fonctionneraient sur deux octets à la fois, mais prendraient 64 Ko de stockage de table).
Aidan Cully
Je n'ai que 16 Ko de RAM et 128 Ko de ROM, donc une table de 64 Ko n'est pas une option.
FigBug
1
Vous utilisez donc une table de 256 octets? ou CRC au niveau du bit? Si vous faites au niveau du bit, bytewise (avec une table de 256 octets) serait 8 fois plus rapide.
Aidan Cully
Au niveau du bit actuellement, je vais essayer une table 256
FigBug
1
67kb / s à 33kb / s? Je ne suis pas sûr de ce que votre autre traitement implique, mais cela ressemble à un peu de surcharge, même pour un PIC. Peut-être que d'autres problèmes entravent vos performances?
Rei Miyasaka

Réponses:

41

Bien qu'il puisse y avoir des options plus rapides que CRC, si vous les utilisez, vous risquez de sacrifier un certain degré de capacité de détection d'erreur. Selon vos besoins en matière de détection d'erreurs, une alternative peut être d'utiliser à la place du code CRC optimisé pour votre application.

Pour une comparaison du CRC avec d'autres options, voir l' excellente réponse de Martin Thompson .

Une option pour aider à cela est pycrc qui est un outil (écrit en python 1 ) qui peut générer du code source C pour des dizaines de combinaisons de modèle et d' algorithme crc . Cela vous permet d'optimiser la vitesse et la taille de votre propre application en sélectionnant et en comparant différentes combinaisons. 1: Nécessite Python 2.6 ou version ultérieure.

Il prend en charge le crc-8 modèle , mais soutient également crc-5, crc-16et crc-32entre autres. Quant aux algorithmes , il prend en charge bit-by-bit, bit-by-bit-fastet table-driven.

Par exemple (téléchargement de l'archive):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Vous pouvez même faire des choses géniales comme spécifier en utilisant des recherches à double quartet (avec une table de recherche de 16 octets) plutôt que la recherche à un octet, avec une table de recherche de 256 octets.

Par exemple (clonage du référentiel git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Compte tenu de vos contraintes de mémoire et de vitesse, cette option pourrait bien être le meilleur compromis entre vitesse et taille de code. La seule façon d'en être sûr serait de le comparer.


Le référentiel pycrc git est sur github , tout comme son traqueur de problème , mais il peut également être téléchargé depuis sourceforge .

Mark Booth
la source
Je ne crois pas que la plupart des gens qui écrivent pour le PIC utilisent C, mais cela pourrait fonctionner si c'est le cas.
Billy ONeal
4
@Billy - Vraiment? Je ne pense pas avoir rencontré de développeur commercial pour PIC qui n'utilisait pas C. Je n'ai certainement pas la patience d'assembleur de nos jours et un C bien structuré peut finir par être assez compact.
Mark Booth
J'utilise un dsPIC et j'utilise C.
FigBug
@FigBug - Merci, content que vous aimiez ma réponse. Si vous exécutez des tests de référence, n'hésitez pas à modifier ma réponse avec vos résultats. J'aimerais savoir à quel point chacun des algorithmes fait une différence en termes de débit d'application et d'empreinte mémoire.
Mark Booth
1
Un autre vote pour pyCrc ici. l'utiliser dans divers projets avec des contraintes différentes et c'est tout simplement génial.
Vicky
11

La parité simple sur un bit (fondamentalement XOR les données sur elle-même encore et encore) est à peu près aussi rapide que possible. Vous perdez cependant beaucoup de la vérification des erreurs d'un CRC.

En pseudocode:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Billy ONeal
la source
1
J'ai examiné cela il y a quelque temps. Je crois que sommer au lieu de xor fonctionne en fait un peu mieux. (normalement, additionnez tout, puis transmettez le complément à 2 de la somme comme somme de contrôle. Sur le récepteur, additionnez tout, y compris la somme de contrôle reçue. Le résultat est 0 si tout est bon et non 0 sinon.)
quick_now
1
@quickly: Je ne pense pas qu'il y ait une différence significative entre ces deux - aucune des deux méthodes ne donne une si bonne assurance que les choses n'ont pas été corrompues. Si l'ajout est plus rapide sur l'architecture cible, utilisez-le à la place.
Billy ONeal
7
Je me suis souvenu: La principale différence entre ADD et XOR est qu'il y a moins de détectabilité des erreurs sur plusieurs bits. Dans le cas d'un flux d'octets, les erreurs dans la même position de bit sont annulées à l'aide de XOR. Lors de l'utilisation d'ADD, la propagation de bits dans un octet de somme de contrôle signifie que ce cas est plus détectable. (Cependant, plusieurs erreurs binaires dans différents bits répartis dans le flux d'octets seront probablement moins détectables - selon les circonstances à l'époque). Tout arrangement de somme de contrôle comme celui-ci est TERRIBLE pour les erreurs sur plusieurs bits, c'est donc un argument assez mineur.
quick_now
XOR est beaucoup moins utile que CRC.
3
@ Thorbjørn: Je pense l'avoir reconnu dans ma réponse. :)
Billy ONeal
10

Un très bon article comparant les performances de diverses sommes de contrôle et CRC dans un contexte intégré:

L'efficacité des sommes de contrôle pour les réseaux embarqués

Quelques citations des conclusions (basées sur leurs études des probabilités d'erreur non détectées):

Quand les erreurs de rafale dominent

XOR, l'ajout de complément à deux et les sommes de contrôle CRC offrent de meilleures performances de détection d'erreurs que l'ajout de complément, les sommes de contrôle Fletcher et Adler.

Dans d'autres applications

un «bon» polynôme CRC, dans la mesure du possible, devrait être utilisé à des fins de détection des erreurs

Si le coût de calcul est très contraint

(comme dans votre cas), utilisez (par ordre d'efficacité):

Autres citations:

La somme de contrôle Fletcher a un coût de calcul inférieur à la somme de contrôle Adler et, contrairement à la croyance populaire, est également plus efficace dans la plupart des situations.

et

Il n'y a généralement aucune raison de continuer la pratique courante d'utiliser une somme de contrôle XOR dans les nouvelles conceptions, car elle a le même coût de calcul logiciel qu'une somme de contrôle basée sur l'addition, mais n'est que la moitié environ aussi efficace pour détecter les erreurs.

Martin Thompson
la source
1
En prime, une somme de contrôle Fletcher est très facile à mettre en œuvre.
RubberDuck
6

La somme de contrôle Adler devrait être suffisante pour vérifier les distorsions de transmission. Il est utilisé par la bibliothèque de compression Zlib et a été adopté par Java 3D Mobile Graphics Standard pour fournir un contrôle d'intégrité des données rapide mais efficace.

De la page wikipedia :

Une somme de contrôle Adler-32 est obtenue en calculant deux sommes de contrôle A et B de 16 bits et en concaténant leurs bits en un entier de 32 bits. A est la somme de tous les octets de la chaîne plus un, et B est la somme des valeurs individuelles de A de chaque étape.

Au début d'une exécution Adler-32, A est initialisé à 1, B à 0. Les sommes sont faites modulo 65521 (le plus grand nombre premier inférieur à 2 ^ 16 ou 65536). Les octets sont stockés dans l'ordre du réseau (big endian), B occupant les deux octets les plus significatifs.

La fonction peut être exprimée comme

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

où D est la chaîne d'octets pour laquelle la somme de contrôle doit être calculée, et n est la longueur de D.

Gnawme
la source
Notez que Adler32 est presque inutile pour de courtes séries de données. Jusqu'à environ 180 octets, il produit de nombreuses collisions.
greyfade
+1 - un juste milieu raisonnable entre un CRC et une parité de bits simple.
Billy ONeal
@greyfade - FigBug a mentionné l'utilisation de blocs de 512 octets, donc cela ne devrait pas être un problème pour l'OP. C'est bien de l'avoir noté pour les personnes ayant d'autres exigences.
Mark Booth
5

Je ne suis au courant de rien qui soit aussi efficace pour la détection d'erreurs qu'un CRC et plus rapide - s'il y en avait, les gens l'utiliseraient à la place.

Vous pouvez essayer une simple somme de contrôle, mais cela est beaucoup moins susceptible de détecter des erreurs.

Bob Murphy
la source
2
Je suis prêt à renoncer à une efficacité pour la vitesse.
FigBug
3

Eh bien, la logique de somme de contrôle elle-même est bonne et les gens peuvent aider avec des algorithmes plus rapides.

Si vous souhaitez améliorer la vitesse de votre composant, vous devrez peut-être envisager de modifier votre technique globale pour séparer le composant de transfert du composant de validation.

Si vous disposez de ces deux éléments indépendants (sur des threads différents), vous pouvez obtenir votre vitesse de transfert complète et renvoyer uniquement les paquets ayant échoué.

L'algorithme ressemblerait à quelque chose comme:

  • Le serveur se décompose en tailles de paquets connues (par exemple, des morceaux de 1 Ko). Les place dans une file d'attente «à envoyer».
  • Chaque paquet est envoyé avec un ID 16 ou 32 bits ET sa somme de contrôle.
  • Le client reçoit chaque paquet et le place dans une file d'attente à traiter.
  • Sur un thread séparé, le client prend un paquet à la fois, fait la validation.
    • En cas de succès, il l'ajoute à la collection finale de paquets (dans l'ordre ID) étant
    • En cas d'échec, il signale l'ID échoué au serveur, qui met ce paquet en file d'attente pour être renvoyé.
  • Une fois que vous avez reçu et validé les paquets et que vous avez les ID dans la séquence correcte (à partir de 1), vous pouvez commencer à les écrire sur le disque (ou faire ce qui est nécessaire).

Cela vous permettra de transmettre à la vitesse la plus élevée possible et si vous jouez avec la taille de votre paquet, vous pouvez déterminer le taux d'échec optimium VS le taux de validation / renvoi.

Robin Vessey
la source
2

Les sommes de contrôle sont traditionnelles

(réduire # '+ flux)

XOR comme indiqué ci-dessus fonctionnerait également

(réduire le flux XOR # ')

Un schéma un peu plus élaboré (plus lent) est le contrôle de parité standard pour les connexions série.

À ce niveau, vous échangez l'exactitude contre la vitesse. Celles-ci échoueront parfois.

Au niveau suivant le plus sophistiqué, vous pouvez utiliser des trucs de type crc / hash.

Une autre conception consisterait à augmenter la taille du bloc utilisé pour le flux.

Vous devriez avoir une estimation du taux d'erreur réel pour régler la sélection de votre algorithme et les paramètres de taille de bloc.

Paul Nathan
la source