Explorateur de portes logiques

Une usine de fabrication ne vous vendra qu'un seul et unique composant : la porte NON-ET à deux entrées. Construisez le demi-additionneur que l'outil dessine sous Demi-additionneur — un bit de somme, un bit de retenue — uniquement avec cela. Combien de portes NON-ET faut-il, et comment savoir si vous avez trouvé la solution la plus économique ?

1. Commencez par la fonction NON, qui est le résultat le plus simple à obtenir d'une porte NON-ET. Reliez ses deux entrées au même fil. La porte demande « ces deux entrées sont-elles à l'état haut ? », et comme toutes deux valent A, elle répond dès lors que A ne l'est pas.

   $$A\uparrow A=\neg (A\wedge A)=\neg A$$

2. Le ET coûte une porte de plus. Un NON-ET est déjà un ET dont la réponse est inversée, il suffit donc de l'inverser à nouveau : envoyez la sortie dans un NON, qui d'après l'étape 1 est une seconde porte NON-ET avec ses entrées reliées. Le OU en nécessite trois, en inversant chaque entrée avant un NON-ET, ce qui revient à appliquer les lois de De Morgan à l'envers.

   $$(A\uparrow B)\uparrow (A\uparrow B)=\neg \neg (A\wedge B)=A\wedge B$$

3. Le OU exclusif est celui qui résiste. L'astuce consiste à calculer le terme intermédiaire une seule fois, puis à le combiner à nouveau avec chaque entrée à son tour. Appelez-le C, et injectez-le dans un NON-ET face à A, puis à nouveau face à B.

   $$C=A\uparrow B,D=A\uparrow C,E=B\uparrow C$$

4. Développez D. On obtient « non à la fois A et (non A ou non B) ». La partie « A et non A » ne peut jamais se produire, elle disparaît donc, et ce qui reste est très court. E est la même expression dans laquelle les lettres sont permutées.

   $$D=\neg (A\wedge (\neg A\vee \neg B))=\neg (A\wedge \neg B),E=\neg (B\wedge \neg A)$$

5. Le dernier NON-ET les réunit. De Morgan transforme un NON-ET de deux négations en un simple OU, et un OU de « A mais pas B » avec « B mais pas A » est précisément la définition du OU exclusif. Quatre portes pour le bit de somme.

   $$D\uparrow E=(A\wedge \neg B)\vee (B\wedge \neg A)=A\oplus B$$

6. Passons à la retenue. Il s'agit de A ET B, dont nous avons évalué le coût à deux portes à l'étape 2 — mais la première de ces deux portes est C, et C se trouve déjà sur un fil au milieu du OU exclusif que vous venez de construire. Prenez sa valeur une troisième fois et reliez-la à elle-même.

   $$C\uparrow C=\neg (A\uparrow B)=A\wedge B$$

7. Il en faut donc cinq, et non six. Vous venez d’en construire la moitié de la démonstration : la retenue nécessite à elle seule 2 portes, d’après l’étape 2, et la somme en nécessite 4, d’après l’étape 5. À l’étape 6, vous constatez qu’elles ont exactement une porte en commun, si bien que 2 + 4 − 1 = 5. Affirmer qu’il est impossible de faire mieux que cinq demande toutefois une autre preuve, que cette page ne fournit pas : ce résultat découle d’une recherche exhaustive parmi tous les réseaux de six portes NON-ET ou moins à deux entrées. Il s’agit d’un calcul informatique, non d’un raisonnement mathématique.

   $$\neg :1,\wedge :2,\vee :3,\oplus :4,\{S,C\}:5$$

8. Le nombre de portes ne dit rien sur le temps de propagation. Suivez la retenue : sortie de G1, directement dans G5, soit une profondeur de deux portes. La somme doit traverser G2 ou G3 puis G4, sa profondeur est donc de trois portes. Comptez les chemins de A à la somme : ils n'ont même pas la même longueur.

   $$A\to G_2\to G_4=2\text{ gates},A\to G_1\to G_2\to G_4=3\text{ gates}$$