Annexe F Quelques précisions sur le codage

Pour ceux qui souhaitent approfondir leur compréhension du codage interne des données, nous donnons dans ce chapitre quelques informations complémentaires¹.

Les ordinateurs, comme les humains, ont besoin de "parler le même langage" pour pouvoir échanger des données. Dans les temps héroïques des premiers ordinateurs, chaque constructeur de machine choisissait ses propres codages pour les données à traiter et à stocker. Mais dès qu'on a commencé à échanger des fichiers de données entre différentes machines, il s'est avéré nécessaire de fixer des normes de représentation. Quand la norme concerne même la représentation interne des données (voir par exemple la norme IEEE 754 décrite ci-après), elle permet de plus la conception de circuits de calcul indépendants qui viennent s'ajouter de manière modulaire à l'ordinateur (co-processeurs de calcul intensif, cartes graphiques...)

F.1 Le codage des caractères

Les premiers ordinateurs étaient américains et les données textuelles échangées étaient en anglais. On a très vite vu émerger la norme ASCII², qui fixe le codage des caractères sur 7 bits, ce qui permet donc 128 positions, dans l'intervalle [0,127]. L'octet (byte en anglais) -- ensemble de 8 bits -- étant une entité de base en informatique, cela laissait l'intervalle [128,255] à la disposition des concepteurs ; certains ont utilisé ces positions pour des codes graphiques, d'autres -- et notamment les européens -- pour coder leurs caractères nationaux (é, è, ç, å, ø, ß, ñ, etc.)

L'internationalisation a ensuite imposé une normalisation des positions entre 128 et 255 également ; mais on se heurte déjà là à la diversité des situations : on ne peut pas "caser" sur 128 positions l'alphabet cyrillique, l'alphabet hébreu, l'alphabet grec, les caractères particuliers des différentes langues, les signes monétaires courants, etc. C'est ainsi qu'est apparue la norme ISO 8859, déclinée en plusieurs variantes ; pour l'Europe occidentale, c'est-à-dire ce qui nous concerne, la norme s'appelle ISO 8859-1, également appelée ISO-Latin-1. Elle reprend le codage ASCII de 0 à 127, et fixe les caractères correspondant aux positions 128 à 255³.

Mais 256 positions ne suffiront jamais si on veut être capable de coder de manière uniforme tous les alphabets, y compris les idéogrammes orientaux. À l'ère de la mondialisation, il apparaît donc nécessaire d'étendre l'espace de codage, c'est pourquoi la norme Unicode a vu le jour. Celle-ci code chaque caractère sur 2 octets, soit 16 bits, ce qui donne 65 536 positions possibles ! Pour l'instant, seules 34 168 positions ont été attribuées, il reste donc de la place pour les extra-terrestres...

