6.1 Introduction : num´ eriser, d´ etecter et corriger
179
est erron´ e. Cette hypoth` ese est raisonnable si la transmission est presque parfaite et que
la probabilit´ e de deux erreurs au sein d’une transmission de huit bits est presque nulle.
Le troisi` eme exemple pr´ esente une id´ ee simple pour construire un code correcteur,
c’est-` a-dire un code permettant de d´ etecter et de corriger une erreur. Il consiste ` a r´ ep´ eter
la totalit´ e du message suffisamment de fois. Par exemple, tous les caract` eres d’un texte
pourraient ˆ etre r´ ep´ et´ es deux fois. Ainsi, le mot « erreur » pourrait ˆ etre transmis sous
la forme « eerrrreeuurr ». Cette premi` ere version de ce code simple n’est cependant pas
un code correcteur, car, mˆ eme si on suppose qu’au plus une lettre par paire puisse ˆ etre
erron´ ee, il ne permet pas la correction des erreurs. Quel ´ etait le message original si nous
recevons « ˆ aˆ agmee » ? ´
Etait-ce « ˆ age » ou « ˆ ame » ? Pour faire de cette id´ ee simple un
code correcteur, il suffit de r´ ep´ eter trois fois chaque lettre. Si l’hypoth` ese d’au plus une
erreur par groupe de trois lettres est raisonnable, alors « ˆ aˆ aˆ agmmeee » sera d´ ecod´ e en
« ˆ ame ». En effet, mˆ eme si les trois lettres « gmm » ne co¨ ıncident pas, une seule est
erron´ ee, par hypoth` ese, et les trois lettres originales ne peuvent donc ˆ etre que « mmm ».
Voici donc un premier exemple de code correcteur ! Ce code est peu utilis´ e, car il est
coˆ uteux : il demande que toute l’information soit transmise en triple. Les codes que
nous pr´ esenterons dans ce chapitre sont beaucoup plus ´ economiques. Comme pour tous
les codes, il n’est pas impossible que, dans un groupe de trois lettres, deux ou mˆ eme
trois soient erron´ ees ; notre hypoth` ese est que ces ´ ev´ enements sont tr` es peu probables.
Comme l’exercice 8 le montre, ce code fort simple conserve cependant un l´ eger avantage
sur le code de Hamming qui sera introduit `
a la section 6.3.
Les codes d´ etecteurs et correcteurs existent donc depuis longtemps. Avec la num´ erisation de l’information, ces codes sont devenus de plus en plus n´ ecessaires et ais´ es ` a
mettre en œuvre. Leur n´ ecessit´ e est facile ` a comprendre quand on connaˆ ıt la grandeur
des fichiers typiques contenant des photos et de la musique. Voici, ` a la figure 6.1, une
toute petite photo num´ eris´ ee : les deux copies repr´ esentent le sommet de la tour d’un des
bˆ atiments de l’Universit´ e de Montr´ eal. `
A gauche, la photo est dans son format original.
`
A droite, la mˆ eme photo a ´ et´ e agrandie huit fois horizontalement et verticalement : on y
voit clairement les pixels, c’est-` a-dire les carr´ es de gris constant. En fait, ces deux photos
ont ´ et´ e fractionn´ ees en 72×72 carr´ es de gris constant (les pixels), et la profondeur du gris
a ´ et´ e rep´ er´ ee sur une ´ echelle de 256 = 2
8 niveaux de gris (le blanc ´ etant `
a une extr´ emit´ e
de cette ´ echelle, le noir ´ etant `
a l’autre). Il faut donc transmettre 72×72×8 = 41,472 bits
pour transmettre cette petite photo en noir et blanc. Et nous sommes fort loin d’une
photo couleur grand format puisque les cam´ eras num´ eriques actuelles ont des capteurs
de plus de 2000 × 3000 pixels couleur
2 !
Le son et, en particulier, la musique sont de plus en plus souvent num´ eris´ es. Par
rapport `
a la num´ erisation des images, celle du son est plus difficile ... `
a visualiser. Il
faut savoir que le son est une onde. Les vagues sur la mer sont une onde qui se propage
2 Ceux qui s’int´ eressent ` a l’informatique sont habitu´ es ` a voir les grandeurs de fichier et les
capacit´ es des espaces-disques mesur´ ees en octets, en kilooctets (Ko, c’est-` a-dire 1000 octets),
en m´ egaoctets (1 Mo = 10
6 octets), en gigaoctets (1 Go = 10
9 octets), etc. Un octet est ´ egal
` a huit bits, et notre petite photo noir et blanc occupe 41 472/8 o = 5184 o = 5,184 Ko.
179
est erron´ e. Cette hypoth` ese est raisonnable si la transmission est presque parfaite et que
la probabilit´ e de deux erreurs au sein d’une transmission de huit bits est presque nulle.
Le troisi` eme exemple pr´ esente une id´ ee simple pour construire un code correcteur,
c’est-` a-dire un code permettant de d´ etecter et de corriger une erreur. Il consiste ` a r´ ep´ eter
la totalit´ e du message suffisamment de fois. Par exemple, tous les caract` eres d’un texte
pourraient ˆ etre r´ ep´ et´ es deux fois. Ainsi, le mot « erreur » pourrait ˆ etre transmis sous
la forme « eerrrreeuurr ». Cette premi` ere version de ce code simple n’est cependant pas
un code correcteur, car, mˆ eme si on suppose qu’au plus une lettre par paire puisse ˆ etre
erron´ ee, il ne permet pas la correction des erreurs. Quel ´ etait le message original si nous
recevons « ˆ aˆ agmee » ? ´
Etait-ce « ˆ age » ou « ˆ ame » ? Pour faire de cette id´ ee simple un
code correcteur, il suffit de r´ ep´ eter trois fois chaque lettre. Si l’hypoth` ese d’au plus une
erreur par groupe de trois lettres est raisonnable, alors « ˆ aˆ aˆ agmmeee » sera d´ ecod´ e en
« ˆ ame ». En effet, mˆ eme si les trois lettres « gmm » ne co¨ ıncident pas, une seule est
erron´ ee, par hypoth` ese, et les trois lettres originales ne peuvent donc ˆ etre que « mmm ».
Voici donc un premier exemple de code correcteur ! Ce code est peu utilis´ e, car il est
coˆ uteux : il demande que toute l’information soit transmise en triple. Les codes que
nous pr´ esenterons dans ce chapitre sont beaucoup plus ´ economiques. Comme pour tous
les codes, il n’est pas impossible que, dans un groupe de trois lettres, deux ou mˆ eme
trois soient erron´ ees ; notre hypoth` ese est que ces ´ ev´ enements sont tr` es peu probables.
Comme l’exercice 8 le montre, ce code fort simple conserve cependant un l´ eger avantage
sur le code de Hamming qui sera introduit `
a la section 6.3.
Les codes d´ etecteurs et correcteurs existent donc depuis longtemps. Avec la num´ erisation de l’information, ces codes sont devenus de plus en plus n´ ecessaires et ais´ es ` a
mettre en œuvre. Leur n´ ecessit´ e est facile ` a comprendre quand on connaˆ ıt la grandeur
des fichiers typiques contenant des photos et de la musique. Voici, ` a la figure 6.1, une
toute petite photo num´ eris´ ee : les deux copies repr´ esentent le sommet de la tour d’un des
bˆ atiments de l’Universit´ e de Montr´ eal. `
A gauche, la photo est dans son format original.
`
A droite, la mˆ eme photo a ´ et´ e agrandie huit fois horizontalement et verticalement : on y
voit clairement les pixels, c’est-` a-dire les carr´ es de gris constant. En fait, ces deux photos
ont ´ et´ e fractionn´ ees en 72×72 carr´ es de gris constant (les pixels), et la profondeur du gris
a ´ et´ e rep´ er´ ee sur une ´ echelle de 256 = 2
8 niveaux de gris (le blanc ´ etant `
a une extr´ emit´ e
de cette ´ echelle, le noir ´ etant `
a l’autre). Il faut donc transmettre 72×72×8 = 41,472 bits
pour transmettre cette petite photo en noir et blanc. Et nous sommes fort loin d’une
photo couleur grand format puisque les cam´ eras num´ eriques actuelles ont des capteurs
de plus de 2000 × 3000 pixels couleur
2 !
Le son et, en particulier, la musique sont de plus en plus souvent num´ eris´ es. Par
rapport `
a la num´ erisation des images, celle du son est plus difficile ... `
a visualiser. Il
faut savoir que le son est une onde. Les vagues sur la mer sont une onde qui se propage
2 Ceux qui s’int´ eressent ` a l’informatique sont habitu´ es ` a voir les grandeurs de fichier et les
capacit´ es des espaces-disques mesur´ ees en octets, en kilooctets (Ko, c’est-` a-dire 1000 octets),
en m´ egaoctets (1 Mo = 10
6 octets), en gigaoctets (1 Go = 10
9 octets), etc. Un octet est ´ egal
` a huit bits, et notre petite photo noir et blanc occupe 41 472/8 o = 5184 o = 5,184 Ko.