Logikgatter: vom Schalter bis zur ALU

Jeder Computer, vom Handy bis zum Rechenzentrum, rechnet mit Schaltungen aus wenigen Arten winziger Entscheidungen: Ist ein Signal an oder aus? Dieser Artikel beginnt mit einem einzelnen Schalter und endet bei einer arithmetisch-logischen Einheit, der ALU, dem Teil eines Prozessors, der addiert, subtrahiert und vergleicht. Zu jedem Schritt gibt es eine Schaltung zum Anklicken.

Der Rechenteil folgt David Goldbergs Anhang „Computer Arithmetic“ [6] in John L. Hennessys und David A. Pattersons Computer Architecture: A Quantitative Approach [5], einem Buch, das jeden Entwurf an Zahlen misst: Wie schnell ist er, und was kostet er?

Einsen und Nullen

Ein Computer kennt keine Zahlen, Buchstaben oder Farben. Im Innersten kennt er nur Signale, die an oder aus sind. Wir schreiben sie als 1 und 0 und nennen einen solchen Wert ein Bit. Auf einem Chip ist ein Bit eine Spannung: nahe der Versorgungsspannung für 1, nahe null für 0. Zwei Zustände sind robust: Ein Signal, das unterwegs etwas Rauschen eingefangen hat, ist immer noch eindeutig hoch oder eindeutig niedrig.

Lange vor der Elektronik veröffentlichte George Boole 1854 ein Buch, das logisches Schließen wie eine Art Algebra behandelt [1]. Die Algebra mit den Werten 0 und 1 und den Operationen UND, ODER und NICHT trägt heute seinen Namen: boolesche Algebra. 1938 zeigte Claude Shannon, dass sich mit dieser Algebra Schaltungen aus Relais und Schaltern beschreiben und vereinfachen lassen [3]. Darauf baut dieser ganze Artikel auf: Logik lässt sich aus Schaltern bauen.

Zwei Schalter genügen schon, um das zu sehen. In Reihe leuchtet die Lampe nur, wenn A und B geschlossen sind. Nebeneinander reicht einer von beiden: A oder B. Klicke auf die Schalter.

Die Grundgatter

Ein Gatter ist eine winzige Schaltung, die eine solche Funktion berechnet. Auf heutigen Chips bestehen Gatter aus Transistoren, Schaltern, die von einer Spannung statt von einem Finger betätigt werden. Drei Gatter sind die Grundlage von allem:

• NICHT (NOT) dreht seinen Eingang um: Aus 0 wird 1, aus 1 wird 0.
• UND (AND) gibt nur 1 aus, wenn alle Eingänge 1 sind, wie die Schalter in Reihe.
• ODER (OR) gibt 1 aus, wenn mindestens ein Eingang 1 ist, wie die Schalter nebeneinander.

Eine Wahrheitstabelle listet den Ausgang für jede Kombination der Eingänge; bei zwei Eingängen sind es vier Zeilen. Drei weitere Gatter sind genauso verbreitet: NAND und NOR sind UND und ODER mit invertiertem Ausgang, und XOR, das exklusive Oder, gibt 1 aus, wenn sich seine Eingänge unterscheiden. In den Symbolen bedeutet der kleine Kreis am Ausgang immer „invertiert“.

Eine Randnotiz zu echten Chips: In CMOS, der Transistortechnik fast aller heutigen Chips, sind die invertierenden Gatter NAND und NOR die kleinsten. Ein UND ist ein NAND mit einem zusätzlichen Inverter dahinter. Bereit für einen kleinen Test? In der Kiste unten steckt ein Gatter. Probiere Eingänge aus, bis du weißt, welches es ist.

Die Spielregeln

Gatter gehorchen Regeln, ganz ähnlich wie Zahlen: A UND 1 = A, A ODER 1 = 1, A UND A = A. Zwei der nützlichsten sind nach Augustus De Morgan benannt, einem Zeitgenossen Booles, dessen Buch Formal Logic 1847 erschien [2]:

• NICHT (A UND B) = (NICHT A) ODER (NICHT B)
• NICHT (A ODER B) = (NICHT A) UND (NICHT B)

In Worten: Ein invertiertes UND ist dasselbe wie ein ODER der invertierten Eingänge, und umgekehrt. Zwei völlig verschiedene Schaltungen, ein Ergebnis. Prüfe es nach: Es gibt nur vier Eingangskombinationen, du kannst also alle ausprobieren.

