Aufbau von Logikgatterschaltungen

In der vorherigen Lektion haben wir die vier grundlegenden Logikgatter kennengelernt. In dieser Lektion werden wir sie miteinander verbinden, um Schaltungen zu bauen, die Probleme aus der Praxis lösen.

Ein einzelnes Logikgatter ist wie eine Schraube — seine Funktion ist für sich genommen begrenzt. Aber wenn man sie kombiniert, kann man beliebig komplexe Funktionen bauen.

Alltagsvergleich: Ein Schloss mit Lego-Steinen bauen

Stell dir vor, du hast vier Farben von LEGO-Bausteinen vor dir:

  • Grüner Baustein = AND-Gatter: Strom fließt nur, wenn beide Enden verbunden sind
  • Oranger Baustein = OR-Gatter: Strom fließt, wenn eines der beiden Enden verbunden ist
  • Roter Baustein = NOT-Gatter: Ein wird Aus, Aus wird Ein
  • Violetter Baustein = XOR-Gatter: Strom fließt, wenn sich die beiden Enden in unterschiedlichen Zuständen befinden

Was kannst du mit diesen Bausteinen bauen?

ein WählerDrei Personen stimmen ab, und die Mehrheit entscheidet. Dies ist eine typische kombinatorische Logikschaltung — man muss nur AND/OR-Gatter verbinden, um sie umzusetzen.

ein KombinationsschlossDie richtigen Tasten müssen gleichzeitig gedrückt werden, um es zu entriegeln. Dies ist im Wesentlichen eine Kaskade von AND-Gattern — jede Taste entspricht einem Eingang, und nur wenn alle Eingänge 1 sind, wird der Ausgang 1.

ein AlarmWenn ein beliebiger Sensor auslöst, ertönt der Alarm. Dies ist im Wesentlichen eine Anwendung von OR-Gattern — solange ein Sensor 1 ausgibt, ertönt der Alarm.

Kombinatorische Logik vs. sequenzielle Logik

Bevor wir tiefer in den Aufbau von Schaltungen eintauchen, unterscheiden wir zwei wichtige Konzepte:

TypeFunktionenAusgang hängt ab vonHat es einen Speicher?Beispiele
Kombinatorische LogikAusgang wird nur durch die aktuelle Eingabe bestimmtaktueller EingabewertneinAddierer, Mehrheitsentscheider, Decoder
Sequenzielle LogikAusgang wird durch aktuelle Eingänge + historischen Zustand bestimmtAktueller Eingang + zuvor gespeicherte WerteJaZähler, Register, Zustandsautomat

Diese Vorlesung konzentriert sich auf kombinatorische Logik.Sequenzielle Logik wird in Vorlesung 9 ausführlich eingeführt.

Eine einfache Möglichkeit, sie zu unterscheiden: Kombinatorische Logik ist „was auch immer du eingibst, ich gebe es aus“ (wie eine mathematische Funktion); sequenzielle Logik ist „ich erinnere mich noch daran, was du vorher eingegeben hast“ (wie das menschliche Gedächtnis).

Methodik zum Schaltungsaufbau: die Drei-Schritt-Methode

Es gibt einen universellen dreistufigen Prozess zum Aufbau jeder kombinatorischen Logikschaltung mit Logikgattern:

  1. Wahrheitstabelle auflistenSchritt 1: Liste alle Kombinationen von Eingaben auf und schreibe die erwartete Ausgabe für jeden Fall auf.
  2. Logikausdruck aufschreibenSchritt 2: Schreibe für jede Zeile, in der die Ausgabe 1 ist, den entsprechenden "Produktterm" (die UND-Kombination der Eingaben) und verbinde dann alle Produktterme mit OR. Dies wird als "Summe-von-Produkten"-Form bezeichnet.
  3. Schaltplan zeichnen / Code schreibenSchritt 3: Übersetze den Logikausdruck in eine Schaltungsverbindung auf Gatterebene.

Üben wir diese Methode anhand von drei Beispielen, von einfach bis fortgeschritten.

Fall 1: Passwortschloss mit zwei Eingängen

AnforderungenFall 1: Entwirf eine einfache Schaltung zur Passwortprüfung. Es gibt zwei Eingaben A und B. Nur wenn A=1 und B=1 gilt, wird die Ausgabe 1 (entsperrt); andernfalls ist die Ausgabe 0 (gesperrt).

Diese Anforderung ist eigentlich nur ein UND-Gatter. Aber wir können sie verwenden, um die Drei-Schritt-Methode zu demonstrieren:

Schritt 1: Wahrheitstabelle

