L'algèbre de Boole et les portes logiques
Partie 4 sur 4
9Les additionneurs
Un additionneur est un circuit capable de faire la somme de plusieurs nombres. Une addition met en œuvre deux sorties : la somme, généralement notée S, et la retenue, généralement notée R. Lorsque l’on fait une somme en décimal (base 10), on ajoute dans un premier temps les deux unités ; si le résultat obtenu est supérieur à 10, on garde l’unité en résultat et on reporte la dizaine en retenue, pour l’ajouter lors de la somme des dizaines. Ce procédé est le même en binaire, avec 2 à la place de 10 (voir le binaire).
9.1Additionner deux nombres de 1 bit
Pour une addition de deux nombres A et B de 1 bit, quatre combinaisons sont possibles, et le résultat occupe 2 bits : un bit pour la somme (S) et un pour la retenue (R). La table de vérité de cette fonction est :
| A | B | R | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Lisons : 0 + 0 = 0 ; 0 + 1 = 1 ; 1 + 0 = 1 ; et 1 + 1 = 10 en binaire, c’est-à-dire somme 0 et retenue 1. On reconnaît deux tables connues : la colonne S est celle du OU exclusif (S = A ⊕ B), la colonne R est celle du ET (R = A . B). Le circuit se représente donc selon un schéma très simple : une porte XOR et une porte ET, alimentées par les mêmes entrées. On l’appelle demi-additionneur, parce qu’il ne gère pas de retenue qui viendrait d’un rang précédent.
9.2L’additionneur complet
Pour additionner des nombres de plusieurs bits, il faut qu’à chaque rang l’additionneur accepte trois entrées : les deux bits à additionner et la retenue venant du rang précédent. On construit cet additionneur complet en enchaînant deux demi-additionneurs et une porte OU, comme le montre la figure 3. Le premier demi-additionneur additionne A et B ; le second ajoute à sa somme la retenue entrante ; la retenue sortante est le OU des deux retenues intermédiaires (une seule des deux peut valoir 1 en même temps, ce que l’on peut démontrer en vérifiant les huit cas).
9.3Additionner des nombres de plusieurs bits
Pour additionner deux nombres de quatre bits, on met quatre additionneurs complets côte à côte, et l’on relie la retenue sortante de chacun à la retenue entrante du suivant. On les enchaîne comme des dominos : on parle d’additionneur à propagation de retenue. Exemple : 0110 (6) + 0111 (7). Rang 0 : 0 + 1 = 1, retenue 0. Rang 1 : 1 + 1 = 0, retenue 1. Rang 2 : 1 + 1 + retenue 1 = 1, retenue 1. Rang 3 : 0 + 0 + retenue 1 = 1, retenue 0. Résultat : 1101, soit 13. On a bien 6 + 7 = 13.
La propagation de la retenue a un coût : le dernier rang doit attendre que tous les précédents aient fini, ce qui ajoute des retards (partie 4.2). Les processeurs utilisent donc des additionneurs plus élaborés, qui « devinent » les retenues à l’avance (additionneurs à anticipation de retenue) pour additionner des nombres de 64 bits presque aussi vite que de 8 bits.
9.4Et la soustraction, la multiplication ?
Une fois l’additionneur construit, le reste en découle. La soustraction se ramène à une addition avec le complément à deux (voir le binaire). La multiplication se ramène à une série d’additions décalées, comme celle que l’on pose à l’école. La division, plus complexe, se ramène à des soustractions répétées. L’ensemble de ces circuits arithmétiques, avec des portes de comparaison et de décalage, forme l’unité arithmétique et logique du processeur, la partie qui exécute les calculs (voir le processeur).
9.5Le dépassement
Que se passe-t-il si le résultat ne tient pas dans le nombre de bits prévu ? Sur 4 bits, 1111 + 0001 donne 10000 : le cinquième bit n’existe pas. La retenue sortante du dernier rang signale ce dépassement (overflow). Les programmes qui ne le surveillent pas obtiennent des résultats faux (15 + 1 = 0), et dans certains cas des failles de sécurité (voir le langage C). Ce qui paraît un détail de circuit est à l’origine de bogues célèbres, dont l’explosion de la fusée Ariane 5 en 1996, causée par la conversion d’un nombre trop grand pour sa case.
Pour s’exercer
Exercice 6 : additionner en binaire avec des portes
Additionnez 1011 et 0110 en binaire, rang par rang, en indiquant les retenues. Vérifiez en décimal.
Voir la réponse
Rang 0 : 1 + 0 = 1, retenue 0. Rang 1 : 1 + 1 = 0, retenue 1. Rang 2 : 0 + 1 + retenue 1 = 0, retenue 1. Rang 3 : 1 + 0 + retenue 1 = 0, retenue 1. Il reste la retenue finale : 1. Résultat : 10001 (17). Décimal : 11 + 6 = 17. Sur 4 bits, le résultat déborde, et la retenue sortante vaut 1 : c’est le dépassement.
Exercice 7 : tout avec des NON ET
Montrez comment fabriquer un NON, puis un ET, avec uniquement des portes NON ET.
Voir la réponse
NON : relier les deux entrées d’une porte NON ET ensemble : /(A.A) = /A (idempotence). ET : placer un NON après un NON ET : /(/(A.B)) = A.B. On obtient ensuite le OU par De Morgan : A + B = /(/A . /B), donc deux NON, un NON ET suffisent. Toute fonction logique se construit ainsi avec une seule sorte de porte.
10Où retrouve-t-on la logique de Boole ?
10.1Dans les langages de programmation
Tous les langages ont des opérateurs logiques : and, or, not en Python (voir Python), &&, ||, ! en C et ses cousins (voir le langage C). Ils obéissent aux lois vues plus haut, y compris De Morgan : écrire not (a or b) ou (not a) and (not b) revient au même. Les langages ont aussi des opérateurs bit à bit (&, |, ^, ~) qui appliquent ET, OU, XOR et NON à chaque bit d’un nombre, en parallèle. Un détail utile : de nombreux langages évaluent « A et B » paresseusement : si A est faux, ils ne regardent même pas B, puisque la réponse est connue (nullité : 0.B = 0). Cette « évaluation en court-circuit » est à l’origine de nombreuses astuces et de quelques pièges.
10.2Dans les bases de données et les recherches
Une requête SQL (voir le SQL) contient une clause WHERE faite de conditions reliées par AND, OR et NOT. Une requête mal parenthésée donne un résultat différent de celui qu’on attendait : le point (ET) l’emporte sur le plus (OU), exactement comme en 5. Ajoutons que SQL a une troisième valeur, « inconnu » (NULL), qui sort du cadre de Boole : c’est la logique « à trois valeurs », source de surprises pour les débutants.
10.3Dans les réseaux
Un masque de sous-réseau s’applique à une adresse IP par un ET bit à bit : c’est ainsi qu’un routeur détermine si une machine est sur le même réseau local (voir les adresses IP). Les droits d’accès d’un fichier sous Unix sont aussi codés par des bits que l’on combine et teste avec des opérations logiques.
10.4Dans la sécurité
L’opération OU exclusif est au cœur de la cryptographie (voir la cryptographie). Pourquoi ? Parce qu’elle est réversible : si l’on calcule M xor K (un message M combiné à une clé K), on retrouve M en refaisant l’opération avec la même clé : (M xor K) xor K = M. Si la clé K est aussi longue que le message, totalement aléatoire et utilisée une seule fois, le résultat est impossible à déchiffrer sans K : c’est le « masque jetable », le seul chiffrement dont on ait prouvé qu’il est incassable. Les chiffrements modernes utilisent le XOR par milliards, mélangé à d’autres opérations. C’est aussi pourquoi l’on ne réutilise jamais une même clé de ce type : deux messages chiffrés avec la même clé, combinés entre eux, annulent la clé et laissent apparaître leur combinaison.
La logique intervient aussi dans la qualité du code : une erreur de logique (un « ou » à la place d’un « et ») dans une vérification d’autorisation peut ouvrir un accès à tout le monde. Un contrôle « l’utilisateur est administrateur ou le fichier est à lui » pris pour « et » est une faille. Les relectures de code de sécurité vérifient donc systématiquement les tables de vérité des conditions.
11Ce qui a changé
Voici les points à actualiser ou à compléter.
- Les tensions. « Environ 5 volts » correspondait aux circuits de l’époque ; aujourd’hui, 1 à 3,3 volts selon les puces.
- Les portes universelles. On oublie souvent qu’avec un seul type de porte (NON ET ou NON OU), on peut tout fabriquer : c’est la base de la fabrication industrielle.
- Le nom de Boole. On écrit parfois « Georges Boole » ; l’usage est George, de naissance anglaise.
- Le rôle de Shannon. C’est lui qui a relié l’algèbre à l’électronique en 1937 : sans ce lien, l’algèbre de Boole serait restée une curiosité philosophique.
- La conception. On ne dessine plus les circuits à la main : des langages de description et des logiciels de synthèse appliquent les lois de simplification à des milliards de portes.
- Les circuits séquentiels. La logique combinatoire ne suffit pas : la mémoire (bascules) en est le complément indispensable.
- Les usages. L’algèbre de Boole irrigue aujourd’hui la programmation, les bases de données, les réseaux, la cryptographie, et même les moteurs de recherche.
Ce qui n’a pas changé : une table de vérité, quelques portes et les lois de composition suffisent pour comprendre comment des interrupteurs deviennent un calcul.