Vom Gatter zum Rechenwerk

1. Worum es geht

In der CPU Sandbox addiert ADD A, B zwei Bytes in einem einzigen Befehl. Aber wie macht ein Chip das, der nur Leitungen kennt, auf denen eine Spannung anliegt oder nicht? Diese Seite baut die Antwort von unten auf: erst Gatter, die aus ein oder zwei Bits ein neues machen, dann Schaltungen, die zwei Zahlen addieren, eine, die sich ein Bit merkt, und am Ende ein kleines Rechenwerk, das addiert, subtrahiert und Bits verknüpft.

Einrichten musst du nichts. Die Schaltungen probierst du direkt auf der Seite aus, und deinen Code schreibst du in die Karten der Aufgaben; »Ausführen« prüft ihn sofort. Was Bits und das Zweiersystem sind, steht im Handbuch unter Bits und Bytes.

2. Gatter

0 und 1 auf einer Leitung

Im Chip liegt auf jeder Leitung eine Spannung an oder nicht. Die eine Möglichkeit heißt 1, die andere 0. Ein Gatter ist eine kleine Schaltung, heute aus wenigen Transistoren, mit einem oder zwei Eingängen und einem Ausgang: Was am Ausgang herauskommt, hängt nur davon ab, was gerade an den Eingängen anliegt. Welche Ausgabe zu welchen Eingaben gehört, sagt die Wahrheitstabelle des Gatters, eine Zeile für jede Kombination der Eingänge.

Vier Gatter reichen für fast alles auf dieser Seite:

• UND liefert 1, wenn beide Eingänge 1 sind, sonst 0.
• ODER liefert 1, wenn mindestens einer der Eingänge 1 ist.
• NICHT hat nur einen Eingang und dreht ihn um: aus 1 wird 0, aus 0 wird 1.
• XOR, das exklusive ODER, liefert 1, wenn genau einer der Eingänge 1 ist.

Klick auf die Eingänge links, oder auf eine Zeile der Wahrheitstabelle. Leitungen mit einer 1 leuchten gelb, Leitungen mit einer 0 sind grau.

Die Schaltzeichen

Die Gatter sind gezeichnet wie in der Norm DIN EN 60617, international IEC 60617: als Rechteck, in dem steht, was das Gatter tut. & steht für UND, ≥1 für ODER (»mindestens eine 1«), =1 für XOR (»genau eine 1«) und 1 für ein Gatter, das seinen Eingang nur weitergibt. Ein kleiner Kreis am Ausgang dreht das Ergebnis um: Die 1 mit Kreis ist das NICHT. Diese Zeichen findest du in den meisten deutschen Schulbüchern. In englischen Büchern und in vielen Simulatoren siehst du stattdessen die amerikanischen Formen nach ANSI/IEEE 91, bei denen jedes Gatter eine eigene Form hat, das UND zum Beispiel wie ein D. Gemeint sind dieselben Gatter.

Zwei Schaltungen vergleichen

Gatter lassen sich hintereinanderschalten: Der Ausgang des einen wird zum Eingang des nächsten. Zwei Schaltungen mit den Eingängen a und b:

1. ein ODER aus a und b, dahinter ein NICHT: nicht (a oder b)
2. ein NICHT für a und eins für b, dahinter ein UND: (nicht a) und (nicht b)

Rechnen mit wahr und falsch

Dass man mit 1 und 0 rechnen kann wie mit Zahlen, nach festen Regeln wie den beiden von eben, ist älter als jeder Computer.

Mehr dazu

• MacTutor: Boole
• Wikipedia: Boolean data type

George Boole (1815–1864), englischer Mathematiker, Professor in Cork in Irland. In seinem Buch The Laws of Thought von 1854 rechnete er mit Aussagen, die wahr oder falsch sind, wie mit Zahlen. Nach ihm heißen true und false in vielen Sprachen Boolean, in Python ist es der Typ bool.

Bild: unbekannter Künstler, um 1864, gemeinfrei, zugeschnitten (Wikimedia Commons)

Gut achtzig Jahre später zeigte Claude Shannon, damals Student am MIT, dass Booles Algebra genau beschreibt, was Schalter tun.

Mehr dazu

• MacTutor: Shannon
• news.mit.edu
• people.math.harvard.edu (PDF)
• Wikipedia: Shannon–Fano coding
• MIT Technology Review: mighty mouse
• Wikipedia: A Symbolic Analysis of Relay and Switching Circuits

Claude Shannon (1916–2001). Wie viele Bits eine Nachricht mindestens braucht, rechnete er 1948 aus und gründete damit die Informationstheorie; das Wort Bit machte er bekannt. Er fuhr Einrad, jonglierte und baute die Maus Theseus, die selbst lernte, durch ein Labyrinth zu finden.

Schon als Student am MIT zeigte er 1937 in seiner Masterarbeit, dass sich Schaltungen aus Relais mit der Algebra von George Boole beschreiben und vereinfachen lassen, mit 1 und 0 für einen Kontakt, der geschlossen oder offen ist. Damit begann die Theorie der digitalen Schaltungen.

