4. Additionneur¶
On s’intéresse à une des opérations arithmétiques les plus simples : l’addition. Notre but est donc de réaliser un circuit logique capable d’additionner deux nombres entiers.
4.1. Demi-additionneur¶
On commence par additionner deux nombres à 1 bit, \(A\) et \(B\) et leur somme \(S\). La table de vérité d’une telle addition est la suivante.
\(A\) |
\(B\) |
\(S=A+B\) |
|---|---|---|
0 |
0 |
00 |
1 |
0 |
01 |
0 |
1 |
01 |
1 |
1 |
10 |
On note que la somme de deux bits peut faire \(2\), c’est à dire \(10\) en binaire. La sortie \(S\) doit donc être codée sur deux bits, qu’on appelle \(S_0\) (bit des unité, de droite), et \(S_1\) (bit de la valeur décimale 2, à gauche). On peut donc ré-écrire la table de vérité ci-dessus ainsi:
\(A\) |
\(B\) |
\(S_1\) |
\(S_0\) |
|---|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
En comparant cette table de vérité avec celles des portes logiques, on se rend compte que \(S_0\) n’est autre qu’un OU-X (OU exclusif) de \(A\) et \(B\), tandis quie celle de \(S_1\) est un ET. On peut dessiner l’additionneur de deux bits (appelé demi-additionneur) ainsi :
Exercice 1
Vérifiez que ce circuit livre bien les bonnes valeurs de sortie qui correspondent aux tables de vérité ci-dessous. Combien de combinaisons différentes devrez-vous tester ?
Solution 1
Le circuit fonctionne correctement. Il faut tester les quatre combinaisons qui apparaissent dans les tables de vérité.
4.2. Additionneur complet¶
Le circuit précédent est particulièrement intéressant, car il montre qu’il est possible d’utiliser des opérateurs logiques pour réaliser l’opération arithmétique de l’addition. L’additionneur est limité: en fait, on l’appelle un demi-additionneur. Il n’est capable d’additionner que deux bits — c’est très limité. En fait, il serait intéressant d’avoir un additionneur de trois bits. Pourquoi ? À cause de la manière dont on pose les additions en colonnes.
Lorsqu’on additionne deux nombres à plusieurs chiffres, que ce soit en base 10 ou en base 2, on commence par la colonne de droite, les unités. On connait le concept de retenue: en base 10, si l’addition des unités dépasse 9, on retient 1 dans la colonne des dizaines. En base 2, de façon similaire, si l’addition des unités dépasse… 1, on retient 1 dans la colonne suivante à gauche. C’est ce qu’on a fait avec le demi-additionneur: on peut considérer que la sortie \(S_0\) représente la colonne des unités dans la somme, et la sortie \(S_1\) représente la retenue à prendre en compte dans la colonne suivante.
C’est ici que ça se complique : pour additionner les chiffres de la deuxième colonne, on doit potentiellement additionner trois chiffres, et plus seulement deux. On a donc, en entrée, les deux bits \(A\) et \(B\) qui viennent des nombres à additionner, et aussi potentiellement cette retenue qui vient de la colonne des unités, qu’on appellera \(C_{in}\) (pour carry, «retenue» en anglais). Ceci est vrai en base 2 comme en base 10. Il faut donc un additionneur plus puissant, à trois entrées, pour prendre en compte cette retenue. Il s’appelle additionneur complet et livrera deux sorties : le bit de somme, appelé simplement \(S\), et la retenue à reporter pour la colonne suivante, appelée \(C_{out}\).
Exercice 2 – Table de vérité de l’additionneur
Déterminez combien de combinaisons différentes sont possibles pour trois signaux d’entrée \(A\), \(B\) et \(C_{in}\) qui chacun peuvent valoir soit 1 soit 0.
Listez toutes ces combinaisons.
Pour chaque combinaison, déterminez la valeur binaire qui est la somme des trois signaux d’entrée.
Finalement, avec les informations ainsi obtenues, complétez la table de vérité d’un additionneur complet qui a deux sorties \(S_0\) et \(C_{out}\) (qui correspond à \(S_{1}\)).
Solution 2 – Table de vérité de l'additionneur
Il y a \(2 \cdot 2 \cdot 2 = 2^3 = 8\) combinaisons différentes. Avec la notation \(A + B + C =\) valeur en décimal \(=\) valeur en binaire, les voici :
\(0 + 0 + 0 = 0_{(10)} = 00_{(2)}\)
\(0 + 0 + 1 = 1_{(10)} = 01_{(2)}\)
\(0 + 1 + 0 = 1_{(10)} = 01_{(2)}\)
\(0 + 1 + 1 = 2_{(10)} = 10_{(2)}\)
\(1 + 0 + 0 = 1_{(10)} = 01_{(2)}\)
\(1 + 0 + 1 = 2_{(10)} = 10_{(2)}\)
\(1 + 1 + 0 = 2_{(10)} = 10_{(2)}\)
\(1 + 1 + 1 = 3_{(10)} = 11_{(2)}\)
La table de vérité est ainsi:
\(A\) |
\(B\) |
\(C_{in}\) |
\(C_{out}\) |
\(S_0\) |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Exercice 3 – Circuit de l’additionneur
Déterminer les fonctions logiques correspondant aux sorties \(S\) et \(C_{out}\) de la table de vérité de l’additionneur de l’exercice ci-dessus. En déduire son circuit logique
Solution 3 – Circuit de l'additionneur
On remarque que \(S_0\) vaut B OU-X \(C_{in}\) si A=0 et NON (B OU-X \(C_{in}\)) si A=1.
Autrement dit \(S_0\) = (NON A) ET (B OU-X \(C_{in}\)) OU (A ET NON (B OU-X \(C_{in}\))).
Cela peut se simpifier en \(S_0\) = A OU-X (B OU-X \(C_{in}\))
Pour \(C_{out}\), on remarque qu’il vaut 1, s’il y a au moins deux 1 parmi les trois entrées. Donc si A est 0 on est obligé d’avoir B et \(C_{in}\) à 1 pour que \(C_{out}\) soit à 1. Si A est 1, alors il suffit que B ou C vale 1 pour que \(C_{out}\) soit à 1.
Autrement dit \(C_{out}\) = (A ET (B OU \(C_{in}\))) OU (B ET \(C_{in}\))
Le circuit correspondant est donc le suivant:
Micro-activité
Vérifier que le circuit donné dans la solution de l’exercice ci-dessus donne bien en sortie la somme des trois entrée.
On peut représenter ce circuit comme un nouveau composant à trois entrées et deux sorties, que l’on dessine simplement ainsi :
4.3. Chaînage d’additionneurs¶
La flexibilité de ce composant fait qu’on peut maintenant facilement l’utiliser pour construire un circuit qui additionne deux nombres \(A\) et \(B\) à 2 bits chacun (donc de \(0 + 0 = 0\) à \(3 + 3 = 6\)).
Si \(A\) est formé de deux bits \(A_0\) et \(A_1\) et que \(B\) est formé des deux bits \(B_0\) et \(B_1\) et avec une sortie \(S\) sur trois bits \(S_0\), \(S_1\) et \(S_2\), on a :
L’additionneur de droite, comme précédemment, additionne les deux bits des unités : \(A_0\) et \(B_0\). Son entrée \(C_{in}\), qui représente l’éventuel troisième chiffre à additionner issu d’une retenue, n’est pas connectée et est toujours 0, vu qu’il n’y a aucune colonne précédente dans l’addition qui aurait pu en livrer une. Il livre comme première sortie \(S_0\), le chiffre des unités, et sa seconde sortie \(C_{out}\) est la retenue à utiliser pour l’addition des chiffres suivants. C’est pourquoi elle est connectée à l’entrée de la retenue du second additionneur \(C_{in}\), qui va lui ajouter également les deux bits de la colonne suivante, \(A_1\) et \(B_1\). Les sorties du second additionneur livrent le deuxième bit \(S_1\) de la valeur de sortie, ainsi que la retenue pour la troisième colonne. Comme il n’y a plus de bits d’entrée pour la troisième colonne, cette retenue peut directement être considérée comme le troisième bit de sortie \(S_2\).
Exercice 4 – Limite de cet additionneur à 2 bits
Avec l’additionneur ci-dessus, est-il possible d’obtenir des 1 sur toutes les sorties, donc d’avoir \(S_2 = S_1 = S_0 = 1\) ?
Solution 4 – Limite de cet additionneur à 2 bits
La configuration \(S_2 = S_1 = S_0 = 1\) représente le nombre décimal 7. Ce serait le résultat de l’addition. Il faudrait ainsi chercher une configuration des bits d’entrées qui, une fois additionnés, donnent 7. Mais ceci n’est pas possible, car sur chacune des entrées \((A_1, A_0)\) et \((B_1, B_0)\), la plus grande valeur représentable est \(11_{(2)}\), autrement dit \(3_{(10)}\) — et c’est impossible d’atteindre 7 en évaluant au maximum \(3+3\).
Exercice 5 – Additionneur de demi-octets
En connectant des additionneurs complets, réalisez un circuit qui additionne deux nombres \(A\) et \(B\) de quatre bits, numérotés \(A_0\) à \(A_3\) et \(B_0\) à \(B_3\), respectivement. Combien de bits de sortie doit-il y avoir pour traiter toutes les valeurs possibles ?
Les entrées sont déjà disposées. Glissez autant d’additionneurs et de bits de sortie que nécessaire et connectez les composants du circuit.
Solution 5 – Additionneur de demi-octets
On a besoin de cinq bits de sortie. Le schéma, représenté horizontalement et de droite à gauche pour être proche de la représentation selon laquelle les additions se résolvent en colonne, est :
Cet exercice démontre l’opportunité de penser en termes modulaires, ce qui revient souvent en informatique. Ici, on a réalisé qu’un additionneur complet résout un sous-problème bien défini d’une addition générale d’un nombre à \(n\) bits, et qu’une fois qu’on a créé un tel additionneur, il suffit d’en connecter plusieurs les uns derrière les autres de manière structurée pour additionner des nombres plus grands.
Exercice 6 – Dépassement de capacité
Le schéma ci-dessous montre le même additionneur de demi-octets de l’exercice précédent, mais, de plus, la valeur en base 10 de ses 4 bits d’entrée pour \(A\) et pour \(B\) est affichée avec un module d’affichage spécial à droite. La même chose est faite pour représenter la valeur \(S = A + B\) (mais seulement sur les quatre premiers bits de \(S\)). Actuellement, le circuit effectue le calcul \(0 + 0 = 0\).
Réglez les entrées du circuit de manière à lui faire effectuer les additions suivantes, et vérifiez le résultat. Dans quelles circonstances est-il correct et pourquoi est-il de temps en temps incorrect ? Comment, en regard de ceci, interpréter le bit de sortie \(S_4\), qui est la retenue de l’additionneur de gauche ?
\(1 + 0\)
\(3 + 1\)
\(3 + 3\)
\(10 + 5\)
\(14 + 1\)
\(14 + 2\)
\(15 + 15\)
Solution 6 – Dépassement de capacité
Dès que la somme dépasse 15, elle n’est plus représentable sur les 4 bits qui sont affichés sur la sortie. La plupart des ordinateurs et smartphones actuels représentent les nombres non pas sur 4 bits, mais sur 64. Mais même avec 64 bits, il y a un nombre maximal que l’on peut représenter (en l’occurrence, \(2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615\).) La retenue du dernier additionneur indique si le résultat est valable : il vaut 1 lorsque le résultat de l’addition n’est pas correctement représenté avec les 4 (ou 64) bits de sortie. Dans les processeurs, il porte souvent simplement le nom de \(C\) (pour carry, retenue). On utilisera dorénavant aussi ce nom.
Exercice 7 – Circuit défectueux
L’additionneur de demi-octets ci-dessous a été endommagé et ne fonctionne plus correctement. Par exemple, lorsqu’on lui demande d’effectuer le calcul \(11 + 1\), il livre comme réponse \(8\).
Déterminez quel composant est défectueux dans ce circuit et comment il faudrait le réparer. Vous pouvez changer les entrées pour vérifier ce qui ne fonctionne pas.
Solution 7 – Circuit défectueux
La retenue sortant du deuxième additionneur depuis la droite est bloquée à 0 à la place de correctement changer de valeur suivant ses entrées.