Problème : tout en NOR, l'universalité de la porte NOR, de l'ordinateur d'Apollo au voteur majoritaire

La stratégie. Chaque pas est une table de vérité d'association, d'interrupteurs d'abord, de portes ensuite, et l'identification d'une porte. Les deux acquis d'informatique (De Morgan, lien entre table et forme normale) donnent la construction générale ; un argument de monotonie montre ce qui manque aux autres portes.

1) La porte d'origine : une NOR à trois entrées. Trois interrupteurs en parallèle conduisent dès que l'un est fermé : la sortie est reliée à la masse si $a+b+c=1$, et tirée à $V_{DD}$ par $R$ sinon. Donc $s=\overline{a+b+c}$ :

$s=1$ sur une seule ligne, celle où toutes les entrées sont nulles : c'est la porte NOR à trois entrées. En reliant $c$ au niveau $0$, élément neutre du OU, $s=\overline{a+b}$ : une NOR à deux entrées. En reliant les trois entrées à $x$, $s=\overline{x+x+x}=\overline{x}$ par idempotence : un inverseur. On notera $\mathrm{NOR}(x)=\overline{x}$ cet usage.

2) NOT, OR, AND en NOR. NOT : une porte, $\overline{a}=\mathrm{NOR}(a)$. OR : la NOR suivie d'un inverseur, $a+b=\overline{\overline{a+b}}=\mathrm{NOR}(\mathrm{NOR}(a,b))$ : deux portes, deux niveaux. AND : par De Morgan, $\overline{\overline{a}+\overline{b}}=\overline{\overline{a}}\cdot \overline{\overline{b}}=ab$, donc $ab=\mathrm{NOR}(\overline{a},\overline{b})=\mathrm{NOR}(\mathrm{NOR}(a),\mathrm{NOR}(b))$ : trois portes, deux niveaux. Vérification par les tables, sur $ab=00,01,10,11$ :

Les colonnes $0111$ et $0001$ sont celles de OR et AND.

Les minimums. Une seule NOR, dont les entrées sont prises parmi $a$, $b$, $0$, $1$, délivre $\overline{a}$, $\overline{b}$, $\overline{a+b}$ ou une constante : jamais $a+b$ ; il faut donc au moins deux portes pour OR. Pour AND : si $a$ (ou $b$) entrait directement dans la dernière porte, la sortie serait nulle dès que $a=1$, alors que $ab=1$ pour $a=b=1$ ; la dernière porte ne reçoit donc que des sorties d'autres portes (et des constantes nulles). Avec deux portes en tout, la dernière ne reçoit que la première, et délivre son complément, $\overline{\overline{(\dots )}}$ : une OR d'entrées prises parmi $a$, $b$, $0$, $1$, jamais $ab$. Il faut donc trois portes. Une recherche exhaustive confirme ces minimums : $1$, $2$, $3$.

