Résumé : cf Résumé_Codage_des_Nombres
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.10^1+5.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.2^3 + 1.2^2 + 0.2^1 + 1.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.2^7 + 1.2^6 + 0.2^5 + 0.2^4 } + \color{blue}{1.2^3 + 0.2^2 + 1.2^1 + 0.2^0} \)
soit \( x = \color{red}{( 1.2^3 + 1.2^2 + 0.2^1 + 0.2^0 )}.2^4 + \color{blue}{(1.2^3 + 0.2^2 + 1.2^1 + 0.2^0)}.2^0 \)
soit \( x = \color{red}{( 1.2^3 + 1.2^2 + 0.2^1 + 0.2^0 )}.16^1 + \color{blue}{(1.2^3 + 0.2^2 + 1.2^1 + 0.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.
Reprenons l’exemple précédent : \( x = 13 = \color{green}{?}.2^3 + \color{orange}{?}.2^2 + \color{blue}{?}.2^1 + \color{red}{?}.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}.2^3 + \color{orange}{1}.2^2 + \color{blue}{0}.2^1 + \color{red}{1}.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} \)
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 \) ).
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 :
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) :
Nous aurons donc sur 4 bits :
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) :
\( X = -b_3.2^3 + b_2.2^2 + b_1.2^1 + b_0.2^0 \)
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.
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.
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.
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 :
\( -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 \)
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.
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.
Le codage d’un nombre en virgule flottante se présente ainsi :
\( -S.M.2^E \)
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.
Intérêts :
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.. ).