#Représentation de l'informationCopier le lien

Toute information manipulée par un ordinateur (texte, nombre, image, son) finit en suites de bits. Comprendre cet encodage, c'est pouvoir prédire ses limites: pourquoi un accent casse, pourquoi un compteur reboucle, pourquoi un fichier grossit.

Prérequis: aucun. Quelques divisions euclidiennes suffisent.

Objectifs d'apprentissage:

• Convertir un entier entre décimal, binaire et hexadécimal.
• Compter les motifs qu'un type peut représenter ($2^k$ sur $k$ bits) et en déduire ses bornes.
• Expliquer l'encodage UTF-8 et le coût variable des caractères.
• Prédire le comportement d'un entier borné (débordement) et d'un flottant (arrondi).
• Justifier pourquoi aucune représentation exacte des réels n'est possible sur une machine.
• Estimer la taille d'un texte ou d'une image à partir de sa représentation.

#Bases de numérationCopier le lien

Un nombre s'écrit en base B avec des chiffres de 0 à B-1; chaque position vaut une puissance de B:

1Décimal (base 10):  13 = 1×10 + 32Binaire (base 2):   13 = 1×8 + 1×4 + 0×2 + 1×1 = 11013Hexadécimal (base 16): 13 = D  (un chiffre hexa vaut 4 bits)

L'hexadécimal sert de sténo pour le binaire: chaque chiffre hexa correspond exactement à 4 bits, donc un octet s'écrit avec deux chiffres hexa. 1101 1011 devient DB. C'est pourquoi les adresses mémoire, les couleurs et les empreintes s'affichent en hexa.

#Conversion par divisions euclidiennesCopier le lien

Pour convertir n en base B: diviser n par B, empiler les restes, lire de bas en haut.

113 en base 2:213 ÷ 2 = 6 reste 1   ↑3 6 ÷ 2 = 3 reste 0   ↑4 3 ÷ 2 = 1 reste 1   ↑5 1 ÷ 2 = 0 reste 1   ↑6Résultat lu de bas en haut: 1101

Vérification inverse: 1×8 + 1×4 + 0×2 + 1×1 = 13. Toute conversion se vérifie ainsi, dans les deux sens.

#Entiers bornés et débordementCopier le lien

Sur n bits non signés, on code les valeurs de 0 à 2^n - 1. Sur 8 bits: de 0 à 255. Ajouter 1 à 255 donne 0: la retenue sortante est perdue, la valeur « reboucle » (arithmétique modulo 256).

1   retenue : 1 1 1 1 1 1 1 12   a      : 1 1 1 1 1 1 1 1   (255)3   b      : 0 0 0 0 0 0 0 1   (1)4   ------------------------5   somme  : 0 0 0 0 0 0 0 0   (0, retenue perdue)

Python n'a pas ce problème sur les entiers (précision arbitraire), mais le C, le Java et la plupart des langages système si. Les conséquences sont réelles: un débordement de compteur peut fausser un instrument, faire échouer un système à une date donnée ou casser une clé de sécurité.

#Compter les mots binairesCopier le lien

Les bases de numération ne servent pas seulement à écrire des nombres: elles permettent de compter les représentations possibles, et donc de connaître la capacité exacte d'un type machine. Le principe est le même que celui d'un arrangement avec répétition: si l'on choisit un symbole parmi $n$ à chacune de $p$ positions, indépendamment, le nombre de mots obtenus est $n^{p}$.

Sur l'alphabet binaire $\{0,1\}$ ($n = 2$):

• il y a $2^{p}$ mots de longueur exactement $p$;
• il y a $2^{p+1} - 1$ mots de longueur au plus $p$ (la somme $1 + 2 + 4 + \dots + 2^{p}$);
• un octet, mot de 8 bits, admet donc $2^{8} = 256$ motifs distincts.

