Codage des données

Le 4 juin 1996, trente-sept secondes après le décollage, Ariane 5 se disloque. La cause tient en une ligne de code héritée d'Ariane 4 : une vitesse horizontale, stockée en flottant sur 64 bits, est convertie en entier signé sur 16 bits. Ariane 5 vole plus vite que sa devancière, la valeur ne tient pas dans le domaine, la conversion déborde. Le calculateur bascule en mode erreur, le second calculateur — même logiciel, même donnée — tombe une milliseconde plus tard, et 370 millions de dollars partent en fumée.

Ce chapitre est celui de ce genre d'accidents. Le chapitre 1 a montré comment écrire des entiers positifs ; il n'a rien dit du signe, de la virgule, ni des lettres. Chaque codage qu'on va poser résout un de ces manques — et chacun a un domaine hors duquel il ment sans prévenir. Reconnaître ce domaine est l'objectif réel du chapitre.

Entiers non signés : le tour du compteur

Sur $n$ bits sans signe, on code les entiers de $0$ à $2^n - 1$. Rien de plus, rien de moins. Un octet va de 0 à 255, un mot de 32 bits jusqu'à 4 294 967 295.

Que se passe-t-il en dépassant ? Le bit qui déborde à gauche n'a nulle part où aller : il est perdu. Sur 8 bits, $255 + 1$ donne 100000000, dont seuls les huit bits de droite sont conservés — soit 00000000, c'est-à-dire 0. L'arithmétique machine n'est pas celle des entiers : c'est l'arithmétique modulo $2^n$, celle d'un compteur kilométrique qui repasse à zéro.

Ce n'est pas une anomalie, c'est le comportement défini du matériel. Ce qui est dangereux, c'est qu'il soit silencieux : aucune exception, aucun message, juste un résultat faux.

Le complément à deux

Il faut maintenant coder les négatifs. La première idée qui vient est aussi la mauvaise : réserver le bit de poids fort au signe et coder la valeur absolue dans le reste. Ce codage, dit signe-valeur absolue, a deux défauts rédhibitoires. Il possède deux zéros, 00000000 et 10000000, qu'il faut traiter séparément partout. Et surtout, l'addition ne fonctionne plus : additionner $(+5)$ et $(-5)$ bit à bit donne 10001010, soit $-10$, ce qui n'a aucun sens. Il faudrait un circuit de soustraction distinct du circuit d'addition.

Le complément à deux résout les deux problèmes d'un coup, et c'est pourquoi toutes les machines l'emploient. Son principe : garder l'addition binaire telle quelle, et choisir le codage des négatifs pour qu'elle tombe juste.

L'idée est celle du compteur. Sur $n$ bits on compte modulo $2^n$ ; reculer de 5 revient donc à avancer de $2^n - 5$. On définit le codage de $-x$ comme celui de $2^n - x$ :

1Sur 8 bits (2⁸ = 256)2 3  +5  →  000001014  −5  →  256 − 5 = 251  →  11111011

Vérifions que l'addition marche, sans aucun circuit spécial :

1   00000101   (+5)2 + 11111011   (−5)3 ──────────4  100000000   → le 9ᵉ bit déborde et disparaît5   00000000   → 0. Exact.

En pratique on n'effectue jamais la soustraction $2^n - x$. On utilise la règle des deux gestes, strictement équivalente : inverser tous les bits, puis ajouter 1.

1   5  =  000001012   ~   →  11111010      (inversion bit à bit)3   +1  →  11111011      = −5

La règle est involutive : l'appliquer à $-5$ redonne $+5$. C'est le meilleur contrôle d'une copie.

Quatre conséquences à connaître par cœur.

Le bit de poids fort est le bit de signe : 0 pour positif ou nul, 1 pour négatif. Ce n'est pas une convention plaquée, c'est une conséquence du codage.

Le domaine est dissymétrique. Sur $n$ bits on code de $-2^{n-1}$ à $+2^{n-1}-1$ : sur 8 bits, de $-128$ à $+127$. Il y a un négatif de plus que de positifs, parce que zéro occupe une place du côté positif. Conséquence pratique : $-(-128)$ n'est pas représentable sur 8 bits, et la règle des deux gestes appliquée à $-128$ redonne $-128$.