ABErwartete Ausgabe Y
000 (gesperrt)
010 (gesperrt)
100 (gesperrt)
111 (entsperrt)

Schritt 2: Logikausdruck

Nur die letzte Zeile hat die Ausgabe 1. Der entsprechende Produktterm ist: A UND B.

Also: Y = A UND B

Schritt 3: Schaltungsimplementierung

Sie benötigen nur ein UND-Gatter, mit A und B als Eingänge und Y als Ausgang.

Zu einfach? Sehen wir uns ein praktischeres Beispiel an.

Fall 2: Mehrheitsentscheider (Kernfall)

AnforderungenDrei Personen (A, B, C) stimmen über einen Vorschlag ab (1 bedeutet Zustimmung, 0 bedeutet Ablehnung). Der Vorschlag wird angenommen, wenn mindestens zwei Personen zustimmen (Ausgabe 1).

Dies ist ein klassischer Mehrheitsentscheider mit drei Eingängen und ein Muss in Lehrbüchern der Digitaltechnik.

Schritt 1: Wahrheitstabelle aufstellen

Drei Eingänge haben insgesamt 23= 8 Kombinationen:

ABCAnzahl der Ja-StimmenBestanden/nicht bestanden: YBeschreibung
00000Niemand dafür
00110Nur C stimmt zu
01010Nur B stimmt zu
01121B und C stimmen zu
10010Nur A stimmt zu
10121A und C stimmen zu
11021A und B stimmen zu
11131Einstimmig angenommen

Schritt 2: Schreibe den logischen Ausdruck

Finde die Zeilen, in denen die Ausgabe 1 ist (Zeilen 4, 6, 7, 8), und schreibe für jede Zeile einen Produktterm:

  • Zeile 4: NOT(A) AND B AND C
  • Zeile 6: A AND NOT(B) AND C
  • Zeile 7: A AND B AND NOT(C)
  • Zeile 8: A AND B AND C

ODER-Verknüpfung verwenden：Y = (NOT(A) AND B AND C) OR (A AND NOT(B) AND C) OR (A AND B AND NOT(C)) OR (A AND B AND C)

Dieser Ausdruck mag etwas lang erscheinen, aber logisch ist er sehr klar:Y ist 1 genau dann, wenn beliebige zwei oder drei Eingänge 1 sind。

Schritt 3: Schaltplan mit SVG zeichnen

three input linesA B C AND gate 1: A AND B ANDConnect to AND1 AND gate 2: B AND C AND AND gate 3: A AND C AND OR gate (combining the outputs of three AND gates) OR Output line YTagsFigure: Three-input majority voter circuit structure

Drei AND-Gatter prüfen, ob jedes der drei Paare "AB", "BC" und "AC" 11 ist, dann fasst das OR-Gatter die Ergebnisse zusammen.

Interaktive Demo: Python-Implementierung des Mehrheitsentscheiders

Beispiel

# Drei-Eingangs-Mehrheitsentscheider (Beispiel-Demo)
# Anforderung: drei Personen stimmen ab; es wird nur angenommen (Ausgabe 1), wenn mindestens zwei zustimmen (1).

# ----- Grundlegende Logikgatter aus Vorlesung 6 wiederverwenden -----
def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def OR(a, b):
    return 1 if a == 1 or b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


# ----- Methode 1: Summe von Produkten (SOP)-Standardform -----
def majority_voter_sop(a, b, c):
    """
Die Sum-of-Products-Implementierung des Mehrheitsentscheiders.
Direkt aus der Wahrheitstabelle ableiten: Finde alle Zeilen, in denen der Ausgang 1 ist,
Schreibe einen AND-Term pro Zeile und verbinde sie dann mit OR.
    """
    term1 = AND(AND(NOT(a), b), c)       # ~A·B·C
    term2 = AND(AND(a, NOT(b)), c)       # A·~B·C
    term3 = AND(AND(a, b), NOT(c))       # A·B·~C
    term4 = AND(AND(a, b), c)            # A·B·C
    return OR(OR(term1, term2), OR(term3, term4))


# ----- Methode 2: Optimierte vereinfachte Form -----
def majority_voter_optimized(a, b, c):
    """
Optimierte Implementierung eines Mehrheitsentscheiders: Y = AB + BC + AC.
Diese Form benötigt weniger Gatter, ist aber logisch äquivalent zu Methode eins.

Warum äquivalent?
Nach dem Erweitern der SOP-Form von Methode 1 kann sie mit dem Absorptionsgesetz der Booleschen Algebra vereinfacht werden:
    ~A·B·C + A·~B·C + A·B·~C + A·B·C
    = (~A·B·C + A·B·C) + (A·~B·C + A·B·C) + (A·B·~C + A·B·C)
    = B·C·(~A+A) + A·C·(~B+B) + A·B·(~C+C)
    = B·C + A·C + A·B
    """
    return OR(OR(AND(a, b), AND(b, c)), AND(a, c))


