Représentation des données et codage

Coder une information, c'est choisir une façon de la représenter à l'aide de symboles élémentaires — en informatique, des bits. On appelle encodage l'opération qui transforme une donnée (un nombre, un caractère...) en une suite de bits selon une règle précise, et décodage l'opération inverse, qui retrouve la donnée d'origine à partir de cette suite de bits. Cette page reprend le vocabulaire des principaux systèmes de codage utilisés en machine : entiers, réels et texte.

Bit, octet et bases de numération

Le bit et l'octet

Un bit (binary digit, chiffre binaire) est la plus petite unité d'information en informatique : il ne peut prendre que deux valeurs, $0$ ou $1$. Un octet (en anglais byte) est un groupement de 8 bits ; il permet de représenter $2^8 = 256$ valeurs différentes, soit les entiers naturels de $0$ à $255$.

Les capacités de mémoire ou de stockage se mesurent en multiples de l'octet : un kilooctet (Ko) vaut environ mille octets, un mégaoctet (Mo) environ un million d'octets, et ainsi de suite.

Un système positionnel : la base b

Le système décimal que nous utilisons au quotidien est un système positionnel en base 10 : la valeur d'un chiffre dépend de sa position. Par exemple, $274$ signifie $2 \times 10^2 + 7 \times 10^1 + 4 \times 10^0$.

On peut construire le même type de système dans n'importe quelle base $b \geqslant 2$, en n'utilisant que $b$ symboles (de $0$ à $b-1$) :

• en base 2 (binaire), on n'utilise que $0$ et $1$ : c'est la base utilisée en interne par les ordinateurs, car un bit ne connaît que deux états ;
• en base 16 (hexadécimal), on utilise seize symboles, $0$ à $9$ puis $A$ (dix) à $F$ (quinze) : deux chiffres hexadécimaux codent exactement un octet, ce qui rend cette base pratique pour écrire des valeurs binaires de façon compacte.

Exemple. Le nombre $2A_{16}$ vaut $2 \times 16^1 + 10 \times 16^0 = 32 + 10 = 42$ en décimal.

Convertir un entier d'une base à une autre

Pour convertir un entier d'une base $b$ vers la base 10, on multiplie chaque chiffre par la puissance de $b$ correspondant à sa position, puis on additionne — comme dans l'exemple précédent.

Pour convertir un entier décimal vers une base $b$, on effectue une suite de divisions euclidiennes par $b$ : le résultat est la juxtaposition des restes obtenus, lus du dernier au premier.

Exemple. Convertissons $45$ en base $3$.

En lisant les restes du dernier au premier : $45 = 1200_3$. Vérification : $1\times 27 + 2\times 9 + 0\times 3 + 0\times 1 = 27+18 = 45$.

Exemple. Convertissons $500$ en base $16$.

