Utilisateur:Merrheim/Architecture des ordinateurs/Représentation des données

Le cours sur la représentation des données

Introduction

Pour être capable d'effectuer des traitements sur des données, un ordinateur doit être capable de représenter des données. Le choix d'un format de représentation est loin d'être neutre et de nombreux éléments sont à prendre en considération :

• la représentation de ma donnée est-elle suffisamment proche de la réalité ? Lorsqu'on représente une image par exemple, elle est légèrement déformée, et moins « fine » que la réalité. Cette approximation est-elle compatible avec le traitement que je veux lui faire subir ?
• le volume de ma donnée est-il raisonnable ? Même si la capacité de stockage des ordinateurs paraît gigantesque, des limites existent et les besoins des utilisateurs sont toujours plus importants. Essayez de stocker 4 heures de films avec une précision suffisante pour qu'il soit projeté sur l'écran géant d'une salle de cinéma et vous verrez rapidement qu'il est nécessaire de réfléchir à la compression des données ! En général ce second point est antagoniste du premier : plus on veut être précis dans la représentation, plus le volume de données sera important. Il faut donc trouver un compromis.L'informatique et ses capacités de stockage et de traitements évoluant de manière spectaculaire, de nouveaux standards toujours plus précis et toujours plus volumineux apparaissent sans cesse et la réalité d'aujourd'hui sera bien différente de celle de demain.

• le format de représentation de ma donnée est-il adapté au traitement qu'on veux lui faire subir ? Certains systèmes de représentation auront des meilleures propriétés que d'autres à ce niveau. Par exemple, si vous voulez réaliser des trucages vidéos sur un film, il vous faudra certainement le décomprésser auparavant avant d'effectuer le traitement : il vous faudra alors un ordinateur avec des volumes de stockage gigantesque pour effectuer cette opération.

• le format utilisé est-il standard ? Si vous stockez des données dans un format que vous êtes le seul au monde à utiliser, vous rencontrerez d'énormes problèmes dès que vous voudrez communiquer avec l'extérieur ! Or notre monde est un monde de communication et il est inenvisageable de travailler seul sur un projet : il faut travailler avec des systèmes de représentation standards et accepter leur qualité mais également leurs défauts. D'ailleurs, la maîtrise des standards informatiques fait l'objet d'une guerre économique sans merci : qui contrôle les standards contrôle l'informatique.

Formats de représentation numériques

Un ordinateur manipule des données très diverses : des entiers, des réels, des textes, des images, des sons. Néanmoins toutes ces données sont représentées par des nombres entiers et en dernier lieu par des suites finies de 0 et de 1 appelés bits. Chaque type de données (les entiers, les réels,...) utilisera un système de représentation qui lui est propre mais à chaque fois la donnée sera représentée par des suites finies de bits. On parle de représentation numérique de ces données.

Intérêt des formats numériques

L'intérêt des formats numériques est de pouvoir transmettre ou dupliquer une donnée à l'infini sans perte de qualité. On peut prendre un texte et le dupliquer un million de fois sur un Cd-ROM par exemple sans qu'il y ait la moindre différence entre chacune des copies et l'original. Il est beaucoup plus facile d'effectuer des traitements automatisés sur des données représentées dans un format numérique. À l'opposé avec les formats analogiques (cassette audio classique, disque vinyle, pellicule photographique, ...) chaque copie modifie le résultat.

Notation hexadécimale

Il ne s'agit pas ici d'un standard de représentation. Il est difficile pour un être humain de noter une longue suite de bits (32 bits par exemple) sans faire d'erreur. La notation hexadécimale permet de représenter une suite de bits de manière plus compacte. Pour cela, on va découper la suite de bits par paquets de 4 bits et on représentera chaque paquet de 4 bits par un caractère :
0000 sera représenté par 0
0001 sera représenté par 1
0010 sera représenté par 2
0011 sera représenté par 3
0100 sera représenté par 4
0101 sera représenté par 5
0110 sera représenté par 6
0111 sera représenté par 7
1000 sera représenté par 8
1001 sera représenté par 9
1010 sera représenté par A
1011 sera représenté par B
1100 sera représenté par C
1101 sera représenté par D
1110 sera représenté par E
1111 sera représenté par F
On écrit donc en base 16.
Exemple 1 :
La suite de bits 0011 1110 1101 1000 0000 1111 0011 0111 s'écrit en notation hexadécimale 3ED80F37

