Bonjour.

Pour comprendre le CRC, je suis allé ici : https://ensiwiki.ensimag.fr/images/f/f3/Tp_crc16.pdf

Je doit avouer avoir plutot bien compris...

Cependant, je ne comprend pas pour quoi on appel cette opération une division binaire sachant que cela n'a rien a voir avec une division.

Alors dites moi, qu'estce que cette opération ? A t-elle un équivalent décimal ? pour quoi l'appeler division ?

Sur le site suivant, on précise la façon de faire un CRC:
https://fr.wikipedia.org/wiki/Contr%C3%B4le_de_redondance_cyclique#:~:text=En%20informatique%20et%20dans%20certains,%C3%A0%20une%20proc%C3%A9dure%20de%20hachage.
On y dit ce qui suit:
«L’opération mathématique essentielle dans le calcul d’un CRC est une division modulo 2 dont le reste représente le CRC.»

Bonjour.

J'avoue ne pas bien comprendre.

J'ai

1/ le message => 1000 0100 (132)
2/ le polynome (variable) => x3+x2+x1+1 => 1111 (15)

Qu'est-ce qu'une division modulo 2 ? je connait le modulo, la division mais pas la division modulo...

il ne sagit pas de 132%2 sinon 15 serait inutile. (132/15)%2 ?

Je ne comprend pas. De quoi s'agit-il ?

Adrien Supra a écrit:

Bonjour.

Pour comprendre le CRC, je suis allé ici : https://ensiwiki.ensimag.fr/images/f/f3/Tp_crc16.pdf

Je doit avouer avoir plutot bien compris...

Cependant, je ne comprend pas pour quoi on appel cette opération une division binaire sachant que cela n'a rien a voir avec une division.

Alors dites moi, qu'estce que cette opération ? A t-elle un équivalent décimal ? pour quoi l'appeler division ?

Je viens de lire le document. En première page, on nous présente une division euclidienne en base 2 (binaire). Simplement, comme on recherche juste le reste de cette division (c'est-à-dire à quoi est congru 11010110110000 modulo 10011 - en base 2, hein !), la partie de droite de la division n'est pas représentée (et on ne la calcule pas). En base 10, on demande combien de fois 44 pour faire 181 (par exemple) et on écrit 4x44 = 176 en-dessous de 181, puis on effectue la soustraction. Là, c'est soit 0x10011, soit 1x10011, donc on se contente de soustraire 00000 ou 10011.

Concernant la page de Wikipédia, il y a peut-être eu confusion entre « modulo 2 » et « en base 2 » ? Après tout, la page en anglais, elle, ne parle pas de division modulo 2.

-
Edité par robun 17 décembre 2020 à 13:03:20

Hello

merci de vous occuper de moi.

Alors dans leur exemple :

1101011011 = 859

10011 = 19

859%19 = 4

Ils donne comme résultat : 1110 = 14

Si on remplace 859 par

1101011011000 = 6872
6872%19 = 13 != 14

 Du coup quoi ? un modulo binaire n'est pas l'équivalent d'un modulo decimal ?

Ya un truc que je vois pas c'est sur...

-
Edité par -Crixus- 17 décembre 2020 à 17:24:41

Ce n'est pas 1101011011000 mais 11010110110000 (4 zéros de plus), qui vaut 13744 en base 10. Le reste de la division par 19 vaut 7. Le résultat est en effet 14, bizarre. Je te laisse vérifier leurs calculs... Mais ce ne sont peut-être pas des soustractions ?

Effectivement, je viens de faire quelques calculs, ce ne sont pas des soustractions. Le document appelle ça des XOR, mais je ne sais pas comment raccorder ça à une opération arithmétique.

-
Edité par robun 17 décembre 2020 à 17:37:54

J'ai cru voir que ce n'est pas une division, au sens de division euclidienne.

Robun disait qu'à chaque étape, on effectue la soustraction.

Mais le document ne parle pas de soustraction, il parle d'opération XOR. Ca ressemble à la soustraction, pour certaines valeurs, ça donne le même résultat qu'une soustraction, mais pas toujours. C'est une soustraction dans laquelle on se trompe systématiquement dès qu'il y a une retenue.

Il faut donc comprendre le mot division, non pas dans le sens de division euclidienne, mais dans un sens plus large. On divise un ensemble en plusieurs sous-ensembles. C'est donc une division.

Le mot division peut aussi s'expliquer par la présentation de l'opération, qui ressemble à la façon dont on pose les divisions, quand on les calcule sans calculatrice.

C'est pour faire craquer les étudiant xD

Merci pour vos analyse.

Je n'avais pas vu le dernier message de Robun. Il n'y a pas d'opération arithmétique 'simple' qui correspond à ce XOR. Par curiosité, ce serait amusant de calculer le CRC pour une douzaine de nombres successifs. Je pense que le résultat serait une suite de 12 nombres ... sans la moindre logique visible.

D'ailleurs, c'est un peu le but du jeu. S'il y avait une logique simple, l'algorithme pourrait être totalement inopérant sur certains jeux de données.