Codage des valeurs numériques

La plupart des personnes ayant déjà entendu les mots "ordinateur" et "numérique" savent que l'information est représentée dans la mémoire d'un ordinateur par des nombres, codés sous la forme d'une suite de "0" et de "1".

Pour représenter à l'aide d'un "alphabet" aussi simple et limité des types de variables aussi différents qu'un nombre réel, un mot, une image, un cours d'informatique... il faut utiliser des méthodes de codage de l'information. Ce chapitre a pour objectif d'étudier le codage des différents types de valeurs numériques : entiers positifs, entiers signés, réels.

Codage des entiers positifs

Codage en base deux

Nous avons l'habitude de coder en base dix, en utilisant dix symboles différents (les chiffres de 0 à 9), codage auquel nous sommes si habitués que nous l'interprétons sans même réfléchir. Ce n'est pourtant pas un système allant de soi , et nous connaissons au moins un autre système de représentation des nombres différent, le système romain. Il n'est pas inutile avant de présenter le codage binaire, d'analyser ce que nous faisons lorsque nous interprétons des entiers codés en base dix.

La base dix est une numération de position : un chiffre figurant dans l'écriture d'un nombre ne représente pas la même valeur selon l'endroit où il est placé dans le nombre. Par exemple dans le nombre qui s'écrit 232 en base 10, le chiffre 2 placé tout à droite représente la valeur 2, alors que celui placé tout à gauche représente la valeur 200.

On dira qu'un digit (c'est ainsi qu'on appelle les chiffres figurant dans la représentation d'un nombre) n'a pas le même poids suivant sa position dans le nombre.
En base dix, les poids respectifs des digits, de la droite vers la gauche, sont 1, 10, 100, 1000... c'est à dire 10⁰, 10¹,10²,10³...

Autrement dit si p est le rang du digit à partir de la droite, en commençant à la valeur 0, alors le poids de ce digit est 10^p. La valeur d'un nombre comme 232 se détermine en faisant la somme sur tous les digits du produit de la valeur v du digit par son poids 10^p.
Par exemple 232 = 2 x 10⁰ + 3 x 10¹ + 2 x 10²

Cette représentation des valeurs entières est bien un codage : il faut connaître la règle pour pouvoir la déchiffrer, même si nous y sommes si habitués que nous ne le réalisons plus!
Ce codage en base dix nécessite de disposer de dix symboles différents pour représenter les 10 entiers positifs inférieures à 10¹. Lorsqu'on veut coder une valeur supérieure ou égale à 10¹, on doit utiliser plus d'un symbole (un "digit") : deux digits pour écrire toutes les valeurs telles que 10¹ ≤ valeur < 10², trois digits pour écrire toutes les valeurs telles que 10² ≤ valeur < 10³, etc...

Que se passe-t-il alors si on ne dispose que de deux symboles différents pour représenter des chiffres, le 0 et le 1 ? Il n'est plus possible de coder les valeurs en base dix, mais on peut le faire en base deux, en utilisant exactement le même principe de la numération de position.
Les poids respectifs des digits, en partant de la droite, sont les puissances de deux successives : 2⁰, 2¹, 2², 2³, 2⁴ ... soit 1,2,4,8,16.... en base 10, ou 1,10,100,1000,10000... en base deux.

Soit par exemple le nombre qui s'écrit en base deux 110110. Pour déterminer sa valeur en base dix, on va faire la somme de chacun des digits qui le composent multipliés par leurs poids respectifs.

digits	1	1	0	1	1	0
poids	25(32)	24(16)	23(8)	22(4)	21(2)	20(1)
valeur	1 × 32  +  1 × 16  +  0 × 8  +  1 × 4  +  1 × 2  +  0 × 1
=  54

Quelques propriétés à connaître

