Comment un calculateur de voiture vérifie-t-il qu'un message reçu n'a pas été abîmé ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Dans une voiture, des dizaines de calculateurs échangent des messages sur un bus de communication, au milieu de parasites électriques. En sciences de l'ingénieur, j'ai appris que chaque trame se termine par un code de contrôle appelé CRC. J'ai été surpris de découvrir que son calcul est une division de polynômes, comme celle que l'on fait pour factoriser, mais avec une arithmétique où 1 + 1 = 0.

L'enjeu et les notions du programme

Effectuer une division de polynômes avec une arithmétique binaire et comprendre pourquoi le reste permet de détecter des erreurs.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Une trame contient des données suivies d'un code de contrôle calculé à partir d'elles. Le récepteur refait le calcul : si le résultat ne concorde pas, la trame a été abîmée. Problématique : comment calcule-t-on ce code, et quelles erreurs détecte-t-il ?

2. 2. Mathématiques : une division de polynômes binaires

   4,5 min

   Un mot binaire est vu comme un polynôme : 1101 correspond à $x^3+x^2+1$x³+x²+1. On calcule avec les coefficients 0 et 1, où l'addition est le OU exclusif ($1+1=0$1+1=0) : addition et soustraction se confondent.

   Le générateur choisi est $g(x)=x^3+x+1$g(x)=x³+x+1, soit 1011, de degré 3. On ajoute 3 zéros au message (on le multiplie par $x^3$x³) : 1101000. On divise par 1011 comme une division posée, en remplaçant la soustraction par le OU exclusif. 1101 ⊕ 1011 = 0110 ; on abaisse les chiffres et on recommence : 1100 ⊕ 1011 = 0111 ; puis 1110 ⊕ 1011 = 0101, et enfin 1010 ⊕ 1011 = 0001. Le reste final, de degré inférieur à 3, est 001.

   On envoie le message suivi du reste : 1101001. Ce mot correspond à un multiple de $g$g : divisé par 1011, il laisse un reste nul. Le récepteur fait la division : reste nul, la trame est acceptée ; reste non nul, elle est rejetée.

   Une erreur ajoute au mot un polynôme $e(x)$e(x). Elle n'est pas détectée seulement si $e$e est lui-même un multiple de $g$g. Une erreur sur un seul bit, $e=x^k$e=x^(k), n'est jamais multiple de $g$g : toujours détectée.

3. 3. SI : en pratique

   2,5 min

   Le bus CAN des voitures utilise un générateur de degré 15 : il détecte toutes les rafales d'erreurs de 15 bits consécutifs ou moins, et ne laisse passer qu'une fraction d'environ $2^{-15}$2⁻¹⁵ des erreurs plus longues. Ethernet utilise un CRC de 32 bits.

   Le calcul se fait en matériel avec un registre à décalage et quelques portes OU exclusif : il ne coûte presque rien. Une trame rejetée est renvoyée. Le CRC détecte les erreurs dues aux parasites, mais n'est pas une protection contre une modification volontaire : pour cela, il faut des signatures cryptographiques.

4. 4. Conclusion

   1,5 min

   Le CRC est le reste d'une division de polynômes à coefficients binaires : pour 1101 et 1011, il vaut 001, et le mot envoyé 1101001 est divisible par le générateur. Toute erreur qui n'est pas un multiple du générateur est détectée. J'ouvre sur les codes correcteurs de Reed-Solomon, qui utilisent aussi des polynômes pour réparer les erreurs.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Faire des retenues comme dans une soustraction ordinaire.
• Oublier d'ajouter les zéros avant la division.
• Croire que le CRC détecte toutes les erreurs possibles.

Revoir les notions

• Polynômes de degré 2 et 3 (Première spé maths) →
• Nombres et calculs (Seconde) →

Autres questions : information et commande numérique

• Comment simplifier la logique d'une alarme pour utiliser moins de composants ?
• Comment un microcontrôleur cadencé à 16 MHz peut-il produire exactement une impulsion par seconde ?
• Combien de tâches un système embarqué peut-il exécuter à temps, et pourquoi le nombre ln 2 apparaît-il ?
• Pourquoi ne peut-on pas avoir à la fois une commande de moteur très fine et une fréquence très élevée ?

Toutes les questions maths-sciences de l'ingénieur →