Représentation des entiers en base 2, ou binaire

On a pu imaginer des systèmes de numération dans différentes bases, mais pour des raisons technologiques les ordinateurs comptent en base deux, ou binaire.

• Tout entier X entre 0 et 2^N-1, peut être représenté par une unique suite de bits x₀ ,x₁ ,...,x_N-1 valant chacun 0 ou 1 telle que :
  

$X=\sum _{i=0}^{N-1}x_{i}.2^{i}$

• La base 2 est un standard de représentation très utilisé pour représenté des entiers postifs au sein d'un ordinateur. La manipulation des entiers ainsi représentés est en effet très aisée. Beaucoup de processeurs représentent les entiers sur 32 bits (N=32) ou sur 64 bits (N=64).
• Nous allons présenter les entiers en base 2 sur seulement 8 bits pour limiter la longueur des calculs.
• Sur 8 bits, on peut représenter en base 2 tous les entiers entre 0 et 2⁸-1=255.

Conversion base 10 vers base 2

Si on se donne un entier entre 0 et 255, comment obtenir sa représentation en base 2 ?

Méthode 1

Nous pouvons commencer par commencer par le bit de gauche (de poids fort) en utilisant l'algorithme suivant :

1. Rechercher la plus grande puissance de 2 inférieur ou égale à X.
2. Soustraire cette puissance de 2 à X.
3. Recommencer au 1) avec le résultat obtenu jusqu'à obtenir 0.
4. On obtient alors l'écriture de X sous la forme d'une somme d'une puissance de 2

Exemple :

On veut représenter 173 en base 2 sur 8 bits :

173-128=45
45-32=13
13-8=5
5-4=1
1-1=0
173=128+32+8+4+1

Obtenir la représentation finale de 173 est maintenant assez simple. On utilise la règle suivante :

Règle :

1. Si 2ⁱ est présent dans la décomposition de X obtenue par l'algorithme précédent x_i=1.
2. Dans le cas contraire, x_i=0.
3. On représentera la suite de bits poids fort en tête c'est-à-dire de x_N-1 à x₀. x_N-1 sera appelé le bit de poids fort et x₀ sera appelé le bit de poids faible.

On a obtenu précédemment $173=2^{7}+2^{5}+2^{3}+2^{2}+2^{0}$ donc on a :
x₇=1
x₆=0
x₅=1
x₄=0
x₃=1
x₂=1
x₁=0
x₀=1
La représentation de 173 en base 2 est donc (10101101)₂.

Méthode 2

Une autre technique consiste à effectuer successivement des divisions entières par 2 et à noter à chaque étape le reste (0 ou 1). On obtient alors les bits de poids faible en premier :

1. Diviser le nombre par 2.
2. Retenir le reste de cette division comme bit.
3. Tant que le quotient de cette division n'est pas 0, recommencer avec le quotient à l'étape 1.

Exemple :
On veut représenter 173 en base 2 sur 8 bits :

173 = 2 * 86 + 1
 86 = 2 * 43 + 0
 43 = 2 * 21 + 1
 21 = 2 * 10 + 1
 10 = 2 *  5 + 0
  5 = 2 *  2 + 1
  2 = 2 *  1 + 0
  1 = 2 *  0 + 1
  0 fin de l'algorithme

Conversion base 2 vers base 10

Si on se donne une suite de bits x_N-1 ,x_N-2 ,...,x₀ qui représente un entier en base 2 et si on veut obtenir sa valeur décimale on utilisera tout simplement la formule : $X=\sum _{i=0}^{N-1}x_{i}.2^{i}$.

Exemple :

Quel est l'entier X représenté en base 2 par (11001110)₂ ?
$X=1.2^{7}+1.2^{6}+0.2^{5}+0.2^{4}+1.2^{3}+1.2^{2}+1.2^{1}+0.2^{0}=128+64+8+4+2=206$

• Quelques valeurs à connaître
  

Pour représenter des entiers positifs uniquement.

• • En base 2 sur N bits, on représente tous les entiers de 0 à 2^N-1.
  • En base 2 sur 8 bits, on représente les entiers de 0 à 255.
  • En base 2 sur 16 bits, on représente les entiers de 0 à 2¹⁶-1=65535.
  • En base 2 sur 32 bits, on représente les entiers de 0 à 2³²-1= 4 294 967 295 (4 milliards environ).
