L’additionneur expliqué simplement : de la porte XOR à l’addition binaire
Votre téléphone fait des milliards d’additions par seconde, et pourtant il ne connaît que 0 et 1. Comment fait-il ? Avec deux portes logiques, un XOR et un ET, branchées côte à côte. Voici l’additionneur, pas à pas, avec son schéma.
| A | B | S | R |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Compter avec seulement 0 et 1
Nous comptons en base dix : dix chiffres, de 0 à 9, et quand on dépasse 9, on écrit un 1 dans la colonne des dizaines. Un ordinateur compte en base deux, ou binaire : deux chiffres seulement, 0 et 1. Quand on dépasse 1, on passe à la colonne suivante. Ainsi deux s’écrit 10, trois 11, quatre 100, cinq 101, six 110. Chaque colonne vaut le double de celle de droite : 1, 2, 4, 8, 16…
Un chiffre binaire s’appelle un bit. Pour un circuit, c’est parfait : un fil est sous tension (1) ou ne l’est pas (0).
Additionner deux bits : quatre cas seulement
Additionner deux bits, A et B, ne donne que quatre cas. 0 + 0 = 0. 0 + 1 = 1. 1 + 0 = 1. Et 1 + 1 = 2, qui s’écrit 10 en binaire : on pose 0 et on retient 1, exactement comme 5 + 7 = 12 en base dix, où l’on pose 2 et l’on retient 1.
Le résultat a donc deux chiffres : la somme S, le chiffre qu’on pose, et la retenue R, celle qu’on garde pour la colonne suivante. Dans la table de vérité, S vaut 0, 1, 1, 0 et R vaut 0, 0, 0, 1.
La somme, c’est une porte XOR
Regardez la colonne S : elle vaut 1 quand A et B sont différents, 0 quand ils sont égaux. C’est exactement la règle de la porte XOR, le « ou exclusif », celle de l’interrupteur va-et-vient d’un couloir. La page de la porte XOR la détaille, avec un circuit à jouer.
La retenue, c’est une porte ET
La colonne R ne vaut 1 que sur la dernière ligne, quand A et B valent 1 tous les deux : c’est la porte ET. Il suffit donc de brancher A et B sur deux portes à la fois, un XOR et un ET, pour obtenir un demi-additionneur, celui du schéma. Deux portes, et la machine sait faire 1 + 1.
Vous pouvez le vérifier vous-même : le dernier des 10 circuits gratuits de l’accueil, « Le demi-additionneur », demande de poser la porte de la somme.
Pourquoi « demi » ?
Parce qu’il lui manque quelque chose. Dès la deuxième colonne d’une addition, il faut additionner trois bits : celui de A, celui de B, et la retenue qui arrive de la colonne de droite. L’additionneur complet a donc trois entrées : A, B et la retenue entrante Re.
Sa somme se calcule avec deux XOR à la suite : A XOR B, puis le résultat XOR Re. Sa retenue sortante vaut 1 dès qu’au moins deux des trois bits valent 1. Ce « au moins deux sur trois », c’est un vote à la majorité, et c’est justement l’avant-dernier circuit gratuit, « Le vote à la majorité » : trois portes ET et deux portes OU. Sans le savoir, celui qui l’a résolu a construit la retenue d’un additionneur.
Une addition complète, colonne par colonne
Additionnons 5 et 3. En binaire, 5 s’écrit 101 et 3 s’écrit 011. Colonne de droite : 1 + 1 = 10, on pose 0, on retient 1. Colonne du milieu : 0 + 1 + la retenue 1 = 10, on pose 0, on retient 1. Colonne de gauche : 1 + 0 + 1 = 10, on pose 0, on retient 1. La dernière retenue devient le premier chiffre : 1000, c’est-à-dire 8. Le compte est bon.
Un circuit fait la même chose : un additionneur par colonne, et la retenue de chacun reliée à l’entrée du suivant. On appelle ce montage un additionneur à propagation de retenue. Pour additionner deux nombres de 64 bits, il suffirait d’en aligner 64 ; les vrais processeurs utilisent des montages plus rapides, mais l’idée de départ est celle-ci.
Et ensuite ?
Avec des additions, on fait des soustractions (grâce à une astuce d’écriture des nombres négatifs, le complément à deux), des multiplications (des additions décalées) et presque tout le calcul d’un ordinateur. Tout part de deux portes qu’un collégien pose en une minute.
En classe, la séance « XOR et l’additionneur » de notre Pack Profs et clubs (15 €) fait calculer somme et retenue à la main, puis les vérifier sur des circuits projetés.