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?

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 ¹ ) 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 .

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);

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é):

• Somme de contrôle de Fletcher
• son complément de complément
• ajout de complément à deux

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.

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.

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.

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.

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.