Codage des nombres

Résumé : cf Résumé_Codage_des_Nombres

1 - Codage des Entiers Non Signés ( UNSIGNED )

1.1 - Bases

Définition : Une base B est un ensemble ordonné de N symboles.

Ex: Base 10 : $B \in \lbrace 0,1,2,3,4,5,6,7,8,9 \rbrace$

Cela permet d’exprimer des Quantités .

$$Q = 45 = 4 \cdot 10^1+5 \cdot 10^0$$

Nous utilisons habituellement cette base tout simplement parce que nous avons 10 doigts.

Le composant fondamental d’un processeur est le transistor, dont l’état peut être ouvert ou bloqué .

Les calculs dans un processeur reposent donc sur une base 2 ( base binaire ). $B \in \lbrace 0,1 \rbrace$

Expression d’une quantité en base 2 : j’applique la définition :

Ex: $x = 0b1101 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 13$

Concernant la base 16, je dois disposer de 16 symboles.

Relation Base 2 <–> Base 16

Soit la valeur en base 2 : $x = 0b\color{red}{1100}\color{blue}{1010}$

Par définition : $x = \color{red}{ 1 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 } + \color{blue}{1 \cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0}$

soit $x = \color{red}{( 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 0\cdot 2^0 )}.2^4 + \color{blue}{(1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0)}.2^0$

soit $x = \color{red}{( 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 0\cdot 2^0 )}.16^1 + \color{blue}{(1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0)}.16^0$

soit $x = \color{red}{C}.16^1 + \color{blue}{A}.16^0$

Pour passer de la base 2 à la base 16, il me suffit donc de faire des paquets de 4 bits, et de retrouver la correspondance entre les deux bases dans le tableau ci-dessus.

La base 16 peut être considérée comme une base binaire à écriture compactée.

Entendons nous bien : la quantité reste la même, qu’elle soit exprimée en base 2, 10 ou 16.
La plupart du temps dans nos programmes nous écrirons des nombres en base 10.
Le processeur verra cela comme de la base 2 de par son architecture, ( et les calculs seront effectués dans cette base )
Les bases 2 et 16 pourront être utilisées lors de l’écriture des programmes pour des questions de masquage ou d’écriture dans des registres de configuration des périphériques.

1.2 - Comment retrouver le codage d’une valeur ?

Reprenons l’exemple précédent : $x = 13 = \color{green}{?}\cdot 2^3 + \color{orange}{?}\cdot 2^2 + \color{blue}{?}\cdot 2^1 + \color{red}{?}\cdot 2^0$

Je peux écrire successivement :

$13 = 6 \times 2 + \color{red}{1}$
$6 = 3 \times 2 + \color{blue}{0}$
$3 = \color{green}{1} \times 2 + \color{orange}{1}$

soit: $13 = [(\color{green}{1}\times 2 + \color{orange}{1})\times 2 + \color{blue}{0} ]\times 2 + \color{red}{1} = \color{green}{1}\cdot 2^3 + \color{orange}{1}\cdot 2^2 + \color{blue}{0}\cdot 2^1 + \color{red}{1}\cdot 2^0$

Le codage binaire de 13 est donc $0b\color{green}{1}\color{orange}{1}\color{blue}{0}\color{red}{1}$

Autrement dit, je peux trouver le codage d’un nombre par divisions successives :

Bien entendu cela est vrai également pour la base 16 :

Le codage hexadécimal de 1234 est donc $0x\color{blue}{4}\color{orange}{D}\color{red}{2}$

Par conséquent, en binaire : $0b\color{blue}{0100}\color{orange}{1101}\color{red}{0010}$

1.3 - Nombre de Valeurs Codables :

Le nombre de valeurs dans un processeur est toujours fini.

Le nombre de bits ( ou de digits ) détermine ce nombre de valeurs codables.

Ex: 4 bits : $2\times 2\times 2\times 2$ possibilités de codage, soit $2^{4}$

Pour des grandeurs non signées ( unsigned ), je peux donc coder des valeurs allant de 0 à 15 ( $2^4 - 1$ ).

1.4 - Addition

En base 10 : si je dépasse 9, il y a une retenue sur le digit supérieur :

$$\begin{align} \color{red}{1}\;\;\;& \\ 8& \\ \underline{+\quad 7}& \\ \color{red}{1}\;5& \end{align}$$

En binaire c’est pareil quand on dépasse 1 :

$$\begin{align} \color{red}{1}\;\;\;& \\ 1& \\ \underline{+\quad 1}& \\ \color{red}{1}\;0& \end{align}$$

Sur 4 bits :

Et si ça déborde ?

