Section 3.1
Codes et mots de code
Dans cette première section du chapitre, nous allons aborder la notion de code. Cette notion est centrale dans ce chapitre sur la représentation de l'information.
Un code est une manière de représenter un ensemble fini de valeurs avec des suites de symboles. Chaque telle suite de symboles est appelée un mot de code. En principe, chaque valeur possible de l'information à représenter est associée à un unique mot de code, et chaque mot de code est associé à une unique valeur.
Les symboles que nous utiliserons dans ce chapitre seront généralement les bits (0 et 1), mais d'autres types de symboles peuvent être utilisés par différents codes.
♣︎ Exemple
Le code Morse (aucun lien avec l'animal) est un exemple de code qui permet de représenter des lettres et des chiffres avec des suites de points et de tirets. Le code Morse utilise donc deux symboles différents : le point (que l'on note ·) et le tiret (que l'on note —).
Pour encoder un message en code Morse, il suffit de remplacer chaque lettre par son mot de code. Ensuite, chaque mot de code est séparée des autres par un espace. On utilise un plus grand espace pour dénoter un espace entre les mots dans la phrase à transmettre.
Ainsi, le mot HELLO est encodé en code Morse par · · · · · · – · · · – · · – – – et le mot WORLD par · – – – – – · – · · – · · – · ·. Il est important de marquer un espace entre les mots de code pour pouvoir les distinguer. De plus, il faut marquer un plus grand espace entre les mots HELLO et WORLD pour obtenir la phrase HELLO WORLD et non HELLOWORLD.
Le code Morse a été conçu pour communiquer des messages via télégraphe. De nos jours, il est encore utilisé par les radioamateurs et par les marins pour communiquer en utilisant des signaux lumineux.
Encoder et décoder
Lorsque l'on passe d'une valeur à un mot de code, on dit que l'on encode la valeur. À l'inverse, lorsque l'on passe d'un mot de code à une valeur, on dit que l'on décode le mot de code.
Un système dont le but est d'encoder des valeurs en mots de code est appelé un encodeur, alors qu'un système dont le but est de décoder des mots de code en valeurs est appelé un décodeur.
Séquences de mots de code
Souvent, étant donné un code, on souhaitera représenter non pas une unique valeur, mais une séquence de valeurs. Par exemple, à l'aide d'un code pour les caractères de texte, on souhaitera représenter des mots tels que SOS (pour "Save Our Souls") ou CQD (pour "Come Quick Danger"), voire des phrases comme "What hath God wrought?" (premier message transmis par télégraphe) ou "something like QWERTYUIOP" (premier message transmis par email).
Dans certains codes, il suffit de concaténer (mettre bout à bout) les mots de code des valeurs de la séquence pour obtenir la représentation de la séquence. Ainsi, un code pour des valeurs individuelles donne immédiatement un moyen de représenter des séquences de valeurs. Or, ce n'est pas toujours le cas. Dans d'autres codes, il faudra utiliser diverses techniques pour délimiter les mots de code d'une séquence.
♣︎ Exemple
Dans le code Morse, certains mots de code sont les préfixes d'autres mots de code. Un mot est le préfixe d'un autre mot si le premier mot forme le début du second mot. Par exemple, le mot de code · est le préfixe des mots de code · – – et · · · ·.
Le fait que certains mots de codes soient les préfixes d'autres mots de code peut rendre le décodage compliqué voire ambigu en cas de simple concaténation de mots de code.
Dans le cas du code Morse, si on venait à simplement concaténer les mots de codes pour encoder une suite de lettres, on pourrait obtenir un résultat qui donne lieu à plusieurs interprétations. On parle alors d'ambiguïté du décodage.
Par exemple, si on venait à encoder la séquence de lettres EEE en Morse sans séparer les mots de code, on obtiendrait la séquence de symboles · · ·. Or, cette séquence de symboles peut être interprétée comme la lettre S (· · ·), ou alors comme trois fois la lettre E (·), ou comme un I (· ·) suivi d'un E (·), ou encore comme un E (·) suivi d'un I (· ·). Le décodage de la séquence de symboles · · · serait donc ambigu.
En Morse, pour séparer les mots de code de deux lettres, on est donc obligé d'ajouter un espace entre les mots de code, on ne peut pas simplement concaténer les mots de code.
Codes à longueur fixe
Une famille de codes très utilisés en pratique et qui se prêtent bien à l'encodage de séquences de valeurs sont les codes à longueur fixe. On appelle code à longueur fixe un code dans lequel tous les mots de code ont la même longueur.
Les codes à longueur fixe sont très pratiques pour représenter des séquences de valeurs. En effet, pour représenter une séquence de valeurs avec un tel code, il suffit de concaténer les mots de code des valeurs de la séquence. Le message obtenu ainsi est totalement non ambigu.
Pour décoder un message, il suffit de le découper en mots de code de même longueur, et de remplacer chaque mot de code par la valeur correspondante. Aucune ambiguïté n'est possible, car chaque mot de code est clairement identifiable dans le message.
♣︎ Exemple
Considérons le code suivant, qui représente les lettres A, B, C et D :
| Lettre | Mot de code |
|---|---|
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
Ce code est un code à longueur fixe. En effet, chaque lettre est représentée par un mot de code de longueur 2.
À l'aide de ce code, on peut représenter la séquence de lettres
ABBA par la séquence
00010100 de façon totalement non ambiguë :
aucune autre interprétation que ABBA n'est possible.
! Remarque
Le nombre maximum de valeur qu'un code à longueur fixe peut représenter est très facilement calculable. Pour un code de longueur fixe n qui utilise b symboles différents, il y a au maximum bn valeurs représentables.
Codes à longueur variable
On appelle un code qui n'est pas à longueur fixe un code à longueur variable. Dans un code à longueur variable, les mots de code n'ont pas tous la même longueur. Certains mots de code peuvent être plus longs et d'autres plus courts.
♣︎ Exemple
Le code Morse contient des mots de code de longueurs variables. Par exemple, le mot de code de la lettre A est – · (de longueur 2) et le mot de code de la lettre B est – · · · (de longueur 4).
Le code Morse est donc un code à longueur variable. En effet les mots de code ont des longueurs qui peuvent différer les unes des autres. Le code Morse n'est donc pas un code à longueur fixe.
Contrairement aux codes à longueur fixe, qui utilisent toujours le même nombre de symboles pour représenter une valeur, les codes à longueur variable permettent de varier la longueur des mots de code en fonction de la valeur à représenter.
Les codes à longueur variable sont particulièrement utiles lorsque les valeurs à représenter varient en fréquence. En effet, il est intéressant de pouvoir utiliser un mot de code plus court pour les valeurs les plus fréquemment utilisées. Ainsi les messages encodés seront généralement plus courts. C'est le cas par exemple pour le code Morse, qui utilise des mots de code plus courts pour les lettres les plus fréquemment utilisées en anglais.
Codes préfixes
On appelle un code préfixe si aucun mot de code n'est le préfixe d'un autre mot de code.
De manière triviale, un code à longueur fixe est un code préfixe. En effet, si tous les mots de code ont la même longueur, aucun mot de code ne peut être le préfixe d'un autre mot de code.
Il existe cependant des codes à longueur variable qui sont des codes préfixes, comme nous le verrons plus bas au travers d'un exemple.
Les codes préfixes ont la propriété de ne pas nécessiter de délimiteur entre les mots de code lorsqu'on encode une séquence. Même sans délimiteur, on peut toujours déterminer clairement les mots de code dans une séquences de mots de code concaténés. Pour cela, il suffit de lire la séquence de mots de code symbole par symbole, de gauche à droite, et de marquer la fin de chaque mot de code dès qu'un mot de code est reconnu.
♣︎ Exemple
Considérons le code suivant, qui représente les lettres A, B, C:
| Lettre | Mot de code |
|---|---|
| A | 0 |
| B | 10 |
| C | 11 |
Ce code est un code préfixe. En effet, aucun mot de code n'est le préfixe d'un autre mot de code. De plus, c'est un code à longueur variable car les mots de code ont des longueurs différentes.
Dans ce code, on peut représenter la séquence de lettres
ABBA par le mot de code
0100110 sans devoir utiliser de délimiteur.
Cette suite de symboles peut être décodée simplement en la lisant
de gauche à droite.
On commence par lire le premier symbole,
qui est un 0. On reconnaît alors le mot de code
0 qui représente la lettre A.
On lit ensuite le symbole suivant, qui est un 1.
Comme le mot de code 1 n'est pas reconnu,
on lit le symbole suivant, qui est un 0.
On reconnaît alors le mot de code 10 qui représente
la lettre B. Et ainsi de suite, jusqu'à ce que
la séquence de symboles soit entièrement lue.
♣︎ Exemple
Comme discuté plus haut, le code Morse n'est pas un code préfixe. En effet, le mot de code de la lettre A est – · et le mot de code de la lettre B est – · · ·. Le mot de code de la lettre A est donc le préfixe du mot de code de la lettre B.
♣︎ Exemple
Les codes sont aussi présent dans la nature. Par exemple, le code génétique est un exemple de code. Les symboles utilisés sont les quatre bases A, C, G, T ou A, C, G, U selon que l'on considère l'ADN ou l'ARN.
Le code des codons de l'ARNm est un code préfixe, et même un code à longueur fixe. En effet, chaque codon est composé de trois bases, et il y a exactement 64 codons différents.
Nous verrons par la suite d'autres codes préfixes, tel que le code UTF-8. Nous aurons même l'occasion de créer nous-même des codes préfixes grâce à la méthode du codage de Huffman pour compresser des données.
Codes binaires
Un code est dit binaire si chaque mot de code qui le compose est formé à partir de deux symboles différents. Le code Morse est un exemple de code binaire. En effet, chaque mot de code est composé d'une séquence de points et de tirets. Les deux symboles utilisés par le code sont donc le point (·) et le tiret (–).
Dans la suite de ce chapitre, nous allons nous intéresser plus particulièrement aux codes binaires et nos symboles seront les deux bits 0 et 1.
L'octet
Dans le cadre des codes binaires (et de la représentation de l'information en général), nous parlerons souvent d'octets. Un octet est simplement une séquence de 8 bits.
✎ Auto-évaluation
On appelle les éléments d'un code ses . Chacun de ces éléments est une suite de .
✎ Auto-évaluation
Un code est dit si chaque mot de code est formé à partir de deux symboles différents.
✎ Auto-évaluation
Le code Morse et l'alphabet phonétique de l'OTAN sont des codes .
Dans la suite de ce chapitre, nous allons tout d'abord revisiter la notation binaire des nombres entiers sous l'angle de la représentation de l'information et des codes. Ensuite, nous allons nous intéresser à la représentation de différents types de données telles que le texte et les images.
! À maîtriser
Avant de poursuivre, assurez-vous de pouvoir :
- Expliquer ce qu'est un code.
- Expliquer ce qu'est un mot de code.
- Expliquer ce qu'est un code à longueur fixe.
- Expliquer ce qu'est un code à longueur variable.
- Expliquer ce qu'est un code préfixe et leur intérêt.
- Expliquer ce qu'est un code binaire.