Java est le premier langage de programmation -- à ma connaissance -- qui a choisi Unicode comme codage interne de ses caractères. Un programme en Java peut donc avoir des variables qui portent des noms japonais et qui sortent des messages d'erreur en russe ; ce programme compilera et s'exécutera sur votre ordinateur français (mais évidemment, pour que vous puissiez visualiser le code source du programme et les messages d'erreur sur votre écran, il faudra que vous installiez des polices de caractères japonaises et cyrilliques sur votre ordinateur).

Rassurez-vous quand même :

Dans ce cours, nous nous limitons à des noms et à des messages en français... and maybe in english.
Coder du français en Unicode, c'est coder en ISO-Latin-1 en intercalant à chaque fois un octet de valeur 0 -- en d'autres termes, les 256 premières positions du codage Unicode correspondent au codage ISO-Latin-1.
De toute façon, Java a prévu les filtres permettant de lire des fichiers où les caractères sont codés sur 8 bits, de convertir les données en interne en caractères sur 16 bits, et de sauvegarder à nouveau en 8 bits (cf. § 6.3.2).

F.2 Le codage des entiers

Les entiers regroupent les types byte, short, int et long. Le type de codage employé est le même, au nombre d'octets utilisés près. Plus précisement :

1 octet pour les byte ® [-128,+127]
2 octets pour les short ® [-32768,+32767]
4 octets pour les int ® [-2³¹,+2³¹-1]
8 octets pour les long ® [-2⁶³,+2⁶³-1]

Quand on code des entiers signés, il faut choisir la manière de représenter les nombres négatifs. Java code les entiers en complément à 2. Il est plus simple cependant de voir d'abord les autres formes de codage, pour comprendre l'intérêt du complément à 2.

F.2.1 Codage avec bit de signe

Dans la mesure où on manipule des entiers signés, la technique la plus simple serait d'avoir un bit de signe. Si le premier bit est 0, on a un entier positif, si c'est 1, on a un entier négatif.

Le problème est qu'on a alors une arithmétique compliquée : a + (-b) ne se calcule pas comme a - b.

F.2.2 Le complément à un

Pour simplifier l'arithmétique, on peut employer le complément à un. Pour un entier positif, on ne change rien ; pour un entier négatif, on inverse tous les bits. Exemple :

8	®	0000 1000
-8	®	1111 0111

On a donc le premier bit à 0 pour les positifs et le premier bit à 1 pour les négatifs. Pour additionner, on fait l'addition binaire et si on a une retenue, on l'ajoute au résultat.

Exemple :

0001 0001

(17)

1111 0111

(-8)

1 0000 1000

(retenue)

0000 1001

(9)

Problème : on a toujours deux représentations de zéro !

F.2.3 Le complément à deux

On représente toujours de la même manière les nombres positifs. En revanche, les nombres négatifs sont représentés par le complément à un auquel on ajoute 1.

Exemple :

8	®	0000 1000
-8	®	1111 0111 + 1 = 1111 1000

Remarque :

+0	®	0000 0000
-0	®	1111 1111 + 1 = 0000 0000

On n'a donc plus cette fois-ci qu'un seul zéro.

Exemple d'addition (on ne tient pas compte du bit qui sort en débordement sur la gauche) :

0001 0001

(17)

1111 1000

(-8)

0000 1001

(9)

Pour ceux que cela amuse, formellement, étant donné un entier en binaire :

b_n b_n-1 ··· b₀, sa valeur est :

(

n-1

i=0

b_i.2ⁱ) - b_n.2ⁿ

d'où le nom de complément à 2 ; en toute rigueur, c'est un complément à 2ⁿ.

Comme déjà précisé, tous les types entiers sont représentés en Java en complément à 2.

F.3 Le codage des réels

Les nombres flottants, utilisés pour représenter les réels, sont en fait des décimaux ; dans un univers numérique (tout du moins dans un univers numérique qui veut rester simple), on n'a pas de nombres en précision infinie.

Pour représenter les flottants, on emploie la norme IEEE 754. Dans une première étape, on considère les nombres décimaux comme :

N = (-1)^s.m.2^e

Avec s le signe, m la mantisse, e l'exposant. C'est la même chose qu'en base 10, avec bien sûr des puissances de 2 plutôt que des puissances de 10.

On normalise ensuite cette représentation en imposant à la mantisse d'être comprise entre 1 et 2 (c'est ce qu'on fait en base 10 en imposant à la mantisse d'être entre 1 et 10).

Puisque la mantisse commence alors forcément par 1, on n'a pas besoin de représenter le dit 1.

Remarque : on n'a pas de représentation de 0.

F.3.1 IEEE 754 pour les `float`

La norme IEEE 754, employée par Java, normalise simplement :

la taille prise pour représenter la mantisse et l'exposant,
une représentation de 0,
des représentations pour +¥ et -¥ et les débordements (comme après une division par 0 par exemple).

Dans le cas des float (32 bits), on a :

le signe dans b₃₁ (le bit le plus à gauche),
l'exposant dans b₃₀--b₂₃ ce qui donne 8 bits,
la mantisse dans le reste : b₂₂--b₀.

L'exposant est représenté en ajoutant 127 (ce qui permet de balayer de -127 à +127).

De plus, conventionnellement, on a :

0 est représenté par exposant = mantisse = 0.
¥ est représenté par exposant = 255 (des 1 partout) et mantisse = 0. Le bit de signe distingue entre +¥ et -¥.
exposant = 255 et mantisse ¹ 0 désigne un débordement dans une opération précédente, et est généralement appelé NaN (not a number).

Pour ceux qui nous suivent encore, un dernier exemple :

on veut coder 17.15.

17 en base 2 ® 10001

0.15 en base 2 ® 0.00 (1001) (1001) ···

17.15 ® 10001.00 (1001) (1001) ···

on normalise : 17.15 = 1.000100 (1001) (1001) ··· × 2⁴

On a donc une mantisse M = 000100 (1001) (1001) ··· (on ne représente pas le 1 "implicite").

L'exposant est représenté par E = e+127 = 131 = 1000.0011. Le nombre est positif donc s = 0.

Tout cela mis ensemble nous donne :

10000011

^exposant

000100 (1001) (1001) (1001) (1001) 1

^mantisse

F.3.2 IEEE 754 pour les `double`

Pour les double, c'est pareil, sauf que l'exposant est codé sur 11 bits et la mantisse sur 52 bits, ce qui nous donne bien 64 bits avec le bit de signe.

1: Merci à Bertrand Gaiffe, qui a rédigé une première version de cette "digression" relative au codage, en s'inspirant en partie de notes de cours trouvées sur le Web.
2: American Standard Code for Information Interchange.
3: Malheureusement pour nous, les grandes entreprises américaines, notamment Microsoft, ne respectent pas toujours cette norme, d'où les soucis qu'on a parfois sur le codage de certains caractères, quand on échange des fichiers entre le monde Microsoft et le monde Unix, par exemple.