La longueur de la représentation binaire d'un entier $n \ge 1$ se déduit de ce comptage. Les mots de longueur $k$ couvrent les valeurs de $2^{k-1}$ à $2^{k}-1$; le nombre de chiffres de $n$ est donc

$\lvert b_n \rvert = \lfloor \log_2 n \rfloor + 1.$

Ainsi $13 = 1101_2$ a $\lfloor \log_2 13 \rfloor + 1 = 3 + 1 = 4$ chiffres. Retenez la borne qui en découle: avec $k$ bits on ne peut nommer que $2^{k}$ objets distincts. C'est cette borne qui rend le principe des tiroirs si efficace pour prouver qu'un encodage est impossible (voir les annales corrigées).

#Capacité des types machineCopier le lien

Cette borne de $2^{k}$ explique les intervalles de valeurs des types des langages compilés. Un int Java est codé sur 4 octets, donc sur 32 bits, et dispose de $2^{32} = 4\,294\,967\,296$ motifs distincts — environ 4,3 milliards. Un long (8 octets, 64 bits) en dispose de $2^{64} \approx 1{,}8 \times 10^{19}$.

C'est cette capacité finie qui produit les deux pathologies vues plus haut. Pour les entiers, $2^{32}$ motifs ne suffisent pas à contenir $\mathbb{N}$: au-delà de la borne, la valeur reboucle. Pour les flottants, $2^{64}$ motifs ne suffisent pas à contenir $\mathbb{R}$ — et cette fois aucune astuce d'implémentation ne peut y remédier, pour une raison mathématique que la section suivante expose.

#Flottants: des approximationsCopier le lien

Un flottant stocke signe, mantisse et exposant en base 2; la plupart des décimaux n'y sont pas exacts:

1print(0.1 + 0.2)          # 0.300000000000000042print(0.1 + 0.2 == 0.3)   # False

Conséquence pratique: ne jamais comparer des flottants par égalité; comparer un écart à une tolérance (abs(a - b) < 1e-9), ou compter en entiers (centimes) quand l'exactitude importe.

#Pourquoi l'approximation est inévitableCopier le lien

On pourrait croire à un défaut d'implémentation, corrigible avec assez de bits. Il n'en est rien. Un double ne dispose que de $2^{64}$ motifs, donc ne peut distinguer au plus que $2^{64}$ nombres réels. Or l'intervalle $[0,1]$ contient une infinité non dénombrable de réels: aucune application injective ne peut aller de $\mathbb{R}$ vers un ensemble de $2^{64}$ motifs, par le principe des tiroirs. Toute représentation des réels sur une machine confond donc nécessairement deux réels distincts.

Autrement dit, un encodage exact des réels exigerait un nombre infini de bits — et un ordinateur ne manipule que des mots finis. C'est la raison de fond pour laquelle les flottants sont une convention d'approximation (IEEE 754), et non une représentation fidèle. La démonstration complète de la non-dénombrabilité de $\mathbb{R}$ est faite dans les annales corrigées.

#Encodage du texte: UTF-8Copier le lien

Un caractère est un point de code Unicode; UTF-8 l'encode sur un nombre variable d'octets (1 à 4) selon sa plage: ASCII sur 1 octet, accents européens sur 2, idéogrammes courants sur 3, émojis sur 4.

#L'erreur classique: couper au milieu d'un caractèreCopier le lien

1s = 'été'                  # 3 caractères2b = s.encode('utf-8')      # 5 octets: é(2) + t(1) + é(2)3print(list(b))             # [195, 169, 116, 195, 169]4try:5    print(b[:4].decode('utf-8'))   # on garde 4 octets sur 56except UnicodeDecodeError as e:7    print('décodage invalide:', e)

Les deux derniers octets (195, 169) forment le « é » final; n'en garder qu'un seul laisse une séquence incomplète et le décodage échoue. En revanche b[:3] donne b'\xc3\xa9t', qui se décode sans erreur en 'ét' — la coupe tombe alors exactement sur une frontière de caractère. C'est le bug des programmes qui tronquent des octets en croyant tronquer des caractères: la troncature n'échoue que si elle tombe au milieu d'une séquence, et un len exprimé en octets ne dit pas où sont ces frontières.

