Lois de De Morgan en pratique : concevoir des circuits uniquement avec NAND

En bref : les deux identités de De Morgan — $\overline{A \cdot B} = \overline{A} + \overline{B}$ et $\overline{A + B} = \overline{A} \cdot \overline{B}$ — permettent d’échanger AND et OR, ou inversement, en distribuant l’inversion. Conséquence pratique : toute fonction logique peut être réalisée uniquement avec des NAND ou uniquement avec des NOR, exactement comme le font les concepteurs de circuits CMOS et les outils de synthèse FPGA.

Les deux identités de De Morgan — $\overline{A \cdot B} = \overline{A} + \overline{B}$ et $\overline{A + B} = \overline{A} \cdot \overline{B}$ — sont faciles à mémoriser. La question plus difficile est de savoir comment les ingénieurs les utilisent réellement. La réponse touche la conception CMOS au niveau transistor, la synthèse FPGA, les implémentations uniquement en NAND ou en NOR et l’optimisation des circuits logiques multiniveaux.

Cet article applique les lois de De Morgan à des situations concrètes : réduire le nombre de portes de véritables circuits, implémenter n’importe quelle logique uniquement avec des NAND ou des NOR et rendre ces équivalences évidentes dans le simulateur.

Rappel rapide : les deux lois

Pour référence, les deux identités de De Morgan sont :

Elles se généralisent à $n$ variables :

Explorer le comportement d’une porte NAND

Application 1 : conversion vers une implémentation uniquement en NAND

En CMOS statique, une porte NAND à deux entrées emploie quatre transistors, tandis qu’une porte AND non inverseuse peut être réalisée par une NAND suivie d’un inverseur. NAND constitue donc une primitive utile, sans pour autant imposer une conception entièrement fondée sur des NAND. La synthèse ASIC mappe la logique sur les cellules disponibles dans une bibliothèque caractérisée ; la synthèse FPGA la mappe principalement sur des LUT et des ressources dédiées.

Processus de conversion

Toute expression en somme de produits (SOP) peut être transformée en réseau NAND-NAND en deux étapes :

1. Partir de la SOP : $Y = AB + CD$
2. Appliquer une double négation : $Y = \overline{\overline{AB + CD}}$
3. Appliquer De Morgan à la barre extérieure : $Y = \overline{\overline{AB} \cdot \overline{CD}}$

Le résultat est un circuit NAND-NAND à deux niveaux : le premier niveau calcule $\overline{AB}$ et $\overline{CD}$, puis le second les combine par une NAND.

Exemple détaillé : fonction de trois variables

Convertissons $Y = A\overline{B}C + \overline{A}BC$ uniquement en NAND :

Étape 1 : introduire une double négation : $Y = \overline{\overline{A\overline{B}C + \overline{A}BC}}$

Étape 2 : appliquer De Morgan à la barre extérieure :

Implémentation :

• Porte 1 (NAND) : entrées $A$, $\overline{B}$, $C$ — sortie $\overline{A\overline{B}C}$
• Porte 2 (NAND) : entrées $\overline{A}$, $B$, $C$ — sortie $\overline{\overline{A}BC}$
• Porte 3 (NAND) : reçoit les sorties des portes 1 et 2 — sortie $Y$

Les portes NOT nécessaires à $\overline{A}$ et $\overline{B}$ sont réalisées en reliant ensemble les deux entrées d’une porte NAND.

Nombre de portes dans ce schéma : 3 NAND + 2 inverseurs à base de NAND = 5 portes NAND. Le schéma AND-OR direct utilise lui aussi cinq portes, mais de trois types différents. Une construction à un seul type de porte est pratique lorsque le stock de boîtiers est limité ; une implémentation sur silicium doit être évaluée à partir des données de surface, de délai et de puissance de la bibliothèque cible.

Essayer le modèle de logique universelle NAND

Application 2 : conversion vers une implémentation uniquement en NOR

