Logikgatter

Intels erster Mikroprozessor, der 4004 von 1971, enthielt 2300 Transistoren. Sie waren zu Gattern verdrahtet, und aus Gattern besteht ein Prozessor ganz und gar.

Shannons zwei Schaltungen auf dem Tisch

Du kannst Shannons zwei Schaltungen mit einer Batterie, einer Lampe und zwei Schaltern nachbauen. Schalte die Schalter hintereinander, dann leuchtet die Lampe nur, wenn der erste und der zweite geschlossen sind. Schalte sie nebeneinander, dann leuchtet die Lampe, wenn einer von beiden geschlossen ist. Diese Schaltungen treffen schon Entscheidungen. Ein Logikgatter ist eine kleine Schaltung derselben Art, gebaut aus Transistoren statt aus Handschaltern. Es nimmt ein oder zwei Eingangsbits und erzeugt nach einer festen Regel ein Ausgangsbit.

Sechs Gatter und die Tabellen, die sie festlegen

AND ergibt nur dann 1, wenn beide Eingänge 1 sind, wie die Schalter in Reihe. OR ergibt 1, wenn mindestens ein Eingang 1 ist, wie die Schalter nebeneinander. NOT hat einen einzigen Eingang und kehrt ihn um, aus 0 wird 1 und aus 1 wird 0. XOR, kurz für „exclusive or“ (exklusives Oder), ergibt 1, wenn die beiden Eingänge verschieden sind. NAND und NOR sind AND und OR mit einem NOT am Ende, ihre Ausgänge sind also genau umgekehrt. Eine Wahrheitstabelle listet jede Kombination der Eingänge und den Ausgang dazu auf. Zwei Eingänge ergeben vier Zeilen, drei ergeben acht, und n Eingänge ergeben 2 hoch n.

Eine Alarmanlage, ein Gleichheitstest und eine Passwortprüfung

Gatter lassen sich zu Regeln beliebiger Größe kombinieren. Nimm eine Einbruchmeldeanlage. Sie soll klingeln, wenn das System scharf geschaltet ist AND (die Tür offen ist OR ein Fenster offen ist). Das ist ein OR-Gatter, das in ein AND-Gatter führt. Um zu prüfen, ob zwei Bits gleich sind, setzt man ein NOT hinter ein XOR, denn XOR ergibt genau dann 1, wenn die Bits verschieden sind. Stell acht davon nebeneinander, verbinde ihre Ausgänge mit AND, und die Schaltung sagt dir, ob zwei ganze Bytes übereinstimmen. Jeder Vergleich in einem Programm, von „Stimmt das Passwort?“ bis „Ist der Timer bei null?“, endet als eine solche Schaltung.

Warum Chiphersteller mit NAND allein auskommen

NAND hat eine praktische Eigenschaft: Jedes andere Gatter lässt sich allein aus NAND-Gattern bauen. Verbinde beide Eingänge eines NAND, und es wird zu NOT, denn NAND von 1 und 1 ist 0 und NAND von 0 und 0 ist 1. Setz dieses NOT hinter ein weiteres NAND, und du hast wieder AND. Ein paar mehr ergeben OR und XOR. Chiphersteller mögen das, weil sie riesige Mengen einer einzigen gut getesteten Form anlegen können. In einem echten Chip ist ein Gatter eine Handvoll Transistoren. Der 4004 hatte 2300 davon, und Intel nennt 1.16 Milliarden für seinen Core-Prozessor der zweiten Generation von 2010. Das sind in 39 Jahren etwa 500 000-mal so viele.