Combien d'erreurs un code peut-il corriger, et comment le savoir en mesurant des distances entre mots binaires ?

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.

Après avoir étudié le bit de parité et le code de Hamming, je me suis demandé s'il existait une règle générale pour savoir combien d'erreurs un code peut corriger. J'ai découvert la distance de Hamming, qui transforme ce problème en problème de géométrie : des mots binaires, des distances, et des boules qui ne doivent pas se chevaucher.

L'enjeu et les notions du programme

Définir une distance sur les mots binaires, en déduire la capacité d'un code par l'inégalité triangulaire, puis dénombrer les boules.

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

1. 1. Introduction

   1 min

   Un code choisit, parmi tous les mots binaires de longueur $n$n, certains mots autorisés. Le récepteur qui reçoit un mot non autorisé sait qu'il y a eu une erreur. Problématique : combien d'erreurs le code peut-il détecter ou corriger ?

2. 2. Mathématiques : une géométrie des mots binaires

   4,5 min

   La distance de Hamming $d(u,v)$d(u,v) est le nombre de positions où $u$u et $v$v diffèrent : $d(10110,11100)=2$d(10110,11100)=2. C'est le nombre de 1 de $u\oplus v$u⊕ v. Elle vérifie l'inégalité triangulaire $d(u,w)\le d(u,v)+d(v,w)$d(u,w)≤ d(u,v)+d(v,w) : pour passer de $u$u à $w$w, il suffit de corriger les différences avec $v$v, puis celles de $v$v avec $w$w.

   Soit $d$d la plus petite distance entre deux mots du code. Détection : $d-1$d-1 erreurs au plus ne transforment jamais un mot du code en un autre. Correction : avec $t$t erreurs et $2t+1\le d$2t+1≤ d, le mot reçu $r$r est à distance au plus $t$t du mot envoyé $c$c. Tout autre mot $c^{\prime }$c' du code vérifie $d(r,c^{\prime })\ge d(c,c^{\prime })-d(c,r)\ge 2t+1-t=t+1$d(r,c')≥ d(c,c')-d(c,r)≥2t+1-t=t+1. Le mot le plus proche est donc $c$c : on corrige en choisissant le mot du code le plus proche. Un code corrige $\lfloor \frac{d-1}{2}\rfloor$lfloor(d-1)/2rfloor erreurs.

   Dénombrement : la « boule » de rayon 1 autour d'un mot de 7 bits contient le mot et ses $\left(\genfrac{}{}{0ex}{}{7}{1}\right)=7$binom71=7 voisins : 8 mots. Le code de Hamming (7, 4) a $2^4=16$2⁴=16 mots, à distance au moins 3, donc des boules disjointes : $16\times 8=128=2^7$16×8=128=2⁷. Elles remplissent tout l'espace.

3. 3. NSI : choisir un code

   2,5 min

   Le code à répétition triple (000, 111) a $d=3$d=3 : il corrige 1 erreur, mais avec un rendement de $\frac{1}{3}$1/3. Le code de Hamming (7, 4) a aussi $d=3$d=3, avec un rendement de $\frac{4}{7}$4/7 : il est bien plus efficace.

   Pour corriger $t$t erreurs, il faut des boules de rayon $t$t disjointes : $2^k\left(1+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{t}\right)\right)\le 2^n$2^(k)(1+binom n1+…+binom nt)≤2ⁿ. Cette borne indique combien de bits de contrôle sont nécessaires. En Python, la distance se calcule en comptant les 1 de $u\oplus v$u⊕ v.

4. 4. Conclusion

   1,5 min

   La distance de Hamming fait des codes une géométrie : avec une distance minimale $d$d, on détecte $d-1$d-1 erreurs et on en corrige $\lfloor \frac{d-1}{2}\rfloor$lfloor(d-1)/2rfloor, par l'inégalité triangulaire. Le dénombrement des boules mesure le prix de cette protection. J'ouvre sur les codes de Reed-Solomon des QR codes, qui corrigent jusqu'à 30 % de symboles abîmés.

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

• Confondre détecter et corriger.
• Oublier la partie entière dans ⌊(d − 1)/2⌋.
• Oublier le mot central dans le décompte d'une boule.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Géométrie repérée (Seconde) →

Autres questions : transmettre et compresser

• Comment un ordinateur peut-il savoir qu'un message a été abîmé pendant sa transmission ?
• Comment un message peut-il se réparer tout seul quand un bit a été faussé ?
• Comment un site marchand sait-il instantanément qu'un numéro de carte bancaire a été mal recopié ?
• Pourquoi la clé d'un IBAN repose-t-elle sur le reste de la division par 97 ?

Toutes les questions maths-nsi →