La transformation duale du réseau NAND-NAND s’applique aux expressions en produit de sommes (POS) et produit des circuits NOR-NOR.

Processus de conversion

1. Partir d’une POS : $Y = (A + B)(C + D)$
2. Appliquer une double négation : $Y = \overline{\overline{(A+B)(C+D)}}$
3. Appliquer De Morgan à la barre extérieure : $Y = \overline{\overline{(A+B)} + \overline{(C+D)}}$

Le résultat est un circuit NOR-NOR à deux niveaux : les NOR du premier niveau calculent $\overline{A+B}$ et $\overline{C+D}$, puis la seconde NOR les combine.

Les portes NOR peuvent convenir naturellement à une logique en produit de sommes ou à une bibliothèque qui propose une cellule complexe appropriée. Le choix entre NAND, NOR et une structure mixte dépend du fan-in, de la capacité de pilotage, de la charge, du placement et de la technologie cible, et non d’une préférence universelle.

Application 3 : optimisation d’un circuit multiniveau

Les circuits réels se limitent rarement à deux niveaux. Face à une logique multiniveau où les inversions sont dispersées, les lois de De Morgan permettent de « pousser les bulles » dans le circuit, d’annuler les inversions redondantes et de réduire le nombre de portes.

Exemple détaillé : simplifier une expression de quatre portes

Simplifions $Y = \overline{\overline{A \cdot B} + \overline{C \cdot D}}$.

Étape 1 — Appliquer De Morgan à la barre extérieure, l’expression interne étant la somme de deux termes :

Étape 2 — Annuler les doubles négations :

Nous sommes partis d’une expression apparemment complexe exigeant 2 NAND, 1 NOR et un inverseur de sortie. Après deux applications des lois de De Morgan, elle se réduit à une seule porte AND à 4 entrées.

Exemple détaillé : pousser les bulles dans un circuit à trois niveaux

Soit $Y = \overline{\overline{(A + B)} \cdot \overline{(C + D)} \cdot E}$.

Étape 1 — Appliquer De Morgan à la NAND extérieure :

Étape 2 — Annuler les doubles négations :

Au niveau des symboles booléens, l’expression se réduit à une porte OR à 5 entrées, dont une est complémentée. La réduction de surface, de délai ou de puissance dans le matériel dépend toutefois des cellules ou LUT disponibles, de leur fan-in, du routage et de la charge.

Application 4 : synthèse FPGA et mapping technologique

Lorsque vous écrivez du Verilog ou du VHDL, l’outil de synthèse ne traduit pas directement votre code en portes AND et OR. Il effectue plutôt un mapping technologique, c’est-à-dire qu’il convertit votre logique dans les primitives disponibles sur le FPGA ou dans la bibliothèque ASIC cible. Les lois de De Morgan constituent une transformation centrale de ce processus.

Comment les outils de synthèse emploient les lois de De Morgan

1. Mapping sur LUT : une LUT de FPGA peut implémenter toute fonction booléenne dans la limite de son nombre d’entrées. La synthèse simplifie et factorise la logique avant de regrouper les fonctions dans les LUT ; les transformations de De Morgan font partie des réécritures équivalentes possibles.

2. Optimisation de polarité : de nombreuses portes de bibliothèque fournissent naturellement des entrées ou des sorties inversées. Le déplacement des bulles peut conserver un signal complémenté utile et éviter l’ajout d’un inverseur distinct.

3. Optimisation du chemin critique : un outil peut retenir une forme équivalente en NAND, en NOR ou en cellule complexe lorsque la bibliothèque caractérisée et le placement prédisent un meilleur résultat temporel. La forme optimale dépend de la technologie.

Exemple concret en Verilog

Considérons ce code RTL :

assign y = ~(a & b) | ~(c & d);

