« »

GRABS Übungsaufgaben Logik und Schaltungen Gatter-Baukasten

Gatter-Baukasten

a)

Level 3: Anwenden

Erstellen Sie die vier grundlegenden Logikelemente NOT (auch Inverter oder INV), AND, OR und XOR mit Hilfe von NAND-Gattern. Rufen Sie dazu die Webseite https://nandgame.com auf und lösen die ersten fünf Level.

Lösung

Lösungen für die Gatter im nandgame. NAND: a (Steuersignal für die Spule) und b zu Relais (default: off), Ergebnis als Steuersignal zu weiterem Relais (default: on) mit Spannungsquelle als Eingabe, Ergebnis ist NAND-Signal. INV: Input zu a und b eines NAND-Gatters, Ergebnis ist Inverse. AND: a und b zu NAND-Gatter, Ergebnis zu INV, Ergebnis ist AND. OR: a invertieren, b invertieren, Ergebnisse zu NAND, Ergebnis ist OR. naives XOR: (a OR b) AND (a NAND b) Bildrechte: © Olav Junker Kjær, The Nand Game

b)

Level 3: Anwenden

Jedes NAND-Gatter ist ein Kostenfaktor bei der Chipherstellung. Minimieren Sie, falls nötig, ihren Entwurf für das XOR-Gatter, sodass höchstens 5 NAND-Gatter dafür nötig sind.

Lösung

Unser Ziel ist es, folgende Wahrheitstabelle durch eine Schaltung umzusetzen:

ABQ = A^B
000
011
101
110

Intuitive Lösung: XOR mit 5 NAND-Gattern

Wir betrachten zunächst die Wertetabelle des XOR-Gatters. Wie in der Vorlesung gezeigt, betrachten wir nur die Zeilen, in denen das Ergebnis eine 1 ist, und konstruieren daraus Logikterme.

ABQ = A^BLogikterm
011/A * B
101A * /B

Aus diesen beiden Termen können wir nun einen Logikterm für das gesamte XOR bestimmen: Q = /A * B + A * /B

  1. Als ersten Schritt können wir diesen Term als Schaltplan nachbauen, beispielsweise mithilfe des NAND-Games (siehe Abbildung).
  2. Diese Schaltung ist allerdings noch nicht minimiert und beinhaltet insgesamt 9 NAND-Gatter. Wir können nun nach und nach die benutzten Bauteile in ihre Komponenten aufteilen (durch die Funktion “Replace with parts”). In Schritt 2 Hier haben wir das OR-Gatter durch seine Bausteine (1×NAND und 2×NOT) ersetzt.
  3. Analog dazu können wir die AND-Gatter von der Ausgangsschaltung wiederum mit deren Bausteinen ersetzen.
  4. Nun können wir durch „gezieltes Hinschauen“ einige Stellen identifizieren, in denen sich Bausteine gegenseitig eliminieren, und andere Stellen, die sich zu einem einzelnen Baustein (beispielsweise ein einzelnes NAND-Gatter) zusammenfassen lassen.
  5. Durch diese Vereinfachungen und das Ersetzen der NOT-Gatter mit den darunterliegenden NAND-Gattern, kommt man auf diese Schaltung mit 5 NAND-Gattern, die die Funktionalität eines XOR-Gatters realisiert.

In der naiven XOR-Lösung wird das OR durch seine Bauteile ersetzt, anschließend auch das AND. Links können dann zwei INVs nacheinander entfernt werden, rechts ein INV+AND zu NAND kombiniert.

Bildrechte: © Olav Junker Kjær, The Nand Game

Exkurs: XOR mit 4 NAND-Gattern

Diese Herausforderung ist etwas für Fortgeschrittene. Keine Sorge, falls ihr hierzu keine passende Lösung gefunden habt. Die Erklärung sollte dennoch nachvollziehbar sein.

Als Ausgangspunkt nutzen wir folgenden Gedanken:

Wenn A,

    dann nicht

        A und B,

    und nicht

        nicht-A und nicht-B, → siehe Schritt 1

oder wenn B,

    dann nicht

        A und B,

    und nicht

        nicht-A und nicht-B → siehe Schritt 1

Daraus können wir folgenden Ausdruck ableiten:

SchrittAusdruckBeschreibung
1A*/(A*B)*/(/A*/B)) + B*/(A*B)*/(/A*/B)/(/A*/B) in beiden Fällen immer TRUE, da A bzw. B gelten
2A*/(A*B) + B*/(A*B)DeMorgan: OR zu NAND
3/(/(A*/(A*B))*/(B*/(A*B)))4 NAND-XOR → Dopplung von /(A * B)

Im Schaltplan sieht das folgendermaßen aus:

Schaltplan, bei dem jedes XOR eine andere Farbe hat.

Lernziele

In dieser Aufgabe …

  • wiederholen die Studierenden ihre theoretischen Kenntnisse über Logik-Gatter.
  • erstellen die Studierenden Schritt für Schritt die ersten Grundbausteine eines Rechner.
  • erhalten die Studierenden einen kurzen Ausblick auf die Schaltungsminimierung.