Chaque instruction qu’exécute le CPU — chaque add, cmp et and du niveau de l’assembleur — finit en signaux qui traversent des portes : de minuscules circuits qui reçoivent quelques bits et en produisent un. Un processeur moderne en compte des milliards. Ce niveau construit tout à partir des portes : additionneurs et ALU, multiplexeurs et décodeurs, puis mémoire et registres.
Des tensions aux bits
Un circuit numérique n’utilise que deux plages de tension. Près de 0 volt signifie 0 ; près de la tension d’alimentation — environ 1 volt dans un CPU moderne — signifie 1. Tout ce qui est entre les deux est interdit. Cet écart fait la robustesse de la logique numérique : un signal un peu bruité reste clairement un 0 ou un 1, et chaque porte ressort des niveaux propres.
Une porte calcule une fonction fixe de ses entrées. La façon dont on la construit avec des transistors relève du niveau des composants, plus bas. À ce niveau-ci, une porte n’est qu’une fonction, décrite par sa table de vérité : une ligne par combinaison d’entrées.
Les portes de base
Basculez A et B et regardez toutes les portes réagir en même temps. La table de vérité sous le circuit met en évidence la ligne courante :
| A | B | NOT A | A AND B | A OR B | A XOR B | A NAND B | A NOR B | A XNOR B |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
Every basic gate fed by the same two switches. Toggle A and B and watch the truth table follow. NAND and NOR are universal: every other gate can be built from either one.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
| Porte | Sortie à 1 quand… | Notation algébrique |
|---|---|---|
| NOT | l’entrée vaut 0 | A̅ (ou ¬A) |
| AND | les deux entrées valent 1 | A·B, ou AB |
| OR | au moins une entrée vaut 1 | A + B |
| XOR | exactement une entrée vaut 1 | A ⊕ B |
| NAND | pas les deux à 1 | ¬(AB) |
| NOR | aucune à 1 | ¬(A + B) |
| XNOR | les entrées sont égales | ¬(A ⊕ B) |
Le petit cercle de NOT, NAND, NOR et XNOR est une bulle d’inversion : il signifie « puis inverser ».
Combien de fonctions existe-t-il ?
Une fonction de n entrées est entièrement décrite par sa table de vérité, qui a 2ⁿ lignes, chacune avec une sortie à 0 ou 1. Il existe donc 2^(2ⁿ) fonctions possibles : 16 fonctions de deux entrées. Listez les lignes dans l’ordre 00, 01, 10, 11, et chaque fonction a un nom de 4 bits formé par sa colonne de sortie : AND est 0001, OR 0111, XOR 0110, NAND 1110, NOR 1000. Les onze autres comprennent les constantes 0000 et 1111, « juste A », « juste B », et quelques-unes comme « A et pas B ».
Avec trois entrées, il y a 256 fonctions, et 65 536 avec quatre. Les tables de vérité grossissent vite : c’est pourquoi il faut aussi une algèbre.
L’algèbre de Boole
L’algèbre de Boole, du nom de George Boole (1815–1864), est une algèbre dont les variables ne valent que 0 ou 1. AND se comporte comme une multiplication, OR comme une addition (sauf que 1 + 1 = 1), et NOT s’écrit avec une barre (A̅), ou ¬ devant un groupe. La plupart des règles semblent familières ; quelques-unes non :
| Loi | Forme AND | Forme OR |
|---|---|---|
| élément neutre | 1·A = A | 0 + A = A |
| élément absorbant | 0·A = 0 | 1 + A = 1 |
| idempotence | A·A = A | A + A = A |
| complément | A·A̅ = 0 | A + A̅ = 1 |
| commutativité | AB = BA | A + B = B + A |
| associativité | (AB)C = A(BC) | (A + B) + C = A + (B + C) |
| distributivité | A(B + C) = AB + AC | A + BC = (A + B)(A + C) |
| absorption | A(A + B) = A | A + AB = A |
| De Morgan | ¬(AB) = A̅ + B̅ | ¬(A + B) = A̅·B̅ |
Deux règles n’ont pas d’équivalent dans l’algèbre du lycée : l’idempotence (A + A = A) et la seconde distributivité (OR se distribue sur AND). Les lois de De Morgan sont celles qui servent le plus : pour inverser un AND, on inverse les entrées et on prend un OR, et inversement. C’est vrai aussi dans le code : !(a && b) équivaut à !a || !b.
De la table de vérité au circuit
Toute fonction peut se construire directement à partir de sa table de vérité :
- Pour chaque ligne dont la sortie vaut 1, écrire le AND des entrées, en inversant celles qui valent 0 sur cette ligne. C’est un terme produit.
- Faire le OR de tous les termes produits.
On obtient une somme de produits. Prenons la fonction majorité de trois entrées, qui vaut 1 quand au moins deux entrées valent 1. Elle vaut 1 sur les lignes 011, 101, 110 et 111, donc :
M = A̅BC + AB̅C + ABC̅ + ABC
| A | B | C | M |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
M is 1 when at least two inputs are 1. Written straight from the truth table: one AND gate per row that outputs 1 (A'BC, AB'C, ABC', ABC), all ORed together. It works for any function, but it's rarely the smallest circuit.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Trois inverseurs, un AND à 3 entrées par terme produit, et un OR à 4 entrées. La méthode marche toujours, mais donne rarement le plus petit circuit.
Des circuits équivalents
L’algèbre de Boole permet de le réduire. Comme ABC = ABC + ABC + ABC (idempotence), le terme ABC peut s’associer à chacun des trois autres :
- A̅BC + ABC = BC(A̅ + A) = BC
- AB̅C + ABC = AC
- ABC̅ + ABC = AB
donc M = AB + AC + BC :
| A | B | C | M |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
The same function as AB + AC + BC: three 2-input ANDs and one OR instead of three NOTs, four 3-input ANDs and a 4-input OR. Boolean algebra proves the two circuits equivalent; compare their truth tables.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Même table de vérité, mais trois AND à 2 entrées et un OR à 3 entrées, au lieu de trois inverseurs, quatre AND à 3 entrées et un OR à 4 entrées. Moins de portes, c’est moins de surface, moins d’énergie et un chemin plus court pour le signal. Les outils de conception de puces font ce genre de simplification automatiquement, sur des millions de portes.
Une seule porte suffit
NAND est universelle : on peut construire NOT, AND et OR — et donc n’importe quelle fonction — avec des portes NAND uniquement.
| A | B | NOT A | A AND B | A OR B |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
NAND is universal: tie both inputs together and it's NOT; follow it with a NOT and it's AND; feed it two inverted inputs and it's OR (De Morgan). So any circuit can be built from NAND gates alone — and NOR works the same way.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
- NOT : un NAND dont les deux entrées sont reliées : ¬(AA) = A̅.
- AND : un NAND suivi de ce NOT.
- OR : par De Morgan, A + B = ¬(A̅·B̅), soit un NAND des deux entrées inversées.
NOR est universelle aussi, par l’argument symétrique. Parmi les portes à deux entrées, seules NAND et NOR ont cette propriété. Ce sont aussi les portes naturelles du CMOS, la technologie de toutes les puces modernes. Un NAND ou un NOR CMOS demande 4 transistors, contre 6 pour AND et OR, qui sont un NAND ou un NOR suivi d’un inverseur. Le matériel raisonne donc souvent en NAND et NOR, même quand le concepteur a écrit AND et OR.
Les portes dans votre code
Ces portes sont exactement ce que calculent les opérateurs bit à bit du C et les instructions logiques du x86 — 64 côte à côte, une par bit :
| C | x86 | Porte, par bit |
|---|---|---|
a & b | and | AND |
a | b | or | OR |
a ^ b | xor | XOR |
~a | not | NOT |
Les opérateurs logiques &&, || et ! sont différents. Ils traitent une valeur entière comme vraie ou fausse et, pour && et ||, évitent d’évaluer le côté droit quand c’est possible : ils se compilent donc en général en sauts conditionnels plutôt qu’en une seule instruction logique.
À retenir
- Une porte calcule un bit à partir de quelques bits d’entrée. Sa table de vérité donne la sortie pour chaque combinaison.
- Deux entrées permettent 16 fonctions ; n entrées, 2^(2ⁿ).
- L’algèbre de Boole — en particulier les lois de De Morgan — réécrit un circuit sans changer ce qu’il calcule.
- Toute fonction se construit comme une somme de produits à partir de sa table de vérité, puis se simplifie en un circuit équivalent plus petit.
- NAND (et NOR) suffit à tout construire, et ce sont les portes naturelles du CMOS.