Nom de code : binaire

L’homme est un être vivant qui capte, qui stocke, qui traite, qui émet de l’information (images, sons, odeurs…). Nos sens nous permettent de les capter, notre cerveau de les stocker et de les traiter. Ainsi, nous sommes capables d’entendre une chanson, de la mémoriser, de la comparer avec d’autres, puis, si nous en faisons notre préférée du moment, de la rechanter de nombreuses fois.

Si l’on veut utiliser un ordinateur pour capter, pour traiter, pour stocker, pour émettre de l’information, il est d’abord nécessaire de la mettre sous une forme que la machine peut, non pas comprendre, mais manipuler : c’est la phase de codage, préalable et nécessaire à tout traitement informatique.

Nous sommes familiers de ces opérations de codage : quand nous écrivons ou lisons, nous utilisons un des nombreux codages basés sur des caractères (des hiéroglyphes égyptiens aux pictogrammes chinois). Quand nous comptons, nous utilisons un codage basé sur des nombres (avec, là aussi, des représentations multiples à travers les âges).

La base du codage

Un ordinateur utilise l’énergie électrique pour fonctionner. Plus précisément, on distingue deux états, haut et bas, associés à deux potentiels électriques, 0 et 12 Volts. D’un point de vue logique (au sens mathématique du terme), on considère que ces deux états correspondent à deux valeurs, à deux bits : 0 (absence de courant) et 1 (présence de courant). On manipule donc des valeurs et des opérations dites « binaires » régies par des règles formelles appelées « algèbre de Boole ». Remarquons au passage qu’un codage n’est pas seulement une représentation, mais aussi une interprétation. Prenons un exemple : en base deux, c’est-à-dire en numération binaire, le nombre 13 se décompose en 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ et s’écrit donc 1101. Si nous souhaitons maintenant coder des entiers négatifs, une façon simple est de réserver la première valeur binaire pour stocker le signe : 0 pour + et 1 pour -. Si nous voulons coder – 9, nous l’écrirons donc 1101. On voit bien qu’une même configuration binaire peut être interprétée de plusieurs façons.

Des chiffres et des lettres

Considérons maintenant un premier type d’information basique. Dès l’invention de l’informatique, les ordinateurs ont pu manipuler des textes composés de caractères, que ce soit pour la saisie des commandes sur un clavier ou pour l’impression des résultats sur le papier. Il a donc fallu adopter une convention commune qui soit utilisée par tous les ordinateurs. Ainsi, est né en 1961 le code ASCII (American Standard Code for Information Interchange) qui associe une valeur numérique à chaque caractère de l’alphabet : 65 pour A, 66 pour B… Mis au point pour traiter la langue anglaise, il fut ensuite enrichi pour coder aussi des caractères accentués.

Ce codage est très simple parce qu’il met en relation un ensemble fini de caractères avec un ensemble fini de valeurs, on parle alors d’« ensemble discret ». En revanche, si nous voulons traiter un type d’information plus complexe, par exemple une information de nature continue, comme le son, il est nécessaire d’abord de l’échantillonner, c’est-à-dire de lui associer un nombre fini de valeurs la représentant. Symétriquement, on sait ensuite reconstruire l’information originale à partir de ces échantillons. Publié en 1993, le codage MP3 est bâti sur ce principe. Il fait partie des « codecs » (mot construit à partir de « compression-décompression ») qui sont les procédés servant à compresser et à décompresser de l’information. Au moment de l’encodage en MP3, on ne conserve du signal musical qu’un ensemble fini de valeurs, des échantillons, que l’on stocke sur nos disques durs ou nos clés USB. Puis, lors de la décompression, au moment de l’écoute, le logiciel reconstruit la musique à partir de ces échantillons sans que l’oreille humaine ne perçoive une quelconque perte de qualité.

On sait étendre ce principe à des données encore plus complexes comme des images. L’échantillonnage est alors réalisé sur plusieurs dimensions spatiales.

Le pigment informatique

