Représentation de l'information · Information, calcul et communication

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);
décrire un signal par son spectre et sa largeur de bande, calculer la fréquence apparente d'une composante repliée, énoncer le théorème d'échantillonnage de Nyquist–Shannon et justifier le filtre anti-repliement et la reconstruction par sinus cardinal;
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 $2^{20} = 1048576$ , 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é.

Le symbole du bit est b, celui de l'octet — groupe de huit bits — est o. Nous écrirons toujours $lo g_{2}$ en toutes lettres, jamais $l g$ , 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? $lo g_{2} 26 \approx 4, 70$ , donc $5$ bits ( $2^{5} = 32 \geq 26$ ). Combien pour désigner une carte d'un jeu de 52? $lo g_{2} 52 \approx 5, 70$ , donc bits. Combien pour un habitant de la Suisse, dont la population dépasse huit millions? , donc 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, \dots, 9$ puis $A, B, C, D, E, F$ pour $10, 11, \dots, 15$ . Nous écrirons systématiquement la base en indice: , , , .

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$ à $2^{8} - 1 = 255$ .

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:

n = 156
print(bin(n), oct(n), hex(n))       # préfixes 0b, 0o, 0x
print(int("10011100", 2), int("9C", 16))

0b10011100 0o234 0x9c
156 156

Pourquoi l'hexadécimal

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

Remplacer le nombre courant par le quotient entier obtenu

Lire la suite des restes du dernier obtenu vers le premier

Recommencer tant que le quotient n'est pas nul

Diviser le nombre courant par 2 et noter le reste, qui vaut 0 ou 1

Question 1.3

Quelle est la valeur décimale de $(2 F 3)_{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$ à $2^{n} - 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$	$\approx 4, 3 \cdot 1 0^{9}$

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 $2^{n}$ . Un additionneur de $n$ bits qui laisse tomber la retenue sortante ne calcule pas $x + y$ mais $x + y mod 2^{n}$ . Dans cet anneau, l'opposé de $x$ existe: c'est . On décide donc que le motif binaire .

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$ , $a_{i} + \overline{a_{i}} = 1$ puisque l'un des deux bits vaut $0$ et l'autre $1$ . En sommant les poids, , ce qui est la première égalité; en ajoutant des deux côtés, , donc est bien l'opposé de modulo . Pour la seconde affirmation, soit et deux entiers représentables et leurs motifs, c'est-à-dire et modulo d'après (1.3). L'additionneur produit le motif , qui est congru à ; si 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$ .

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 .

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 \cdot 1 0^{- 11}$ comme $2, 998 \cdot 1 0^{8}$ . 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} \cdot m \cdot 2^{e}$ , avec $1 \leq m < 2$ . Comme la partie entière de $m$ vaut alors toujours $1$ , on ne la stocke pas: c'est le , un bit gagné gratuitement.

Décoder un double, champ par champ

Exemple 1.4 · Décodage complet du double le plus proche de 0,1

Les 64 bits, obtenus par pack(">d", 0.1) du module struct de Python, sont

from struct import pack, unpack
bits = format(unpack(">Q", pack(">d", 0.1))[0], "064b")
print(bits[0], bits[1:12], bits[12:])   # signe, exposant, mantisse

0 01111111011 1001100110011001100110011001100110011001100110011010

Signe. $s = 0$ : le nombre est positif.

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:

>>> 0.1 + 0.2
0.30000000000000004
>>> 0.1 + 0.2 == 0.3
False
>>> from decimal import Decimal
>>> Decimal(0.1)
Decimal('0.1000000000000000055511151231257827021181583404541015625')