Einen Code mit so wenigen Bits wie möglich suchten er und Robert Fano fast gleichzeitig, jeder für sich. Der Shannon-Fano-Code kam nah heran, aber nicht immer ganz.

In derselben Arbeit von 1948 ließ er englische Texte Wort für Wort entstehen, jedes Wort nach dem vorigen aus einem Buch gezogen: ein winziges Sprachmodell, von Hand.

Foto: Tekniska museet, CC BY 2.0, zugeschnitten (Wikimedia Commons)

3. Alles aus NAND

Zwei weitere Gatter haben einen Kreis am Ausgang: NAND ist ein UND, dessen Ergebnis umgedreht wird, und NOR ein umgedrehtes ODER.

NAND hat eine erstaunliche Eigenschaft: Aus NAND-Gattern allein lässt sich jedes andere Gatter bauen, und damit jede Schaltung überhaupt. Chips werden darum gern aus NAND gebaut: In der heute üblichen CMOS-Technik braucht ein NAND vier Transistoren, ein UND sechs, denn es ist ein NAND mit einem NICHT dahinter.

Gatter aus NAND bauen

In den beiden Karten unten steht nand(a, b) schon fertig. Deine Funktionen dürfen ihre Eingänge nur an nand weitergeben, als ob sie Leitungen wären: nicht selbst vergleichen, nicht rechnen und keine Tabelle nachschlagen. Darauf achtet die Prüfung: Sie ruft deine Funktionen zuerst mit 0 und 1 auf und dann noch einmal mit Signalen, die nur nand lesen kann. Ein if a == 1 oder ein a & b in deinem Code fällt dabei auf, auch wenn die Ergebnisse stimmen. nand selbst ist mit == geschrieben, denn in Ruby und Python gibt es keine Transistoren.

4. Zwei Bits addieren: der Halbaddierer

Im Zweiersystem addierst du schriftlich wie im Zehnersystem, nur dass jede Ziffer 0 oder 1 ist. Zwei Bits zusammen ergeben höchstens 1 + 1, und das ist im Zweiersystem 10: Die Ziffer, die stehen bleibt, ist 0, und eine 1 geht als Übertrag in die nächste Spalte.

In der Spalte a + b steht das Ergebnis mit zwei Ziffern: Die linke Ziffer ist der Übertrag c, die rechte die Summe s.

Eine Schaltung, die das rechnet, hat zwei Eingänge und zwei Ausgänge: die Summe s und den Übertrag c, englisch Carry. Jeder der beiden Ausgänge ist ein einziges Gatter.

5. Drei Bits: der Volladdierer

Beim schriftlichen Addieren kommt in jeder Spalte außer der rechten der Übertrag aus der Spalte davor dazu. So addierst du 0110 und 0111, von rechts nach links, die Überträge klein darüber:

 Übertrag   1 1 0
            0 1 1 0      6
          + 0 1 1 1    + 7
          ---------    ---
            1 1 0 1     13

In der dritten Spalte von rechts stehen 1, 1 und der Übertrag 1: zusammen 3, im Zweiersystem 11, also Summe 1 und wieder ein Übertrag. Eine Schaltung für eine solche Spalte hat drei Eingänge, a, b und den Übertrag von rechts c_in, und zwei Ausgänge, die Summe s und den Übertrag nach links c_out. Sie heißt Volladdierer. Ihre Wahrheitstabelle hat acht Zeilen, eine für jede Kombination der drei Eingänge.

Einen Volladdierer kannst du aus zwei Halbaddierern bauen. Der erste addiert a und b, der zweite addiert zu dessen Summe den Übertrag c_in. Bleibt die Frage, was aus den beiden Überträgen wird.

def full_adder(a, b, c_in)
  s1, c1 = half_adder(a, b)
  s, c2 = half_adder(…)
  [s, …]    # hier: c1 und c2 zusammen
end

def full_adder(a, b, c_in):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(…)
    return [s, …]    # hier: c1 und c2 zusammen

6. Vier Bits: der Addierer

Für Zahlen mit vier Bits stellst du vier Volladdierer nebeneinander, so wie die vier Spalten der schriftlichen Addition: Jeder bekommt ein Bit von a und das Bit von b darunter, und sein Übertrag c_out wird der Übertrag c_in seines linken Nachbarn. Der rechte bekommt als Übertrag eine feste 0. Weil der Übertrag von rechts nach links durch alle Volladdierer läuft, heißt die Schaltung Ripple-Carry-Addierer, nach englisch ripple, eine kleine Welle.

Aus vier Bits kommen dabei vier Bits heraus und ein Übertrag aus der linken Spalte, der in kein Bit mehr passt.

In Ruby und Python sind die vier Bits einer Zahl eine Liste, das höchste Bit vorn, so wie du die Zahl schreibst: 0110 ist [0, 1, 1, 0]. Das Bit ganz rechts hat also den Index 3.