3) Toute fonction, en deux niveaux. L'étage de sortie. Par le lien entre table et forme normale disjonctive complète (acquis d'informatique), la somme $P_1+\cdots +P_k$ vaut $1$ exactement sur les lignes où $f=0$ : chaque $P_j$ vaut $1$ sur sa ligne et sur elle seule. Donc $f=\overline{P_1+\cdots +P_k}=\mathrm{NOR}(P_1,\dots ,P_k)$. L'étage d'entrée. Un produit de littéraux est, par De Morgan généralisé, le NOR de leurs compléments : par exemple, pour la ligne $x=0$, $y=1$, $z=0$, $$\overline{x}y\overline{z}=\overline{x+\overline{y}+z}=\mathrm{NOR}(x,\overline{y},z).$$ Chaque $P_j$ est donc une porte NOR, qui reçoit directement les variables nulles sur la ligne et, à travers un inverseur NOR, celles qui y valent $1$. D'où $$f=\mathrm{NOR}(\mathrm{NOR}(\dots ),\dots ,\mathrm{NOR}(\dots )),$$ deux niveaux de NOR, plus au plus $n$ inverseurs : toute fonction se réalise avec la seule porte NOR. Les cas extrêmes se règlent à part : si $f$ ne vaut jamais $0$, $f=1=\mathrm{NOR}(0)$ ; si elle vaut toujours $0$, $f=\mathrm{NOR}(1)$. Application au XOR : $f=0$ sur les lignes $00$ et $11$, d'où $P_1=\overline{a}\overline{b}=\mathrm{NOR}(a,b)$, $P_2=ab=\mathrm{NOR}(\overline{a},\overline{b})$ et $$a\oplus b=\mathrm{NOR}(\mathrm{NOR}(a,b),\mathrm{NOR}(\mathrm{NOR}(a),\mathrm{NOR}(b))):$$ cinq portes, et la table se vérifie ligne à ligne ($00\mapsto 0$, $01\mapsto 1$, $10\mapsto 1$, $11\mapsto 0$). Le coût. Pour $n$ entrées, jusqu'à $2^n$ lignes à $0$, donc jusqu'à $2^n$ portes à $n$ entrées et une porte finale à $2^n$ entrées : la méthode prouve l'universalité, mais elle dépasse vite le « nombre raisonnable de composants » du programme ; c'est en regroupant des lignes qu'on obtient des circuits économes, comme le montre le voteur.

4) Le voteur majoritaire. La condition. La majorité est $0$ si et seulement si deux entrées au moins valent $0$. Or deux entrées valent $0$ si et seulement si leur somme est nulle ; « deux entrées au moins sont nulles » équivaut donc à « l'une des sommes $a+b$, $b+c$, $c+a$ est nulle ». Ainsi $m=1$ si et seulement si les trois sommes valent $1$ : $$m=(a+b)(b+c)(c+a)=\overline{\overline{a+b}+\overline{b+c}+\overline{c+a}}=\mathrm{NOR}(\mathrm{NOR}(a,b),\mathrm{NOR}(b,c),\mathrm{NOR}(c,a)),$$ la seconde égalité par De Morgan. Le câblage : quatre NOR à trois entrées (les trois premières ont une entrée reliée à $0$), soit deux circuits intégrés d'Apollo, et deux niveaux : le vote est acquis en $2t_p$.

La table : $m=1$ exactement pour $abc\in \{011,101,110,111\}$, ce qui est la table de $ab+bc+ca$, la forme établie dans le cours (on développe aussi $(a+b)(b+c)(c+a)$ : les termes se réduisent par absorption à $ab+bc+ca$). Comparaison : la méthode générale, partie des quatre lignes où $m=0$, demande trois inverseurs, quatre NOR à trois entrées et une NOR finale à quatre entrées, qu'Apollo n'avait pas : huit portes au moins, contre quatre en regroupant. La fiabilité : le voteur se trompe si deux calculateurs au moins se trompent : $$P_{\text{faux}}=3p^2(1-p)+p^3=3p^2-2p^3\approx 3,0\times 10^{-6},$$ trois cents fois moins qu'un calculateur seul, le voteur étant supposé sûr (c'est le point faible du montage : on le triple à son tour dans les systèmes critiques).

5) Le comparateur tout-NOR, et la NAND. Avec $g=\mathrm{NOR}(a,b)=\overline{a+b}$ : $$\mathrm{NOR}(a,g)=\overline{a}\cdot \overline{g}=\overline{a}(a+b)=\overline{a}b,\mathrm{NOR}(b,g)=\overline{b}(a+b)=a\overline{b},$$ par De Morgan puis $\overline{a}a=0$. Enfin $\mathrm{NOR}(\overline{a}b,a\overline{b})=\overline{\overline{a}b+a\overline{b}}=\overline{a\oplus b}$ : le XNOR, comparateur d'égalité, en quatre NOR ; le XOR en demande cinq (un inverseur de plus, ou la construction de la question 3), et une recherche exhaustive montre que ce sont les minimums. Avec des NAND, c'est l'inverse : quatre pour le XOR, cinq pour le XNOR. La logique négative : un circuit tout-NOR relu avec la convention inversée, comme lors de l'identification de la puce sans étiquette, est un circuit dont chaque porte est lue comme une NAND ($\overline{\mathrm{NOR}(\overline{a},\overline{b})}=\overline{ab}$), et il réalise la fonction $f^{\ast }(a,b)=\overline{f(\overline{a},\overline{b})}$. Or l'application $f\mapsto f^{\ast }$ est une bijection de l'ensemble des fonctions (elle est sa propre réciproque) : toute fonction $h$ s'écrit $h=f^{\ast }$ avec $f=h^{\ast }$. Réaliser $f$ en NOR, c'est donc réaliser $h$ en NAND : la NAND est universelle, comme le cours l'a montré directement.