L'extension de signe. Pour élargir un nombre de 8 à 32 bits, on ne complète pas par des zéros mais par le bit de signe répété. Sinon $-5$ deviendrait 251. C'est exactement l'instruction que le chapitre 6 nommera lb contre lbu.

Les mêmes bits, deux lectures. 11111011 vaut 251 non signé et $-5$ signé. Le motif ne porte pas son interprétation : c'est l'instruction du processeur qui décide, et c'est la raison pour laquelle le chapitre 6 distingue les comparaisons signées des non signées.

Détecter le débordement

Il faut distinguer deux cas, que le matériel signale par deux indicateurs différents.

Le débordement non signé se produit quand une retenue sort du bit de poids fort. Le processeur lève l'indicateur de retenue (carry).

Le débordement signé se produit quand le résultat sort de $[-2^{n-1},\, 2^{n-1}-1]$. Il se détecte ainsi : la retenue entrant dans le bit de signe diffère de la retenue qui en sort. Le processeur lève l'indicateur de débordement (overflow). Une règle plus simple à retenir en TD : additionner deux nombres de même signe et obtenir un résultat de signe opposé est un débordement signé — et additionner deux nombres de signes contraires ne peut jamais déborder.

Les deux sont indépendants : une même addition peut déborder dans un cas et pas dans l'autre. C'est bien pourquoi le processeur maintient deux indicateurs, et pourquoi le compilateur choisit l'instruction de branchement selon que la variable était déclarée signée ou non.

Virgule flottante : IEEE 754

Coder $3{,}14$ demande un autre principe : la notation scientifique en binaire. Tout réel non nul s'écrit $\pm 1{,}m \times 2^{e}$, et la norme IEEE 754 range ces trois morceaux dans un mot. En simple précision, sur 32 bits :

Deux astuces méritent d'être comprises. Le bit implicite : puisque la partie entière de la notation normalisée vaut toujours 1, on ne la stocke pas — 23 bits stockés donnent 24 bits de précision. Et l'exposant biaisé : au lieu d'un exposant signé, on stocke $e+127$, ce qui permet de comparer deux flottants positifs comme s'ils étaient des entiers, en un seul circuit.

La double précision, sur 64 bits, suit le même schéma avec 11 bits d'exposant et 52 de mantisse. Certains motifs sont réservés : exposant tout à 1 et mantisse nulle codent $\pm\infty$, exposant tout à 1 et mantisse non nulle codent NaN (not a number), et l'exposant tout à 0 code zéro et les nombres dénormalisés.

Reste la propriété qui coûte le plus cher en pratique : un flottant binaire ne peut pas représenter exactement $0{,}1$. En base 2, $1/10$ est un développement infini périodique, exactement comme $1/3$ en base 10. La machine stocke donc une valeur voisine, et :

10.1 + 0.2 = 0.30000000000000004

Ce n'est pas un bogue, c'est un arrondi, et il est inévitable dans tout codage à précision finie. La conséquence est une règle absolue : on ne compare jamais deux flottants avec une égalité stricte. On teste que leur écart est inférieur à une tolérance. Et en informatique financière, on n'emploie pas de flottants du tout — on compte en centimes, avec des entiers.

Caractères : d'ASCII à Unicode

Un caractère est un nombre, et rien d'autre. La difficulté n'a jamais été technique, elle a été de se mettre d'accord sur la table.

ASCII (1963) code 128 caractères sur 7 bits : les chiffres à partir de 48, les majuscules à partir de 65, les minuscules à partir de 97. Deux détails qui servent en TD : l'écart majuscule → minuscule vaut exactement 32, soit un seul bit à basculer ; et le caractère '7' vaut 55, pas 7 — d'où le − '0' de toutes les conversions caractère vers chiffre.

ASCII ne connaît ni le é, ni le ß, ni le grec. Les pages de codes sur 8 bits, comme Latin-1, ont ajouté 128 caractères chacune, avec le résultat prévisible : un même octet signifiait autre chose d'une page à l'autre, et tout échange mal étiqueté produisait des é — c'est l'origine des accents cassés qu'on voit encore.

Unicode sépare enfin deux questions que tout le monde confondait. Il attribue à chaque caractère un point de code unique et abstrait (U+00E9 pour é), sans dire comment le stocker. Le stockage relève d'un encodage, et le dominant est UTF-8, à taille variable : 1 octet pour l'ASCII — qui reste donc valide tel quel —, 2 à 4 octets au-delà.

