CRC et polynômes

Bonjour,

Je ne suis pas une bête en math, mais je me pose tout de même quelques questions au sujet des relations entre les algorithmes de CRC et Cie. et les mathématiques.

Tout d'abord, le CRC, est abusivement, et même trés abusivement appelé parfois « somme de contrôle », alors qu'il n'a rien à voir avec une somme (Adler-32 par contre en est vraiment une). Cela devrait suffire à un induire un doute sur la rigueure mathématique de ces algorithmes.

Et justement, je me pose encore une question, en lisant l'exellent tutoriel de DVSoft, sur developpez.com ( http://dvsoft.developpez.com/Articles/CRC ). L'algotithme fait que les facteur du polynôme ne peuvent jamais êtres négatifs... ou plutôt disont que les facteurs étant sur un seul bit, les facteur +1 et -1 s'en trouvent confonduent, et les seuls facteurs possibles sur 1 bit sont +1 et 0.

Apparement, cela n'a rien d'une division polynômiale au sens stricte du terme. Alors je me dit que l'aspect « division polynômiale » n'est qu'une manière commode et pratique de décrire l'algorithme, mais qu'au finale, les théorie sur les CRC n'ont peut-être alors rien à voir avec les polynômes au sens strict.

A moins qu'il n'existe en math des théorie sur les polynôme à facteur congruants ? ... encore une fois, je ne suis pas une bête en mat... alors peut-être que je raconte n'importe quoi... mais cette historie me perturbe.

Enfin, bref, j'ai bien compris l'algo pour les CRC, 16 ou 32, ou je ne sais encore... mais malgré que je les ai compris, il n'y a pour moi qu'un vague rapport entre les CRC et les divisions polynômiales.

Je suis largué, j'ai manqué un épisode ? ou c'est bien ça ? il n'y a pas de rapport véritablement stricte ?

Merci d'avance pour tout vos commentaires... et si démonstration ou exposé mathématique il y a dans ces commentaires, alors pitié... ne soyez pas trop innacessibles. Merci encore par avance.

Effectivement l'informatique et les mathématiques divergent.

Là ou l'un emploi la notion de division, c'est en fin de compte la division en base 2 de la représentation binaire déduite des coéfficients (en base 2) d'un polynome. Là ou l'autre emploi la notion de division, c'est dans l'espace vectoriel des polynomes sur N à coéfficients dans [[0, 1]].

Les CRC on été fortement utilisés en télécommunication, ou les opérations de bits à bits (décalage, somme, XOR) sont trés faciles à réaliser. Et je doit pas me tromper de beaucoup pour dire que les coéfficients ont été trouvé de telle manière à respecter une contrainte générique du style "pour 1 seul bit d'écart entre 2 polynomes, le CRC doit fortement varier".

Maintenant pour une étude plus approfondie, voilà ce que j'ai trouvé sur :google: :
A good introduction to CRC's can be found in the classic Error Correcting Codes, by Peterson and Weldon (Cambridge, Mass., MIT Press, 1972), but you can expect to do some serious math to understand it.

Même avec la plus grande chance, ce document doit surement rester introuvable :aie:

En tout cas si tu trouves du matériel théorique mathématiques derrière les CRC ça m'intéresse grandement.

EDIT : peut-être que là (en Anglais) ?

http://www.num.math.uni-goettingen.d...e/abthesis.htm

Bonjour mon chèr,

Citation:

---

Effectivement l'informatique et les mathématiques divergent

---

Oui, mais de mon avis de longue date, et cela commence même un peu à être à la monde depuis récement, l'algorithmique reflête mieux certaines réalité que les mathématiques. C'est vrai que les deux sont différentes (les maths pour ce qui est statiques, et l'algo pour ce qui est dynamique... tel est le crédo dans l'air du temps)

Citation:

---

Et je doit pas me tromper de beaucoup pour dire que les coéfficients ont été trouvé de telle manière à respecter une contrainte générique du style "pour 1 seul bit d'écart entre 2 polynomes, le CRC doit fortement varier".

---

C'est tout à fait ça. Il y a d'autres fonctions de contrôl, qui font des sommes, et qui sont reconnues comme peu fiable, parce qu'un simple réordonnancement des octets de la chaîne d'entré, produit toujours la même clé de contrôle. C'est le cas des sommes modulo une puissance de deux. Les CRC n'ont pas ce défaut. Mais il ont été plusieurs fois pris en défaut : des gens ont réussi par exemple à modifier des codes en entrée, en préservant le CRC du message initial... mais les codes modifiés étaient destinés à des attaques... faut quand même être fort pour ça.. ouille... pas pour moi ça.

