Codage des entiers
Codage des entiers
Codage des entiers
En binaire, un nombre correspond à une suite de 0 et de 1, que l’on convertit en une écriture en puissance de 10 usuelle en sommant le produit des chiffres du nombre par des puissances de 2 successives.
On considère $n = overline{x_nx_{n-1}…x_1x_0}^2$ avec $x_n in {0; 1 }$.
Alors, $n = displaystyle sum_limits{k = 0}^n x_k 2^k = x_0 times 2^0 + x_1 times 2^1 + … +x_n times 2^n$.
Pour coder un tel entier, on utilise une mémoire composée de $n + 1$ bits, avec $n + 1 geq 8$.
Le bit de rang 0 est appelé bit de poids faible.
Le bit de rang $n$ est appelé bit de poids fort.
Il y a $n + 1$ bits.
| n | n-1 | n-2 | 2 | 1 | 0 |
I. Codage des entiers naturels
On souhaite par exemple coder $19$. On sait que $19 = overline{10011}^2$.
On écrit donc ces chiffres en partant de la droite et du bit de poids faible. On remplit le reste des cases par des 0.
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| n | n-1 | n-2 | … | 4 | 3 | 2 | 1 | 0 |
On suppose que $n + 1 = 8$.
Dans une telle situation, le nombre maximal que l’on peut coder correspond au nombre où tous les chiffres sont des 1 :
$displaystyle sum_limits{k = 0}^7 2^k = 2^{7 + 1} – 1 = 2^8 – 1 = 255$.
En utilisant 8 bits on peut coder tous les entiers compris entre 0 et 255.
De même, si on suppose que $n + 1 = 16$, on peut écrire tous les entiers compris entre 0 et $2^{16} – 1 = 65535$.
II. Codage des entiers relatifs
1. Méthode du nombre binaire signé
Une des solutions est l’utilisation de nombre binaire signé.
Dans ce cas, le $n + 1$ème bit (qui correspond au bit de rang $n$) est réservé pour coder le signe du nombre considéré.
L’usage du $1$ dans le bit de poids fort indique que le nombre est négatif.
Exemple :
On veut coder l’entier $-10 = – overline{1010}^2$.
On écrit alors dans les bits la série suivante, en inscrivant dans le bit de poids fort le chiffre $1$ car le nombre codé est négatif.
| 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| n | n-1 | n-2 | … | 4 | 3 | 2 | 1 | 0 |
L’usage de réserver le bit de poids fort au signe implique la perte d’un bit et donc une réduction des possibilités de codage des nombres positifs.
En effet, si $n + 1 = 8$, il n’y a que 7 bits pour coder les nombres.
Le plus grand nombre vaut alors $displaystyle sum_limits{k = 0}^6 2^k = 2^{6 + 1} – 1 = 2^7 – 1 = 127$.
On peut alors coder tous les entiers relatifs compris entre $-127$ et $+127$.
Si $n+ 1 = 16$, il est alors possible de coder tous les entiers relatifs compris entre $-32767$ et $32767$.
En informatique, $0$ est considéré comme un nombre positif et est donc codé en n’utilisant que des $0$.
Il reste donc une possibilité qui correspond au $0$ négatif et codé en utilisant un $1$ dans le bit de poids fort et des $0$ ailleurs, qui est utilisé pour coder l’entier $-2^n$.
On code alors tous les entiers relatifs compris entre $-2^n$ et $-2^{n-1}$.
2. Méthode des compléments à 2
Principe
Une autre solution est l’utilisation de la méthode des compléments à 2.
Si l’entier est positif, la méthode ne change pas.
Si l’entier est négatif, on commence par coder sa valeur absolue, c’est à dire son opposé qui est positif.
On code alors selon la méthode binaire signé positif puis on complémente tous les bits non utilisé à 1 puis on ajoute 1.
Exemple
On souhaite coder l’entier relatif $-14$.
On sait que $|-14| = 14$.
On commence donc par coder sa valeur absolue donc $14$, le bit de poids fort contient un 0 car 14 est positif.
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
Dans une nouvelle ligne, on remplace les 0 par des 1 et réciproquement.
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
A ce nouveau nombre on ajoute $1$ dans le bit de poids faible, en se souvenant que $1 + 1$ correspond à une retenue de 1 pour la colonne suivante.
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
Remarque
Dans la méthode précédente, on voit qu’en ajoutant 1, il est possible de propager la retenue dans chaque colonne si tous les bits contenaient des 1.
Se faisant, on obtiendrait alors un chiffre qui devrait être stocké plus loin que le bit de poids fort.
Or, si tous les bits contenaient des 1, cela signifie que l’on codait le nombre de contenant que des 0, c’est à dire l’entier 0 qui n’est pas négatif : il ne sera donc jamais codé en utilisant la méthode des compléments à 2.
Si les entiers codés sont différents de 0, alors le codage de la valeur absolue fait au moins apparaitre un 1, donc le complément fait apparaitre au moins un 0 : la propagation de la retenue éventuelle est donc forcément stoppée.
Exemple
Codage de $-1$ en reprenant ces trois étapes.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
On se propose de regarder d’un point de vue mathématique les opérations que l’on réalise pour le codage.
La première étape correspond au codage de la valeur absolue $|x|$ du nombre $x$, qui ne contient que des 0 sauf le bit de poids faible qui contient un 1.
Pour trouver le complément à 1 de ce nombre, on soustrait en réalité le nombre ne contenant que des 1 et la valeur absolue du nombre codé.
Le nombre ne contenant que des 1 correspond à $2^8 – 1$.
On vient donc de coder l’entier naturel $2^8 – 1 – |x|$.
Si on ajoute $1$ à ce nombre, on trouve alors $2^8 – |x|$, dans le codage des entiers naturels.
Finalement, il ne s’agit donc pas du complément à 2 mais à $2^8$ que l’on code, mais pour simplifier, on dira complément à 2.
Technique pour écrire rapidement le complément à 2
Pour écrire plus rapidement le complément à 2, il existe des techniques.
Une technique consiste à coder la valeur absolue du nombre, puis de partir du bit de poids faible et de recopier les chiffres jusqu’au premier 1 inclus.
Les chiffres suivants sont inversés par rapport au codage de la valeur absolue.
Exemple avec le codage de -20 :
On code 20 :
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Puis on obtient:
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
Intérêt d’une telle méthode
On code par exemple par la méthode du binaire signé les entiers 3 et $-4$.
Si on somme les deux séries de 8 bits obtenus deux à deux, on obtient alors un nouveau nombre qui n’est pas égal à $-1$
En utilisant la méthode des compléments à 2, on obtient en addition bit à bit le nombre -1.