Calculatrice CRC / XOR / division modulo 2

Comment utiliser la calculatrice CRC / XOR / division modulo 2

Pour calculer un CRC par division modulo 2, suivez ces 4 étapes :

• Saisissez le message binaire (bits de données) dans le premier champ.
• Saisissez le polynôme générateur sous forme de bits binaires dans le second champ.
• La calculatrice ajoute (n − 1) bits nuls, où n est la longueur du générateur.
• Cliquez sur Calculer pour XORer le message bit par bit et lisez le reste comme CRC.

Le quotient est généralement ignoré en CRC — le reste est la somme de contrôle qui s'ajoute au message avant la transmission.

CRC et arithmétique modulo 2

Un contrôle de redondance cyclique détecte les erreurs de transmission en traitant un message comme un grand polynôme binaire et en le divisant par un polynôme générateur convenu. La division se fait en arithmétique modulo 2 (GF(2)), où addition et soustraction sont identiques et valent XOR — il n'y a ni retenue ni emprunt. Le reste de cette division est le CRC. Lorsque le récepteur divise le message plus le CRC par le même générateur, un reste de 0 signifie qu'aucune erreur n'a été détectée. Cette calculatrice reproduit exactement ce processus bit à bit.

Comment fonctionne la division CRC modulo 2

La calculatrice calcule le CRC au moyen de cinq actions internes :

• Ajoute (n − 1) bits nuls au message, où n est le nombre de bits du générateur.
• Aligne le générateur sous le bit 1 le plus à gauche du reste courant.
• XOR le générateur dans ces bits (soustraction modulo 2 sans emprunt).
• Décale vers le bit 1 suivant et répète l'alignement XOR.
• S'arrête lorsque les bits restants sont moins nombreux que le générateur ; ces bits sont le CRC.

Chaque bit du quotient vaut 1 partout où le générateur est XORé et 0 ailleurs, mais pour le CRC seul le reste final compte.

Formule de la division CRC

La calculatrice CRC / XOR / division modulo 2 calcule CRC = (M(x) · xⁿ⁻¹) mod G(x) dans GF(2), où M(x) est le message, G(x) le générateur de n bits, et toutes les additions sont des XOR. La trame transmise est M(x)·xⁿ⁻¹ + CRC, que G(x) divise exactement. Côté réception, un reste nul confirme l'intégrité.

Problèmes d'exemple CRC / XOR

Ces exemples montrent la division modulo 2 avec XOR à chaque étape.

Exemple 1 — Message 1101, générateur 101

1. Longueur du générateur 3, donc ajoutez 2 zéros : 1101 devient 110100.
2. XOR 101 dans les bits de tête de façon répétée : 110100 → 011100 → 001000 → 000010.
3. Les 2 derniers bits, 10, sont le reste CRC.

Exemple 2 — Pourquoi la soustraction est un XOR

1. En modulo 2, 1 + 1 = 0 et 1 − 1 = 0, donc addition et soustraction sont la même opération.
2. Cette opération est exactement le XOR bit à bit, sans retenue ni emprunt.
3. Chaque étape de division est donc un XOR du générateur dans les bits courants.

Exemple 3 — Vérification côté récepteur

1. Ajoutez le CRC au message et divisez par le même générateur.
2. XORer bit par bit exactement comme avant.
3. Un reste de 0 signifie qu'aucune erreur n'a été détectée.

Longueur du générateur 3, donc ajoutez 2 zéros : 1101 devient 110100.
XOR 101 dans les bits de tête de façon répétée : 110100 → 011100 → 001000 → 000010.
Les 2 derniers bits, 10, sont le reste CRC.

En modulo 2, 1 + 1 = 0 et 1 − 1 = 0, donc addition et soustraction sont la même opération.
Cette opération est exactement le XOR bit à bit, sans retenue ni emprunt.
Chaque étape de division est donc un XOR du générateur dans les bits courants.

Ajoutez le CRC au message et divisez par le même générateur.
XORer bit par bit exactement comme avant.
Un reste de 0 signifie qu'aucune erreur n'a été détectée.

Problèmes CRC résolus

Comment calculer le CRC de 10110 avec le générateur 1011 ?

Ajoutez 3 zéros (longueur du générateur 4) pour obtenir 10110000, puis XORer vers le bas. Alignez 1011 sous chaque 1 de tête et XOR : 10110000 → 00100000 → après des XOR successifs, les 3 bits finaux forment le reste CRC. Le reste s'ajoute ensuite à 10110 pour que la trame complète soit divisible par 1011 sans reste.

Pourquoi un reste nul signifie-t-il que les données sont intactes ?

L'émetteur a choisi le CRC pour que la trame transmise soit un multiple exact du générateur. Tout multiple de G(x) divisé par G(x) laisse un reste 0. Si des bits basculent en transit, la trame n'est plus en général un multiple, donc la division côté récepteur laisse un reste non nul, signalant une erreur.

Erreurs fréquentes CRC / modulo 2

La division CRC modulo 2 produit 5 erreurs fréquentes :

• Utiliser une soustraction binaire ordinaire avec emprunts au lieu du XOR.
• Ajouter un mauvais nombre de bits nuls (il faut la longueur du générateur moins un).
• Aligner le générateur sous un bit 0 au lieu du 1 de tête.
• Traiter des retenues comme si elles existaient en arithmétique GF(2).
• Rapporter le quotient comme CRC au lieu du reste.

La calculatrice CRC / XOR / division modulo 2 XOR à chaque étape, ajoute les zéros corrects et renvoie le reste comme somme de contrôle.

Questions frequentes