Bits et bases, entiers signés et complément à deux, virgule flottante IEEE 754, texte et Unicode, images et sons échantillonnés.
Objectifs du chapitre
À la fin de ce chapitre, vous serez capable de:
définir l'information comme la réduction d'un ensemble de possibilités, justifier le bit comme unité et expliquer pourquoi les machines comptent en base deux plutôt qu'en base dix;
convertir un nombre entre les bases 2, 8, 10 et 16, dans les deux sens, partie entière et partie fractionnaire comprises, et dire pourquoi l'hexadécimal est l'écriture abrégée du binaire;
représenter un entier signé en complément à deux, expliquer pourquoi ce codage transforme la soustraction en addition, et prévoir ce qui se passe en cas de débordement;
décoder un nombre en virgule flottante IEEE 754 champ par champ, expliquer pourquoi 0,1 n'est pas représentable, et reconnaître l'absorption et l'élimination catastrophique dans un calcul;
calculer la taille d'un texte, d'une image non compressée ou d'une seconde de son échantillonné, et distinguer sans hésiter les préfixes décimaux (ko, Mo, Go) des préfixes binaires (Kio, Mio, Gio);
situer les dix chapitres du cours autour de la question qui les unit: combien de bits, combien d'opérations, combien de temps?
Ce que «information» veut dire ici
Une information est un choix
Le mot «information» a, dans la langue courante, un sens qui résiste à la mesure: une nouvelle est intéressante, un rapport est utile, une photographie est belle. L'informatique, comme la théorie des communications dont elle est issue, retient du mot un sens beaucoup plus étroit, et c'est précisément cette étroitesse qui le rend quantifiable. Une information, ici, est la désignation d'une possibilité parmi plusieurs. Rien de plus. Ce que l'on mesure n'est pas ce que le message signifie, mais combien de possibilités il élimine.
Imaginez le jeu des vingt questions. Votre interlocuteur pense à un objet; vous ne pouvez poser que des questions auxquelles il répond par oui ou par non. Chaque réponse coupe en deux l'ensemble des objets encore possibles: après une question il en reste la moitié, après deux le quart, après k questions la fraction 2−k. Vingt questions suffisent donc à isoler un objet parmi , soit plus d'un million. Ce n'est pas une astuce: c'est le contenu quantitatif de la notion d'information, et nous venons d'en fixer l'unité.
220=1048576
Le symbole du bit est b, celui de l'octet — groupe de huit bits — est o. Nous écrirons toujours log2 en toutes lettres, jamais lg, et nous réserverons ln au logarithme naturel.
La formule (1.1) et son inverse suffisent déjà à répondre à des questions concrètes. Combien de bits pour désigner une lettre de l'alphabet latin? log226≈4,70, donc 5 bits (25=32≥26). Combien pour désigner une carte d'un jeu de 52? log252≈5,70, donc 6 bits. Combien pour un habitant de la Suisse, dont la population dépasse huit millions? log2(8⋅106)≈22,9, donc 23 bits — moins de trois octets pour désigner sans ambiguïté n'importe qui dans le pays. Ce genre de calcul, fait en dix secondes, est l'un des réflexes que ce cours veut installer.
Pourquoi deux, et pas dix
Nous comptons en base dix parce que nous avons dix doigts; aucune loi de la nature n'y oblige. Les machines, elles, comptent en base deux, et il vaut la peine de comprendre que ce choix est physique avant d'être mathématique.
Un circuit électronique ne manipule pas des chiffres, il manipule des tensions, toujours bruitées. Pour distinguer dix niveaux entre 0 et 3,3 V, il faudrait décider de quel côté d'une frontière tombe une tension mesurée, avec des frontières espacées d'environ 0,33 V: la moindre perturbation — un couplage capacitif avec la piste voisine, une variation de température, la commutation d'un circuit à côté — fait basculer la lecture. Avec deux niveaux seulement, la frontière est au milieu et la marge de bruit vaut la moitié de la tension d'alimentation. Un transistor utilisé en interrupteur, bloqué ou saturé, réalise naturellement ces deux états, et il les régénère: un étage logique reçoit un signal dégradé et ressort un signal propre. C'est cette régénération, impossible avec un signal continu, qui permet d'enchaîner des milliards d'opérations sans que l'erreur s'accumule.
À cette raison de fiabilité s'en ajoute une de raisonnement: la logique booléenne — vrai/faux, ET, OU, NON — se transpose terme à terme dans l'arithmétique binaire, ce qui permet de construire une addition à partir de portes logiques. Vous verrez cette construction en systèmes logiques; nous nous contenterons ici de son résultat.
Le choix n'est pourtant pas une fatalité, et il est honnête de le dire. Des machines ternaires ont réellement existé: la Setun, construite à l'Université de Moscou à la fin des années 1950, utilisait trois états. Et les mémoires flash actuelles stockent plusieurs bits par cellule en distinguant plusieurs niveaux de charge — jusqu'à seize niveaux, soit quatre bits, dans les cellules dites QLC. Mais ces mémoires multi-niveaux sont précisément celles qui s'usent le plus vite et qui exigent le plus de correction d'erreurs — ce qui illustre exactement l'argument de la marge de bruit, et nous ramènera au chapitre 8.
Question 1.1
Un système d'immatriculation doit numéroter sans ambiguïté 5 000 vélos. Combien de bits faut-il au minimum?
Les bases de numération
La numération de position
Notre écriture des nombres est positionnelle: dans 2025, le chiffre 2 de gauche ne vaut pas la même chose que celui du milieu, parce que sa position lui attribue un poids. C'est une invention, et une invention tardive en Europe; la généraliser à une base quelconque ne demande que de remplacer dix par b.
Les bases qui nous occupent sont la base 2 (chiffres 0 et 1), la base 8 ou octal (chiffres 0 à 7) et la base 16 ou hexadécimal, dont les seize chiffres sont 0,1,…,9 puis A,B,C,D,E,F pour 10,11,…,15. Nous écrirons systématiquement la base en indice: (1011)2, (234)8, (9C)16, (2025)10.
Le binaire
En base deux, la relation (1.2) devient une somme de puissances de deux, chacune présente ou absente. Un groupe de huit bits — un octet — code donc les entiers de 0 à 28−1=255.
Figure 1.1. Un octet: huit cases, chacune portant une puissance de deux, du bit de poids fort b₇ (poids 128, à gauche) au bit de poids faible b₀ (poids 1, à droite). Les cases teintées sont celles qui valent 1; la somme de leurs poids donne la valeur codée, ici 156. Le même octet s'écrit 234 en octal et 9C en hexadécimal.
La lecture d'un nombre binaire est donc immédiate: on additionne les poids des cases à 1. La figure 1.1 donne 128+16+8+4=156. L'écriture, elle, demande une petite mécanique.
En Python, les trois écritures sont accessibles directement, et les préfixes 0b, 0o, 0x rappellent la base employée:
Un octet quelconque s'écrit avec huit chiffres binaires, mais avec exactement deux chiffres hexadécimaux, et la correspondance se fait par blocs de quatre bits sans aucun calcul. C'est toute la raison d'être de l'hexadécimal: ce n'est pas une base «plus pratique» pour calculer, c'est une abréviation du binaire. Un ingénieur qui lit C3 A9 sait immédiatement qu'il s'agit de 11000011 10101001, et il le sait chiffre par chiffre, alors que la lecture décimale (195 169) lui cache la structure des bits. C'est pourquoi on écrit en hexadécimal les adresses mémoire, les octets d'un fichier, les couleurs d'une page web (#F46622), les empreintes des fonctions de hachage du chapitre 9 et les adresses matérielles des cartes réseau du chapitre 10.
L'octal, qui découpe par trois bits, sert aujourd'hui surtout aux permissions des fichiers sous Unix (chmod 755), où trois groupes de trois bits — lecture, écriture, exécution — se lisent en un coup d'œil.
Les fractions
La méthode des divisions successives a une contrepartie pour la partie fractionnaire: on multiplie par la base et l'on récolte les parties entières.
Retenez cette phrase, car la moitié de ce chapitre en découle: le facteur 5 du nombre dix est la source de presque toutes les surprises numériques d'un ordinateur.
Question 1.2
Remettez dans l'ordre les étapes de la conversion d'un entier décimal en binaire par divisions successives.
Glissez les éléments pour les mettre dans le bon ordre
1.
Recommencer tant que le quotient n'est pas nul
2.
Lire la suite des restes du dernier obtenu vers le premier
3.
Diviser le nombre courant par 2 et noter le reste, qui vaut 0 ou 1
4.
Remplacer le nombre courant par le quotient entier obtenu
Question 1.3
Quelle est la valeur décimale de (2F3)16?
Les entiers
Entiers non signés
Un mot de n bits interprété comme un entier non signé (unsigned) code les valeurs de 0 à 2n−1. Les tailles usuelles donnent les plages suivantes, qu'il faut connaître comme des repères:
taille
valeurs
valeur maximale
8 bits (1 octet)
256
255
16 bits
65536
65535
32 bits
4294967296
≈4,3⋅109
64 bits
18446744073709551616
≈1,8⋅1019
Ces plages sont fixes, et c'est leur intérêt: un entier de 32 bits occupe toujours quatre octets, quelle que soit sa valeur, ce qui permet de calculer l'adresse du millième élément d'un tableau par une multiplication. C'est aussi leur danger, sur lequel nous reviendrons.
Le complément à deux
Il reste à coder les nombres négatifs. L'idée naïve — réserver un bit pour le signe et coder la valeur absolue sur les autres — fonctionne, mais elle a deux défauts: elle produit deux zéros (+0 et −0), et surtout elle oblige le processeur à traiter l'addition et la soustraction par des circuits différents, car il faut comparer les signes avant de décider s'il faut ajouter ou retrancher. Le complément à deux évite les deux écueils, et c'est le codage qu'utilisent aujourd'hui tous les processeurs.
Le point de départ est l'arithmétique modulo 2n. Un additionneur de n bits qui laisse tomber la retenue sortante ne calcule pas x+y mais x+ymod2n. Dans cet anneau, l'opposé de x existe: c'est 2n−x. On décide donc que le motif binaire 2n−xreprésente−x.
Sur huit bits, la plage est donc [−128,127]; sur seize bits, [−32768,32767]; sur trente-deux bits, [−2147483648,2147483647]. La plage est asymétrique: il y a un négatif de plus que de positifs, parce que le zéro occupe une place du côté positif. Il en résulte que −(−128) n'est pas représentable sur huit bits — une bizarrerie bien réelle, qui fait que la valeur absolue d'un entier peut être négative.
Démonstration. Pour chaque position i, ai+ai=1 puisque l'un des deux bits vaut 0 et l'autre 1. En sommant les poids, x+x=∑i=0n−12i=2n−1, ce qui est la première égalité; en ajoutant 1 des deux côtés, x+1+x=2n≡0, donc x+1 est bien l'opposé de x modulo 2n. Pour la seconde affirmation, soit u et v deux entiers représentables et u~,v~ leurs motifs, c'est-à-dire u~≡u et v~≡v modulo 2n d'après (1.3). L'additionneur produit le motif u~+v~mod2n, qui est congru à u+v; si u+v est représentable, c'est donc exactement son motif. □
Le procédé pratique tient en une ligne: pour coder −x, on inverse tous les bits de x et l'on ajoute 1.
Figure 1.2. La roue du complément à deux sur 4 bits. Les seize motifs 0000 à 1111 sont placés en cercle; la moitié droite porte les valeurs positives ou nulles, la moitié gauche (en couleur) les valeurs négatives. Additionner revient à avancer d'autant de crans dans le sens des aiguilles d'une montre: partant de 0101 (+5), quatre crans mènent à 1001, qui vaut −7 et non +9. En haut, le passage de 1111 à 0000 est inoffensif (−1 + 1 = 0); en bas, le passage de 0111 à 1000 est le débordement.
La figure 1.2 rend visible l'essentiel: les entiers d'un ordinateur ne forment pas une droite, ils forment un cercle. On peut toujours avancer; ce qui n'existe pas, c'est la garantie d'arriver où l'on croit.
Le débordement, et une conséquence réelle
Sur huit bits, 100+100=200 n'est pas représentable: le motif obtenu est (11001000)2, dont la valeur signée est 200−256=−56. Additionner deux nombres positifs a donné un nombre négatif, et aucune alarme ne s'est déclenchée. De même 127+1=−128, et −128−1=+127.
Cette mécanique a détruit une fusée. Le 4 juin 1996, le vol inaugural d'Ariane 5 (vol 501) s'est achevé par l'autodestruction du lanceur environ quarante secondes après le décollage, emportant les quatre satellites de la mission scientifique Cluster. Le rapport de la commission d'enquête indépendante présidée par Jacques-Louis Lions (ESA/CNES, 1996) a établi la chaîne causale: dans le système de référence inertielle, une valeur de vitesse horizontale, calculée en virgule flottante sur 64 bits, était convertie en entier signé de 16 bits. Le logiciel avait été repris d'Ariane 4, dont la trajectoire ne produisait jamais de valeur supérieure à 32767; celle d'Ariane 5, plus rapide, l'a dépassée. La conversion a levé une erreur d'opérande qui n'était pas protégée — le calcul en question ne servait d'ailleurs plus à rien après le décollage —, les deux calculateurs redondants se sont arrêtés pour la même raison au même instant, et les données de diagnostic qu'ils ont alors émises ont été interprétées par le pilote automatique comme des données de vol.
Trois leçons, toutes transposables:
une plage de représentation est une hypothèse sur le monde, et cette hypothèse doit être vérifiée ou documentée;
la redondance ne protège pas d'une erreur déterministe: deux exemplaires du même logiciel échouent au même instant sur la même donnée;
réutiliser un composant, c'est aussi réutiliser ses hypothèses.
Les nombres à virgule: la norme IEEE 754
L'idée de la virgule flottante
Les entiers ne suffisent pas: il faut représenter 6,674⋅10−11 comme 2,998⋅108. Une virgule fixe — disons trois chiffres après la virgule — gaspillerait tout: elle ne pourrait coder ni l'un ni l'autre. La solution est la même que la notation scientifique: on sépare une mantisse (les chiffres significatifs) et un exposant (l'ordre de grandeur), et l'on laisse la virgule flotter.
En binaire, cela s'écrit x=(−1)s⋅m⋅2e, avec 1≤m<2. Comme la partie entière de m vaut alors toujours 1, on ne la stocke pas: c'est le bit implicite, un bit gagné gratuitement.
Décoder un double, champ par champ
Figure 1.3. Anatomie d'un double IEEE 754: 1 bit de signe, 11 bits d'exposant et 52 bits de mantisse, dessinés à l'échelle. Le nombre décodé est celui qu'un programme obtient en écrivant 0,1. La mantisse y répète le motif 1001, qui est la période du développement binaire de 1/10, et se termine par 1010: les quatre derniers bits ne sont pas 1001 mais son arrondi supérieur. La valeur exacte du double obtenu est écrite en bas, et elle n'est pas 0,1.
Pourquoi 0,1 n'est pas représentable, et ce que cela coûte
L'exemple 1.2 a donné la raison de fond: 1/10 n'est pas dyadique, donc son écriture binaire est infinie, donc aucune mantisse finie ne peut la contenir. Ce n'est pas un défaut de la norme IEEE 754 ni un bogue de votre langage: c'est la même chose que l'impossibilité d'écrire 1/3 avec un nombre fini de décimales. Ce qui surprend, c'est seulement que les fractions «rondes» de notre base dix ne le soient pas en base deux.
La conséquence la plus célèbre s'observe en trois lignes dans n'importe quel interpréteur:
Détaillons. Le double le plus proche de 0,1 vaut 0,1000000000000000055511…, celui de 0,2 vaut 0,2000000000000000111022… (le double du précédent, exactement, puisque multiplier par deux ne change que l'exposant). Leur somme exacte est 0,3000000000000000166533453693773481…, qui n'est pas représentable; l'arrondi au plus proche donne 0,30000000000000004440892…, affiché 0.30000000000000004. Or le double le plus proche de 0,3 vaut 0,29999999999999998889777… Les deux nombres diffèrent d'un seul bit de mantisse — mais ils diffèrent, et le test d'égalité est faux.
Absorption
Les flottants ont un pas variable: l'écart entre deux doubles consécutifs vaut 2e−52, donc il grandit avec la grandeur des nombres. Près de 1, il vaut 2−52≈2,2⋅10−16; près de 1016, il vaut 2.
Élimination catastrophique
Question 1.4
Le plus petit entier positif qui ne soit pas représentable exactement en binary64 s'écrit 2k+1. Que vaut k?
À vous de manipuler
L'explorateur ci-dessous réunit les deux moitiés du chapitre. Les trois premiers résultats sont des changements de base: ils sont exacts, et le passage du décimal au binaire, à l'octal et à l'hexadécimal n'y perd rien. Le dernier ne l'est pas. Faites glisser le curseur du bas: l'erreur de représentation s'annule pour 0,25, 0,50, 0,75 et 1,00 — les seules valeurs de la liste dont le dénominateur est une puissance de deux — et elle ne s'annule nulle part ailleurs, 0,10 compris.
Explorateur 1.1 · Explorateur de conversion: bases et virgule flottante
Le curseur du haut fixe un entier sur un octet, celui du bas une fraction décimale. Les trois premiers résultats sont des changements de base, donc exacts. Le dernier ne l'est pas: il donne la valeur exacte du double qui stocke la fraction, et l'écart entre cette valeur et la fraction demandée. Cet écart est nul pour 0,25, 0,50, 0,75 et 1,00 — dont le dénominateur est une puissance de deux — et non nul partout ailleurs, 0,10 compris.
Entier n (sur 8 bits)156
Fraction décimale f0,10
n en base 2
(10011100)₂
n en base 8
(234)₈
n en base 16
(9C)₁₆
Développement binaire de f
0,0001100110011001…
Double effectivement stocké
0,10000000000000000555111512…
Erreur de représentation
+5,55·10⁻¹⁸
Le texte
ASCII, ou le monde en sept bits
Représenter un texte, c'est convenir d'une table de correspondance entre des caractères et des entiers. La table ASCII (American Standard Code for Information Interchange), normalisée en 1963, en fixe une sur sept bits, donc 27=128 positions: les chiffres, les lettres latines majuscules et minuscules, la ponctuation, l'espace, et 33 caractères de commande hérités du télétype (retour chariot, saut de ligne, sonnerie).
caractère
code décimal
binaire (7 bits)
hexadécimal
espace
32
0100000
20
0
48
0110000
30
A
65
1000001
41
a
97
1100001
61
La table n'est pas arbitraire: les chiffres se suivent à partir de 48, ce qui permet de convertir un chiffre en sa valeur par une soustraction; les majuscules et les minuscules sont décalées de 32=25 exactement, de sorte que changer la casse revient à basculer un seul bit. Ce genre d'élégance, invisible à l'usage, est ce qui fait la différence entre une table et une bonne table.
Le défaut d'ASCII est dans son nom: American. Sept bits ne laissent aucune place à é, ü, ç, ø, sans parler du grec, du cyrillique, de l'arabe ou du chinois. Le huitième bit d'un octet étant disponible, chaque région s'est fabriquée sa table des positions 128 à 255: ISO 8859-1 (dite latin-1) pour l'Europe occidentale, ISO 8859-5 pour le cyrillique, Windows-1252 pour une variante propriétaire, et ainsi de suite. Résultat: un même octet 233 désignait é ici et une lettre toute différente ailleurs, et un fichier ne portait pas l'indication de la table employée. Nous allons voir les dégâts.
Unicode et UTF-8: deux choses différentes
La sortie de crise a demandé de séparer deux questions qu'on avait confondues.
Unicode dit quel numéro porte un caractère; l'encodage dit comment écrire ce numéro en octets. Confondre les deux est l'erreur la plus courante du domaine, et elle rend incompréhensibles la moitié des messages d'erreur que vous rencontrerez.
Quand on se trompe d'encodage: le mojibake
Si un fichier ne dit pas dans quel encodage il est écrit, le programme qui le lit doit deviner. Quand il devine mal, on obtient du mojibake (文字化け, «caractères transformés» en japonais). Voici l'expérience, faite réellement:
texte = "Représentation de l'information"octets = texte.encode("utf-8") # encodage correct: 32 octetsprint(len(texte), "caractères,", len(octets), "octets")print(octets[:8].hex(" ").upper()) # les octets réelsprint(octets.decode("latin-1")) # relu avec le mauvais jeu de caractères
Deux remarques pour finir. D'abord, la faute inverse — lire du latin-1 comme de l'UTF-8 — ne produit pas de mojibake mais une erreur: les motifs d'UTF-8 sont contraints, et un octet isolé supérieur à 127 n'est pas un début de séquence valide. Cette asymétrie est une qualité d'UTF-8: il est auto-détectable avec une bonne probabilité. Ensuite, la longueur d'une chaîne cesse d'être une notion unique: «Représentation de l'information» fait 31 caractères, 32 octets, et un nombre de colonnes à l'écran qui dépend encore d'autre chose. Toute fonction length doit dire laquelle des trois elle compte.
Question 1.5
Un fichier écrit en UTF-8 est ouvert par un éditeur qui suppose du latin-1. Que voit-on?
Images et sons
Une image matricielle
Échantillonner et quantifier un son
Un son est une grandeur continue, la pression acoustique p(t). La numériser demande deux discrétisations distinctes, l'une en temps, l'autre en amplitude.
Le choix de fe n'est pas libre. Le théorème d'échantillonnage (Nyquist–Shannon, que nous admettons ici — sa démonstration relève de l'analyse de Fourier) affirme qu'un signal ne contenant aucune fréquence supérieure à fmax est entièrement déterminé par ses échantillons pris à la fréquence fe>2fmax. L'oreille humaine perçoit jusqu'à environ 20 kHz; le disque compact échantillonne à 44,1 kHz, ce qui laisse la marge nécessaire pour le filtre anti-repliement, puisque 44100/2=22050 Hz.
Question 1.6
Quelle est la taille, en mégaoctets décimaux (Mo), d'une minute de son stéréo échantillonné à 44,1 kHz sur 16 bits?
Les unités: ko ou Kio?
Il reste un point de vocabulaire, apparemment mineur, qui produit plus de confusion que tout le reste du chapitre réuni.
Les préfixes du Système international sont décimaux: kilo vaut 103, méga 106, giga 109, téra 1012. Mais les tailles de mémoire sont naturellement des puissances de deux, parce qu'un bus d'adresse de n fils désigne 2n cases. Or 210=1024 est proche de 103, et l'usage s'est installé d'appeler «kilo-octet» le groupe de 1024 octets. L'approximation était excellente pour le kilo (2,4 % d'écart); elle se dégrade à chaque étage.
Pourquoi votre disque de «500 Go» en affiche moins
C'est la conséquence directe et la plus visible de cette double convention, et elle mérite un paragraphe honnête, car l'explication courante — «le fabricant triche» — est fausse.
Le fabricant du disque emploie les préfixes du SI, comme la norme le lui demande: son disque de 500 Go contient 500⋅109=500000000000 octets, ni plus ni moins. Le système d'exploitation, lui, divise ce nombre par 230 et affiche encore, dans plusieurs cas, le symbole «Go»:
230500⋅109=1073741824500⋅109=465,66.
L'utilisateur lit donc «465,66 Go» sur une boîte marquée «500 Go» et conclut qu'on lui a pris 34,34 unités, soit 6,87 % de la capacité. Personne n'a rien pris: deux échelles différentes portent le même nom. La grandeur physique est identique dans les deux lectures — ce sont bien 5⋅1011 octets —, et l'affichage correct serait «465,66 Gio».
Deux précisions pour être complet. D'une part, l'écart grandit avec l'échelle: un disque de 2 To s'affiche 2⋅1012/240=1,82 Tio, soit 9,05% de moins que le nombre écrit sur la boîte. D'autre part, une partie réelle de la capacité est effectivement indisponible, pour une raison sans rapport: le système de fichiers réserve de la place pour ses propres structures (table d'allocation, journal, blocs de réserve). Cette part-là est bien consommée, mais elle est d'un tout autre ordre de grandeur que les 6,87 % de la confusion d'unités, et il faut se garder de mélanger les deux explications. La première est une question de notation; la seconde est une question de format.
Combien de bits, combien d'opérations, combien de temps?
Ce chapitre a répondu à la première des trois questions du cours, et seulement à la première: combien de bits faut-il pour représenter quelque chose? Un entier, une couleur, une lettre, une seconde de son — nous savons maintenant compter, et nous savons ce que coûte l'arrondi lorsque le monde continu doit entrer dans un nombre fini de cases.
La suite du cours déplie les deux autres questions.
Chapitres 2 à 5 — combien d'opérations, et est-ce seulement possible? Le chapitre 2 définit l'algorithme, sa terminaison et son coût, et introduit les notations O, Ω et Θ. Le chapitre 3 montre ce que la récursivité et le principe «diviser pour régner» font gagner. Le chapitre 4 donne les structures de données — piles, files, arbres, tables de hachage, graphes — et le prix de chaque opération sur chacune. Le chapitre 5 franchit la frontière: certains problèmes n'ont aucun algorithme, le problème de l'arrêt en tête, et d'autres n'en ont aucun de rapide connu, ce qui est la question P contre NP.
Chapitres 6 à 8 — combien de bits, au minimum? Le chapitre 6 mesure l'information d'une source par l'entropie de Shannon et établit la borne que nul code ne peut franchir. Le chapitre 7 construit les codes qui s'en approchent (Huffman, Lempel-Ziv) et explique pourquoi aucun algorithme ne peut comprimer tous les fichiers. Le chapitre 8 fait le chemin inverse: il ajoute des bits, en quantité calculée, pour survivre au bruit d'un canal.
Chapitres 9 et 10 — sûrement, et à distance. Le chapitre 9 montre comment deux personnes qui ne se sont jamais rencontrées peuvent partager un secret sur un canal public, et pourquoi la sécurité de RSA repose sur un coût de calcul et non sur une impossibilité. Le chapitre 10 décrit le réseau en couches et sépare deux grandeurs que l'on confond sans cesse: le débit et la latence — la seconde étant bornée par la vitesse de la lumière, que nul protocole ne négociera.
Une constante traverse ces dix chapitres, et vous venez d'en voir la première forme: tout se paie. Une représentation exacte se paie en bits; une réponse rapide se paie en mémoire; une transmission fiable se paie en redondance; un secret se paie en calcul. L'informatique n'est pas l'art de tout obtenir, c'est l'art de savoir ce que l'on paie.
Synthèse
L'information est un choix. Désigner une possibilité parmi N équiprobables coûte ⌈log2N⌉ bits; n bits distinguent 2n possibilités. La base deux s'impose pour une raison physique — la marge de bruit et la régénération du signal — avant toute raison mathématique.
Les bases 8 et 16 sont des abréviations du binaire, parce qu'un chiffre y vaut exactement trois ou quatre bits. Une fraction s'écrit exactement en binaire si et seulement si son dénominateur est une puissance de deux; le facteur 5 de notre base dix est la source de la quasi-totalité des surprises numériques.
Le complément à deux ferme la droite des entiers en cercle: le bit de poids fort porte le poids −2n−1, l'opposé s'obtient en inversant les bits et en ajoutant un, la soustraction devient une addition, et la plage [−2n−1,2n−1−1] est asymétrique. Le débordement ne déclenche aucune alarme — Ariane 501 en 1996 est le rappel le plus coûteux de ce fait.
IEEE 754 stocke (−1)s(1+M/252)2E−1023 sur 64 bits. Le double le plus proche de 0,1 vaut 0,1000000000000000055511151231257827… et 0.1 + 0.2 rend 0.30000000000000004: ce n'est pas un bogue mais un arrondi correct. Les deux pièges à reconnaître sont l'absorption (un petit terme disparaît devant un grand) et l'élimination catastrophique (une soustraction de nombres proches révèle les erreurs déjà commises). On ne teste jamais l'égalité de deux flottants.
Toute numérisation se chiffre. Une image de L×H pixels sur p bits pèse LHp/8 octets (6,22 Mo en 1920 × 1080 couleur vraie); une minute de son au format CD pèse 10,584 Mo. Et les préfixes décimaux (ko, Mo, Go) ne sont pas les préfixes binaires (Kio, Mio, Gio): l'écart de 7,4 % au niveau giga explique entièrement qu'un disque de 500 Go affiche 465,66 Gio.
Série d'exercices du chapitre 1Exercice 1 sur 5
Question 1.7
Combien de valeurs distinctes un mot de 12 bits peut-il représenter?
Problème guidé 1.1 · Une carte mémoire pour un appareil photographique
Un appareil photographique produit des images de 4000 × 3000 pixels en couleur vraie (24 bits par pixel). On étudie d'abord le format brut, sans aucune compression. La carte mémoire utilisée est annoncée à 32 Go par son fabricant, qui emploie les préfixes du Système international. On veut savoir combien de photographies elle contient et vérifier au passage la cohérence des unités.
1
Le poids d'une photographie
Chaque pixel occupe trois octets (un par canal rouge, vert et bleu), et il faut compter tous les pixels de la grille.
Question
Quelle est la taille d'une photographie non compressée, en mégaoctets décimaux (Mo)?
La même taille en préfixes binaires
Le contenu de la carte
Ce que le système affichera
Exercices
Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.
Exercice 1.1 · Conversions dans les deux sens
Écrire 2025 en base 2, en base 8 et en base 16.
Écrire (BE)16 en base 2, en base 8 et en base 10.
Convertir 0,8125 en base 2, et vérifier le résultat.
Donner la valeur décimale de (101101,101)2.
Sans calculer, dire combien de chiffres hexadécimaux comporte l'écriture d'un entier de 64 bits, et pourquoi.
Solution
1. Divisions successives par 2: les restes obtenus sont 1,0,0,1,0,1,1,1,1,1,1, lus à l'envers (11111101001)2. Vérification: 1024+512+256+128+64+32+8+1=2025.
Exercice 1.2 · Complément à deux et débordement
On travaille sur huit bits en complément à deux.
Écrire les motifs de +100, −100, −1 et −128.
Effectuer l'addition 100+100 et interpréter le résultat. Y a-t-il débordement? Justifier par la règle des signes.
Effectuer −128−1 et interpréter.
Montrer que la valeur absolue d'un entier de huit bits n'est pas toujours représentable.
Un compteur non signé de 16 bits est incrémenté chaque milliseconde. Au bout de combien de temps repasse-t-il par zéro?
Solution
1.+100=64+32+4=(01100100)2. Pour −100: inversion (10011011)2, plus un, — c'est l'octet de la figure 1.1, qui vaut en non signé et en complément à deux. Pour : inversion de donne , plus un, : tous les bits à un, ce qui est la signature du dans ce codage, quelle que soit la largeur du mot. Pour : le motif est , car par (1.3) ; c'est la seule valeur dont l'opposé n'est pas représentable.
Exercice 1.3 · Décoder et raisonner en virgule flottante
Un double a pour contenu hexadécimal 4019000000000000. Décoder son signe, son exposant et sa mantisse, et donner sa valeur.
Expliquer pourquoi 0,5 est représenté exactement alors que 0,1 ne l'est pas.
On calcule s=∑k=11071/k en virgule flottante. Vaut-il mieux sommer dans l'ordre croissant des k ou décroissant? Justifier.
Pourquoi le test if (x == 0.3) après x = 0.1 + 0.2 est-il faux, et par quoi le remplacer?
Solution
1. On écrit les 64 bits: 4=0100, 0=0000, 1=0001, 9=1001, puis onze fois 0000. La chaîne est donc
01000000000110010000…0.
Exercice 1.4 · Textes, encodages et longueurs
Combien d'octets occupe la chaîne «Analyse» en UTF-8? Et «Àéîõü»?
Le caractère € a pour point de code U+20AC. Montrer, en détaillant les bits, qu'il occupe trois octets en UTF-8 et donner leur valeur hexadécimale.
Un fichier commence par les octets C3A9. Que voit un lecteur qui suppose de l'UTF-8? Et un lecteur qui suppose du latin-1?
Pourquoi lire un fichier latin-1 comme de l'UTF-8 produit-il généralement une erreur, alors que l'inverse produit du texte lisible mais faux?
Solution
1. «Analyse» ne contient que des caractères ASCII: 7 caractères, 7 octets. «Àéîõü» contient cinq caractères dont les points de code sont U+00C0, U+00E9, U+00EE, U+00F5, U+00FC, tous compris entre 128 et 2047: chacun occupe deux octets, soit 10 octets pour 5 caractères. Ici, le surcoût d'UTF-8 par rapport au latin-1 est de 100 %; sur un texte français ordinaire, il est de quelques pour cent seulement, puisque les caractères accentués y sont minoritaires.
2.20AC en hexadécimal vaut 2⋅4096+0+10⋅16+12=8364. Ce nombre dépasse 2047=211−1, donc le gabarit à deux octets (11 bits utiles) ne suffit pas: il faut celui à trois octets, 1110xxxx 10xxxxxx 10xxxxxx, qui offre 4+6+6=16 bits utiles. Sur seize bits, 8364=(0010000010101100)2. On répartit: 0010 dans le premier gabarit, 000010 puis 101100 dans les deux suivants:
111000101000001010101100=E282AC.
Vérification en Python: '€'.encode('utf-8').hex() rend e282ac. Le signe de l'euro coûte donc trois octets, contre un seul dans les tables latin-9 ou Windows-1252 — un détail qui a réellement freiné l'adoption d'UTF-8 dans les systèmes de caisse.
4. Parce que les motifs d'UTF-8 sont contraints: un octet dont les bits de tête sont 10 ne peut apparaître qu'en continuation d'une séquence commencée par 110, 1110 ou 11110. Or les octets accentués du latin-1 sont typiquement isolés entre des octets ASCII: le décodeur UTF-8 rencontre un octet supérieur à 127 qui n'annonce rien de valide, ou une séquence annoncée que le fichier n'honore pas, et il signale une erreur. Dans l'autre sens, latin-1 accepte les 256 octets possibles sans exception: il ne peut jamais échouer, donc il ne peut jamais prévenir. Cette asymétrie est un choix de conception délibéré d'UTF-8, et c'est aussi ce qui permet à un éditeur de deviner l'encodage avec une bonne fiabilité.
Exercice 1.5 · Tailles, débits et unités
Une agence archive des photographies de 6000×4000 pixels en couleur vraie, non compressées.
Quelle est la taille d'une photographie, en Mo et en Mio?
Combien de temps faut-il pour transmettre une photographie sur un lien symétrique de 100 Mbit/s, en supposant le lien parfaitement exploité?
L'agence stocke ses archives sur un disque annoncé à 4 To. Combien de photographies y tiennent, et quelle capacité le système d'exploitation affichera-t-il en tébioctets?
La même agence archive aussi des bandes sonores au format du disque compact. Quelle durée de son, en heures, occupe la même place qu'une photographie?
Un responsable affirme que «le disque de 4 To a perdu 10 % à cause du formatage». Que répondre?
Solution
1.6000×4000=24000000 pixels, à 3 octets chacun: 72000000 octets, soit 72 Mo. En préfixes binaires, 72⋅106/220=68,66Mio.
2. Le débit est donné en bits par seconde, la taille en octets: il faut convertir. 72⋅106 octets =576⋅106 bits, et
t=100⋅106576⋅106=5,76 s.
C'est la borne inférieure: elle ignore les en-têtes des protocoles et la latence, dont le chapitre 10 montre qu'elle ne se réduit pas en augmentant le débit.
3. Le disque contient 4⋅1012 octets. Nombre de photographies: 4⋅1012/72⋅106=55555,6, donc 55 555 photographies complètes. Capacité affichée: 4⋅1012/240=3,638 .
4. Une minute de son au format CD pèse 10,584 Mo (exemple 1.9). Le rapport vaut 72/10,584=6,803 minutes, soit environ 6 min 48 s — donc 0,113 heure. Autrement dit, une seule photographie brute pèse autant que près de sept minutes de musique: l'image est, de loin, le format le plus coûteux des trois que ce chapitre a chiffrés, ce qui explique que la compression d'images ait été historiquement la première à être normalisée.
5. Deux phénomènes distincts sont mélangés. L'écart entre 4 To affichés par le fabricant et 3,638 Tio affichés par le système est de (4−3,638)/4=9,05%, et il ne correspond à aucune perte: c'est le rapport 1012/240=1,0995 entre deux définitions du préfixe «téra», donc une question de notation. Le formatage, lui, consomme réellement de la place — table d'allocation, journal, blocs de réserve du contrôleur —, mais c'est une part d'un tout autre ordre de grandeur, et elle dépend du système de fichiers choisi. La bonne réponse est donc: le disque contient bien octets comme annoncé, votre système les affiche dans une autre unité en lui donnant le mauvais nom, et la place réellement consommée par le formatage est une question séparée qu'il faut mesurer et non déduire de cet écart.
Références
Abelson, H., Ledeen, K. & Lewis, H., Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion, Addison-Wesley — chapitre 3 pour la numérisation et la représentation des images et des sons.
Patterson, D. & Hennessy, J., Computer Organization and Design, Morgan Kaufmann — chapitre 3 pour l'arithmétique des ordinateurs, le complément à deux et IEEE 754.
Goldberg, D., «What Every Computer Scientist Should Know About Floating-Point Arithmetic», ACM Computing Surveys, vol. 23, n° 1, 1991 — la référence sur l'arrondi, l'absorption et l'élimination.
IEEE Std 754-2019, IEEE Standard for Floating-Point Arithmetic, IEEE — le texte normatif du format binary64.
The Unicode Consortium, The Unicode Standard, et Yergeau, F., UTF-8, a transformation format of ISO 10646, RFC 3629, 2003 — points de code et encodage.
ESA/CNES, Ariane 5 — Flight 501 Failure: Report by the Inquiry Board (présidé par J.-L. Lions), Paris, 1996 — le rapport public sur le débordement de conversion.
Polycopiés du cours ICC de l'EPFL.
(ak…a1a0)b
[0,1[
∑i≥1a−ib−i
(0,a−1a−2…)b
(9C)16=9⋅16+12=144+12=156
0,6875=11/16
5
5
0,1
(11111011)2
e=1019−1023=−4
2−4=1/16=0,0625
0,1
ε=2−52≈2,22⋅10−16
1
ε/2
108
0,0
x=10−8
cosx
1
2sin2(x/2)/x2
0,5
Regroupement par trois bits depuis la droite, en complétant à gauche: 011111101001→(3751)8. Vérification: 3⋅512+7⋅64+5⋅8+1=1536+448+40+1=2025.
Regroupement par quatre bits: 011111101001→(7E9)16. Vérification: 7⋅256+14⋅16+9=1792+224+9=2025.
2.B=11=(1011)2 et E=14=(1110)2, donc (BE)16=(10111110)2. En octal, regroupement par trois: 010111110→(276)8. En décimal: 11⋅16+14=190, ou par la somme des poids 128+32+16+8+4+2=190.
3. Multiplications successives par 2: 0,8125×2=1,625 (bit 1, reste 0,625); 0,625×2=1,25 (bit 1, reste 0,25); 0,25×2=0,5 (bit 0); 0,5×2=1 (bit 1, reste nul). Donc 0,8125=(0,1101)2. Vérification: 21+41+161=168+4+1=1613=0,8125. Le développement est fini parce que 0,8125=13/16 a un dénominateur qui est une puissance de deux.
4. Partie entière: (101101)2=32+8+4+1=45. Partie fractionnaire: (0,101)2=21+81=0,625. Donc (101101,101)2=45,625.
5. Un chiffre hexadécimal code exactement quatre bits, donc 64/4=16 chiffres, ni plus ni moins si l'on conserve les zéros de tête. C'est pourquoi une adresse mémoire de 64 bits s'écrit avec seize chiffres hexadécimaux, et une empreinte de 256 bits avec soixante-quatre.
(10011100)2
156
−100
−1
(00000001)2
(11111110)2
(11111111)2
−1
−128=−27
(10000000)2
−128+0=−128
2.(01100100)2+(01100100)2=(11001000)2. Lu en complément à deux, ce motif vaut −128+64+8=−56. Il y a débordement: deux opérandes positifs ont produit un résultat de signe négatif, ce qui est le critère exact. La valeur rendue est 200−256=−56, c'est-à-dire 200 modulo 256 ramené dans [−128,127].
3.−128 est (10000000)2 et −1 est (11111111)2. Leur somme binaire vaut 101111111; la retenue sortante est abandonnée et il reste (01111111)2=+127. Là encore débordement: deux opérandes négatifs ont donné un résultat positif. C'est le passage en bas de la roue de la figure 1.2, dans l'autre sens.
4. La plage est [−128,127], asymétrique. Pour x=−128, ∣x∣=128 n'appartient pas à la plage: le calcul de la valeur absolue par «inverser et ajouter un» rend (10000000)2, c'est-à-dire −128 lui-même. Une fonction abs sur huit bits admet donc un point fixe négatif. Le même phénomène existe sur 32 et 64 bits, aux bornes correspondantes.
5. Un compteur non signé de 16 bits parcourt 216=65536 valeurs avant de revenir à zéro. À une incrémentation par milliseconde, cela fait 65536 ms =65,536 s, soit un peu plus d'une minute. Ce genre d'estimation est exactement ce qui manquait au calcul d'Ariane 501: une borne de représentation confrontée à la plage réelle de la grandeur mesurée.
Signe s=0: positif. Exposant: (10000000001)2=1024+1=1025, donc e=1025−1023=2. Mantisse: les bits stockés sont 1001 suivis de zéros, donc M/252=2−1+2−4=0,5625 et m=1,5625. Valeur: 1,5625×22=6,25. Vérification: 6,25=25/4, dénominateur 22, donc dyadique, donc exactement représentable — ce que confirme la mantisse qui se termine par des zéros.
2.0,5=1/2 a pour dénominateur une puissance de deux: son écriture binaire (0,1)2 est finie, elle tient dans la mantisse, et l'arrondi est nul. 0,1=1/10 a le facteur premier 5 au dénominateur; son écriture binaire (0,00011)2 est infinie périodique, et la mantisse de 53 bits significatifs la tronque puis l'arrondit. L'écart vaut 5,55⋅10−18.
3. Il vaut mieux sommer dans l'ordre décroissant des k, c'est-à-dire en commençant par les plus petits termes. En ordre croissant, la somme partielle atteint rapidement une valeur de l'ordre de 10 à 16, alors que les derniers termes valent 10−7: le rapport est de l'ordre de 108, encore loin de 1/ε≈4,5⋅1015, donc l'absorption n'est pas totale ici, mais chaque addition perd des bits et l'erreur s'accumule sur 107 opérations. En commençant par les petits termes, on les fait contribuer entre eux avant de les ajouter au gros de la somme, et l'erreur finale est nettement plus faible. Le principe général: additionner des nombres d'ordres de grandeur comparables. L'algorithme de sommation compensée de Kahan pousse la même idée plus loin en conservant explicitement le reste de chaque arrondi.
4. Le test est faux parce que 0,1, 0,2 et 0,3 sont chacun remplacés par le double le plus proche, et que la somme des deux premiers arrondis n'est pas l'arrondi de 0,3: la somme rendue vaut 0,3000000000000000444089… alors que le double le plus proche de 0,3 vaut 0,2999999999999999888978… Il faut remplacer le test d'égalité par une comparaison à une tolérance, par exemple ∣x−0,3∣≤10−9 pour une tolérance absolue, ou ∣x−y∣≤τmax(∣x∣,∣y∣) pour une tolérance relative τ adaptée à la grandeur. Si les valeurs sont des montants d'argent, il faut sortir de la virgule flottante: entiers de centimes ou type décimal exact.