• L'écriture en base 2 d'un nombre pair se termine forcément par un 0 (et par 1 pour un nombre impair).
• Pour multiplier par 2 un nombre écrit en base 2, il suffit de décaler tous ses digits d'un rang vers la gauche, et d'ajouter un 0 à la fin.
  Pour multiplier par 2ⁿ, il suffit donc de décaler tous ses digits de n rang vers la gauche, et d'ajouter n 0 à la fin.
  En Python l'opérateur << permet ainsi de décaler n fois vers la gauche un nombre entier en ajoutant des 0 à la fin.
  y=x<<n avec n entier donne le même résultat que y=x*2**n, mais plus rapidement.
  
• De même, pour faire une division entière par 2, on effectue un décalage d'un rang de tous les digits vers la droite. Le digit le plus à droite, qui constitue le reste de la division, est éliminé.
  Pour diviser par 2ⁿ, il suffit donc de décaler tous les digits de n rang vers la droite,
  En Python y=x>>n avec n entier donne le même résultat que y=x//2**n
  L'exécution de ces opérations de décalage par la machine est extrêmement rapide, car très simple à effectuer.

Taille des données

L'octet et ses multiples

La question de la taille des données se pose souvent : cette taille peut être exprimée en nombre de digits, ou nombre de bits (le mot bit est une contraction de binary digit, digit binaire).

En effet la plus grande valeur qu'on puisse coder sur n bits, s'écrit avec n "1" successifs.
Si on ajoute 1 à ce nombre, on est obligé d'utiliser un digit supplémentaire à gauche et on obtient un "1" suivi de n "0", soit 2ⁿ . Le nombre représenté par n"1" successifs vaut donc bien 2ⁿ - 1.

Exemple : sur 5 bits on peut écrire les valeurs de 0 à 11111 en base deux, c'est à dire de 0 à 31 en base dix, ce qui fait bien 2⁵=32 valeurs allant de 0 à 2⁵ - 1.

Les multiples usuels de l'octet, selon la norme actuellement en vigueur, sont :
• le kilooctet (ko) : 10³ octets
• le mégaoctet (Mo) : 10⁶ octets
• le gigaoctet (Go) : 10⁹ octets
• le téraoctet (To) : 10¹² octets
etc.

Evaluation de la taille d'une valeur en binaire

Il peut être utile d'évaluer le nombre de bits nécessaire pour coder une valeur donnée, ou le résultat d'un calcul, sans avoir à rechercher leur écriture en binaire.

Exemple : quel est la taille en binaire du nombre qui s'écrit 8653 en base 10 ? Aide: table des puissances de 2(cliquer pour afficher ou masquer)
Réponse : 8653 appartient à l'intervalle [2¹³ ; 2¹⁴[ . La taille de cette donnée en binaire est donc 14 bits.

Il est également possible de déterminer la taille en bits d'un entier positif p en utilisant la fonction log₂(p).
On peut calculer la taille en bits de p ainsi :
- calculer log₂(p)
- prendre la partie entière (troncature) du résultat et lui ajouter 1

Pour calculer la valeur de log₂(x), on peut utiliser la fonction Python log2 de la bibliothèque math. ou bien chercher la fonction logarithme à base 2 dans le menu de la calculatrice. Autre possibilité avec une des deux fonctions log disponibles par les touches de la calculatrice : utiliser la relation log₂(x) = log(x) / log(2) = log₁₀(x) / log₁₀(2)

Exemple en mode interactif en Python (la fonction trunc permet de réaliser la troncature pour ne garder que la partie entière):

Algorithme de conversion

La méthode pour passer de la représentation en base deux à la représentation en base 10 a déjà été présentée. Un algorithme simple permet d'effectuer l'opération inverse.

Exemple : nombre à convertir : 23
Initialement : on donne à N la valeur 23
N divisé par 2 donne 11 et il reste 1.
On place 1 le plus à droite possible et on donne à N la valeur 11.
Résultat provisoire : ______1

N divisé par 2 donne 5 et il reste 1.
On place 1 le plus à droite possible (donc juste à la gauche du précédent) et on donne à N la valeur 5.
Résultat provisoire : _____11

N divisé par 2 donne 2 et il reste 1.
On place 1 le plus à droite possible (donc juste à la gauche des précédents) et on donne à N la valeur 2.
Résultat provisoire : ____111

