De Morgans Gesetze in der Praxis: Schaltungsentwurf nur mit NAND

Kurzfassung: De Morgans zwei Identitäten – $\overline{A \cdot B} = \overline{A} + \overline{B}$ und $\overline{A + B} = \overline{A} \cdot \overline{B}$ – erlauben es, UND gegen ODER (und umgekehrt) auszutauschen, indem die Invertierung verteilt wird. Der praktische Gewinn: Jede logische Funktion lässt sich ausschließlich mit NAND oder ausschließlich mit NOR implementieren – genau das tun CMOS-Chipdesigner und FPGA-Synthesewerkzeuge.

De Morgans zwei Identitäten – $\overline{A \cdot B} = \overline{A} + \overline{B}$ und $\overline{A + B} = \overline{A} \cdot \overline{B}$ – sind leicht auswendig zu lernen. Die schwierigere Frage ist, wie praktizierende Ingenieure sie tatsächlich einsetzen. Die Antwort umfasst CMOS-Entwurf auf Transistorebene, FPGA-Synthese, Implementierungen nur mit NAND und nur mit NOR sowie die Optimierung mehrstufiger Schaltungen.

Dieser Artikel konzentriert sich darauf, De Morgans Gesetze in realen Entwurfsszenarien anzuwenden – darauf, wie sie die Gatterzahl in tatsächlichen Schaltungen reduzieren, wie sie jede Logik als NAND- oder NOR-Variante ermöglichen und wie der Simulator die Äquivalenzen offensichtlich macht.

Kurze Wiederholung: Die zwei Gesetze

Zur Referenz De Morgans zwei Identitäten:

Sie lassen sich auf $n$ Variablen verallgemeinern:

Verhalten des NAND-Gatters erkunden

Anwendung 1: Umwandlung in eine Implementierung nur mit NAND

In statischem CMOS benötigt ein NAND-Gatter mit zwei Eingängen vier Transistoren; ein nichtinvertierendes UND lässt sich als NAND mit nachgeschaltetem Inverter realisieren. Damit ist NAND ein nützlicher Grundbaustein, doch daraus folgt nicht, dass ein vollständiger Entwurf ausschließlich NAND-Gatter verwenden sollte. Die ASIC-Synthese bildet Logik auf die Zellen einer charakterisierten Bibliothek ab, die FPGA-Synthese dagegen hauptsächlich auf Lookup-Tables und dedizierte Ressourcen.

Der Umwandlungsprozess

Jeder Ausdruck in Sum-of-Products-Form (SOP) lässt sich in zwei Schritten in die NAND-NAND-Form umwandeln:

1. Beginnen Sie mit der SOP: $Y = AB + CD$
2. Wenden Sie doppelte Negation an: $Y = \overline{\overline{AB + CD}}$
3. Wenden Sie De Morgan auf den äußeren Überstrich an: $Y = \overline{\overline{AB} \cdot \overline{CD}}$

Das Ergebnis ist eine zweistufige NAND-NAND-Schaltung: Die NANDs der ersten Stufe berechnen $\overline{AB}$ und $\overline{CD}$, das NAND der zweiten Stufe verknüpft sie.

Durchgerechnetes Beispiel: Funktion mit 3 Variablen

Wandeln Sie $Y = A\overline{B}C + \overline{A}BC$ in eine Implementierung nur mit NAND um:

Schritt 1: Doppelt negieren: $Y = \overline{\overline{A\overline{B}C + \overline{A}BC}}$

Schritt 2: De Morgan auf den äußeren Überstrich anwenden:

Implementierung:

• Gatter 1 (NAND): Eingänge $A$, $\overline{B}$, $C$ – Ausgang $\overline{A\overline{B}C}$
• Gatter 2 (NAND): Eingänge $\overline{A}$, $B$, $C$ – Ausgang $\overline{\overline{A}BC}$
• Gatter 3 (NAND): Eingänge sind die Ausgänge von Gatter 1 und Gatter 2 – Ausgang $Y$

Die NICHT-Gatter für $\overline{A}$ und $\overline{B}$ entstehen, indem die beiden Eingänge eines NAND-Gatters miteinander verbunden werden.

Gatterzahl in diesem Schaltbild: 3 NAND-Gatter + 2 NAND-basierte Inverter = 5 NAND-Gatter. Die direkte UND-ODER-Darstellung verwendet ebenfalls fünf Gatter, jedoch drei Gattertypen. Eine Konstruktion aus nur einem Gattertyp ist bei einem eingeschränkten Bauteilbestand praktisch; eine Siliziumimplementierung muss anhand der Flächen-, Laufzeit- und Leistungsdaten der Zielbibliothek bewertet werden.

Vorlage für universelle NAND-Logik ausprobieren

Anwendung 2: Umwandlung in eine Implementierung nur mit NOR