L’outil de synthèse reconnaît $\overline{AB} + \overline{CD}=\overline{ABCD}$. Il peut employer des portes distinctes, une cellule complexe de la bibliothèque ou une seule LUT de FPGA si sa capacité d’entrée le permet. Le RTL spécifie le comportement ; les rapports produits pour la cible choisie établissent la surface et le timing de l’implémentation.

Application 5 : matériel ancien et substitution de portes

Lorsque vous réparez du matériel ancien ou travaillez avec un stock de composants limité, les lois de De Morgan deviennent votre outil principal de substitution.

Constructions à base de portes universelles

Avec uniquement des NAND, il est possible de construire toutes les autres portes :

La construction OR découle directement de De Morgan : $A + B = \overline{\overline{A} \cdot \overline{B}}$, c’est-à-dire NAND(NOT A, NOT B).

Cette propriété est également utile lorsque le stock de composants est restreint. Si seules des sections d’un 74LS00 sont disponibles, trois sections NAND peuvent réaliser une fonction OR, sous réserve que le remplacement respecte les exigences du circuit d’origine en matière de tension, de fan-out, de timing, de puissance et d’entrées inutilisées.

Vérification à l’oscilloscope

Lorsque vous construisez des transformations de De Morgan dans DigiSim, comparez les sorties du circuit d’origine et du circuit transformé. Un OSCILLOSCOPE_8CH peut afficher ces deux sorties avec leurs entrées.

La vérification exhaustive des combinaisons d’entrées stables valide la table de vérité. L’application de transitions aux entrées peut aussi révéler les différences représentées par le modèle de délai de propagation du simulateur, mais elle n’établit pas le timing d’une implémentation physique donnée.

Des circuits logiquement équivalents ne sont pas nécessairement équivalents du point de vue du timing. Des schémas NAND-NAND et AND-OR peuvent tous deux comporter deux niveaux logiques, tout en différant par les délais des cellules, le slew d’entrée, le fan-out, la charge et le routage. Des niveaux d’inversion supplémentaires peuvent allonger un chemin, mais seule une analyse temporelle propre à la cible permet d’établir une supériorité de vitesse physique.

Erreurs fréquentes dans l’application de De Morgan

L’inversion partielle

Les étudiants pensent souvent à inverser chaque terme, mais oublient d’échanger l’opérateur. Ils écrivent alors $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$, ce qui est faux. Remplacez toujours AND par OR, ou OR par AND.

Entrées flottantes dans les circuits NAND/NOR

Lorsque vous construisez des circuits uniquement en NAND dans DigiSim, attribuez une source définie à chaque entrée pertinente. Dans un circuit CMOS réel, une entrée laissée flottante peut prendre une tension imprévisible, commuter sous l’effet d’un bruit couplé et augmenter le courant d’alimentation. Reliez les entrées physiques inutilisées au niveau logique valide approprié conformément à la fiche technique du composant ; dans un exercice de schéma, utilisez la source CONSTANT correspondante.

Confondre équivalence logique et équivalence temporelle

Deux circuits ayant la même table de vérité peuvent présenter des délais de propagation très différents. Lors d’une conversion par les lois de De Morgan, vérifiez toujours si la transformation ajoute ou supprime des niveaux de portes.

Défi : optimisation multiniveau

Prenez cette expression et réduisez-la au nombre minimal de portes :

Indice : appliquez De Morgan à la NAND extérieure, annulez les doubles négations et observez ce qui reste. Solution : $Y = (A + \overline{B}) + (\overline{A} + B) = A + \overline{A} + B + \overline{B} = 1$. L’expression entière est toujours vraie — aucune porte n’est nécessaire.

C’est une démonstration puissante : associées à la loi du complément, les lois de De Morgan peuvent parfois éliminer des circuits entiers.

Poursuivez avec les tables de Karnaugh pour aborder visuellement les mêmes simplifications, ou revenez aux fondements de l’algèbre booléenne. Ouvrez la référence du composant NAND pour câbler vous-même l’une de ces conversions.