N divisé par 2 donne 1 et il reste 0
On place le 0 juste à la gauche des précédents bits, et on donne à N la valeur 1.
Résultat provisoire : ___0111

N divisé par 2 donne 0 et il reste 1.
On place le 1 juste à la gauche des précédents bits, et on donne à N la valeur 0.
Résultat provisoire : __10111

La conversion est terminée puisque N est nul, le résultat provisoire devient le résultat final : 10111.

Codage en hexadécimal

L'écriture en hexadécimal (base seize) est plus compacte et lisible que l'écriture en binaire (base deux), tout en étant très facile à convertir vers et depuis celle-ci.

L'hexadécimal est une numération de position dans laquelle seize symboles différents sont disponibles pour coder toutes les valeurs inférieurs à seize.

Ces symboles sont :

Base dix	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Base seize	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
Base deux	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111

En base 16 les poids des digits sont, de droite à gauche : 16⁰=1, 16¹=16, 16²=256, 16³=4096, etc...

Par exemple le nombre qui s'écrit en base seize 1C8 s'écrira en base dix :
1 × 16² + 12 × 16¹ + 8 × 16⁰ = 1 × 256 + 12 × 16 + 8 × 1 = 456

Un digit hexadécimal peut coder autant de valeurs que 4 bits. Deux digits hexadécimaux suffisent pour coder toutes les valeurs qui peuvent s'écrire sur un octet binaire. Le digit hexadécimal de gauche code les quatre bits de gauche, et celui de droite, les quatre bits de droite. Avec un peu d'habitude (ou le tableau ci-dessus) la conversion base seize - base deux est donc quasi-immédiate

Par exemple A5 (base seize) s'écrit en base deux 10100101, car A se code 1010 et 5 se code 0101.

Réciproquement, pour convertir depuis la base deux vers la base 16, il faut grouper les bits quatre par quatre, en complétant si nécessaire par des "0" à gauche, puis écrire pour chaque groupe de quatre bits le digit hexadécimal correspondant.