En incluant la retenue qui déborde ( Carry ), le résultat est correct, mais ce dernier serait alors sur 5 bits.
Or il faut considérer un résultat sur 4 bits ( taille des opérandes ).
Ce résultat est donc faux, le bit d’état Carry permet alors d’indiquer un débordement pour une somme d’entiers non signés.

L’additionneur binaire :

Considèrons un additionneur élémentaire :

L’association parallèle de 4 additionneurs élémentaires permet de fabriquer un additionneur ( d’entiers non signés ) 4 bits :

---

2 - Codage des Entiers Signés ( SIGNED )

Jusqu’à présent toutes les valeurs étaient exclusivement positives.
Une première solution pour coder des quantités positives et négatives serait de modifier le bit de poids fort :

…
-2 –> 0b1010
-1 –> 0b1001
0 –> 0b0000
1 –> 0b0001
2 –> 0b0001
…

à ce moment-là, si j’additionne bit à bit 1 + (-1), j’obtiens 0b1010, soit -2.
Une addition avec ce codage supposerait quelques manipulations supplémentaires pour obtenir un résultat correct.

Il existe un codage permettant d’obtenir un résultat correct : le codage complément à 2 ( ou plus précisément complément à $2^N$ ).

Comme nous travaillons sur des intervalles finis , nous utilisons la propriété du modulo ( tout ce qui dépasse disparait ).

Exemple en base 10 : Je travaille dans l’intervalle [0 99], toutes les opérations se font modulo 100 :

40 - 30 = 10

J’obtiens le même résultat en faisant :

[ 40 + (100-30) ]modulo 100 = [ 40 + 70 ]modulo 100 = [ 110 ]modulo 100 = 10

Dans cette perspective on peut considérer que 70 représente une quantité négative -30

Tout ce qui est entre 0 et 49 sont des quantités positives, les valeurs comprises entre 50 et 99 représentent des quantités négatives.

En binaire c’est pareil, considérons un exemple sur 4 bits ( modulo $2^4$ ):

la quantité signée -1 aura le même codage que la quantité non signée $2^4 - 1$, soit 15.

Réalisons alors l’addition 1 + (-1) :

Il y a une retenue dans C, mais le résultat est correct ( donc tout va bien )

Nous aurons donc sur 4 bits :

2.1- Définition d’un nombre codé en complément à 2

sur 4 bits :

$-3 = -( 2^4 -13 )$
$-3 = -( 2^4 - 1.2^3 - 1.2^2 - 0.2^1 - 1.2^0 )$
$-3 = - 2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$

or $( -2^4 + 2^3 = -2^3 )$

donc $-3 = - 2^3 + 1.2^2 + 0.2^1 + 1.2^0$

D’où la définition d’un nombre codé en complément à 2 ( sur 4 bits) :

$\boxed{ X = -b_3.2^3 + b_2.2^2 + b_1.2^1 + b_0.2^0 }$

2.2 - Entendons nous bien :

Même si tous les nombres négatifs ont un poids fort à 1 ( que l’on nommera d’ailleurs bit de signe) , Il ne suffit pas de mettre le poids fort à 1 pour trouver le codage de l’opposé d’un nombre positif.

2.3 - Comment retrouver le codage d’un nombre négatif à partir de sa valeur positive

1. J’applique la définition du complément : par exemple +3 : 0b0011
   Le codage de -3 en signé est le même que le codage de $( 2^4 -3 )$ en non signé, soit 13 = 0b1101
2. Nous pouvons remarquer que, quelque soit X : $X + \bar{X} = 2^N - 1$
   Donc $\bar{X} + 1 = 2^N - X = -X modulo 2^N$
   Je peux donc prendre le codage de +3 : 0b0011, complémenter chaque bit et ajouter 1 pour trouver le codage de -3.
   $+\bar{3} + 1 = 0b1100 + 0b0001 = 0b1101$

2.4 - Débordements

Si j’additionne 2 nombres de signes opposés ( ex : +7 + (-2), +2 + (-8), etc.. ) , je retomberai toujours dans l’intervalle de définition [-8 +7], donc pas de débordement.

L’addition de 2 nombres de même signe donnant un résultat de signe opposé correspond à un débordement signé ( oVerflow )

Remarquons au passage que les deux dernières retenues sont opposées dans ce cas.

2.5 - Extension de Format

Supposons que je passe d’un format signé 4 bits à un format signé 8 bits.

Nombres Positifs

il suffit d’ajouter des zéros sur les poids forts pour compléter :

+3 = 0b0011 –> 0b00000011

Nombres Négatifs

On peut remarquer que $-2^N + 2^{N-1} = -2^{N-1}$

Ainsi si j’applique la définition du codage complément à 2 :