6) Ce qui manque aux autres portes. AND et OR. Disons qu'une fonction est croissante si faire passer une entrée de $0$ à $1$ ne fait jamais passer la sortie de $1$ à $0$. Les entrées $a$, $b$ et les constantes sont croissantes ; le ET et le OU de deux fonctions croissantes sont croissants (si $u$ et $v$ ne descendent pas, ni $uv$ ni $u+v$ ne descend) ; donc, de proche en proche, tout circuit de AND et de OR est croissant. Or $\overline{a}$ passe de $1$ à $0$ quand $a$ passe de $0$ à $1$ : NOT n'est pas réalisable. Les fonctions obtenues sont $0$, $1$, $a$, $b$, $ab$, $a+b$ : six sur seize (l'ensemble est stable par ET et OU). XOR. Avec des XOR et les constantes, on n'obtient que des fonctions de la forme $\alpha \oplus \beta a\oplus \gamma b$, avec $\alpha ,\beta ,\gamma \in \{0,1\}$ (cette forme est stable par XOR) : huit fonctions, dont NOT, mais jamais AND (pour $ab$, la ligne $00$ impose $\alpha =0$, la ligne $10$ impose $\beta =0$, la ligne $01$ impose $\gamma =0$, et la ligne $11$ donnerait $0\ne 1$). NOR. Elle cumule les deux ingrédients qui manquent : elle inverse (elle n'est pas croissante) et elle n'est pas de la forme affine (elle vaut $1$ sur une seule ligne). Partie de $a$ et $b$ seules, elle engendre bien les seize fonctions. Ordre de grandeur : environ $5600$ portes NOR ont guidé un vaisseau vers la Lune, pour $55\mathrm{W}$, une dizaine de milliwatts par porte, la facture d'une logique à résistance de rappel ; un processeur actuel compte de $10^9$ à $10^{10}$ transistors.

Le résultat obtenu — l'universalité de la porte NOR. Toute fonction logique, donnée par sa table de vérité, se réalise avec la seule porte NOR : la sortie est le NOR des produits associés aux lignes où la fonction vaut $0$, et chacun de ces produits est un NOR des entrées ou de leurs compléments, eux-mêmes obtenus par des NOR montées en inverseurs ; deux niveaux de portes suffisent, plus les inverseurs d'entrée. NOT, OR et AND demandent une, deux et trois NOR ; le XNOR quatre, le XOR cinq. Par logique négative, la porte NAND est universelle elle aussi. AND et OR seules ne le sont pas, faute d'inversion, ni le XOR seul, faute de réaliser AND. C'est ce qui permit de câbler l'ordinateur de guidage d'Apollo avec un seul type de circuit intégré, deux NOR à trois entrées.

Ce que le problème installe. Chaque pas est une table de vérité d'association, puis l'identification d'une porte : trois interrupteurs en parallèle avec une résistance de rappel donnent une NOR, et des NOR assemblées donnent toutes les portes. De Morgan et le lien table-forme normale, acquis d'informatique, transforment la table en circuit de NOR en deux niveaux ; regrouper les lignes (le voteur) rend le circuit économe. L'universalité tient à deux propriétés que l'on sait reconnaître sur une table : la porte inverse, et elle n'est pas affine. Et la logique négative fait passer d'une porte universelle à l'autre.