# ============================================
# Die vollständige Wahrheitstabelle ausgeben und die beiden Methoden vergleichen
# ============================================
print("=" * 60)
print(Wahrheitstabelle für Mehrheitsabstimmung mit drei Eingängen (BEISPIEL-Demo))
print("=" * 60)
print()
print("┌───┬───┬───┬────────┬──────────┬──────────┐")
print(│ A │ B │ C │ Bestanden? │ SOP-Methode │ Optimierungsmethode │)
print("├───┼───┼───┼────────┼──────────┼──────────┤")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            count = a + b + c
            passed = "Bestanden" if count >= 2 else "Nicht bestanden"
            sop = majority_voter_sop(a, b, c)
            opt = majority_voter_optimized(a, b, c)
            print(f"│ {a} │ {b} │ {c} │ {passed} │ {sop} │ {opt} │")
print("└───┴───┴───┴────────┴──────────┴──────────┘")

# ============================================
# Nutzungsstatistik von Gatterschaltungen
# ============================================
print("\n" + "=" * 60)
print(" Vergleich der Anzahl der Gatter, die von den beiden Methoden verwendet werden")
print("=" * 60)
print()
print(Methode 1 (vollständige SOP-Form):)
print(NOT-Gatter: 3 (~A, ~B, ~C))
print(AND-Gatter: 4 (vier AND-Terme, jeder erfordert 2 AND-Gatter mit zwei Eingängen))
print(OR-Gatter: 3 (Kombination von vier Produkttermen))
print(Gesamt: ungefähr 14 grundlegende Gatteraufrufe)
print()
print("Methode 2 (optimierte Form Y = AB + BC + AC):")
print(AND-Gatter: 3 (AB, BC, AC))
print(OR-Gatter: 2 (Kombination von drei Produkttermen))
print(" Gesamt: 5 grundlegende Gatteraufrufe")
print()
print(Nach der Optimierung wird die Gatteranzahl um etwa 65% reduziert!)
print("Das ist der technische Wert der Vereinfachung der booleschen Algebra.")

Beachten Sie den Umwandlungsprozess von der Wahrheitstabelle zum logischen Ausdruck. Dies ist eine der Kernfähigkeiten im Entwurf digitaler Schaltungen: Wenn Sie eine Wahrheitstabelle sehen, können Sie den Ausdruck schreiben; wenn Sie einen Ausdruck sehen, können Sie den Schaltplan zeichnen. Die drei entsprechen einander eins zu eins.

Fall 3: 1-Bit-Komparator

AnforderungenVergleiche zwei 1-Bit-Binärzahlen A und B. Gib drei Signale aus: A>B, A=B, A<B

Dies ist eine sehr wichtige Grundschaltung — Mehrbit-Komparatoren und Bedingungsauswertungen in CPUs bauen darauf auf.

Schritt 1: Wahrheitstabelle

ABA > BA = BA < B
00010
01001
10100
11010

Schritt 2: Logikausdruck

Betrachten Sie die Wahrheitstabelle:

  • A > B ist genau dann 1, wenn: A=1 AND B=0. Also: Greater = A AND NOT(B)
  • A = B ist genau dann 1, wenn: A und B gleich sind. Also: Equal = NOT(A XOR B), oder Equal = (A AND B) OR (NOT(A) AND NOT(B))
  • A < B ist genau dann 1, wenn: A=0 AND B=1. Daher: Less = NOT(A) AND B

Beachten Sie, dass die Erkennung von A = B eng mit dem XOR-Gatter zusammenhängt. Ein XOR-Ausgang von 1 bedeutet "verschieden"; die Negation davon ergibt "gleich".

Schritt 3: Code-Implementierung

Beispiel

# 1-Bit-Komparator (Beispiel-Demo)
# Vergleiche zwei 1-Bit-Binärzahlen A und B

def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def OR(a, b):
    return 1 if a == 1 or b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


def one_bit_comparator(a, b):
    """
1-Bit-Komparator: vergleicht A und B.
Gibt ein Tupel (Größer, Gleich, Kleiner) zurück.
    """
    greater = AND(a, NOT(b))   # A > B: A=1 und B=0
    less = AND(NOT(a), b)      # A < B: A=0 und B=1
    # A = B: weder größer noch kleiner
    # Äquivalent zu NOT(A XOR B), hier verwenden wir eine andere Implementierung
    equal = AND(NOT(greater), NOT(less))
    return (greater, equal, less)