Das Dual zur NAND-NAND-Umwandlung funktioniert für Ausdrücke in Product-of-Sums-Form (POS) und ergibt NOR-NOR-Schaltungen.

Der Umwandlungsprozess

1. Beginnen Sie mit einer POS: $Y = (A + B)(C + D)$
2. Doppelt negieren: $Y = \overline{\overline{(A+B)(C+D)}}$
3. De Morgan auf den äußeren Überstrich anwenden: $Y = \overline{\overline{(A+B)} + \overline{(C+D)}}$

Das Ergebnis ist eine zweistufige NOR-NOR-Schaltung: Die NORs der ersten Stufe berechnen $\overline{A+B}$ und $\overline{C+D}$, das NOR der zweiten Stufe verknüpft sie.

NOR-Gatter können für Product-of-Sums-Logik oder für eine Bibliothek mit einer geeigneten komplexen Zelle die naheliegende Wahl sein. Ob NAND-, NOR- oder gemischte Gatterstrukturen günstiger sind, hängt von Fan-in, Treiberstärke, Last, Platzierung und Zieltechnologie ab; einen universellen Vorrang gibt es nicht.

Anwendung 3: Optimierung mehrstufiger Schaltungen

Reale Schaltungen sind selten auf zwei Stufen beschränkt. Wenn Sie auf mehrstufige Logik mit verstreuten Invertierungen treffen, erlauben De Morgans Gesetze Ihnen, „Blasen zu schieben“, um überflüssige Invertierungen aufzuheben und die Gatterzahl zu reduzieren.

Durchgerechnetes Beispiel: Einen Ausdruck mit 4 Gattern vereinfachen

Vereinfachen Sie: $Y = \overline{\overline{A \cdot B} + \overline{C \cdot D}}$

Schritt 1 — De Morgan auf den äußeren Überstrich anwenden (der Ausdruck darin ist eine Summe aus zwei Termen):

Schritt 2 — Die doppelten Negationen aufheben:

Wir begannen mit einem scheinbar komplexen Ausdruck, der 2 NAND-Gatter, 1 NOR-Gatter und einen Ausgangsinverter zu erfordern schien. Nach zweimaliger Anwendung von De Morgans Gesetzen reduziert er sich auf ein einziges UND-Gatter mit 4 Eingängen.

Durchgerechnetes Beispiel: Blasenverschieben in einer dreistufigen Schaltung

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

Schritt 1 — De Morgan auf das äußere NAND anwenden:

Schritt 2 — Die doppelten Negationen aufheben:

Auf der Ebene Boolescher Symbole reduziert sich der Ausdruck auf ein ODER-Gatter mit 5 Eingängen, von denen einer invertiert ist. Ob diese Form in Hardware kleiner, schneller oder energiesparender ist, hängt von den verfügbaren Zellen beziehungsweise LUTs sowie von deren Fan-in, Verdrahtung und Last ab.

Anwendung 4: FPGA-Synthese und Technologieabbildung

Wenn Sie Verilog oder VHDL schreiben, übersetzt das Synthesewerkzeug Ihren Code nicht direkt in UND- und ODER-Gatter. Stattdessen führt es Technologieabbildung durch – es überträgt Ihre Logik in die spezifischen Grundbausteine, die in der Ziel-FPGA- oder ASIC-Bibliothek verfügbar sind. De Morgans Gesetze sind dabei eine zentrale Transformation.

Wie Synthesewerkzeuge De Morgans Gesetze einsetzen

1. LUT-Abbildung: Eine FPGA-Lookup-Table kann jede Boolesche Funktion bis zu ihrer maximalen Eingangsanzahl implementieren. Die Synthese vereinfacht und faktorisiert die Logik, bevor sie Funktionen in LUTs packt; De-Morgan-Transformationen gehören zu den möglichen äquivalenten Umformungen.

2. Polaritätsoptimierung: Viele Bibliothekszellen stellen von Natur aus invertierte Ausgänge oder Eingänge bereit. Durch Bubble-Pushing kann ein bereits vorhandenes komplementiertes Signal erhalten und ein separater Inverter vermieden werden.

3. Optimierung kritischer Pfade: Ein Werkzeug kann eine äquivalente NAND-, NOR- oder komplexe Zellstruktur wählen, wenn die charakterisierte Bibliothek und die Platzierung dafür ein besseres Timing erwarten lassen. Welche Form gewinnt, ist technologieabhängig.

Ein konkretes Verilog-Beispiel

Betrachten Sie diesen RTL-Code:

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

Das Synthesewerkzeug erkennt $\overline{AB} + \overline{CD}=\overline{ABCD}$. Es kann getrennte Gatter, eine komplexe Bibliothekszelle oder – sofern die Eingangsanzahl ausreicht – eine einzelne FPGA-LUT verwenden. Der RTL-Code legt das Verhalten fest; erst die Berichte für das gewählte Ziel belegen die implementierte Fläche und das Timing.