D'où une conséquence que le chapitre 7 du cours de systèmes retrouvera : en UTF-8, le nombre d'octets n'est pas le nombre de caractères. Le mot « été » occupe 5 octets pour 3 caractères. Couper une chaîne au milieu d'un caractère produit un octet invalide.

Images et sons : échantillonner puis quantifier

Le monde est continu, la machine discrète. Toute numérisation fait donc deux choses, et chacune perd de l'information.

Échantillonner, c'est découper : une image en pixels, un son en instants de mesure. Pour le son, le théorème de Shannon impose d'échantillonner à plus du double de la fréquence maximale à conserver — d'où les 44,1 kHz du disque compact, un peu plus du double des 20 kHz audibles.

Quantifier, c'est arrondir chaque échantillon sur un nombre fini de niveaux. La profondeur est ce nombre de bits : 8 bits par composante pour une image courante — d'où les 256 niveaux de rouge du #4f46e5 du chapitre 1 —, 16 bits par échantillon pour le CD.

Le calcul de taille en découle directement, et c'est l'exercice type :

1Image 1920 × 1080, 3 composantes de 8 bits2  1920 × 1080 × 3 = 6 220 800 octets ≈ 5,9 Mio par image, non compressée3 4Son stéréo, 44 100 Hz, 16 bits, 1 minute5  44 100 × 2 × 2 × 60 = 10 584 000 octets ≈ 10 Mio

Ces ordres de grandeur expliquent à eux seuls l'existence de la compression — et la distinction entre compression sans perte (PNG, FLAC), qui restitue l'original bit pour bit, et avec perte (JPEG, MP3), qui jette ce que la perception ne remarque pas.

À vous

L'exercice code le complément à deux sur 8 bits dans les deux sens, puis détecte le débordement signé. Les trois fonctions sont courtes ; ce qui compte est de faire tomber les cas limites, et ils sont volontairement présents dans le jeu de tests : $-128$, dont l'opposé n'existe pas, et $100+50$, qui déborde sans produire la moindre retenue sortante.

const N = 8;
const MODULO = 1 << N;          // 256
const MIN = -(1 << (N - 1));    // −128
const MAX = (1 << (N - 1)) - 1; // +127

const bits = (motif) => motif.toString(2).padStart(N, "0");

// Entier signé -> motif de N bits. Un négatif se code comme 2^N + x.
function coder(x) {
  if (x < MIN || x > MAX) return null;   // hors domaine : incodable
  return x < 0 ? MODULO + x : x;
}

// Motif de N bits -> entier signé.
function decoder(motif) {
  return motif;   // ← faux : cette lecture ignore le bit de signe
}