Prenons l’exemple des jeux vidéo qui, quelle que soit leur nature, sont tous basés sur des images affichées sur un écran. Que cet écran soit d’ordinateur ou bien de télévision, qu’il soit cathodique ou plat, sa surface est composée d’un ensemble de points élémentaires appelés « pixels » (contraction de picture element en anglais). Ces pixels sont organisés de façon très régulière en lignes et colonnes à la façon d’un tableau.

Photographie en deux résolutions différentes. © DocSciences / P. Raynaud
À droite, l’image est crénelée, sa « résolution » est insuffisante. Pour atténuer cet effet, on utilise des méthodes dites de « filtrage » (à gauche) qui s’inspirent des principes de la perception visuelle humaine.

Dans le cas le plus simple, celui d’une image monochrome (pixels uniquement noirs ou blancs), on utilise un codage basique où le blanc est représenté par la valeur 0 et le noir par 1. Pour une image en couleurs, il suffit de définir une fonction associant une valeur unique à une couleur donnée (8 pour le bleu nuit, 45 pour le vert clair…). En fait, pour des raisons principalement technologiques, les couleurs sont codées à partir de 3 composantes de base : le rouge, le vert et le bleu (RVB). Ainsi, le rouge s’exprimera (1, 0, 0), le jaune (0, 1, 1)… Au final, une image étant constituée d’un tableau de pixels et un pixel étant associé à une couleur, on en déduit facilement qu’une image est une matrice de valeurs numériques (les anglophones l’appellent bit-map). On parle alors d’image numérique et surtout pas d’image virtuelle puisque son support lui est bien réel.

Trucs et astuces pour la mémoire

Chaque ordinateur dispose d’une capacité de mémoire finie. On dit qu’un fichier a un poids en octets, c’est-à-dire qu’il occupe une « place » dans cette mémoire.

Prenons un exemple concret : on utilise aujourd’hui des écrans possédant une définition spatiale WSXGA (norme d’affichage Wide Super Extended Graphics Array). Ils se composent de 1 050 lignes et de 1 680 colonnes, on dénombre alors 1 050 × 1 680 pixels, soit 1 764 000 pixels.

Si l’on veut avoir le choix parmi 16 millions de coloris, il faut coder la valeur de la couleur sur 3 octets. En effet, on peut ainsi traiter 2²⁴ (2⁸ × 2⁸ × 2⁸), soit 16 777 215 valeurs différentes. Au final, pour stocker une image WSXGA avec un choix possible de 16 millions de couleurs, il faut disposer d’une mémoire de 1 764 000 × 3 = 5 292 000 octets, c’est-à-dire environ 5 mégaoctets.

Une illustration en dessin vectoriel.
© INRIA – CNRS / ARTIS
Cette image est un « dessin vectoriel » : des dessinateurs ont défini des zones le long de quelques courbes et c’est le logiciel qui calcule les dégradés en diffusant les couleurs et les flous dans ces zones.

Il y a encore peu de temps, le prix de la mémoire limitait les espaces de stockage offerts dans les ordinateurs. Il était alors facile de saturer un disque dur lorsque sa capacité totale s’exprimait en quelques dizaines de mégaoctets. On s’est donc très tôt intéressé à des méthodes de compression permettant de réduire la mémoire nécessaire pour stocker, par exemple, une image numérique.

Aujourd’hui, la diminution du prix de la mémoire a conduit à des tailles de disques significativement plus importantes. Cependant, une seconde motivation a relancé l’intérêt pour les méthodes de compression d’images : leur transfert sur les réseaux. Qui d’entre nous n’a pas pesté contre la durée du chargement d’une page d’un serveur web ? Souvent, cette lenteur est due à la taille des images contenues dans cette page. En effet, l’augmentation régulière des vitesses de transfert dans les réseaux est constamment absorbée par l’augmentation tout aussi régulière du nombre d’images et de leurs définitions (spatiale et colorimétrique).