Noch überraschender: Eine einzige Gatterart reicht für alles. Henry M. Sheffer zeigte 1913, dass sich die gesamte boolesche Algebra aus einer einzigen Operation aufbauen lässt [4]. Seine Operation war „weder … noch“, unser NOR, und NAND funktioniert genauso. Deshalb heißen NAND und NOR universelle Gatter.

Zählen mit Bits

Ein einzelnes Bit sagt nur ja oder nein. Mehrere Bits nebeneinander ergeben eine Zahl. Wie bei Dezimalziffern hat jede Stelle einen Wert, nur verdoppeln sich die Werte, statt sich zu verzehnfachen: 1, 2, 4, 8 und so weiter. Mit acht Bits lässt sich von 0 bis 255 zählen.

Und negative Zahlen? Goldberg nennt vier Arten, sie in Bits zu schreiben, und das Zweierkomplement die verbreitetste [6, S. J-7–J-8]. Die Idee: Das oberste Bit zählt negativ, −128 bei acht Bits, alle anderen zählen wie bisher positiv [6, Gl. J.2.3]. 11111111 ist dann −1, und acht Bits decken −128 bis 127 ab. Eine Zahl und ihr Negatives ergeben zusammen 2ⁿ, hier 256 [6, S. J-7]. Schalte unten die Lesart um und sieh, was dieselben Bits bedeuten.

Halbaddierer und Volladdierer

Binäre Addition funktioniert wie die schriftliche Addition in der Schule, Spalte für Spalte: 0 + 0 = 0, 0 + 1 = 1 und 1 + 1 = 10, eine 0 und ein Übertrag von 1 in die nächste Spalte. Genau hier beginnt Goldbergs Anhang mit der Ganzzahlarithmetik [6, S. J-2]. Ein Halbaddierer addiert zwei Bits a und b: Seine Summe ist s = a XOR b, sein Übertrag c = a UND b.

Ein Volladdierer nimmt zusätzlich den Übertrag aus der Spalte rechts daneben als dritten Eingang. Seine Summe ist 1, wenn eine ungerade Zahl seiner Eingänge 1 ist, sein Übertrag, wenn mindestens zwei es sind [6, Gl. J.2.1, J.2.2]. Er lässt sich aus zwei Halbaddierern und einem ODER-Gatter bauen:

Der Ripple-Carry-Addierer

Um zwei Zahlen mit n Bits zu addieren, stellt man n Volladdierer in eine Reihe und verbindet den Übertrag jedes einzelnen mit dem Übertragseingang des nächsten. Das ist der Ripple-Carry-Addierer [6, S. J-3, Abb. J.1]. Der Übertrag ins unterste Bit ist vorerst 0; bei der Subtraktion wird er noch nützlich.

Jetzt die Frage, die Hennessys und Pattersons Buch jedem Entwurf stellt: Wie schnell ist er? Goldberg zählt Logikebenen, die Zahl der Gatter, die ein Signal nacheinander durchlaufen muss, denn genaue Zeiten hängen von der Technologie ab. Ein Volladdierer braucht zwei Ebenen für seinen Übertrag, also steht der Übertrag aus dem obersten Bit nach 2n Ebenen fest [6, S. J-3]: 16 bei 8 Bits, 128 bei 64 Bits. Der Ripple-Carry-Addierer ist der langsamste Addierer, aber auch der billigste [6, S. J-3]. Drücke auf „Schlimmster Fall“ und verfolge den Übertrag von rechts nach links. Bis er ankommt, zeigen die Ausgänge eine falsche Summe.

Schnellere Addierer berechnen die Überträge parallel. Ein Carry-Lookahead-Addierer nutzt zwei Signale pro Bit: generate, g = a UND b, dieses Bit erzeugt selbst einen Übertrag, und propagate, p = a ODER b, dieses Bit reicht einen ankommenden Übertrag weiter [6, S. J-37]. Damit lässt sich jeder Übertrag direkt aus den Eingängen hinschreiben. Ein reiner Carry-Lookahead-Addierer braucht nur fünf Logikebenen, doch bei vielen Bits bräuchten seine Gatter unpraktisch viele Eingänge. Echte Entwürfe ordnen dieselbe Idee deshalb als Baum an, der etwa log₂ n Ebenen statt 2n braucht [6, S. J-38–J-39]. Ein paar Gatter mehr für einen viel schnelleren Addierer: quantitativer Entwurf im Kleinen.

Subtraktion und Überlauf