Anwendung 5: Historische Hardware und Gatterersatz

Wenn Sie mit alter Hardware oder begrenzten Bauteilbeständen arbeiten, sind De Morgans Gesetze Ihr wichtigstes Werkzeug für den Gatterersatz.

Die universellen Gatterkonstruktionen

Mit ausschließlich NAND-Gattern können Sie jedes andere Gatter aufbauen:

Die ODER-Konstruktion folgt direkt aus De Morgan: $A + B = \overline{\overline{A} \cdot \overline{B}}$, also NAND(NOT A, NOT B).

Das ist auch bei einem eingeschränkten Bauteilbestand nützlich. Sind nur Sektionen eines 74LS00 verfügbar, können drei NAND-Sektionen eine ODER-Funktion implementieren – vorausgesetzt, der Ersatz erfüllt die Anforderungen der ursprünglichen Schaltung an Spannung, Fan-out, Timing, Leistungsaufnahme und unbenutzte Eingänge.

Überprüfung mit dem Oszilloskop

Vergleichen Sie beim Aufbau von De-Morgan-Transformationen in DigiSim die Ausgänge der ursprünglichen und der umgeformten Schaltung. Ein OSCILLOSCOPE_8CH kann beide Ausgänge zusammen mit ihren Eingängen darstellen.

Eine vollständige Prüfung aller stabilen Eingangskombinationen verifiziert die Wahrheitstabelle. Durch das Schalten der Eingänge lassen sich außerdem Unterschiede sichtbar machen, die das Laufzeitmodell des Simulators abbildet; damit ist jedoch kein Timing für eine konkrete physische Implementierung nachgewiesen.

Logisch äquivalente Schaltungen sind nicht zwingend auch zeitlich äquivalent. Eine NAND-NAND- und eine UND-ODER-Darstellung können beide zwei logische Stufen besitzen; dennoch unterscheiden sich möglicherweise Zelllaufzeiten, Eingangssignalsteilheit, Fan-out, Last und Verdrahtung. Zusätzliche Inversionsstufen können einen Pfad verlängern, eine physische Geschwindigkeitsaussage erfordert jedoch stets eine zielspezifische Timing-Analyse.

Häufige Fallstricke bei der Anwendung von De Morgan

Das unvollständige Umkehren

Lernende erinnern sich oft daran, jeden Term zu invertieren, vergessen jedoch, den Operator umzudrehen. Dadurch entsteht $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$, was falsch ist. Tauschen Sie stets UND gegen ODER beziehungsweise ODER gegen UND aus.

Schwebende Eingänge in NAND/NOR-Schaltungen

Geben Sie beim Aufbau reiner NAND-Schaltungen in DigiSim jedem relevanten Eingang eine definierte Quelle. Ein schwebender Eingang einer realen CMOS-Schaltung kann eine unbestimmte Spannung annehmen, durch eingekoppeltes Rauschen schalten und den Versorgungsstrom erhöhen. Unbenutzte physische Eingänge sind gemäß Datenblatt des Bausteins mit einem geeigneten gültigen Logikpegel zu verbinden; in einer Schaltplanübung verwenden Sie dafür die entsprechende CONSTANT-Quelle.

Logische Äquivalenz mit zeitlicher Äquivalenz verwechseln

Zwei Schaltungen mit derselben Wahrheitstabelle können sehr unterschiedliche Signallaufzeiten haben. Prüfen Sie beim Umwandeln einer Schaltung mithilfe von De Morgans Gesetzen stets, ob die Transformation Gatterstufen hinzufügt oder entfernt.

Herausforderung: Mehrstufige Optimierung

Nehmen Sie diesen Ausdruck und reduzieren Sie ihn auf die minimale Anzahl von Gattern:

Hinweis: Wenden Sie De Morgan auf das äußere NAND an, heben Sie die doppelten Negationen auf und sehen Sie, was übrig bleibt. (Lösung: $Y = (A + \overline{B}) + (\overline{A} + B) = A + \overline{A} + B + \overline{B} = 1$. Der gesamte Ausdruck ist immer wahr – überhaupt keine Gatter erforderlich.)

Das ist eine eindrucksvolle Demonstration: De Morgans Gesetze können zusammen mit dem Komplementgesetz manchmal ganze Schaltungen eliminieren.

Fahren Sie mit Karnaugh-Diagrammen fort, um einen visuellen Zugang zu denselben Vereinfachungen zu erhalten, oder lesen Sie erneut die Grundlagen der Booleschen Algebra. Öffnen Sie die NAND-Komponentenreferenz, um eine dieser Umwandlungen selbst zu verdrahten.