Citation:

---

EDIT : peut-être que là (en Anglais) ?

http://www.num.math.uni-goettingen.d...e/abthesis.htm

---

Oui, les messages d'erreur 404 sont effectivement en anglais généralement, et celui-ci ne fait pas exception :D

Bon, je n'ai rien trouvé concernant les théories, mais j'ai appris plusieurs choses, qui au passage, démontre bien tout le bricolage qu'il y a avec ces algo. Ils sont paramétrables, et par exemple on peut décider de changer l'ordre des bits des octets en entrée, appliqué une inversion en sortie, etc, etc.

Bien sûre, tout algorithme déterministe est mathématiquement formalisable.... alors on ne peut pas dire que cela ne correspond à rien de mathématique, mais reconnaissont quand est loin, et trés loin le plus souvent, de la notion habituelle de polynômes (qui ne servent que de base à ces algos).

Quelques documentations trop précieuses pour les manquer (je n'ai pas encore lu en profondeur)

Un survol de l'art en la matière des checksum :
http://www.unixware.it/freeveracity/...checksums.html

Des explications détaillées sur les algo de CRC (ça s'appel « a painless guide », mais je vous promet des migraines quand-même) :
http://www.ross.net/crc/download/crc_v3.txt

Et pour finir, un catalogue des paramètres qui caractérise chacun des animaux de la jungle des algos CRC (pour connaître la signification du format employé pour présenter les paramères, veuillez vous reportez au document précédent) :
http://homepages.tesco.net/~rainstorm/crc-catalogue.htm

En attendant, mon algo à moi ne renvoie toujours pas les bonnes clés... la division polynomiale me semble pourtant ok. Et à ce sujet, une chose interessante, est un pseudo paramètre des différents CRC : le paramètre Check, qui n'est à proprement parlé un paramètre, mais qui est le résultat renvoyé par l'algo pour la chaine ASCII "123456789". ... Très util pour tester la correctitude d'une implémentation.

Si quelqu'un a un algo de CRC-32, bit-à-bit (sans table), et qui fonctionne sans erreur, je veux bien voir (c'est pour le besoin de tout comprendre)... c'est ce que j'essai de faire, mais ça ne marche pas... pas encore.

(suite du précédent post)

Si ça t'interesse toujours mchk0123, j'ai lu le deuxième document que j'indiquais dans le précédent post, et il contient plusieurs éléments de théorie assez interessants.... ;)

Sinon, je sèche sur une implémentation, qui fonctionne parfaitement quand le registre est initialisé à zéro (cas de plusieurs variante de CRC), mais qui ne donne pas les bons résultats quand le registre est initialisé à 0xFFFFFFFF.

C'est étrange, parce que si mon implémentation n'était pas bonne, alors elle ne fonctionnerait dans aucun des deux cas, et pourtant elle fonctionne bien dans le premier cas, mais pas dans le second.

Si quelqu'un(e) a déjà tenté une implémentation d'un algo CRC sans lookup-table, alors j'aimerais bien avoir la série de valeurs du registre remainder, pour comparer avec ma série de valeurs, et comprendre où ça coince.

Help me please, give me those values ... I'm becoming crazy :(

Dommage pour mon lien qui ne marche plus (il marchait hier), il contenait des informations théoriques.

Pour ton implémentation, de mémoire si tu initialise à 0xffffffff je crois que tu dois prendre la négation à 2 ou l'opposé du résultat, sinon ce n'est pas bon (je sais pas exactement dans le détail car je cite de mémoire).

Re-bonjour Monsieur/Madame Math :)

Citation:

---

Dommage pour mon lien qui ne marche plus (il marchait hier), il contenait des informations théoriques.

---

Il marchait vraiment hier ? :D C'est trop drôle ça :D Qu'est-ce qui est arrivé tout à coup à cette page ?

Citation:

---

Pour ton implémentation, de mémoire si tu initialise à 0xffffffff je crois que tu dois prendre la négation à 2 ou l'opposé du résultat, sinon ce n'est pas bon (je sais pas exactement dans le détail car je cite de mémoire).

---

Il n'y a jamais de complément à deux avec les CRC... et même surtout pas, puisque c'est une arithmétique avec des coéfficient modulo 2 (dans GF(2), comme disent les matheux/ses).