# Wahrheitstabelle ausgeben
print("=" * 50)
print(Wahrheitstabelle für 1-Bit-Komparator (BEISPIEL-Demo))
print("=" * 50)
print()
print("┌───┬───┬────────┬────────┬────────┐")
print("│ A │ B │ A > B  │ A = B  │ A < B  │")
print("├───┼───┼────────┼────────┼────────┤")
for a in [0, 1]:
    for b in [0, 1]:
        gt, eq, lt = one_bit_comparator(a, b)
        print(f"│ {a} │ {b} │ {gt} │ {eq} │ {lt} │")
print("└───┴───┴────────┴────────┴────────┘")

# Einige nützliche Szenarien testen
print("\nTestszenario: ")
a_test, b_test = 1, 0
gt, eq, lt = one_bit_comparator(a_test, b_test)
print(f"A={a_test}, B={b_test}: A>B={gt}, A=B={eq}, A<B={lt}")
print(f"Interpretation: A ist größer als B" if gt else ("A ist gleich B" if eq else "A ist kleiner als B"))

Fall 4: 2-zu-4-Decoder

AnforderungenEingabe einer 2-Bit-Binärzahl (00, 01, 10, 11) und dafür sorgen, dass genau eine der entsprechenden 4 Ausgangsleitungen gleich 1 ist, während die übrigen gleich 0 sind.

Der Decoder ist eine Kernkomponente in der CPU — wenn die CPU ein Register auswählen möchte, verwendet sie im Wesentlichen einen Decoder.

Wahrheitstabelle

A1A0Y0Y1Y2Y3
001000
010100
100010
110001

logischer Ausdruck

  • Y0 = NOT(A1) AND NOT(A0)
  • Y1 = NOT(A1) AND A0
  • Y2 = A1 AND NOT(A0)
  • Y3 = A1 AND A0

Beispiel

# 2-4-Decoder (Beispiel-Demo)
# Eingabe: 2-Bit-Binärzahl A1 A0
# Ausgabe: genau eine der 4 Leitungen ist 1

def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


def decoder_2to4(a1, a0):
    """
2-zu-4-Leitungsdecoder.
Gib die Liste [Y0, Y1, Y2, Y3] zurück,
Genau eine davon ist 1, die übrigen sind 0.
    """
    Y0 = AND(NOT(a1), NOT(a0))  # 00 → Y0
    Y1 = AND(NOT(a1), a0)       # 01 → Y1
    Y2 = AND(a1, NOT(a0))       # 10 → Y2
    Y3 = AND(a1, a0)            # 11 → Y3
    return [Y0, Y1, Y2, Y3]


# Wahrheitstabelle ausgeben
print("=" * 50)
print(2-4-Decoder-Wahrheitstabelle (BEISPIEL-Demo))
print("=" * 50)
print()
print("┌────┬────┬────┬────┬────┬────┐")
print("│ A1 │ A0 │ Y0 │ Y1 │ Y2 │ Y3 │")
print("├────┼────┼────┼────┼────┼────┤")
for a1 in [0, 1]:
    for a0 in [0, 1]:
        Y = decoder_2to4(a1, a0)
        print(f"│ {a1}  │ {a0}  │ {Y[0]}  │ {Y[1]}  │ {Y[2]}  │ {Y[3]}  │")
print("└────┴────┴────┴────┴────┴────┘")