• Quelques exemples d'utilisation de la base 2
  
  • Pour repérer un endroit dans la RAM, le numéro de la case mémoire est représenté en base 2.
  • Pour repérer un secteur sur un disque dur, le numéro du secteur est représenté en base 2.
  • Lorsqu'un programme en C++ utilise une variable de type unsigned int, il est en général représenté en base 2.
  • etc.

Représentation des entiers signés en complément à 2

La base 2 ne permet de représenter que des entiers positifs. Pour représenter un entier signé, c'est-à-dire pouvant être positif ou négatif, on utilise en général le complément à 2. Beaucoup de processeurs manipulent les entiers signés en complément à 2 sur 32 bits ou sur 64 bits. La raison est que les additions sont très faciles à effectuer avec cette représentation. Pour des raisons pratiques, nous étudierons ici le complément à 2 sur 8 bits.

• Conversion base 10 vers complément à 2
  

On veut représenter X en base 2 sur N bits.
Règle :
1) Si X est négatif, le premier bit sera à 1 et les N-1 autres bits seront la représentation de 2^N-1+X en base 2 sur (N-1) bits.
2) Si X est positif, le premier bit sera à 0 et les N-1 autres bits seront la représentation de X en base 2 sur (N-1) bits.

Règle (autrement dit) :
1) Si X est négatif, les N bits représentent 2^N+X en base 2.
2) Si X est positif, les N bits représentent X en base 2.

On peut représenter en complément à 2 les entiers de -2^N-1 à 2^N-1-1.

• Exemple 1 :
  

On veut représenter -67 en complément à 2 sur 8 bits.
-67 est négatif le premier bit vaut donc 1.
128-67=61 on représente 61 en base 2 sur 7 bits.
61-32=29
29-16=13
13-8=5
5-4=1
1-1=0
61 s'écrit donc en base 2 sur 7 bits 011 1101
-67 s'écrit donc en complément à 2 sur 7 bits 1011 1101

• Exemple 2 :
  

On veut représenter 53 en complément à 2 sur 8 bits.
53 est positif le premier bit est à 0.
53-32=21
21-16=5
5-4=1
1-1=0
53 s'écrit donc en complément à 2 sur 8 bits 0011 0101

• Conversion complément à 2 vers base 10
  

X est un entier donc la représentation en complément à 2 est x_N-1 , x_N-2,...,x₁, x₀. La valeur décimale de X est :
$X=-2^{N-1}.x_{N-1}+\sum _{i=0}^{N-2}x_{i}.2^{i}$

• Exemple 3 :
  

Voici un entier X représenté en complément à 2 donner sa valeur décimale 1011 0110
$X=-2^{7}+2^{5}+2^{4}+2^{2}+2^{1}=-128+32+16+4+2=-74$

• Exemple 4 :
  

Voici un entier X représenté en complément à 2 donner sa valeur décimale 0000 1110
$X=2^{3}+2^{2}+2^{1}=8+4+2=14$

• Quelques valeurs à connaître
  
  • En complément à 2 sur N bits on représente tous les entiers de -2^N-1 à 2^N-1-1.
  • En complément à 2 sur 8 bits on représente tous les entiers de -128 à +127.
  • En complément à 2 sur 16 bits on représente tous les entiers de -32768 à +32767.
  • En complément à 2 sur 32 bits on représente tous les entiers de -2³¹=-2 147 483 648 à 2³¹-1=2 147 483 647 (environ plus ou moins 2 milliards).

• Caractéristiques
  
  • -1 est représenté par une suite de 1 sur N bits. Par exemple, sur 8 bits : 11111111
  • le successeur de -1 (soit -1+1) tronqué à 8 bits est 00000000, soit 0

• Utilisation du complément à 2 :
  Lorsqu'on utilise le type int dans un programme en C++, la donnée est le plus souvent représentée en complément à 2.

Représentation des réels dans le format IEEE-754

Nous allons étudier ici la représentation des réels dans le format IEEE-754. Il existe en fait 2 standards : le format IEEE-754 simple précision sur 32 bits et le format IEEE-754 double précision sur 64 bits. Le plus utilisé aujourd'hui est le format IEEE-754 double précision mais nous allons étudier le format IEEE-754 simple précision pour des raisons de concision.

