6 / 63 · Concept

Portes universelles : construire des circuits uniquement avec NAND

Démontrer la complétude fonctionnelle de NAND et NOR par construction et vérifier les signaux intermédiaires de XOR.

Que signifie « construire n'importe quel circuit » ?

NAND permet de réaliser NOT, AND et OR. Toute fonction combinatoire à un nombre fini d'entrées peut s'exprimer avec ces opérations : c'est en ce sens que NAND est une porte universelle^{Porte universelle Un seul type de porte est universel si sa répétition permet de réaliser toute fonction booléenne. NAND et NOR en sont les exemples classiques.}. Cela ne signifie pas qu'une porte NAND résout à elle seule le stockage, l'horloge, le câblage et l'alimentation.

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

Relier le même signal aux deux entrées de NAND réalise NOT. AND ajoute une inversion^{Négation L'opération NOT échange 0 et 1. Une barre au-dessus d'une expression applique NOT à toute l'expression qu'elle couvre. En savoir plus} après NAND ; OR utilise les lois de De Morgan^{Lois de De Morgan Le complément d'un AND est le OR des entrées complémentées ; le complément d'un OR est le AND des entrées complémentées. En savoir plus}. NOR permet aussi de construire NOT en reliant ses entrées, puis de démontrer sa complétude par des constructions analogues.

Construire XOR avec quatre NAND

Définissez les signaux intermédiaires dans cet ordre :

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

Former XOR avec un signal intermédiaire partagé

Premier NAND: n0 = NAND(a, b)
Deux NAND intermédiaires: n1 = NAND(a, n0); n2 = NAND(b, n0)
Dernier NAND: y = NAND(n1, n2)

Les deux NAND du deuxième étage sont en parallèle. Il y a quatre portes au total, mais le plus long chemin logique ne compte que trois étages. Dans un modèle simple où chaque porte prend au maximum 2 ns, la somme maximale vaut 6 ns. Les effets réels de la charge et du câblage doivent être étudiés séparément.

Comparer le résultat des quatre NAND à XOR

XOR · Table de vérité
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

Remplissez les quatre lignes, puis comparez avec XOR ci-dessus. L'équivalence fonctionnelle compare les sorties pour toutes les entrées ; elle ne garantit ni le même nombre de portes ni le même retard de propagation^{Retard de propagation Temps nécessaire après un changement d'entrée pour que la sortie se stabilise à sa valeur correcte. Équivalence logique et caractéristiques temporelles sont distinctes. En savoir plus}.

Essayez vous-même

Écrivez NOT et AND uniquement avec des NOR. Combien de portes et d'étages sur le plus long chemin faut-il pour AND ?

Lire l’explication

NOT a=NOR(a,a). AND=NOR(NOR(a,a), NOR(b,b)). Deux inversions d'entrée et un NOR final donnent trois portes au total et deux étages sur le plus long chemin.