#Images et sons: même principeCopier le lien

Une image numérique est une grille de pixels; chaque pixel est un triplet (ou quadruplet) de composantes. Une image 1920×1080 en RGBA (4 octets par pixel) non compressée: 1920 × 1080 × 4 = 8 294 400 octets, environ 8 Mo. Les formats PNG et JPEG réduisent cette taille par compression, avec ou sans perte, mais la donnée de départ est cette grille. Le son suit la même logique: un échantillon toutes les 1/44100 seconde, 16 bits par échantillon, deux canaux.

#Codage: ce que le mot désigne exactementCopier le lien

Passer d'un objet à sa représentation binaire porte un nom précis. Un codage d'un alphabet $A$ dans un alphabet $B$ est une application injective de $A^{+}$ (les mots non vides sur $A$) dans $B^{+}$. L'injectivité est la condition non négociable: deux objets différents doivent recevoir deux codes différents, sans quoi le décodage serait ambigu.

Quelques codages usuels:

• la représentation binaire d'un entier naturel, de l'ensemble des entiers vers les mots sur $\{0,1\}$;
• le code Morse, de l'alphabet latin vers les mots sur $\{-,.\}$;
• le codage en base $b$, qui associe à un mot sur un alphabet de lettres sa représentation dans $\{0,\dots,b-1\}$.

Cette distinction entre « le code identifie l'objet » et « le code se relit tout seul » est la même que celle qui sépare l'injectivité de la bijectivité. Elle explique pourquoi UTF-8 a été conçu avec des octets de continuation reconnaissables (le préfixe 10): la synchronisation perdue au milieu d'un flux se retrouve, et une coupe accidentelle ne peut pas être confondue avec un caractère valide.

#Quiz éclairCopier le lien

#ExercicesCopier le lien

1. Conversion à la main. Convertissez 45 en binaire et en hexadécimal par divisions euclidiennes. Attendu: 101101 et 2D. Vérifiez avec bin(45) et hex(45).
2. Taille d'un texte. Estimez le nombre d'octets de la chaîne 'café à côté' en UTF-8, puis vérifiez avec len(s.encode('utf-8')). Justifiez le décompte caractère par caractère.
3. Compteur 8 bits. Écrivez un compteur 8 bits qui part de 250 et affiche les 8 valeurs suivantes en simulant l'arithmétique modulo 256. Attendu: 250..255 puis 0, 1.
4. Choix de comparaison. Expliquez pourquoi total == 0.3 est un test fragile et écrivez la version robuste.
5. Capacité d'un champ. Une base de données stocke un identifiant sur 12 bits. Combien d'objets distincts peut-elle nommer ? Que se passe-t-il à l'objet suivant ?
6. Longueur binaire. Combien de chiffres binaires faut-il pour écrire 1000 ? Vérifiez avec la formule $\lfloor \log_2 n \rfloor + 1$ puis avec len(bin(1000)) - 2.

#CorrectionsCopier le lien

145 ÷ 2 = 22 r 1 ↑        45 ÷ 16 = 2 r 13 (D) ↑222 ÷ 2 = 11 r 0 ↑311 ÷ 2 =  5 r 1 ↑         2 ÷ 16 = 0 r 2 ↑4 5 ÷ 2 =  2 r 1 ↑5 2 ÷ 2 =  1 r 0 ↑         hexa: 2D6 1 ÷ 2 =  0 r 1 ↑7binaire: 101101

1s = 'café à côté'2print(len(s))                    # 11 caractères3print(len(s.encode('utf-8')))    # 15 octets

1compteur = 2502for _ in range(8):3    print(compteur)4    compteur = (compteur + 1) % 2565# Sortie: 250 251 252 253 254 255 0 1

1assert abs(total - 0.3) < 1e-9