Des interrupteurs qui ne savent pas compter
La caisse d’une boulangerie additionne une baguette et un croissant en quelques milliardièmes de seconde. Pourtant, rien dans le processeur ne sait compter.
Chaque petit composant répond seulement par oui ou par non à une question sur deux bits. Cette leçon construit l’addition à partir de ces questions.
À la fin de cette leçon
Remarque
Je peux construire un additionneur à partir de portes logiques.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Porte logique | un circuit qui change un ou deux bits d’entrée en un bit de sortie |
| Table de vérité | la liste de toutes les entrées avec la sortie de chacune |
| Retenue | le bit passé au rang suivant quand une somme est trop grande |
| Demi-additionneur | deux portes qui additionnent deux bits |
| Additionneur complet | des portes qui additionnent deux bits et une retenue |
| Débordement | un résultat trop grand pour les bits gardés |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Quatre portes répondent sur des bits
Une porte logique reçoit des bits et rend un seul bit. ET rend 1 seulement si les deux entrées valent 1. OU rend 1 si au moins une entrée vaut 1. OU exclusif, noté XOR, rend 1 si les entrées diffèrent. NON n’a qu’une entrée et l’inverse.
Une table de vérité donne chaque cas avec sa sortie. Deux entrées ne donnent que quatre cas.
Table de vérité : trois portes
| A | B | A ET B | A OU B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Aller dans le dossier d’architecture
cd ~/archAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Appliquer les portes à 12 et 10
python3 -c "print(12 & 10, 12 | 10, 12 ^ 10)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Exemple travaillé : les portes, bit par bit
| Bits | Nombre | |
|---|---|---|
| A | 1100 | 12 |
| B | 1010 | 10 |
| A ET B | 1000 | 8 |
| A OU B | 1110 | 14 |
| A XOR B | 0110 | 6 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Deux portes additionnent deux bits
L’addition de deux bits n’a que quatre cas. 0 + 0 donne 0, 0 + 1 et 1 + 0 donnent 1. Mais 1 + 1 donne 2, qui s’écrit 10 en binaire.
Le bit de droite du résultat est A XOR B. Le bit de gauche, la retenue, est A ET B. Une porte XOR et une porte ET forment donc un demi-additionneur.
Table de vérité : un demi-additionneur
| A | B | Somme (XOR) | Retenue (ET) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
XOR donne la somme sans les retenues
python3 -c "print(12 + 10, 12 ^ 10, (12 & 10) << 1)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
L’additionneur complet reçoit une retenue
Chaque rang, sauf le premier, doit aussi ajouter la retenue du rang de droite. Il additionne donc trois bits.
Un additionneur complet le fait avec deux demi-additionneurs et une porte OU. Quatre additionneurs complets à la suite additionnent des nombres de 4 bits. La retenue se propage de droite à gauche : on parle d’additionneur à propagation de retenue.
Exemple travaillé : 0101 + 0011, de droite à gauche
| Rang | A | B | Retenue entrante | Somme | Retenue sortante |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 0 | 1 | 0 | 1 |
| 8 | 0 | 0 | 1 | 1 | 0 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Quand le résultat ne tient pas
Un additionneur garde un nombre fixe de bits. Pour des nombres sans signe, la retenue qui sort du dernier rang est perdue et le résultat repart de zéro.
Pour des nombres signés, le test change. 0101 + 0011 font 8, mais en complément à deux sur 4 bits, 1000 se lit -8. Deux positifs ont donné un négatif : c’est aussi un débordement, sans aucune retenue sortante.
Écrire un programme qui additionne 250 et 10
printf '.globl _start\n_start:\n li a0, 250\n li a1, 10\n add a0, a0, a1\n li a7, 93\n ecall\n' > deborde.sAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
L’assembler
riscv64-linux-gnu-as deborde.s -o deborde.oAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Faire l’édition de liens
riscv64-linux-gnu-ld deborde.o -o debordeAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le lancer dans l’émulateur
qemu-riscv64 ./debordeAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Lire le code de sortie
echo $?Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent qu’un débordement veut toujours dire une retenue sortie du dernier rang. C’est vrai seulement sans signe. En complément à deux, 1110 + 0011 fait sortir une retenue, et pourtant -2 + 3 = 1 est juste. Il y a débordement signé quand deux entrées de même signe donnent un résultat de l’autre signe.
Pour aller plus loin : soustraire avec un additionneur
Un processeur n’a pas de circuit à part pour la soustraction. Il calcule a - b comme a + (NON b) + 1, car NON b + 1 vaut -b en complément à deux.
Écrivez soustraire(a, b) avec votre additionner : inversez chaque bit de b, ajoutez-le à a, puis ajoutez 0001. Essayez 0111 - 0010 et 0010 - 0111. Dites ensuite comment le matériel peut éviter la seconde addition.