• Le format IEEE-754 simple précision
  • Ecriture de 0 : si X est nul, sa représentation est constituée de 32 bits à 0.
  • Ecriture sous forme scientifique
    

Si X n'est pas nul, nous allons rechercher s, e et m tel que :
$X=(-1)^{s}.2^{e}.(1+m)\,$
avec
- s peut valoir 0 ou 1.
- e doit être un entier signé.
- m est compris dans l'intervalle [0;1[.

• • Recherche de s
    

La valeur de s est simple à trouver : s vaut 0 si X est positif ou nul et vaut 1 si X est négatif.

• • Recherche de e
    

Trois cas sont à envisager :
- si |X|>=2, on va diviser la valeur absolue de X autant de fois que nécessaire jusqu'à obtenir un entier de l'intervalle [1;2[. e sera le nombre de divisions effectuées.
- si |X|<1, on va multiplier la valeur absolue de X par 2 autant de fois que nécessaire jusqu'à obtenir un entier de l'intervalle [1;2[. e sera l'opposé du nombre de multiplications.
- si 2>|X|>=1, alors e sera nul.

• • Recherche de m
    

Si on connait X, s et e alors il est facile de trouver m !

• • Exemple 1 : X=-9.6
    

X est négatif donc s=1.
On va diviser 9.6 par 2. 9.6/2=4.8
4.8/2=2.4
2.4/2=1.2 on s'arrête car cette valeur appartient à l'intervalle [1;2[
On a divisé 3 fois par 2 donc e=3.
On obtient facilement m=1.2-1=0.2

• • Exemple 2 : X=0.375
    

X est positif donc s=0.
On va multiplier 0.375 par 2 :
0.375 * 2= 0.75
0.75*2=1.5 on s'arrête car cette valeur appartient à l'intervalle [1;2[
On a multiplié 2 fois par 2 donc e=-2.
On trouve m=1.5-1=0.5.

• • Exemple 3 : X=-1.05

X est négatif donc s=1.
1.05 est dans l'intervalle [1;2[ donc e=0.
On obtient m=0.05.

• • Obtention de la représentation
    

La représentation finale s'obtiendra en justaposant :
- le bit s sur 1 bit.
- l'exposant e sur 8 bits
- la mantisse m sur 23 bits

• • Représentation de l'exposant
    

Pour représenter e, on va calculer E=e+127 et on écrit E en base 2 sur 8 bits.

• • Représentation de la mantisse
    

Règle :

1) On multiplie m par 2
2) On calcule la partie entière et la partie décimale du résultat.
3) La partie entière du résultat est un nouveau bit de la représentation.
4) On recommence le 1) avec la partie décimale du résultat.
5) On recommence jusqu'à obtenir les 23 bits de la mantisse.

• • Exemple de représentation 1 : X=-9.6
    

On avait obtenu s=1, e=3 et m=0.2.
E=127+e=130.
On doit écrire 130 en base 2 sur 8 bits.
130-128=2
2-2=0
130=128+2
130 s'écrit donc en base 2 sur 8 bits 1000 0010
m=0.2.
0.2*2=0.4=0+0.4 ==> attention cette ligne va se répéter plus bas.
0.4*2=0.8=0+0.8
0.8*2=1.6=1+0.6
0.6*2=1.2=1+0.2
0.2*2=0.4=0+0.4 ==> identique à la première ligne !
La représentation de la mantisse sera donc 0011 0011 0011 0011 0011 001
La représentation de -9.6 dans le format IEEE-754 est donc :
1 1000 0010 0011 0011 0011 0011 0011 001
soit en hexadécimal C119 9999

• • Exemple de représentation 2 : X=0.375
    

On avait trouvé s=0, e=-2 et m=0.5
E=127+e=125
On écrit 125 en base 2 sur 8 bits.
125-64=61
61-32=29
29-16=13
13-8=5
5-4=1
4-4=0
125=64+32+16+8+4+1
125 s'écrit donc en base 2 sur 8 bits 0111 1101
m=0.5
0.5*2=1=1+0
0*2=0=0+0==> cette ligne se répète indéfiniment.
La représentation de la mantisse est donc 1000 0000 0000 0000 0000 000
La représentation de 0.375 dans le format IEE-754 simple précision est donc 0 0111 1101 1000 0000 0000 0000 0000 000
soit en hexadécimal 3EC0 0000

• • Exemple de représentation 3 : X=-1.05
    

On avait trouvé s=0, e=0 et m=0.05
E=e+127=127
On représente 127 en base 2 sur 8 bits.
127-64=63
63-32=31
31-16=15
15-8=7
7-4=3
3-2=1
1-1=0
127 s'écrit donc en base 2 sur 8 bits 0111 1111
m=0.05
0.05*2=0.1=0+0.1
0.1*2=0.2=0+0.2
0.2*2=0.4=0+0.4 ==> cette ligne va se répéter.
0.4*2=0.8=0+0.8
0.8*2=1.6=1+0.6
0.6*2=1.2=1+0.2
0.2*2=0.4=0+0.4 ==> identique à la ligne 3
La mantisse s'écrit donc 00 0011 0011 0011 0011 0011 0
Le représentation de -1.05 dans le format IEEE-754 imple précision est donc 1 0111 1111 00 0011 0011 0011 0011 0011 0
soit en hexadécimal BF86 6666

• • Comment retrouver la valeur d'un réel représenté dans ce format ?
    

Si on vous donne la représentation dans le format IEEE-754 d'un réel, comment faire pour retrouver la valeur décimale de ce réel ?
- Dans un premier temps, il faut l'écrire en binaire et retrouver chaque champ : le premier bit permettra de retrouver la valeur de s, les 8 bits suivants la valeur de l'exposant et les 23 derniers bits la valeur de la mantisse.
- À partir du champ exposant, on effectue la transformation base 2 vers base 10 et on retrouve alors la valeur de E. Il suffit de retrancher 127 et on obtient la valeur de e.
- Pour retrouver la valeur de m, il faut considérer que chaque bit à un poids : le premier bit de la mantisse à comme poids 2^-1, le deuxième à comme poids 2^-2, et ainsi de suite jusqu'au dernier qui a comme poids 2^-23. On retrouve la valeur de m en additionnant le poids des bits qui ont la valeur 1 dans la mantisse.
- À partir de la valeur de s, de e et de m on retrouve aisément la valeur de X grâce à la formule :
$X=(-1)^{s}.2^{e}.(1+m)\,$

Représentation des caractères

• le code ASCII
  

Le code ASCII permet de représenter des caractères sur 7 bits : on peut représenter des lettres majuscules et minuscules, des chiffres, des caracères spéciaux , par exemple #,{,(, et des caractères non imprimables qui servaient autrefois à envoyer des données sur un réseau.

• le code ISO 8859-1
  

Chaque caractère est représenté sur 8 bits et ce codage est une extension du codage ASCII : il propose en plus des lettres accentuées utilisées dans de nombreux alphabets. Il existe d'autres extensions à 8 bits du code ASCII, qui ne sont pas compatibles entre-elles.

• le codage unicode
  

Ce système de codage représente des caractères sur 16 bits : il peut afficher des caractères dans des alphabets non latin, l'alphabet cyrillique par exemple.

Exercices

Exercice 1

Représenter en base 2 sur 8 bits les entiers 78, 199 et 53.

Solution

78² en base 10 (64.32.16.8.4.2.1) = 64 + 8 + 4 + 2, soit (1.0.0.1.1.1.0)²

Exercice 2

Voici des entiers représentés en base 2 sur 8 bits. Donnez leurs valeurs décimales respectives :
(1001 1011)
(0011 1100)
(0101 0101)

Exercice 3

Représentez en complément à 2 sur 8 bits les entiers -100, 83 et -29.

Exercice 4

Voici des entiers représentés en complément à 2 sur 8 bits. Donnez leurs valeurs décimales respectives :
(1101 1001)
(1011 1010)
(0111 0100)

Exercice 5

Représentez dans le format IEEE-754 simple précision les réels -0.15, 6.6 et -23. Le résultat final sera noté en hexadécimal.

Exercice 6

Voici 3 réels représentés dans le format IEEE-754 simple précision (notation hexadécimale); Donnez leurs valeurs décimales respectives.
4258 0000
BF30 0000
40B0 0000

Liens sur Wikipédia

• w:numérisation
• w:Système binaire
• w:Complément à deux
• w:Arithmétique binaire
• w:IEEE 754

Représentation des données