$-3 = 0b1101 = -1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$
$-3 = 0b11101 = -1.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$
$-3 = 0b111101 = -1.2^5 + 1.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$
$-3 = 0b1111101 = -1.2^6 + 1.2^5 + 1.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$
$-3 = 0b11111101 = -1.2^7 + 1.2^6 + 1.2^5 + 1.2^4 + 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0$

Il suffit donc d’ajouter des 1 sur les poids forts pour étendre le format des nombres négatifs.

2.6 - L’additionneur/Soustracteur

Une soustraction peut être vue comme l’addition de l’opposé d’un nombre.
Nous avons vu précédemment que pour trouver le codage de l’opposé d’un nombre, il suffit de :

• complémenter ce nombre
• Ajouter 1

$-X = \bar{X}+1$

La complémentation conditionnelle peut être réalisée avec une porte ou exclusif ; La retenue de poids faible peut servir à ajouter 1.

$S = A - B = A + \bar{B} + 1$

---

3 - Codage des Réels : Virgule Fixe

Nous avons supposé précédemment que les pondérations étaitent entières :

$7 = 0b0111 = 0.2^3 + 1.2^2 + 1.2^1 + 1.2^0$

Je peux très bien faire correspondre des pondérations fractionnaires à mes digits :

$0b0.111 = 0.2^0 + 1.2^{-1} + 1.2^{-2} + 1.2^{-3} = 0+0.5+0.25+0.125 = 0.875$

La Quantité Représentée est donc Fractionnaire

Le Codage ( les 0 et les 1 ) est le même pour la quantité +7 et +0.875.

Le format I.Q utilisé pour ce dernier est 1.3 ( 1 bit pour la partie entière, 3 bits pour la partie fractionnaire ).

Ce format est fixé a priori pour un calcul ( d’où le nom virgule fixe )

Dans les langages informatiques il n’existe pas de type standard ‘virgule fixe’.
Le processeur effectue ses calculs bit à bit ( cf additionneur ), le codage d’un entier étant le même que pour une quantité à virgule, c’est le type entier ( int ) qui est utilisé pour réaliser un calcul en virgule fixe.

Exemple :

Je dois réaliser le calcul suivant sur 8 bits : $y = 3.75 \times 2.3 - 1.2 \times 0.5$ ( je dois normalement trouver 8.025 )

Je dois donc coder : 3.75, 2.3, -1.2 et 0.5.

Il me faut suffisamment de bits pour coder la partie entière ‘3’ de la valeur max ‘3.75’, soit 3 bits en signé.

On part donc sur le format I.Q 3.5

Le codage de 3.7 au format virgule fixe 3.5 est le même que le codage entier de $( 3.75 \times 2^5 )$, soit 120 = 0x78.

Il en va de même pour les autres valeurs :

$3.75 \times 2^5 = 120$
$2.3 \times 2^5 = 73.6$ – arrondi –> 74
$-1.2 \times 2^5 = -38.4$ – arrondi –> -38
$0.5 \times 2^5 = 16$

REMARQUE : Comme le codage se fait sur un nombre de bits fini, je suis obligé d’arrondir ; ici l’erreur de codage sera toujours inférieure à $2^5$

La multiplication de 2 valeurs au format 3.5 me donne un résultat au format 6.10 ( doublement du format des opérandes et décalage de la virgule comme en base 10 ).

J’ai donc un résultat $2^{10}$ fois trop grand.

$y = Y/2^{10}$
$y = 8.072125$

Les arrondis font que mon résultat n’est pas exactement le résultat attendu.

---

4 - Codage des Réels Virgule Flottante

Dès lors que je déclare une variable en tant que float ou double dans un programme, il s’agit d’un codage virgule flottante.

4.1 - Norme IEEE P754 ( version 32 bits )

Le codage d’un nombre en virgule flottante se présente ainsi :

$-S.M.2^E$

• s : bit de signe ( 0 positif, 1 négatif )
• E : Exposant
• M : Mantisse, 1 < M < 2, au format virgule fixe unsigned 1.23

Exemple : Codage de -60.47

s = 1
$E = log_2(60.47) = \frac{ln(60.47)}{ln(2)} -> E = 5 -> E+127 = 132 = 0x84$
$M = \frac{60.47}{2^5}=1.8896875 -> 1.8896875*2^{23} = 15851848 = 0xF1E148$

Comme le bit de poids fort de la mantisse vaut toujours 1, ce bit de poids fort disparait.

4.2 - Intérêts/inconvénients du codage virgule flottante :

Intérêts :

• Dynamique : possibilité de coder des valeurs très grandes ou très petites ( grâce à l’exposant )
• Précision : l’erreur ne porte que sur la mantisse, elle est donc bornée

Inconvénient : Si le processeur ne possède pas d’unité de calcul pour traiter les flottants, le calcul prend plus de temps ( il faut traiter la matrice, l’exposant, faire des décalages, normaliser, etc.. ).