def add4(a, b)
  s = [0, 0, 0, 0]
  c = 0
  3.downto(0) do |i|
    # hier: full_adder mit a[i], b[i] und c; das Bit nach s[i], der Übertrag nach c
  end
  [s, c]
end

def add4(a, b):
    s = [0, 0, 0, 0]
    c = 0
    for i in range(3, -1, -1):
        # hier: full_adder mit a[i], b[i] und c; das Bit nach s[i], der Übertrag nach c
        pass
    return [s, c]

7. Ein Bit merken: das Flipflop

Bis hierher hing der Ausgang jeder Schaltung nur davon ab, was gerade an ihren Eingängen anliegt. Eine solche Schaltung heißt Schaltnetz. Ein Register wie A in der CPU Sandbox muss sich aber eine Zahl merken, auch wenn sich die Eingänge danach ändern. Dafür führt man den Ausgang eines Gatters zurück an einen Eingang davor: Die Schaltung bekommt einen Zustand und heißt dann Schaltwerk.

Das einfachste Schaltwerk ist das RS-Flipflop aus zwei NOR-Gattern. Sein Ausgang Q ist das gespeicherte Bit, der zweite Ausgang Qnicht Q (»Q quer«) das umgedrehte Bit. Jedes NOR bekommt einen Eingang von außen und den Ausgang des anderen NOR:

• \(\mathrm{Q} = \mathrm{NOR}(\mathrm{R}, \overline{\mathrm{Q}})\)
• \(\overline{\mathrm{Q}} = \mathrm{NOR}(\mathrm{S}, \mathrm{Q})\)

S heißt Set, »setzen«, und R Reset, »zurücksetzen«. Am Anfang sind S und R beide 0, Q ist 0 und Qnicht Q ist 1. Denk an die Wahrheitstabelle von NOR: Es liefert nur dann 1, wenn beide Eingänge 0 sind.

Mit Takt: das D-Flipflop

Damit der verbotene Zustand nicht vorkommt, bekommt das Flipflop zwei UND-Gatter davor. Der Eingang D (Daten) sagt, welches Bit gespeichert werden soll, und der Takt sagt, wann: Ist der Takt 1, wird D gespeichert, und Q folgt D. Ist der Takt 0, sind S und R beide 0, und das Flipflop hält sein Bit, egal was an D anliegt. Weil das NICHT vor dem einen UND steht, sind S und R nie zugleich 1.

Genauer heißt diese Schaltung taktzustandsgesteuertes D-Flipflop oder D-Latch: Solange der Takt 1 ist, folgt Q dem Eingang D. Die Register eines Prozessors übernehmen D dagegen meist nur in dem Augenblick, in dem der Takt von 0 auf 1 springt; das erreicht man mit zwei solchen Latches hintereinander. Ein Register mit 8 Bit besteht aus acht Flipflops mit demselben Takt, eins für jedes Bit.

8. Das Rechenwerk

Der Teil des Prozessors, der rechnet, heißt Rechenwerk oder ALU, nach englisch Arithmetic Logic Unit. Es bekommt zwei Zahlen und einen Befehl und liefert ein Ergebnis und die Flags: kleine Merker, die sagen, wie die Rechnung ausgegangen ist. Die MiniCPU der CPU Sandbox kennt zum Rechnen unter anderem ADD, SUB, AND, OR und XOR und hat zwei Flags (Handbuch, MiniCPU: Flags):

• ZF, das Zero-Flag, ist 1, wenn das Ergebnis 0 ist.
• CF, das Carry-Flag, ist nach ADD der Übertrag aus dem obersten Bit und nach SUB 1, wenn geborgt werden musste, weil die erste Zahl kleiner war. AND, OR und XOR setzen CF immer auf 0.

Das Rechenwerk dieser Seite hat dieselben fünf Befehle und dieselben beiden Flags, nur mit 4 statt mit 8 Bit. Für AND, OR und XOR reichen vier Gatter nebeneinander, eins für jedes Bit. Für ADD gibt es den Addierer. Bleibt SUB, und auch dafür nimmt das Rechenwerk den Addierer.

Und in der CPU Sandbox

Die ALU der MiniCPU kannst du dir genauso vorstellen, nur 8 Bit breit und mit weiteren Befehlen wie ADC, CMP und den Schiebebefehlen SHL und SHR. In der Sandbox selbst rechnet sie mit JavaScript, nicht mit Gattern, aber ihre Ergebnisse und Flags sind dieselben. Dass sie 8 Bit breit ist, merkst du in der Stufe MiniCPU 8X: Rechnungen mit den 16-Bit-Registern X und Y brauchen dort einen Takt mehr. CMP A, B rechnet A − B wie SUB und behält nur die Flags: Danach sagt CF = 1, dass A kleiner als B ist, genau wie bei deinem Rechenwerk.

9. Wie geht es weiter?

In der CPU Sandbox programmierst du einen ganzen Prozessor mit Registern, Speicher und Bildschirm, erst in Assembler und später in C. Das Rechenwerk dieser Seite steckt dort in jedem ADD und jedem CMP.