Interaktive Mathe- und Wissenschafts-Lektionen
DIGITALLOGIK — WELCHER BAUSTEIN ERLEDIGT DIE AUFGABE?
Jede Digitalschaltung ist eine Wahrheitstabelle im Schaltbild-Gewand. Die Frage ist nie, was ein Gatter tut, sondern welche Tabelle du brauchst: eine Entscheidung aus zwei Bits, eine ganze Logikfamilie aus einem einzigen Bauteil, Arithmetik samt Übertrag oder einen Schalter, der ein Signal aus mehreren auswählt. Diese vier Fälle decken fast alles ab, was ein Grundkurs verlangt.
01
Was du weißt: Zwei Eingänge, ein Ausgang und eine Regel, die sich als vier Zeilen schreiben lässt. Wähle das Gatter, dessen Ausgangsspalte deiner Regel entspricht.
Logik: Y = A ⊕ B
Rechenbeispiel: XOR mit A = 1 und B = 0 liefert 1; dasselbe Gatter liefert 0, sobald beide Eingänge übereinstimmen
Diesen Fall öffnen: XOR unterscheidet
02
Was du weißt: NAND ist funktional vollständig. Jedes andere Gatter lässt sich allein aus Kopien davon aufbauen, und damit auch jede Schaltung, die du als Wahrheitstabelle beschreiben kannst.
Logik: NOT A = NAND(A, A)
Rechenbeispiel: NAND(1, 1) = 0. Legt man beide Eingänge zusammen, gilt NAND(A, A) = NOT A; führt man das zurück, ergeben zwei NANDs ein AND
Diesen Fall öffnen: NAND universell
03
Was du weißt: Die Addition zweier Bits ergibt eine zweistellige Antwort. Das niederwertige Bit ist A XOR B, das höherwertige — der Übertrag — ist A AND B.
Logik: S = A ⊕ B, C = A ∧ B
Rechenbeispiel: 1 + 1 ergibt Summe = 0 und Übertrag = 1, also binär 10 — die einzige der vier Zeilen, in der der Übertrag anspricht
Diesen Fall öffnen: Halbaddierer 1+1
04
Was du weißt: Zwei Dateneingänge und eine Auswahlleitung. Der Ausgang übernimmt genau den Eingang, auf den die Auswahl zeigt, und ignoriert den anderen vollständig.
Logik: Y = A·¬S + B·S
Rechenbeispiel: A = 0, B = 1, S = 1 → Ausgang = 1, denn Ausgang = A·(NOT S) + B·S
Diesen Fall öffnen: MUX Auswahl
Eine Halbleiterfabrik verkauft Ihnen genau ein einziges Bauteil: das NAND-Gatter mit zwei Eingängen. Bauen Sie den Halbaddierer, den das Werkzeug unter Halbaddierer zeichnet — ein Summenbit, ein Übertragsbit —, aus nichts anderem auf. Wie viele NAND-Gatter werden benötigt, und woran erkennen Sie, dass Sie die günstigste Schaltung gefunden haben?
Beginnen Sie mit NOT, dem Einfachsten, wozu sich ein NAND bringen lässt. Verbinden Sie beide Eingänge mit derselben Leitung. Das Gatter fragt „sind beide auf High?“, und da beide A sind, antwortet es immer dann, wenn A es nicht ist.
AND kostet ein weiteres Gatter. Ein NAND ist bereits ein AND, dessen Ergebnis umgekehrt wurde; kehren Sie es also wieder um: Führen Sie den Ausgang in ein NOT, was nach Schritt 1 ein zweites NAND mit verbundenen Eingängen ist. OR benötigt drei Gatter, indem jeder Eingang vor einem NAND invertiert wird — was De Morgan rückwärts gelesen entspricht.
XOR ist dasjenige, das sich widersetzt. Der Trick besteht darin, den mittleren Term einmal zu berechnen und ihn nacheinander gegen jeden Eingang auszuspielen. Nennen Sie ihn C und führen Sie ihn zusammen mit A in ein NAND sowie noch einmal zusammen mit B.
Formen Sie D aus. Es lautet „nicht sowohl A als auch (nicht A oder nicht B)“. Die Hälfte „A und nicht A“ davon kann niemals eintreten, fällt also weg, und was übrig bleibt, ist kurz. E ist dieselbe Aussage mit vertauschten Buchstaben.
Das letzte NAND führt sie zusammen. De Morgan macht aus einem NAND zweier Negationen ein einfaches OR, und ein OR von „A, aber nicht B“ mit „B, aber nicht A“ ist genau die Bedeutung von XOR. Vier Gatter für das Summenbit.
Nun zum Übertrag. Er ist A AND B, was in Schritt 2 mit zwei Gattern veranschlagt wurde — doch das erste dieser beiden ist C, und C liegt bereits auf einer Leitung in der Mitte des soeben gebauten XOR. Greifen Sie es ein drittes Mal ab und verbinden Sie es mit sich selbst.
Damit sind es fünf und nicht sechs. Die eine Hälfte davon hast du eben konstruiert: Der Übertrag allein benötigt nach Schritt 2 genau 2 Gatter, die Summe nach Schritt 5 genau 4. In Schritt 6 siehst du, dass beide genau ein Gatter gemeinsam nutzen. Also gilt 2 + 4 − 1 = 5. Dass keine Schaltung mit weniger als fünf Gattern auskommt, ist eine eigene Aussage, für die diese Seite keinen Beweis liefert. Sie beruht auf einer vollständigen Suche durch alle NAND-Netzwerke mit zwei Eingängen und höchstens sechs Gattern, also auf einer Berechnung statt auf einem mathematischen Argument.
Die Anzahl der Gatter sagt nichts über die Laufzeit aus. Verfolgen Sie den Übertrag: aus G1 direkt in G5, zwei Gatter tief. Die Summe muss G2 oder G3 und danach G4 passieren, ist also drei Gatter tief. Zählt man die Wege von A zur Summe, sind diese nicht einmal gleich lang.
Antwort
Fünf NAND-Gatter, und fünf ist das Minimum. Stellen Sie das Werkzeug auf Halbaddierer mit A = 1 und B = 1 ein, und es zeigt das Summenbit springt auf 0 und der Übertrag wird 1. Verfolgen Sie diese Zeile in der Skizze: C = 0, dann D = E = 1, dann S = 0, und das Übertragsgatter, das C gegen sich selbst ausliest, ergibt 1. C wird einmal berechnet und dreimal abgelesen, was die gesamte Ersparnis ausmacht.
Die Tiefen in Schritt 8 haben eine Konsequenz, die die Wahrheitstabelle nicht zeigen kann. Nähert man sich 1 + 1 aus der Zeile darüber, wobei A bereits High ist und B steigt: Der Übertrag steigt nach zwei Gatterlaufzeiten; die Summe fällt erst nach der dritten. Für eine volle Gatterlaufzeit zeigen die beiden Ausgangspins 1 und 1, was als Übertrag und Summe binär 11 entspricht, womit der Addierer kurzzeitig behauptet, dass 1 + 1 = 3 ist. Ein getakteter Baustein sieht dies nie, da die Taktperiode länger gewählt wird als der langsamste Pfad durch die Logik. Sie zu kurz zu wählen, ist genau das, was eine Timing-Verletzung ausmacht.