Codes

Les systèmes de traitement de l'information ont toujours utilisé des techniques de codage, bien avant l'informatique : les différents systèmes d'écriture, le Braille, le Morse, la sténo. Avec la généralisation de la numérisation de l'information sous toutes ses formes, il existe maintenant une grande variété de codes, adaptés à ses divers supports de transmission et de stockage (cables coaxiaux, ondes hertziennes, disques magnétiques, CD-ROM, Mini-Disc, etc). Les codes sont conçus, outre la simple représentation de l'information, pour satisfaire à certaines exigences sur l'information codée :

• réduire sa taille, c'est la compression de données ;
• la rendre incompréhensible par des tiers, par chiffrement, c'est la cryptographie ;
• permettre de reconstituer l'information initiale, même si elle a été altérée par un bruit, c'est la correction d'erreurs.

Le schéma général est indiqué par la figure 2.1.

 
 

Les codes font intervenir plusieurs notions, que nous définissons ici brièvement. Un langage est un ensemble de mots, un mot est une suite finie de symboles, un symbole est un élément d'un alphabet, et un alphabet est un ensemble quelconque, de préférence fini. Quand on s'intéresse à des textes, on travaille avec un alphabet formé d'un jeu de caractères : par exemple l'alphabet formé des 26 lettres de l'alphabet latin, en minuscules et en majuscules, des 10 chiffres, des signes de ponctuation et de quelques symboles usuels (<, &, @, etc) que l'on trouve sur un clavier d'ordinateur anglais (un clavier français devrait y ajouter les lettres accentuées). Quand on s'intéresse à ce que contient la mémoire d'un ordinateur, c'est l'alphabet binaire, formé des deux symboles 0 et 1 qui est à considérer. Le traitement des langages a maintenant des applications très au-delà des besoins de l'informatique. Par exemple, l'analyse du génome humain se fait à l'aide des mêmes techniques et requiert des algorithmes élaborés, vu la taille des données en jeu.

  Soit A un ensemble dont les éléments seront appelés des symboles ; une suite finie $(a_1, \ldots, a_m)$ de symboles est appelée un mot sur l'alphabet A ; un tel mot est aussi noté $a_1\ldots a_m$, et l'entier m est sa longueur. L'ensemble de tous les mots sur l'alphabet A est noté $A^\star$. Le produit (de concaténation ) des mots $u=a_1\ldots a_m$ et $v=b_1\ldots b_n$ est le mot $uv = a_1\ldots a_m b_1\ldots b_n$, de longueur m+n. C'est une opération associative, pour laquelle le mot vide $\varepsilon$, de longueur nulle, est élément neutre. Un langage sur un alphabet A est un sous-ensemble de $A^\star$.

Un code est un langage C sur un certain alphabet A, muni d'un codage, qui est une application d'un certain ensemble S vers C et d'un décodage qui réalise l'opération inverse. Souvent, l'ensemble codé S est lui-même l'alphabet d'un langage, dit alphabet source et le codage s'étend naturellement en un codage de $S^\star$. Les codes les plus simples sont de longueur constante. Le plus connu est le code ASCII  , qui contient tous les mots de longueur 7 sur l'alphabet binaire, autrement dit, les 128 (= 2⁷) mots de 7 bits, et permet ainsi de représenter les caractères usuels anglais. Par exemple, le caractère A est codé par le mot binaire 1000001, écrit plus commodément 0x41 en notation hexadécimale (le préfixe 0x signale un nombre hexadécimal, c'est-à-dire en base 16). Le codage d'un mot de l'alphabet source se fait à l'aide d'une table, structure de données associant à chaque symbole de l'alphabet source son code :

Symbole	Code
A	1000001
B	1000010
C	1000011
...	...

    Il existe des codes ASCII étendus, à 8 bits (un octet), qui représentent aussi les lettres accentuées, par exemple le code ISO8859-1, appelé aussi latin-1, adapté à la plupart des langues de l'Europe de l'ouest et du nord ; le caractère À est représenté dans ce code par le mot binaire 11000000, ou 0xC0. Un tel code ne peut représenter que 256 (= 2⁸) caractères, ce qui est insuffisant. Par souci d'internationalisation, les caractères de Java (comme de la plupart des langages conçus pour l'Internet : XML, HTML4, ECMAScript, WML, etc.) utilisent le code Unicode, sur 16 bits. Celui-ci permet de représenter au plus 65 536 caractères, ce qui suffit pour un grand nombre de langues (mais pas vraiment pour toutes) ; par exemple, le nouveau symbole de l'euro a récemment reçu le code 0x20AC (en binaire, 00100000 10101100). Notons que toutes les valeurs des types primitifs de Java sont également représentées à l'aide de codes de longueur constante sur l'alphabet $\{0,1\}$ : des mots de 32 bits pour le type int, de 64 bits pour double, etc.