On distingue deux grandes familles de compression d’images : avec ou sans perte. Dans le premier cas, on accepte de dégrader légèrement la qualité de l’image reconstruite (après avoir été compressée) pour diminuer la taille de la mémoire nécessaire à son stockage. En fait, on exploite les capacités de la perception visuelle : en moyenne, un œil humain ne peut distinguer qu’un nombre limité de nuances de couleurs, quelques centaines tout au plus, en tout cas beaucoup moins que les 16 millions autorisées par la technologie. Nous sommes donc incapables de distinguer les différences entre une image originale et la même image dont les couleurs sont codées sur 2 octets au lieu de 3. On obtient ainsi très facilement un gain de stockage de l’ordre de 30 %. Dans le second cas, on se contente de diminuer cette taille tout en préservant l’intégralité des informations contenues dans l’image initiale. Par exemple, en repérant dans l’image des suites de n pixels voisins possédant la même couleur C ; on remplace alors chaque suite de n fois la valeur associée à C, donc stockée sur n x 3 octets, par un seul couple (n, C) qui sera stocké sur 1 + 3 octets. On remarque que le taux de compression de cette méthode est variable : par exemple, si l’on veut stocker sur un cédérom l’image d’une salle d’un château où se déroule le scénario d’un jeu, la taille de l’image codée ne sera pas la même si la pièce est éclairée ou plongée dans l’obscurité totale.

Il faut souligner le rôle prépondérant joué par la télévision : si nous pouvons regarder autant de chaînes sur notre téléviseur depuis un satellite, sur notre ordinateur et maintenant sur notre téléphone portable, c’est bien grâce aux méthodes de compression de plus en plus performantes qui sont mises au point par les chercheurs pour répondre aux besoins du monde des médias. Il existe de très nombreuses méthodes de compression pour les fichiers (LZW, ZIP), les images (JPEG, TIFF), les vidéos (MPEG)… Il faut noter que quasiment toutes ces méthodes sont basées sur des théories mathématiques : transformée de Fourier, ondelettes, fractales, transformée en cosinus discrète…

Pour éviter tout malentendu

Grâce à l’invention des réseaux, il est possible de véhiculer des informations sous leur forme codée : textes, sons, images… Ainsi pour le caractère A, on transfèrera la valeur 65, elle-même codée en binaire par 1000001. Malheureusement, les réseaux informatiques ne sont pas fiables à 100 % et il est nécessaire de mettre en œuvre des mécanismes de consolidation pour s’assurer de transmissions fidèles. Le premier d’entre eux est baptisé « code détecteur d’erreur ».

Par exemple, on émet l’hypothèse que tous les octets transmis doivent comporter un nombre pair de bits. Pour cela, on utilise sept bits pour le codage de l’information et le huitième pour vérifier l’hypothèse. Si nous reprenons notre caractère A, nous transmettrons donc l’octet 01000001, le premier zéro rétablit la parité des zéros et vient ainsi confirmer la validité de l’information. Si durant la transmission, un problème survient, alors une valeur binaire est modifiée ; il suffit au moment de la réception de vérifier la parité de l’octet reçu pour détecter cette erreur. Naturellement, ce premier principe simple ne fonctionne que s’il y a un nombre impair d’erreurs de transmission. Pour diminuer cette contrainte, on peut appliquer le même principe sur un groupe d’octets en considérant la parité sur tous les énièmes bits.

Voilà comment, pour l’ordinateur, nos courriels, nos photos, nos chansons favorites… ne sont que des valeurs numériques. Rappelons encore une fois qu’un codage n’est rien sans une interprétation associée qui permet de donner du sens aux traitements réalisés par les logiciels sur ces listes de nombres. Maintenant que nous savons comment sont codées les informations, reste à comprendre comment elles sont traitées : c’est l’objet du prochain article consacré aux algorithmes.

Cet article est paru dans la revue DocSciences n°5 Les clés de la révolution numérique, éditée par le CRDP de l’Académie de Versailles en partenariat avec l’Inria.