Détaillons. Le double le plus proche de $0, 1$ vaut $0, 1000000000000000055511 \dots$ , celui de $0, 2$ vaut $0, 2000000000000000111022 \dots$ (le double du précédent, exactement, puisque multiplier par deux ne change que l'exposant). Leur somme exacte est $0, 3000000000000000166533453693773481 \dots$ , qui n'est pas représentable; l'arrondi au plus proche donne $0, 30000000000000004440892 \dots$ , affiché 0.30000000000000004. Or le double le plus proche de $0, 3$ vaut Les deux nombres diffèrent d'un seul bit de mantisse — mais ils diffèrent, et le test d'égalité est faux.

«L'ordinateur se trompe» — non: il arrondit

Quand un tableur affiche $0, 1 + 0, 2 \neq = 0, 3$ , aucune erreur ne s'est produite. Chaque opération a été correctement arrondie, comme la norme l'exige: le résultat rendu est le nombre représentable le plus proche du résultat exact. Ce qui est faux, c'est l'hypothèse tacite du lecteur — que les décimaux qu'il écrit existent dans la machine. Ils n'existent pas: la machine stocke le dyadique le plus proche. La conséquence pratique est une règle absolue: ne testez jamais l'égalité de deux flottants. Comparez $∣ x - y ∣$ à une tolérance choisie en fonction de la grandeur, ou travaillez en décimal exact (type en Python) quand il s'agit d'argent, ou en entiers de centimes. La comptabilité, la facturation et la fiscalité se font en entiers ou en décimal exact, jamais en virgule flottante.

Absorption

Les flottants ont un pas variable: l'écart entre deux doubles consécutifs vaut $2^{e - 52}$ , donc il grandit avec la grandeur des nombres. Près de $1$ , il vaut $2^{- 52} \approx 2, 2 \cdot 1 0^{- 16}$ ; près de $1 0^{16}$ , il vaut .

Élimination catastrophique

Question 1.4

Le plus petit entier positif qui ne soit pas représentable exactement en binary64 s'écrit $2^{k} + 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 $2^{7} = 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$

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 = 2^{5}$ 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.

UTF-8 (RFC 3629)

UTF-8, conçu par Ken Thompson et Rob Pike en 1992 et normalisé par la RFC 3629, est un encodage à longueur variable: un point de code occupe 1, 2, 3 ou 4 octets.

points de code	octets	motif binaire
`U+0000` à `U+007F`	1	`0xxxxxxx`
`U+0080` à `U+07FF`	2	`110xxxxx 10xxxxxx`
`U+0800` à `U+FFFF`	3	`1110xxxx 10xxxxxx 10xxxxxx`
`U+10000` à `U+10FFFF`	4	`11110xxx 10xxxxxx 10xxxxxx 10xxxxxx`

Les bits x reçoivent, dans l'ordre, les bits du point de code. Trois propriétés en découlent: les 128 caractères ASCII gardent leur octet inchangé, donc tout fichier ASCII est déjà un fichier UTF-8 valide; un octet de continuation commence toujours par 10, donc on reconnaît le début d'un caractère sans remonter au début du fichier; et aucun caractère n'est le préfixe d'un autre — nous retrouverons cette propriété sous le nom de code préfixe au chapitre 7.

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 octets
print(len(texte), "caractères,", len(octets), "octets")
print(octets[:8].hex(" ").upper())      # les octets réels
print(octets.decode("latin-1"))         # relu avec le mauvais jeu de caractères

31 caractères, 32 octets
52 65 70 72 C3 A9 73 65
ReprÃ©sentation de l'information

Le mécanisme est entièrement lisible dans la troisième ligne. Les octets C3 A9 sont, en UTF-8, la paire qui code é. Relus un par un comme du latin-1, ils deviennent deux caractères: C3 $= 195$ est Ã, et A9 $= 169$ est ©. D'où Ã©. Le fichier n'est pas corrompu: pas un bit n'a changé. C'est l'interprétation qui est fausse, exactement comme l'octet $(10011100)_{2}$ qui vaut $156$ ou $- 100$ selon la convention choisie.

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 $f_{e}$ n'est pas libre. Le théorème d'échantillonnage de Nyquist–Shannon, que la section suivante énonce et justifie, affirme qu'un signal ne contenant aucune fréquence supérieure à $f_{m a x}$ est entièrement déterminé par ses échantillons pris à la fréquence $f_{e} > 2 f_{m a x}$ . L'oreille humaine perçoit jusqu'à environ 20 kHz; le disque compact échantillonne à kHz, ce qui laisse la marge nécessaire pour le filtre anti-repliement, puisque 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?

Signaux, échantillonnage et reconstruction

La section précédente a compté les bits d'un son échantillonné en prenant $f_{e}$ comme une donnée. Il reste à comprendre pourquoi $44, 1$ kHz suffit, ce qui arrive quand on échantillonne trop lentement, et comment un lecteur reconstruit une onde continue à partir d'une suite de nombres. La question est plus profonde qu'elle n'en a l'air: entre deux échantillons, le signal aurait pu faire n'importe quoi. Que des valeurs prises à des instants isolés puissent déterminer toute la courbe paraît d'abord impossible; c'est pourtant exactement ce qu'affirme le théorème de Nyquist–Shannon, sous une hypothèse précise qu'il faut apprendre à reconnaître.

Un signal comme somme de sinusoïdes

Le bon langage pour parler d'un signal est celui des fréquences. Un diapason produit, à très peu près, une seule sinusoïde; une corde de violon en produit une fondamentale et ses harmoniques; une voix, une infinité qui varient au cours du temps. Le résultat central de l'analyse de Fourier, que nous admettons parce que sa démonstration demande une théorie de l'intégration que ce cours ne suppose pas, est que tout signal physique raisonnable s'écrit comme une somme — finie, infinie, ou continue sous forme d'intégrale — de sinusoïdes.

Un sinus est une sinusoïde comme une autre, puisque $sin (2 π f t) = cos (2 π f t - π /2)$ : seule la phase change. Le spectre décrit ce qui varie et à quelle vitesse; c'est lui, et non l'allure de la courbe dans le temps, qui décide de la fréquence d'échantillonnage nécessaire.

Prenons un la de diapason enrichi de deux harmoniques, $x (t) = cos (2 π \cdot 440 t) + 0, 5 cos (2 π \cdot 880 t) + 0, 25 cos (2 π \cdot 1320 t)$ . Son spectre compte trois raies, à 440, 880 et 1 320 Hz, et sa largeur de bande vaut Hz. Une voix au téléphone est volontairement limitée à la bande 300–3 400 Hz; une musique enregistrée pour l'oreille humaine, à environ 20 kHz. Ces nombres ne disent rien de la «forme» du signal; ils disent jusqu'où montent ses fréquences, et c'est tout ce dont l'échantillonnage a besoin.

Ce que voient les échantillons: le repliement

Échantillonner à la fréquence $f_{e}$ , c'est ne garder que les valeurs $x [n] = x (n T_{e})$ aux instants $t = n T_{e}$ , où est la et un entier. La question décisive est: deux signaux différents peuvent-ils donner les mêmes échantillons? La réponse est oui, et le phénomène porte un nom.

Démonstration. Puisque $f_{e} T_{e} = 1$ , on a $2 π (k f_{e} \pm f) n T_{e} = 2 π k n \pm 2 π f n T_{e}$ . Le terme est un multiple entier de , que le cosinus ne voit pas. Il reste , qui vaut parce que le cosinus est pair. Pour la seconde affirmation: si est l'entier le plus proche de , alors , donc , et s'écrit ou selon le signe de .

Le nom vient de l'image: l'axe des fréquences est replié en accordéon sur l'intervalle $[0, f_{e} /2]$ , et toute fréquence vient se poser sur son représentant dans cet intervalle. La fréquence $f_{e} /2$ , frontière du pli, s'appelle la fréquence de Nyquist.

Le théorème d'échantillonnage

Le théorème 1.2 dit ce qui se perd. Le théorème suivant dit à quelle condition rien ne se perd.

Démonstration de la seconde affirmation (complète). Supposons d'abord $f_{e} < 2 B$ , et prenons la sinusoïde $cos (2 π B t)$ , de fréquence $B$ , permise par l'hypothèse. Par le théorème 1.2, elle a les mêmes échantillons que $cos (2 π f_{a} t)$ , où . Les deux fréquences sont distinctes et toutes deux au plus égales à : deux signaux différents de la classe considérée sont confondus. Reste le cas limite , qui piège souvent. Le signal donne alors les échantillons pour : une sinusoïde d'amplitude 1 a les mêmes échantillons que le silence. C'est pourquoi l'inégalité est stricte.

Idée de la première affirmation (esquisse; la démonstration complète est admise parce qu'elle repose sur la transformée de Fourier). Restons, pour l'intuition, avec un signal qui est une somme finie de sinusoïdes de fréquences toutes inférieures à $f_{e} /2$ . Le théorème 1.2 dit que chaque fréquence de l'intervalle $[0, f_{e} /2)$ est son propre représentant: deux fréquences distinctes de cet intervalle ne se replient jamais l'une sur l'autre, puisque le repliement ne fait qu'identifier une fréquence hors de l'intervalle à une fréquence dedans. Les suites d'échantillons de sinusoïdes de fréquences distinctes dans $[0, f_{e} /2)$ restent donc distinguables, et l'on montre — c'est de l'algèbre linéaire, admise ici — qu'on peut retrouver à partir des échantillons l'amplitude et la phase de chacune. Connaître toutes les amplitudes et toutes les phases, c'est connaître le signal à instant, pas seulement aux instants d'échantillonnage.

Un comptage donne la même conclusion par un autre chemin. Sur une durée $d$ , un signal à bande limitée par $B$ n'a, en ordre de grandeur, que $B d$ fréquences utiles espacées de $1/ d$ , chacune portant deux nombres, une amplitude et une phase: environ $2 B d$ nombres en tout. Un échantillonnage à $2 B$ fournit précisément $2 B d$ échantillons sur la même durée. Le théorème dit que ce comptage est juste: un signal de bande $B$ a $2 B$ degrés de liberté par seconde, et échantillons par seconde suffisent à les fixer.

Filtrer avant d'échantillonner

Le filtre est nécessairement analogique, ou du moins il agit avant la prise des échantillons qui comptent: une fois le repliement produit, aucun calcul sur les nombres ne peut le défaire. Il détruit délibérément de l'information — les fréquences au-delà de $f_{c}$ — pour éviter d'en fabriquer de la fausse. C'est un arbitrage qui reviendra dans ce cours: mieux vaut une perte connue qu'une erreur indiscernable.

Un filtre réel ne passe pas d'un coup de «tout laisser» à «tout couper»: il lui faut une bande de transition. Le format du CD montre comment on la place. On veut conserver la bande audible, jusqu'à 20 kHz. Une fréquence $f$ légèrement supérieure à $f_{e} /2 = 22, 05$ kHz se replie en $f_{e} - f$ ; ce replié reste inaudible tant que $f_{e} - f \geq 20$ kHz, c'est-à-dire tant que kHz. Le filtre doit donc laisser passer jusqu'à 20 kHz et avoir tout éliminé à 24,1 kHz: sa bande de transition s'étend sur kHz, et les fréquences qui s'y trouvent ne se replient qu'entre 20 et 22,05 kHz, là où l'oreille ne les entend pas. La marge de kHz sur les kHz du strict minimum est le prix de ce filtre réalisable.

La téléphonie classique fait le même calcul à une autre échelle: elle échantillonne à 8 kHz et filtre donc la voix en dessous de 4 kHz — en pratique à 3,4 kHz, la même marge de transition. Et l'image a son équivalent spatial: réduire une photographie de rayures fines en sautant simplement des pixels produit des motifs ondulés qui n'existaient pas, le moiré; un logiciel de retouche correct floute légèrement l'image avant de la réduire, ce qui est exactement un filtre passe-bas.

Question 1.7

Un capteur de vibrations est échantillonné à $f_{e} = 1000$ Hz. Le signal utile est en dessous de 200 Hz, mais une machine voisine produit une vibration parasite à 900 Hz. Que se passe-t-il sans filtre anti-repliement?

Reconstruire: l'interpolation par sinus cardinal

Reste le chemin inverse: d'une suite de nombres $x [n]$ , refaire une onde continue $x (t)$ . Le théorème 1.3 affirme que c'est possible; voici comment.

La formule se lit facilement. Chaque échantillon $x [n]$ pose, centrée sur son instant $n T_{e}$ , une «bosse» en forme de sinus cardinal, multipliée par sa valeur; le signal reconstruit est la somme de toutes ces bosses. Aux instants d'échantillonnage, la formule redonne exactement les échantillons: en $t = m T_{e}$ , l'argument du terme $n$ vaut l'entier $m - n$ , et est nul pour tous les sauf , où il vaut 1. les échantillons, tous les termes contribuent, et c'est là que la formule fait son travail: elle choisit, parmi toutes les courbes qui passent par les points, l' courbe de bande inférieure à . Le théorème 1.3 garantit que c'est la bonne, puisque le signal d'origine en est une.

Deux méthodes plus naïves viennent à l'esprit, et toutes deux sont fausses au sens du théorème. Tenir chaque valeur jusqu'à l'échantillon suivant produit un escalier, dont les marches verticales contiennent des fréquences arbitrairement élevées; relier les points par des segments produit des angles, qui en contiennent aussi. Dans les deux cas, on fabrique des fréquences au-delà de $f_{e} /2$ qui n'étaient pas dans le signal. La somme de sinus cardinaux est précisément la reconstruction qui n'en ajoute aucune.

Elle a deux défauts pratiques, qu'il faut connaître. La somme est infinie et le sinus cardinal ne décroît qu'en $1/ u$ : chaque échantillon influence le signal reconstruit loin de son instant. Et elle utilise les échantillons futurs: la valeur en $t$ dépend de $x [n]$ pour $n T_{e} > t$ . Un convertisseur réel tronque donc la somme, accepte un petit retard pour disposer des échantillons suivants, et approche le sinus cardinal par un filtre de reconstruction — encore un passe-bas, de coupure $f_{e} /2$ . Le principe reste celui de (1.8).

Question 1.8

Avec $T_{e} = 1$ , les échantillons sont $x [0] = 2$ , $x [1] = 1$ et tous les autres sont nuls. Que vaut le signal reconstruit par la formule de Whittaker–Shannon en $t = 1/2$ ?

Retenez la chaîne complète, qui est celle de tout appareil audio numérique et de toute carte d'acquisition: filtrer (passe-bas sous $f_{e} /2$ ), échantillonner (à $f_{e} > 2 B$ ), quantifier (sur $q$ bits, ce qui ajoute l'erreur d'arrondi de la section précédente), puis, à la lecture, reconstruire (par un passe-bas qui réalise approximativement la somme de sinus cardinaux). Les deux premières étapes ne perdent rien que l'on n'ait choisi de perdre; la troisième perd toujours un peu; la quatrième rend exactement ce que les échantillons contiennent. Et le nombre de bits produit par seconde, $f_{e} \cdot q \cdot c$ par (1.7), est fixé par le théorème d'échantillonnage pour le premier facteur et par la quantification pour le deuxième. Le chapitre 7 montrera comment on le réduit ensuite, en jetant précisément ce que l'oreille ou l'œil ne perçoivent pas.

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 $1 0^{3}$ , méga $1 0^{6}$ , giga $1 0^{9}$ , téra $1 0^{12}$ . Mais les tailles de mémoire sont naturellement des puissances de deux, parce qu'un bus d'adresse de $n$ fils désigne $2^{n}$ cases. Or est proche de , et l'usage s'est installé d'appeler «kilo-octet» le groupe de octets. L'approximation était excellente pour le kilo (2,4 % d'écart); elle se dégrade à chaque étage.

ISO/IEC 80000-13

La norme ISO/IEC 80000-13 (reprenant la CEI 60027-2 de 1998) réserve les préfixes SI à leurs valeurs décimales et introduit des préfixes binaires distincts:

préfixe binaire	valeur	préfixe décimal	valeur	excès du binaire
kibioctet (Kio)	$2^{10} = 1024$	kilooctet (ko)	$1 0^{3}$	$+ 2, 4 %$

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 \cdot 1 0^{9} = 500000000000$ octets, ni plus ni moins. Le système d'exploitation, lui, divise ce nombre par $2^{30}$ et affiche encore, dans plusieurs cas, le symbole «Go»:

\frac{500 \cdot 1 0 ^{9}}{2 ^{30}} = \frac{500 \cdot 1 0 ^{9}}{1 073 741 824} = 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 \cdot 1 0^{11}$ 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 \cdot 1 0^{12} / 2^{40} = 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 $⌈ lo g_{2} N ⌉$ bits; $n$ bits distinguent $2^{n}$ 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 $- 2^{n - 1}$ , l'opposé s'obtient en inversant les bits et en ajoutant un, la soustraction devient une addition, et la plage 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.

Série d'exercices du chapitre 1Exercice 1 sur 5

Question 1.9

Combien de valeurs distinctes un mot de 12 bits peut-il représenter?

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}$ .

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.

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 = \sum_{k = 1}^{1 0^{7}} 1/ k$ en virgule flottante. Vaut-il mieux sommer dans l'ordre croissant des ou décroissant? Justifier.

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 $C3 A9$ . 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 . Ce nombre dépasse , donc le gabarit à deux octets (11 bits utiles) ne suffit pas: il faut celui à trois octets, , qui offre bits utiles. Sur seize bits, . On répartit: dans le premier gabarit, puis dans les deux suivants:

Exercice 1.5 · Tailles, débits et unités

Une agence archive des photographies de $6000 \times 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?