# Zeige ein tatsächliches Anwendungsszenario
print("\nPraktisches Anwendungsszenario: Verwendung eines Decoders zum Auswählen von Registern)
registers = ["R0", "R1", "R2", "R3"]
for a1 in [0, 1]:
    for a0 in [0, 1]:
        Y = decoder_2to4(a1, a0)
        idx = Y.index(1)          # Finde heraus, welche Ausgangsleitung 1 ist
        print(fAdresse A1A0={a1}{a0} → wählt Register {registers[idx]} aus)

Der Decoder ist eine klassische „Eins-zu-viele“-Schaltung. Sein Gegenstück ist der Multiplexer (MUX), der „Viele-zu-eins“ ist. Beide sind im Entwurf von CPU-Datenpfaden sehr verbreitet. Der Decoder wird verwendet, um „ein Ziel auszuwählen“ (z. B. in welches Register geschrieben werden soll), während der Multiplexer verwendet wird, um „eine Quelle auszuwählen“ (z. B. aus welchem Register die ALU Daten liest).

Universalgatter: Was NAND und NOR besonders macht

In der tatsächlichen Chipherstellung sind NAND- und NOR-Gatter auf einer "niedrigeren Ebene" als AND- und OR-Gatter.

NAND-Gatter = AND + NOTDas heißt, zuerst AND ausführen, dann invertieren. NAND und NOR werden "Universalgatter" genannt, weil jedes für sich allein alle booleschen Funktionen implementieren kann.

Warum werden in Chips NAND/NOR bevorzugt? Weil in der CMOS-Technologie:

  • Ein NAND-Gatter benötigt nur 4 Transistoren, während ein AND-Gatter 6 benötigt (AND = NAND + NOT).
  • NAND-Gatter haben eine schnellere Schaltgeschwindigkeit
  • Daher wird die AND-Funktion in tatsächlichen Chips auf niedriger Ebene mit NAND + NOT implementiert.

Als Nächstes überprüfen wir die "Universalität" des NAND-Gatters:

Beispiel

# Beweis der Universalität des NAND-Gatters (Beispieldemo)
# Das NAND-Gatter allein kann die drei Grundfunktionen implementieren: NOT, AND, OR

def NAND(a, b):
    """NAND-Gatter: Das Ergebnis von AND wird invertiert.
Y = 0 genau dann, wenn a=1 und b=1"""
    return 0 if a == 1 and b == 1 else 1


NOT mit NAND implementieren: NOT(A) = NAND(A, A)
def NOT_from_NAND(a):
    return NAND(a, a)


# AND mit NAND implementieren：AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))
def AND_from_NAND(a, b):
    nand_ab = NAND(a, b)
    return NAND(nand_ab, nand_ab)


# OR mit NAND implementieren: OR(A,B) = NAND(NOT(A), NOT(B))
def OR_from_NAND(a, b):
    return NAND(NOT_from_NAND(a), NOT_from_NAND(b))


# ============================================
# Überprüfen
# ============================================
print("=" * 60)
print(Demonstrieren Sie die Universalität von NAND-Gattern (BEISPIEL-Demo).)
print("=" * 60)

print("\n[Überprüfen: NOT durch NAND implementiert]")
for a in [0, 1]:
    expected = 1 if a == 0 else 0
    actual = NOT_from_NAND(a)
    print(f" A={a}: NOT_from_NAND = {actual}, Erwartet = {expected}, {'Bestanden' if actual == expected else 'Fehlgeschlagen'}")

print("\n[Überprüfen: AND durch NAND implementiert]")
for a in [0, 1]:
    for b in [0, 1]:
        expected = 1 if a == 1 and b == 1 else 0
        actual = AND_from_NAND(a, b)
        print(f" A={a}, B={b}: AND_from_NAND = {actual}, Erwartet = {expected}, {'Bestanden' if actual == expected else 'Fehlgeschlagen'}")

print("\n[Überprüfung: OR mit NAND implementiert])
for a in [0, 1]:
    for b in [0, 1]:
        expected = 1 if a == 1 or b == 1 else 0
        actual = OR_from_NAND(a, b)
        print(f" A={a}, B={b}: OR_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")

print("\nFazit: Nur NAND-Gatter sind nötig, um JEDE Boolesche Funktion zu konstruieren.)
print(Deshalb kann der nand2tetris-Kurs einen kompletten Computer ausgehend von NAND-Gattern bauen.)

nand2tetris (From NAND to Tetris) ist ein berühmter Informatikkurs. Er fordert dich heraus, Schritt für Schritt nur mit NAND-Gattern eine CPU, Speicher und ein Betriebssystem zu bauen und schließlich ein Tetris-Spiel auszuführen. Wenn du an den Low-Level-Details von Computern interessiert bist, kann ich es sehr empfehlen.

Interaktive Demo: Schaltungs-Builder für Mehrheitsentscheider (Beispiel für vis-network-Demo)

Verwende untenvis-networkEs visualisiert eine Majority-Voter-Schaltung mit drei Eingängen (Y = AB + BC + AC).Klicke auf die Eingangsknoten A, B, C, um 0/1 umzuschalten, die Schaltung wertet dann automatisch aus und aktualisiert die Farben aller Drähte —Rotbedeutet, dass das Signal 1 ist,graubedeutet, dass das Signal 0 ist.

Mehrheitsentscheider mit drei Eingängen (klicke auf A/B/C-Knoten zum Umschalten)

A=0, B=0, C=0 → Nicht bestanden (erfordert mindestens 2 Ja-Stimmen)
Eingangsknoten A Eingangsknoten B Eingangsknoten C AND-Gatter OR-Gatter Ausgang Y
Weitere Erweiterungen