L'opposé du résultat : je suppose que tu parle du fameux XorOut. C'est effectivement un des paramètre de ces algo... l'application d'un masque avec un XOR. Si ce masque vaut 0xFFFFFFFF, alors le résultat est une inversion des bits, effectivement, et si le masque vaut 0x00000000, alors le résultat reste inchangé.

Mais il n'y a pas de relation directe entre la valeur initiale du registre et la valeur du masque à appliquer en sortie. Ces deux paramètres sont indépendants. Dans le cas du CRC-32 Ethernet (le CRC-32 le plus courant), la valeur initiale du registre de calcul est 0xFFFFFFFF, et la valeur du masque XOR en sortie et de 0xFFFFFFFF, effectivement.

J'ai essayé avec et sans le masque en sorti, le résultat est le même : ça ne correspond pas au résultats devant être renvoyé avec la chaîne de teste "123456789" (c'est une chaine de teste standard pour vérifié les implémentations de calcul CRC).

Sinon, est-ce que tu as vu un peu le deuxième document ? :) Tu l'a trouvé interessant ? :)

Désolé pas encore eu le temps de parcourir le lien.

Pour ton pb. de runtest, tu as essayé de comparer l'implémentation + les outputs avec l'algo standardisé suivant : http://www.gzip.org/zlib/rfc-gzip.html ?

Coucou,

J'ai comparé avec un algo de référence... celui qui est dans le lien dont je parle trop (c'est un algo de référence sans table). Et là j'ai compris pourquoi ça ne marchait pas chez moi. Je ne sais pas trop encore l'expliquer, mais je peux dire en tout cas, que comme on est plus dans l'algo que dans les math, s'il y en a que ça interesse, il faut savoir qu'il faut donner la priorité à l'algo de référence plutôt qu'à l'aspect mathématique de la chose.

Comment expliquer mon erreur... je faisait la division polynomial en ajoutant un certains nombre de zéro à la suite du message. Ce nombre de zéro était égale au degré du polynôme diviseur. C'était une manière de s'assurer de la divisibilité, pour peu que le dividence, c'est-à-dire le message, contenait au moins un bit à un, car sinon il restait de toute façon à zéro. Mon implémentation étant basée sur un registre à décalage, je l'initialisait à zéro, comme indiqué pour les parmètres des différents CRC.

Ma méthode de division donnait les bon résultat avec un reste initialisé à zéro... qui correspond effectivement à une division polynomiale à coéfficient modulo 2. Mais travailler avec un registre initialisé à 0xFFFFFFFF, ressemble plus à du bricolage qu'à des math, et là, l'implémentation de référence prend tout son sens, car il y a deux grande manière de faire le calcul, et selon que l'on emploie l'une ou l'autre, le résulat bien qu'étant le même avec un reste initial de zéro, devient totalement différent avec un reste initial à 0xFFFFFFFF.

C'est compréhensible, puisque le point de départ étant la division polynomial, les deux implémentations de la division sont légitime... mais seulement au départ. Et c'est un peu par arbitraire que seule une des deux est reconnu. C'est celle qui a été choisi, et c'est ainsi.

Je ne sais pas si je m'exprime clairement, mais voilà.

Je vais faire mon propre tuto sur la question, et il va falloir donc que j'explique bien tout ça... et surtout que je m'inprègne bien de l'implémentation de référence, parce que ce n'est pas celle qui me semblait la plus naturelle de prime abord pour implémenter la division (il faut toujours avoir à l'esprit, qu'avec un reste initialisé à zéro, l'implémentation de référence n'est pas la seule possible).

En tous cas merci mchk0123, pour ta présence encourageante :D

... pffff... j'y suis enfin arrivé... ne me reste plus qu'à bien comprendre en profondeur maintenant, une implémentation qui n'était pas la plus naturelle à mon esprit.

Oilà...

Citation:

---

Envoyé par Hibou57

Oui, mais de mon avis de longue date, et cela commence même un peu à être à la monde depuis récement, l'algorithmique reflête mieux certaines réalité que les mathématiques. C'est vrai que les deux sont différentes (les maths pour ce qui est statiques, et l'algo pour ce qui est dynamique... tel est le crédo dans l'air du temps)

---

8O en particulier sur le rouge...

Vous constaterez que je reste de marbre malgré une température interne à plus de 52 degrés... :mouarf: