6
Codes correcteurs
La partie ´ el´ ementaire est constitu´ ee des sections 6.1 ` a 6.4. Elle explique la n´ ecessit´ e
des codes correcteurs, introduit le corps fini F2 de deux ´ el´ ements et d´ ecrit une famille
de codes correcteurs non triviaux, les codes de Hamming. L’arithm´ etique du corps F2
sera nouvelle pour la plupart des lecteurs, mais la partie ´ el´ ementaire n’utilise que les
concepts relatifs aux espaces vectoriels et `
a l’alg` ebre matricielle (sur F2). Elle peut ˆ etre
couverte en trois heures. Les sections 6.5 et 6.6 forment la partie avanc´ ee. Les corps
finis Fpr , o` u p est premier, sont construits par l’introduction sur les polynˆ omes de
degr´ e inf´ erieur `
a r d’une multiplication modulo un polynˆ ome irr´ eductible. La pratique
sur quelques exemples permet d’assimiler facilement ce concept qui peut, au premier
abord, sembler d´ eroutant. Les codes de Reed–Solomon sont enfin pr´ esent´ es `
a la derni` ere
section. Il faut au moins trois heures suppl´ ementaires pour couvrir la partie avanc´ ee.
6.1 Introduction : num´ eriser, d´ etecter et corriger
La transmission d’information `
a distance a ´ et´ e utilis´ ee tr` es tˆ ot dans l’histoire de
l’humanit´ e
1 . La d´ ecouverte des lois physiques de l’´ electromagn´ etisme et de leurs applications a permis d’envoyer des messages sous forme ´ electrique d` es la seconde moiti´ e du
XIX
e si` ecle. Que la communication se fasse directement `
a l’aide d’une langue humaine
(tel le fran¸ cais ou l’anglais) ou soit pr´ ealablement encod´ ee (par exemple, `
a l’aide du code
Morse (1836)), l’utilit´ e de pouvoir d´ etecter et corriger des erreurs lors de la transmission
se fait rapidement sentir.
Une premi` ere m´ ethode permettant d’am´ eliorer la fid´ elit´ e de la transmission d’un
message poss` ede une importance historique. Au d´ ebut de la t´ el´ ephonie (avec ou sans
fil), la qualit´ e de la transmission laissait beaucoup ` a d´ esirer. Il ´ etait donc usuel d’´ epeler
1 Selon la l´ egende, le soldat charg´ e de rapporter la victoire des Ath´ eniens sur les Perses en
l’an 490 aurait couru la distance entre Marathon et Ath` enes et serait mort d’´ epuisement ` a son
arriv´ ee. La longueur du marathon olympique est maintenant de 41,195 km.
Codes correcteurs
La partie ´ el´ ementaire est constitu´ ee des sections 6.1 ` a 6.4. Elle explique la n´ ecessit´ e
des codes correcteurs, introduit le corps fini F2 de deux ´ el´ ements et d´ ecrit une famille
de codes correcteurs non triviaux, les codes de Hamming. L’arithm´ etique du corps F2
sera nouvelle pour la plupart des lecteurs, mais la partie ´ el´ ementaire n’utilise que les
concepts relatifs aux espaces vectoriels et `
a l’alg` ebre matricielle (sur F2). Elle peut ˆ etre
couverte en trois heures. Les sections 6.5 et 6.6 forment la partie avanc´ ee. Les corps
finis Fpr , o` u p est premier, sont construits par l’introduction sur les polynˆ omes de
degr´ e inf´ erieur `
a r d’une multiplication modulo un polynˆ ome irr´ eductible. La pratique
sur quelques exemples permet d’assimiler facilement ce concept qui peut, au premier
abord, sembler d´ eroutant. Les codes de Reed–Solomon sont enfin pr´ esent´ es `
a la derni` ere
section. Il faut au moins trois heures suppl´ ementaires pour couvrir la partie avanc´ ee.
6.1 Introduction : num´ eriser, d´ etecter et corriger
La transmission d’information `
a distance a ´ et´ e utilis´ ee tr` es tˆ ot dans l’histoire de
l’humanit´ e
1 . La d´ ecouverte des lois physiques de l’´ electromagn´ etisme et de leurs applications a permis d’envoyer des messages sous forme ´ electrique d` es la seconde moiti´ e du
XIX
e si` ecle. Que la communication se fasse directement `
a l’aide d’une langue humaine
(tel le fran¸ cais ou l’anglais) ou soit pr´ ealablement encod´ ee (par exemple, `
a l’aide du code
Morse (1836)), l’utilit´ e de pouvoir d´ etecter et corriger des erreurs lors de la transmission
se fait rapidement sentir.
Une premi` ere m´ ethode permettant d’am´ eliorer la fid´ elit´ e de la transmission d’un
message poss` ede une importance historique. Au d´ ebut de la t´ el´ ephonie (avec ou sans
fil), la qualit´ e de la transmission laissait beaucoup ` a d´ esirer. Il ´ etait donc usuel d’´ epeler
1 Selon la l´ egende, le soldat charg´ e de rapporter la victoire des Ath´ eniens sur les Perses en
l’an 490 aurait couru la distance entre Marathon et Ath` enes et serait mort d’´ epuisement ` a son
arriv´ ee. La longueur du marathon olympique est maintenant de 41,195 km.