Für die Subtraktion braucht es keine neue Schaltung. Im Zweierkomplement erhält man das Negative einer Zahl so: jedes Bit invertieren, dann 1 addieren. Also ist a − b = a + (NICHT b) + 1: b auf dem Weg in den Addierer invertieren und den Übertrag ins unterste Bit auf 1 setzen [6, S. J-8]. Dafür war der Übertragseingang da.

Mit einer festen Zahl von Bits kann ein Ergebnis zu groß werden. Goldberg beschreibt, wie man diesen Überlauf erkennt: Bei vorzeichenlosen Zahlen gibt es einen Übertrag aus dem obersten Bit; im Zweierkomplement unterscheidet sich der Übertrag ins oberste Bit von dem aus ihm heraus [6, S. J-8]. Prozessoren melden solche Ereignisse in Flag-Bits, etwa einem C-Bit für den Übertrag und einem V-Bit für den Überlauf [6, S. J-11, Abb. J.5]. Beim Subtrahieren auf diese Weise heißt ein Übertrag von 1 einfach, dass kein Borgen nötig war.

Die ALU

Eine arithmetisch-logische Einheit, kurz ALU, ist der Teil eines Prozessors, der rechnet, und sie verbindet alles von oben. Patterson und Hennessy bauen in ihrem Anhang „The Basics of Logic Design“ Schritt für Schritt eine [7], und die ALU hier folgt diesem Entwurf. Jedes Bit bekommt eine Scheibe mit einem UND-Gatter, einem ODER-Gatter und einem Volladdierer. Ein Multiplexer, ein Wahlschalter aus Gattern, entscheidet, welches der drei Ergebnisse hinausgeht. Zwei weitere Multiplexer können a und b auf dem Weg hinein invertieren. Acht Scheiben nebeneinander, über ihre Überträge verbunden, ergeben eine 8-Bit-ALU.

Mit nur vier Steuerleitungen beherrscht sie sechs Operationen: UND, ODER und Addition direkt; Subtraktion, indem b invertiert und der Übertrag gesetzt wird; NOR und NAND, indem beide Eingänge invertiert werden, die De Morganschen Gesetze bei der Arbeit. Vier Flags beschreiben das Ergebnis: Zero, Negative, Carry und Overflow. Wähle eine Operation, öffne die Steuerleitungen und löse die Aufgaben.

Wie es weitergeht

Eine ALU allein ist noch kein Prozessor. Register halten die Operanden, ein Steuerwerk entscheidet, welche Operation läuft, und der Speicher enthält das Programm. Wie all das entworfen und gemessen wird, von Caches bis zu Pipelines, ist das Thema von Hennessys und Pattersons Computer Architecture: A Quantitative Approach [5]. Goldbergs Anhang in diesem Buch geht weiter mit Multiplikation, Division und Gleitkommazahlen [6]. Und der Anhang „The Basics of Logic Design“ in Pattersons und Hennessys Computer Organization and Design behandelt den Stoff dieses Artikels ausführlich, von Gattern bis zur ALU [7].

Quellen

1. G. Boole, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. London: Walton and Maberly, 1854. Online bei Project Gutenberg
2. A. De Morgan, Formal Logic: or, The Calculus of Inference, Necessary and Probable. London: Taylor and Walton, 1847. Online im Internet Archive
3. C. E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” Transactions of the American Institute of Electrical Engineers, Bd. 57, Nr. 12, S. 713–723, 1938. doi:10.1109/T-AIEE.1938.5057767
4. H. M. Sheffer, “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants,” Transactions of the American Mathematical Society, Bd. 14, Nr. 4, S. 481–488, 1913. doi:10.1090/S0002-9947-1913-1500960-1
5. J. L. Hennessy und D. A. Patterson, Computer Architecture: A Quantitative Approach, 6. Aufl. Morgan Kaufmann (Elsevier), 2017. ISBN 978-0-12-811905-1. Verlagsseite
6. D. Goldberg, “Appendix J: Computer Arithmetic,” Online-Anhang in J. L. Hennessy und D. A. Patterson, Computer Architecture: A Quantitative Approach, 6. Aufl. Morgan Kaufmann (Elsevier), 2017. Verwendet: Abschnitte J.2 “Basic Techniques of Integer Arithmetic” (ab S. J-2) und J.8 “Speeding Up Integer Addition” (ab S. J-37). Begleitmaterial des Verlags
7. D. A. Patterson und J. L. Hennessy, Computer Organization and Design RISC-V Edition: The Hardware/Software Interface, 2. Aufl. Morgan Kaufmann (Elsevier), 2020. ISBN 978-0-12-820331-6. Anhang A: “The Basics of Logic Design.” Verlagsseite