Exemple : conversion de 1100101011 (base deux) vers la base seize
1100101011 = 0011 0010 1011 → 32B en base seize (ce nombre s'écrit 811 en base 10)

Notations

Plusieurs conventions de notation peuvent être employées pour indiquer dans quelle base une suite de symboles représentant un nombre doit être interprétée.

Convention des mathématiciens

La suite de symboles représentant le nombre est mise entre parenthèses et la base est indiquée en indice, en base dix.
Par exemple (1100)₂ = (C)₁₆=(12)₁₀ = 12 (la base dix étant la base par défaut).

Conventions des informaticiens

Les bases deux et seize sont les seules utilisées couramment en informatique, la base huit étant utilisée occasionnellement.

Une variante paresseuse de la convention précédente, où la base indiquée en indice, mais sans les parenthèses, est souvent employé dans la documentation.

Pour la programmation, une convention reconnue par de nombreux langages consiste à faire précéder la suite de symboles représentant un nombre par le chiffre '0' suivi d'une lettre minuscule désignant la base : b (binaire) pour la base deux, x (hexadécimal) pour la base seize, o (octal) pour la base huit.

Codage des entiers signés

Codage en complément à deux

Si l'on veut pouvoir manipuler des nombres pouvant être positifs ou négatifs, se pose le problème du codage du signe. Nous avons l'habitude de signaler un entier négatif écrit en base dix par le signe -, mais cela n'est pas permis en binaire puisque seuls les deux symboles 0 et 1 sont disponibles

Plusieurs solutions sont envisageable. Celle utilisée en pratique tient compte des contraintes suivantes :
• un nombre positif doit pouvoir être distingué d'un nombre négatif par un critère simple.
• le codage choisi ne doit pas employer inutilement de l'espace mémoire.
• l'addition bit par bit de deux entiers doit donner des résultats exacts, quels que soient les signes de ces entiers, avec un minimum d'ajustement. En particulier la somme d'un entier positif et de son opposé doit donner 0.
• passer d'un nombre à son opposé doit faire appel à la même méthode, que ce nombre soit positif, négatif ou nul.

Il s'agit de la méthode du binaire signé en complément à 2.

Par exemple, pour l'entier positif 87 qui s'écrit en base deux sur un octet 01010111 :

nombre initial	0 1 0 1 0 1 1 1
inversion des bits	1 0 1 0 1 0 0 0
ajout de 1	+     1
résultat final	1 0 1 0 1 0 0 1

La valeur -87 s'écrit donc 10101001.

Si on additionne bit par bit 01010111 et 10101000 (c'est à dire 87 et -87): Tous les bits de l'octet obtenu sont à 0 : le résultat de l'addition de 87 et -87 est bien égal à 0, si on s'en tient à la taille de donnée choisie (la dernière retenue n'a pas sa place dans l'octet)

La même démarche (inversion des bits et ajout de 1) appliquée à un entier négatif donne bien son opposé.

Par exemple en partant de -87 qui se code 10101001, l'inversion de tous les bits donne 01010110, auquel on ajoute 1 pour obtenir 01010111 : on retrouve bien le code binaire de l'entier positif 87 .
De plus par cette méthode la valeur 0 est bien son propre opposé : si on inverse tous les bits de 00000000 puis qu'on ajoute 1 au résultat, tous les bits de l'octet obtenu sont à 0. Ici encore le résultat obtenu est correct sous réserve que l'on "oublie" la dernière retenue, qui n'a pas sa place dans l'octet.

Avec ce codage, la plus petite valeur négative que l'on puisse coder sur un octet s'écrit en base deux 10000000, qui vaut -128. Un octet permet donc de coder toutes les valeurs de -128 à +127, ce qui représente 255 valeurs. On peut donc coder exactement autant de valeurs différentes sur un octet en codage binaire classique ou en complément à deux.

Le principe du complément à deux s'étend naturellement à tout format d'entier binaire de taille définie. Le bit le plus à gauche est toujours le bit de signe, valant 0 pour un nombre positif et 1 pour un négatif.
Pour un format entier signé sur n bits, les entiers positifs, de valeur comprise entre 0 et 2^n-1-1 sont codés sur les n-1 bits de droite. Les entiers négatifs sont compris entre 0 et -(2^n-1).

Formats d'entiers signés usuels et taille des données

De nombreux langages de programmation définissent plusieurs formats de nombres entiers parmi lesquels le programmeur peut choisir afin d'optimiser l'usage de la mémoire. En effet il est préférable de ne pas mobiliser quatre octets pour écrire un index de boucle compris entre 0 et 20 par exemple (un octet non signé suffit).

Les formats les plus courants sont : octet (8 bits) non signé, octet (8 bits) signé, double octet signé (16 bits), quadruple octet signé (32 bits), octuple octet signé (64 bits).

Codage des réels en virgule flottante

Principe du codage en virgule flottante

Le codage des réels en virgule flottante repose sur le même principe que l'écriture scientifique des réels en base dix... mais en base deux.

Petit rappel sur la notation scientifique en base dix

La notation scientifique est une convention permettant d'écrire une valeur réelle avec une précision donnée.

Elle se compose :
• d'un signe + ou -
• d'une valeur numérique m telle que 1 ≤m < 10. m est la mantisse du nombre.
• d'une puissance de dix, 10^e, e pouvant être positif ou négatif.

La valeur du nombre est (+/-) m × 10^e
La précision de l'écriture dépend du nombre de chiffres significatifs utilisés pour écrire la mantisse.
Par définition la mantisse n'a qu'un seul chiffre avant la virgule. Ce chiffre est compris entre 1 et 9: on a donc 1 ≤m < 10.

La notation en virgule flottante, en base deux

La notation en virgule flottante suit exactement le même principe que la notation scientifique, mais en base deux, en n'utilisant que des 0 et des 1.

• Le signe du nombre est codé par un bit de signe s: s = 0 si le nombre est positif, s = 1 s'il est négatif.
• La mantisse m est telle que 1 ≤m < 2 . Cela implique que m s'écrit en base deux avec un seul chiffre avant la virgule, et que celui-ci est obligatoirement un "1". Par conséquent, on n'a besoin de coder que les chiffres après la virgule, en base deux.
• La puissance qui multiplie la mantisse est une puissance de deux, et l'exposant e est écrit en base deux.

Le code d'un réel en virgule flottante sera donc composé de trois parties :
• le bit de signe
• les bits après la virgule de la mantisse
• le code de l' exposant

Les formats utilisés pour coder les réels en virgule flottante sont normalisés, le nombre de bits attribués respectivement à la mantisse et à l'exposant étant fixés.

La précision dépend du nombre de bits utilisés pour écrire la mantisse. Par exemple, dans le format 'virgule flottante simple précision', la mantisse s'écrit sur 24 bits, dont seuls les 23 qui suivent la virgule sont codés.

L'étendue des valeurs dépend surtout du nombre de bits utilisés pour coder l'exposant. Par exemple dans le format 'virgule flottante simple précision', l'exposant signé est codé sur 8 bits. L'ordre de grandeur des valeurs que l'on peut coder dans ce format va de 10^-38 à 10⁺³⁸

Codage binaire des nombres entre 0 et 1

Poids des bits après la virgule

Pour coder en binaire la partie décimale de la mantisse, la méthode est la même que pour le codage des entiers: à chaque position après la virgule correspond un poids, mais il s'agit maintenant des puissances négatives de 2.

Le premier bit après la virgule a un poids (en base dix) de 2^-1=1/2=0,5 , le second un poids de 2^-2=1/4=0,25, le troisième un poids 2^-3=1/8=0,125 , etc...

 

Algorithme de conversion

Exemples d'application

1. Conversion de 0,5625 en base deux

r = 0,5625

r = 2*r = 1,125
On ajoute le "1" qui forme la partie entière après la virgule dans le résultat : 0,1
On ne garde que la partie fractionnaire de r : r = 0,125

r = 2*r = 0,25
On ajoute le "0" qui forme la partie entière après la virgule dans le résultat : 0,10
On ne garde que la partie fractionnaire de r : r = 0,25

r = 2*r = 0,5
On ajoute le "0" qui forme la partie entière après la virgule dans le résultat : 0,100
On ne garde que la partie fractionnaire de r : r = 0,5

r = 2*r = 1
On ajoute le "1" qui forme la partie entière après la virgule dans le résultat : 0,1001
On ne garde que la partie fractionnaire de r : r = 0

La conversion est terminée, le résultat est 0,1001.
Pour le coder en virgule flottante, on écrira ce résultat sous la forme 1,001 × 2^-1. Le code en virgule flottante sera donc composé du bit de signe (0 pour ce nombre positif), des bits formant la partie fractionnaire de la mantisse (001) et du code binaire de l'exposant (ici l'exposant vaut -1, qu'il faudra encore coder en binaire par une méthode fixée par la norme utilisée).

2. Conversion de 0,3 en base deux

r = 0,3

r = 2*r = 0,6
On ajoute le "0" qui forme la partie entière après la virgule dans le résultat : 0,0
On ne garde que la partie fractionnaire de r : r = 0,6

r = 2*r = 1,2
On ajoute le "1" qui forme la partie entière après la virgule dans le résultat : 0,01
On ne garde que la partie fractionnaire de r : r = 0,2

r = 2*r = 0,4
On ajoute le "0" qui forme la partie entière après la virgule dans le résultat : 0,010
On ne garde que la partie fractionnaire de r : r = 0,4

r = 2*r = 0,8
On ajoute le "0" qui forme la partie entière après la virgule dans le résultat : 0,0100
On ne garde que la partie fractionnaire de r : r = 0.8

r = 2*r = 1,6
On ajoute le "1" qui forme la partie entière après la virgule dans le résultat : 0,01001
On ne garde que la partie fractionnaire de r : r = 0.6

Cette valeur de r a déjà été rencontrée précédemment : on peut en déduire que l'écriture binaire de la valeur qui s'écrit 0,3 en base deux possède un nombre infini de décimales, le motif 1001 se répétant indéfiniment. Donc 0,3 s'écrit en base deux 0,01001100110011... = 0,01001

Approximation et conséquences

Pour coder la valeur 0,3 en virgule flottante, on doit commencer par écrire le résultat de la conversion en base deux, (0,01001)₂, sous la forme 1,0011 × 2^-2. Le code binaire de la partie fractionnaire de la mantisse étant infini, il sera nécessaire de le tronquer, ou plutôt de l'arrondir au plus proche, pour pouvoir l'écrire sur un nombre fini de bits.
Comme 0,3, la majeure partie des nombres compris entre 0 et 1 s'écrit en base 2 avec un nombre infini de bits. Leur codage en virgule flottante avec un nombre fini de bits entraîne donc nécessairement une approximation. Il arrive donc que les calculs en virgule flottante génèrent une erreur apparente, heureusement extrêmement faible, due aux arrondis nécessités par la taille finie de la mantisse.

Exemples: exécuter le programme Python suivant :

1. print("1+2==3 est",1+2==3)
2. print("0.1+0.2==0.3 est",0.1+0.2==0.3)
3. print("0.01+0.02==0.03 est",0.01+0.02==0.03)
4. print("3*0.1==0.3 est",3*0.1==0.3)
5. print("2*0.15==0.3 est",2*0.15==0.3)
6. print("1.5*0.2==0.3 est",1.5*0.2==0.3)

Quelques réponses sont pour le moins surprenantes d'un point de vue mathématique... mais tout à fait explicables par la représentation interne des flottants (les observations ne sont pas liées à Python, on peut les reproduire dans n'importe quel langage)

On peut regarder d'un peu plus près quelle est la valeur de l'écart entre le résultat attendu et le résultat obtenu :

1. print("0.1+0.2-0.3 =",0.1+0.2-0.3)
2. print("3*0.1-0.3 =",3*0.1-0.3)
3. print("1.5*0.2-0.3 =",1.5*0.2-0.3)

Cet écart est extremement faible (c'est rassurant!) et présente ici la même valeur dans les trois cas. S'il provient bien des arrondis, il doit correspondre au dernier digit binaire de la mantisse et doit donc être égal à une puissance de 2. On peut le vérifier en utilisant la fonction log₂ vue précédemment:

1. from math import log2
2. print(log2(0.1+0.2-0.3))

Le résultat est -54. Cela veut dire qu'en virgule flottante, le résultat de (0.1+0.2-0.3) est 2^-54. = (0.000000000000000000000000000000000000000000000000000001)₂.
Ce résultat s'écrit sur exactement un digit binaire, il est donc bien raisonnable d'attribuer l'origine de l'écart apparent entre 0,1+0,2 et 0,3 aux arrondis. Par exemple le programme ci-dessous boucle indéfiniment, alors qu'on s'attendrait à huit itérations (rappel : on peut forcer l'arrêt d'un programme par Ctrl+C ou, sous Pyzo, Ctrl+I)

1. x=0
2. while x!=0.8:
3.     x=x+0.1

On peut envisager d'écrire plutôt

1. x=0
2. while x<0.8:
3.     x=x+0.1

mais ce n'est pas forcément la meilleure solution. En ajoutant "print(x)" dans la boucle, on peut en effet se rendre compte ici qu'elle est effectuée une fois de trop, car la valeur approchée de 0,8 codée en virgule flottante est très légèrement supérieure à 0,8.

Il est plus sûr d'écrire :

1. x=0
2. while abs(x-0.8)>0.01:
3.     print(x)
4.     x=x+0.1

Dans le code ci-dessus, au lieu de vérifier si x est égal à la valeur cible 0,8, on vérifie si x est suffisamment proche de celle-ci, en fonction de ce que l'on souhaite obtenir ( abs(x-0.8) donne la valeur absolue de l'écart entre x et la valeur cible 0,8)