// Addition machine : on additionne, on tronque à N bits, et on regarde si
// le résultat SIGNÉ est celui attendu.
function additionner(a, b) {
  const brut = (coder(a) + coder(b)) % MODULO;
  return { motif: brut, valeur: decoder(brut) };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Corrigez decoder : si le bit de poids fort vaut 1, le motif code un
//    négatif, et sa valeur est motif − 2^N.
// 2. Écrivez deborde(a, b) : vrai si a + b sort de [MIN, MAX].
//    Indice : deux nombres de signes contraires ne débordent jamais.

function deborde(a, b) {
  return false;   // ← à écrire
}

const CAS = [
  { a: 5, b: -5 }, { a: 100, b: 50 }, { a: -100, b: -50 },
  { a: -128, b: 1 }, { a: 127, b: -1 }, { a: 60, b: 60 },
];

for (const { a, b } of CAS) {
  const r = additionner(a, b);
  const exact = a + b;
  const attendu = exact < MIN || exact > MAX;
  const marque = r.valeur === exact ? "  ok" : "  X débordement";
  const detecte = deborde(a, b) === attendu ? "" : "   (deborde() se trompe)";
  console.log(
    (a + " + " + b).padEnd(12) + "= " + String(r.valeur).padStart(5) +
    "  " + bits(r.motif) + marque + detecte
  );
}

console.log("opposé de -128 :", coder(128) === null ? "incodable sur 8 bits" : "?");

const N = 8;
const MODULO = 1 << N;
const MIN = -(1 << (N - 1));
const MAX = (1 << (N - 1)) - 1;

const bits = (motif) => motif.toString(2).padStart(N, "0");

function coder(x) {
  if (x < MIN || x > MAX) return null;
  return x < 0 ? MODULO + x : x;
}

function decoder(motif) {
  // Le bit de poids fort EST le bit de signe : s'il vaut 1, le motif code
  // le négatif motif − 2^N. C'est l'exacte réciproque de coder().
  return motif >= MODULO / 2 ? motif - MODULO : motif;
}

function additionner(a, b) {
  const brut = (coder(a) + coder(b)) % MODULO;
  return { motif: brut, valeur: decoder(brut) };
}

function deborde(a, b) {
  // Deux signes contraires ne peuvent pas déborder : la somme est comprise
  // entre les deux opérandes. Le débordement n'arrive donc que sur deux
  // nombres de même signe dont la somme change de signe.
  const s = a + b;
  if (a >= 0 !== b >= 0) return false;
  return s < MIN || s > MAX;
}

const CAS = [
  { a: 5, b: -5 }, { a: 100, b: 50 }, { a: -100, b: -50 },
  { a: -128, b: 1 }, { a: 127, b: -1 }, { a: 60, b: 60 },
];

for (const { a, b } of CAS) {
  const r = additionner(a, b);
  const exact = a + b;
  const attendu = exact < MIN || exact > MAX;
  const marque = r.valeur === exact ? "  ok" : "  X débordement";
  const detecte = deborde(a, b) === attendu ? "" : "   (deborde() se trompe)";
  console.log(
    (a + " + " + b).padEnd(12) + "= " + String(r.valeur).padStart(5) +
    "  " + bits(r.motif) + marque + detecte
  );
}

console.log("opposé de -128 :", coder(128) === null ? "incodable sur 8 bits" : "?");

En travaux pratiques

  5 = 0000 0101
inversion = 1111 1010
  + 1   = 1111 1011  ←  -5

vérification :
0000 0101   ( 5)
+ 1111 1011   (-5)
-----------
10000 0000   → tronqué à 8 bits → 0000 0000

sur 8 bits signés : de -128 à +127

-128 = 1000 0000
inversion = 0111 1111
    + 1 = 1000 0000  ←  -128 de nouveau !

en C : -INT_MIN est un comportement INDÉFINI

for (int i = 0; i > -1; i++) ;   /* boucle « tant que positif » */

gcc -O0 : s'arrête après 2 147 483 647 (retour à -2147483648)
gcc -O2 : ne s'arrête JAMAIS

/* le compilateur a le droit de supposer que le débordement
 signé n'arrive pas : il en déduit que i > -1 est toujours vrai */

float 0.1  →  0x3DCCCCCD
signe 0 | exposant 0111 1011 (123 → 123-127 = -4) | mantisse 1.6

valeur réelle stockée : 0.100000001490116119384765625

0.1 + 0.2 = 0.30000000000000004440892098500626
0.1 + 0.2 == 0.3  →  faux

/* la comparaison correcte */
if (fabs(a - b) < 1e-9) ...

« éléphant »  →  C3 A9 6C C3 A9 70 68 61 6E 74
                  ^^^^^      ^^^^^
                   é          é   : DEUX octets chacun

8 caractères, 10 octets

fichier coupé au milieu du é : é remplacé par  (octet invalide)

octet 0110 1001 → quatre 1 → bit de parité paire : 0

un bit inversé  : 0111 1001 → cinq 1  → parité 1 attendue → DÉTECTÉ
deux bits       : 0111 1101 → six 1   → parité 0 attendue → INVISIBLE

Ce que la suite en fait

Le complément à deux n'est pas qu'une convention d'écriture : c'est ce qui permet à une machine de n'avoir qu'un seul circuit d'addition pour additionner et soustraire. Le chapitre 4 construira ce circuit porte par porte, et l'on verra que soustraire revient à inverser une entrée et à forcer la retenue initiale à 1 — deux fils, pas un second additionneur.

Le chapitre 6 retrouvera tout le reste : l'extension de signe dans les instructions de chargement, la distinction signé/non signé dans les branchements, et les décalages qui multiplient par des puissances de deux. Et le domaine de valeurs, ici présenté sur 8 bits, deviendra celui du bus d'adresses au chapitre 5 : $2^{32}$ adresses, soit 4 Gio d'espace adressable — la vraie raison de la bascule vers le 64 bits.

À retenir