En lisant les restes du dernier au premier (le reste $15$ s'écrit $F$) : $500 = 1F4_{16}$. Vérification : $1\times 256 + 15\times 16 + 4\times 1 = 256+240+4 = 500$.

Cet algorithme se programme directement en Python, en généralisant à une base $b$ quelconque (inférieure ou égale à 10, pour rester avec des chiffres simples) :

def entier_vers_base(n, b):
    """Renvoie l'ecriture de l'entier naturel n en base b (b <= 10), sous forme de chaine"""
    if n == 0:
        return "0"
    chiffres = ""
    while n > 0:
        chiffres = str(n % b) + chiffres
        n = n // b
    return chiffres
 
print(entier_vers_base(45, 3))    # "1200"

Combien de bits faut-il pour coder un entier naturel $N$ ? Avec $n$ bits, on représente les entiers de $0$ à $2^n - 1$ (soit $2^n$ valeurs). Il faut donc le plus petit $n$ tel que $2^n - 1 \geqslant N$.

Coder les entiers relatifs : le complément à deux

Le problème du signe

Un entier relatif peut être négatif : il faut coder à la fois sa valeur absolue et son signe. Une idée naïve consisterait à réserver le bit de poids fort comme bit de signe ($0$ pour $+$, $1$ pour $-$) ; mais cette approche a deux défauts : le nombre $0$ possède alors deux écritures ($+0$ et $-0$), et l'addition binaire habituelle ne fonctionne plus dès qu'un des deux opérandes est négatif.

Le complément à deux

La solution retenue par tous les ordinateurs actuels est le complément à deux. Pour coder un entier négatif $-N$ (avec $N>0$) sur $n$ bits :

1. écrire $N$ (sa valeur absolue) en binaire sur $n$ bits ;
2. inverser tous les bits (les $0$ deviennent des $1$ et inversement) : c'est le complément à un ;
3. ajouter $1$ au résultat (en ignorant une éventuelle retenue finale).

Exemple. Codons $-100$ sur 8 bits.

1. $100 = 01100100_2$
2. Complément à 1 : $10011011$
3. On ajoute 1 : $10011100$

Donc $-100$ se code $10011100$ sur 8 bits. Pour décoder, on applique la règle inverse : si le bit de poids fort vaut $1$, le nombre est négatif, et on lui applique de nouveau le complément à deux (inverser les bits puis ajouter 1) pour retrouver sa valeur absolue. Vérification : à partir de $10011100$, complément à 1 donne $01100011$, puis $+1$ donne $01100100 = 100$ ; le nombre codé est donc bien $-100$.

Avec $n$ bits en complément à deux, on représente les entiers relatifs de $-2^{n-1}$ à $2^{n-1}-1$. Sur 8 bits : de $-128$ à $127$.

Dépassement de capacité

Un dépassement de capacité (overflow) se produit quand le résultat d'une opération sort de l'intervalle représentable sur le nombre de bits disponible : le calcul « déborde », un bit est perdu, et le résultat obtenu n'a plus de sens.

Exemple. Sur 8 bits (intervalle $-128$ à $127$), additionnons $127$ ($01111111_2$) et $1$ ($00000001_2$) :

Mathématiquement, $127+1=128$, une valeur qui n'est pas représentable sur 8 bits signés. Le résultat binaire obtenu, $10000000$, est bien tronqué à 8 bits ; en le décodant selon la règle du complément à deux (bit de poids fort à $1$, donc négatif ; complément à 1 : $01111111$, puis $+1$ : $10000000$, qui vaut $128$ en binaire non signé), on trouve $-128$. Le calcul a donc débordé et produit $-128$ au lieu de $128$. C'est ce type de dépassement qui peut provoquer des bugs silencieux dans un programme manipulant des entiers de taille fixe.

Coder les nombres réels : la norme IEEE 754

Un nombre à virgule flottante ne peut pas toujours être représenté exactement en binaire avec un nombre fini de bits, tout comme $1/3$ n'a pas d'écriture décimale finie. La norme IEEE 754 définit une façon standard de coder une valeur approchée d'un nombre réel sur un nombre fixe de bits, en le décomposant en trois parties : le signe, l'exposant et la mantisse.

En simple précision (32 bits) :

• le signe : $0$ pour un nombre positif, $1$ pour un nombre négatif ;
• l'exposant, codé avec un biais de $2^7-1 = 127$ (on ajoute $127$ à l'exposant réel avant de le coder en binaire), ce qui permet de représenter aussi bien des exposants négatifs que positifs sans bit de signe séparé ;
• la mantisse : les chiffres après la virgule du nombre une fois écrit sous forme normalisée $1{,}\ldots \times 2^e$ (le chiffre « 1, » initial n'est jamais stocké, car il est toujours présent).

Exemple. Codons $5{,}75$.

1. En binaire : $5 = 101_2$ et $0{,}75 = 0{,}11_2$ (car $0{,}75\times 2 = 1{,}5$ donne le chiffre 1 avec un reste $0{,}5$, puis $0{,}5\times 2=1{,}0$ donne le chiffre 1 et s'arrête), donc $5{,}75 = 101{,}11_2$.
2. Forme normalisée : $101{,}11_2 = 1{,}0111 \times 2^2$.
3. Exposant codé : $127+2 = 129 = 10000001_2$.
4. Mantisse (23 bits, complétée par des zéros) : $01110000000000000000000$.
5. Signe : $0$ (positif).

Résultat : $0\ 10000001\ 01110000000000000000000$.

Cette représentation étant approchée, deux calculs mathématiquement égaux peuvent donner des résultats légèrement différents en machine :

print(0.1 + 0.2)          # affiche 0.30000000000000004
print(0.1 + 0.2 == 0.3)   # affiche False

$0{,}1$ n'a pas d'écriture binaire finie (comme $1/3$ n'a pas d'écriture décimale finie) : il est arrondi lors de son codage IEEE 754, et cet arrondi se propage dans les calculs. C'est pourquoi on évite de comparer deux flottants avec ==, et qu'on préfère vérifier qu'ils sont proches à une tolérance près (avec math.isclose, par exemple).

Coder du texte : ASCII, Unicode, UTF-8

Le code ASCII et son extension

Pour représenter du texte en machine, il faut associer un nombre à chaque caractère : c'est l'encodage. La norme ASCII (American Standard Code for Information Interchange) associe à chaque caractère un nombre codé sur 7 bits, soit $2^7 = 128$ caractères possibles. Les fonctions Python ord et chr permettent de passer d'un caractère à son code et inversement :

ord("S")   # 83
chr(83)    # "S"

L'ASCII a été conçu pour l'anglais et ne comporte aucun caractère accentué. Des normes comme ISO-8859-1 l'ont étendu sur 8 bits (256 caractères) pour ajouter les caractères accentués d'Europe occidentale (é, à, ç...).

Unicode et l'encodage UTF-8

Unicode va beaucoup plus loin : il attribue un numéro (un « point de code ») à des dizaines de milliers de caractères, couvrant la quasi-totalité des systèmes d'écriture du monde. Unicode définit quels numéros correspondent à quels caractères, mais pas comment les stocker en mémoire sous forme d'octets : c'est le rôle d'un encodage.

UTF-8 est l'encodage d'Unicode le plus répandu, notamment sur le Web. Son principe : chaque caractère est codé sur un nombre variable d'octets (de 1 à 4) selon son point de code.

• les caractères ASCII (points de code de $0$ à $127$) sont codés sur un seul octet, identique à leur code ASCII : UTF-8 reste donc compatible avec l'ASCII ;
• les autres caractères sont codés sur 2, 3 ou 4 octets.

Exemple. Le caractère « é » a pour point de code Unicode $233$ (noté U+00E9). Comme $233 > 127$, il ne tient pas sur un seul octet en UTF-8 : il est codé sur deux octets, 0xC3 0xA9.

Décoder, c'est l'opération inverse de l'encodage : retrouver la suite de caractères à partir d'une suite d'octets, en sachant quel encodage a été utilisé. Un même fichier texte peut être enregistré avec des encodages différents ; l'ouvrir avec le mauvais encodage produit des caractères mal affichés. En Python, on précise l'encodage utilisé lors de l'ouverture d'un fichier :

with open("texte.txt", encoding="utf-8") as f:
    contenu = f.read()