Wie funktioniert ein Logikaddierer? Summe und Übertrag

7 und 9 allein mit Schaltern addieren

Logikgatter addieren Binärzahlen, indem sie für jede Stelle ein Summenbit und ein Übertragsbit erzeugen. Ein Volladdierer übernimmt auch den Übertrag der vorherigen Stelle. Beim Ripple-Carry-Addierer muss jeder Übertrag erst die Gatter durchlaufen, bevor das Endergebnis stabil ist.

Auf Papier passt 7 + 9 in eine Zeile: 6 an der Einerstelle, die 1 übertragen, Ergebnis 16. Ein Computer hat weder Papier noch eine Vorstellung davon, was eine Zahl ist. Er hat Schalter, die ein- oder ausgeschaltet sind. Wie kommt eine Ansammlung von Schaltern von 7 und 9 auf 16?

Die Platine oben erklärt das Schicht für Schicht und führt dann weiter. Zu Beginn zeigt sie einen 4-Bit-Ripple-Carry-Addierer. An der Vorderkante stehen acht Bitschalter für die Zahlen A und B von jeweils 0 bis 15, dahinter zwanzig Logikgatter und an der Hinterkante fünf Ergebnis-LEDs. Beim Umschalten leuchten die Kupferleiterbahnen, die eine 1 führen. Das Licht läuft mit der am Regler „Gatterlaufzeit“ eingestellten Geschwindigkeit durch die Gatter. Das Eckfeld zeigt Eingänge und LEDs gleichzeitig binär und dezimal.

Der Regler „Schaltung“ wählt eine von 15 Schaltungen aus denselben Gatterchips. Dazu gehören ein einzelnes Gatter, Halb- und Volladdierer, 4-Bit- und 8-Bit-Ripple-Carry-Addierer, Carry-Lookahead-Addierer, Addierer/Subtrahierer, Komparator, Multiplexer, 7-Segment-Decoder, SR-Latch, D-Flipflop, Zähler, eine kleine ALU und ein Rätsel aus vier NAND-Gattern. Alle laufen in derselben Simulation. So lassen sich Gatterzahl und Einschwingzeit vergleichen.

Zahlen aus zwei Ziffern

Im Dezimalsystem ist jede Stelle zehnmal so viel wert wie die rechte Nachbarstelle: Einer, Zehner, Hunderter. Binär funktioniert es mit zwei statt zehn. Die Stellen haben die Werte 1, 2, 4 und 8. Vier Bits können daher jede Zahl von 0 (0000) bis 15 (1111) speichern. Auf der Platine ist A0 die Einerstelle und A3 die Achterstelle. Kleine Zahlen unter den Schaltern geben ihren Stellenwert an.

Sieben ist 4 + 2 + 1, also 0111. Neun ist 8 + 1, also 1001. Ihre Summe 16 braucht eine fünfte Stelle mit dem Wert 16: Das Ergebnis ist 10000. Diese fünfte Stelle ist die Übertrags-LED C4. Nur durch sie kann die Platine Summen über 15 anzeigen.

Binärzahlen passen zur Elektronik, weil eine Leitung nur zwei deutlich getrennte Zustände braucht. Eine Schaltung muss nicht 3 von 3,5 Volt unterscheiden, sondern nur „hoch“ von „niedrig“. Das lässt sich milliardenmal pro Sekunde viel zuverlässiger erledigen.

Ein Transistor als Schalter

Für den einfachen Versuch steht „Schaltung“ auf „Ein Gatter“ und die Auswahl unter dem Modell auf „Draht“. Schalter X verbindet eine LED über eine Drahtbrücke mit der Versorgung. Die LED zeigt genau den Schalterzustand: 1 ist an, 0 ist aus.

Bei „Transistor“ erscheint ein NPN-Transistor mit drei Anschlüssen. Ein kleiner Strom in den mittleren Anschluss, die Basis, lässt einen viel größeren Strom zwischen den anderen beiden, Kollektor und Emitter, fließen. Die LED leuchtet. Ohne Basisstrom erlischt sie. Der Transistor ist ein Schalter geworden, den Elektrizität statt eines Fingers betätigt.

Das ist eine Vereinfachung, auf die das Modell hinweist. Ein realer Transistor ist ein analoges Bauteil: In einem bestimmten Bereich bewirkt mehr Basisstrom mehr Kollektorstrom. Logikschaltungen sind so ausgelegt, dass er nur ganz aus oder ganz ein bleibt und den Zwischenbereich möglichst schnell durchläuft. Deshalb lässt er sich als Schalter behandeln.

Gatter aus Transistorpaaren

Sobald ein Schalter einen anderen steuert, lassen sich Entscheidungen aufbauen. Heutige Chips verwenden MOSFETs in zwei Ausführungen. n-Kanal-Transistoren leiten bei hohem Eingang, p-Kanal-Transistoren bei niedrigem. CMOS-Logik kombiniert sie so, dass ein Netzwerk den Ausgang zur Versorgung und das andere nach Masse zieht. Bei jeder Eingabe leitet genau eines der beiden. Ein ruhendes Gatter nimmt fast keinen Strom auf. Diese Eigenschaft zeigten Chih-Tang Sah und Frank Wanlass 1963 bei Fairchild. Sie ermöglicht Milliarden Transistoren in einem Telefon, ohne dass es schmilzt.

Beim Zählen der Transistoren werden die unterschiedlichen Kosten sichtbar:

Ausgerechnet AND, meist das zuerst erklärte Gatter, braucht mehr Bauteile als NAND. In CMOS ergeben sich zunächst invertierende Funktionen, weil das n-Kanal-Netzwerk den Ausgang absenkt. Zwei n-Kanal-Transistoren in Reihe ziehen ihn nur bei zwei Einsen herunter: NAND. Zwei parallel ergeben NOR. Für AND kommt ein Inverter hinzu. „Transistoren je Chip“ zeigt die jeweiligen Zahlen. Bei „Ein Gatter“ lassen sich alle sieben Typen und der einfache Draht durchgehen.

NAND hat noch eine Eigenschaft. Ausschließlich daraus entstehen NOT durch verbundene Eingänge, AND aus NAND und NOT, OR durch vorheriges Invertieren beider Eingänge und alle weiteren Funktionen. Darauf beruht die letzte Schaltung. Im Labor unter den Bedienelementen werden die Eingänge von vier NAND-Gattern gewählt. Mit der richtigen Verbindung entspricht der Ausgang in allen vier Zeilen XOR.

Halbaddierer: XOR für die Summe, AND für den Übertrag

Die XOR-Wahrheitstafel entspricht der letzten Ziffer einer Binäraddition. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 und 1 + 1 = 10. Im letzten Fall stehen an dieser Stelle 0 und im Übertrag 1. Die rechte Ziffer jedes Ergebnisses ist genau die XOR-Spalte. Nur die letzte Zeile hat einen Übertrag von 1: genau AND.

Ein XOR und ein AND mit denselben zwei Eingangsbits addieren sie also. Dieses Paar heißt Halbaddierer. Auf der Halbaddierer-Platine steht es allein; im 4-Bit-Addierer bildet es den ersten Block jedes Bits. Bei A = 1 und B = 1 liefert XOR die Summe 0 und AND den Übertrag 1.

Volladdierer: drei Bits hinein, zwei heraus

Für die Einerstelle genügt ein Halbaddierer. Alle anderen Stellen müssen drei Werte addieren: ein Bit von A, eines von B und den Übertrag von rechts. Ein Volladdierer erledigt das mit zwei Halbaddierern und einem OR. Auf der Platine heißen die Signale je Bit:

1. p = A xor B und g = A and B (erster Halbaddierer)
2. S = p xor C und t = p and C (zweiter Halbaddierer mit Eingangsübertrag C)
3. Ausgangsübertrag = g or t

Das OR bekommt nie zwei Einsen zugleich. Sind A und B beide 1, ist p gleich 0 und t kann nicht 1 sein. Es vereinigt nur die beiden Möglichkeiten: Die Stelle erzeugt selbst einen Übertrag (g), oder sie reicht den empfangenen Übertrag weiter (t). Die acht Zeilen der Volladdierer-Wahrheitstafel erfassen alle Fälle. Der größte, 1 + 1 + 1 = 3, ergibt Übertrag 1 und Summe 1.

Fünf Gatter je Bit ergeben bei vier Bits die 20 Gatter des 4-Bit-Addierers. Der Ausgangsübertrag jedes Volladdierers führt zum Eingangsübertrag seines linken Nachbarn, entsprechend dem Übertragen der 1 auf Papier. Diese Kette erklärt den Namen Ripple Carry. Im Betrieb markiert die Wahrheitstafel im Eckfeld die verwendete Zeile jedes Bits. So kann Bit 0 auf 1 1 0 stehen, während Bit 3 auf 0 1 1 wartet.

Warum der Übertrag Zeit braucht

Kein Gatter antwortet sofort. Nach einer Eingangsänderung folgt der Ausgang etwas später. Diese Zeit heißt Gatterlaufzeit oder Ausbreitungsverzögerung. Im Modell dauert jedes Gatter genau eine Einheit. Der Regler dehnt sie zum Beobachten auf 0,05 bis 2,4 Sekunden.

Bei 7 + 9, ausgehend von 0 + 0, geschieht Folgendes:

Jedes Bit braucht zwei Gatterlaufzeiten zum Weiterreichen: eine für das AND, das t erzeugt, und eine für das OR am Ausgangsübertrag. Über vier Bits kommt der letzte Übertrag nach 8 Laufzeiten an. Der ungünstigste Fall der 4-Bit-Platine braucht 9, entsprechend 2n + 1 bei n = 4 Bits. „Laufzeit je Chip“ zeigt den Zeitpunkt der letzten Ausgangsänderung. Entlang der Übertragskette steigen die Zahlen auf 2, 4, 6, 8.

Während dieser 8 Laufzeiten erscheinen auch falsche Ergebnisse. Nach Laufzeit 6 kann das Feld 01000 anzeigen, also 8. Das ist kein Defekt, sondern eine Summe von vor der Ankunft des Übertrags. Auch reale Schaltungen haben solche kurzen Fehlausgaben, sogenannte Glitches. Ein Prozessor wartet deshalb eine feste Zeit für den langsamsten Pfad, bevor er den Addiererausgang liest. Diese Wartezeit bestimmt die Taktfrequenz mit. Im „Zeitdiagramm“ erscheint derselbe Ablauf als Wellenform mit zunächst wechselnden Ausgängen.

Die 8-Bit-Platine macht den Aufwand deutlich. Acht gleiche Volladdierer ergeben 40 Gatter. Bei 255 + 1 läuft ein Übertrag durch jedes Bit. Die LEDs werden nach 16 Gatterlaufzeiten stabil, doppelt so spät wie bei 15 + 1 auf der 4-Bit-Platine. Ein entsprechend gebauter 64-Bit-Addierer bräuchte im ungünstigsten Fall 129 Laufzeiten. „Eine Laufzeit pro Schritt“ und „Nächste Laufzeit“ unter dem Modell erlauben einzelne Schritte.

Überträge vorausberechnen

Schnelle Addierer warten nicht auf die ganze Kette. Eine Stelle erzeugt selbst einen Übertrag, wenn g = A and B gleich 1 ist, und reicht einen empfangenen weiter, wenn p = A xor B gleich 1 ist. Beide Signale stehen in allen Stellen gleichzeitig nach einer Gatterlaufzeit bereit. Daraus lassen sich die Überträge vollständig ausdrücken:

• C1 = g0 + p0 C0
• C2 = g1 + p1 g0 + p1 p0 C0
• C3 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 C0
• C4 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 C0

C2 bedeutet: Ein Übertrag erreicht Bit 2, wenn Bit 1 einen erzeugt, wenn Bit 1 einen von Bit 0 erzeugten weiterreicht oder wenn Bits 1 und 0 beide den Eingangsübertrag durchlassen. Jede Zeile entspricht AND-Gattern mit einem nachfolgenden OR. Alle Überträge sind nach drei Gatterlaufzeiten da, die Summen eine später. Die Carry-Lookahead-Platine braucht dafür 26 Gatter. 15 + 1 wird nach 4 Laufzeiten stabil statt nach 8 beim Ripple-Addierer. Die Tabelle zeigt P, G und Übertrag jedes Bits.

Der Preis liegt in den AND-Gattern. Schon C4 braucht ein AND und ein OR mit jeweils 5 Eingängen. Mit jeder Stelle wachsen die Terme. Breite Addierer kombinieren deshalb kleine Lookahead-Blöcke von vier Bits mit einer zweiten Lookahead-Ebene zwischen den Blöcken. Gerald Rosenberger von IBM meldete 1957 ein Patent für einen binären Carry-Lookahead-Addierer an. Charles Babbage hatte das Problem ein Jahrhundert zuvor erkannt und für seine Analytical Engine eine Übertragsvorhersage entworfen. Heute ist ein 4-Bit-Addierer mit schnellem Übertrag ein Katalogbauteil: Texas Instruments führt weiterhin den SN74LS283.

Mit demselben Addierer subtrahieren

Computer brauchen keinen getrennten Subtrahierer. Im Zweierkomplement, der üblichen Darstellung negativer Zahlen, entsteht minus B durch Umkehren aller Bits von B und anschließendes Addieren von 1. A − B ist also A + (not B) + 1.

Die Platine „Addierer/Subtrahierer“ setzt vor jedes Bit von B ein XOR. Bei ausgeschaltetem SUB reicht es B unverändert durch. Bei eingeschaltetem SUB kehrt es das Bit um. Dieselbe SUB-Leitung speist den Eingangsübertrag und liefert die zusätzliche 1. Für 5 − 7 wird B = 0111 zu 1000. Der Addierer berechnet 0101 + 1000 + 1 = 1110. Mit Vorzeichen ist diese 4-Bit-Zahl −2, ohne Vorzeichen 14. Auch das ist auf seine Weise richtig: 5 − 7 + 16 = 14. Die Bedeutung derselben Bits hängt von der Lesart ab. Das Feld zeigt beide.

Eine 4-Bit-Zahl mit Vorzeichen reicht nur von −8 bis 7. Manche Ergebnisse passen nicht hinein. Die grüne V-LED erkennt das durch XOR aus dem Übertrag in das höchste Bit und dem Übertrag heraus. Sind sie verschieden, leuchtet sie. 7 + 1 bei ausgeschaltetem SUB aktiviert sie, denn 0111 + 0001 = 1000 wird als −8 gelesen. Die zusätzliche XOR-Reihe braucht am Anfang eine weitere Gatterlaufzeit, das V-Gatter am Ende ebenfalls eine. Der ungünstigste Fall braucht daher 11.

Zwei Zahlen vergleichen

Wie entscheidet eine Schaltung, dass 9 größer als 5 ist? Wie bei geschriebenen Zahlen zählt die höchste unterschiedliche Stelle. Der Komparator berechnet das pro Bit. A > B bedeutet A ist 1 und B ist 0, also ein AND mit invertiertem B. A < B ist der umgekehrte Fall. Gleich sind die Bits, wenn keines zutrifft, entsprechend einem NOR beider Ergebnisse.

Danach werden die Stellen gewichtet. A ist größer, wenn Bit 3 das sagt, oder wenn Bit 3 gleich ist und Bit 2 es sagt, oder wenn Bits 3 und 2 gleich sind und Bit 1 es sagt, und so weiter. Vier AND-Terme gehen in ein OR, wie bei den Lookahead-Überträgen. 1001 und 0101 unterscheiden sich zuerst in Bit 3 mit der 1 bei A. Die LED A > B leuchtet nach 4 Gatterlaufzeiten; der ungünstigste Fall braucht 5. Die Platine hat 29 Gatter. Der TI SN74LS85 erledigt dasselbe in einem Gehäuse und besitzt zusätzliche Eingänge für den Vergleich längerer Zahlen mit mehreren Chips.

Einen Eingang wählen und eine Ziffer zeichnen

Zwei weitere Schaltungen sammeln ebenfalls AND-Ausgänge in einem OR.

Ein Multiplexer wählt aus. Die 4-zu-1-Platine hat vier Dateneingänge D0 bis D3 und zwei Auswahlbits. Jeder Dateneingang führt in ein AND mit 3 Eingängen, das auch die Auswahlbits oder ihre Umkehrungen erhält. Bei jeder Einstellung lässt genau ein AND Daten durch. Das OR reicht dieses Bit an Y weiter. Sieben Gatter, drei Gatterlaufzeiten. Vom Registersatz eines Prozessors bis zur Quellenwahl eines Fernsehers gibt es Multiplexer überall dort, wo eine Leitung eines von mehreren Signalen führen soll.

Ein Decoder zeichnet. Eine 7-Segment-Anzeige hat sieben balkenförmige LEDs a bis g. Jede Ziffer beleuchtet eine andere Gruppe: 1 die Segmente b und c, 8 alle sieben. Für jedes Segment lassen sich seine Ziffern auflisten und zu einer Produktsumme vereinfachen, also AND-Terme mit einem OR. Der Decoder der Platine wurde so entwickelt: 4 Inverter, 28 gemeinsam genutzte AND-Terme und 7 OR, insgesamt 39 Gatter und drei Laufzeiten vom Schalter zum Segment. Er zeichnet neben 0 bis 9 auch die Hexadezimalziffern A bis F. Der TI SN74LS47 ist die Katalogversion für 0 bis 9.

Schaltungen mit Gedächtnis

Bisher vergisst jede Schaltung. Die Schalter ändern sich, der Ausgang folgt. Nichts hängt von früheren Zuständen ab. Speicher braucht eine Schleife.

Das SR-Latch besteht aus zwei NOR-Gattern, deren Ausgang jeweils zum anderen führt. Bei S = 0 und R = 0 hält die Schleife ihren bisherigen Zustand Q = 1 oder Q = 0, solange Strom anliegt. Eine 1 an S erzwingt Q = 1, eine 1 an R erzwingt Q = 0. Nach dem Setzen kann S wieder aus sein, Q bleibt 1. Acht Transistoren speichern so ein Bit.

Das Latch hat eine verbotene Eingabe. Bei S = 1 und R = 1 sind beide Ausgänge 0. Werden beide gleichzeitig freigegeben, beginnen die Gatter ein Wettrennen. Im Modell mit exakt gleichen Laufzeiten wird die Schleife nie stabil: Die Ausgänge wechseln gemeinsam bei jeder Gatterlaufzeit. Das Feld meldet dies. Ein reales Latch ist nie vollkommen symmetrisch. Eine Seite gewinnt, doch welche und nach welcher Zeit, lässt sich nicht vorhersagen. Das heißt Metastabilität. Digitale Schaltungen werden so entworfen, dass sie im normalen Betrieb vermieden wird.

Ein D-Flipflop vermeidet das Problem, indem es Daten nur in einem Augenblick übernimmt. Die Platine nutzt die Sechs-NAND-Schaltung des Chips 7474. Bei niedrigem wie hohem Takt kann D beliebig wechseln, ohne Q zu ändern. Nur beim Anstieg von CLK von 0 auf 1 übernimmt Q den Wert von D und hält ihn bis zur nächsten steigenden Flanke. In 49.152 zufälligen Schritten von D und CLK befolgte Q diese Regel jedes Mal.

Taktimpulse zählen

Vier Flipflops stehen nebeneinander. Eine kleine Schaltung addiert zur aktuellen Zahl eins und führt das Ergebnis zurück an ihre D-Eingänge. Jeder Taktimpuls lädt die nächste Zahl. Der 4-Bit-Zähler braucht dafür 30 Gatter: 24 NAND in den vier Flipflops und sechs für den Addierer. Bit 0 wechselt immer, Bit 1 bei Bit 0 gleich 1, Bit 2 bei Bits 1 und 0 gleich 1 und Bit 3, wenn alle drei darunter 1 sind.

Ein „Taktimpuls“ macht die Reihenfolge sichtbar. Die Flanke erreicht alle vier Flipflops gleichzeitig. Ihre Ausgänge ändern sich zwei Gatterlaufzeiten später. Danach bereiten die Plus-eins-Gatter die nächste Zahl lange vor dem nächsten Impuls vor. Weil alle Bits an derselben Flanke wechseln, heißt das synchroner Zähler, wie beim TI SN74LS161A. Nach 1111 folgt wieder 0000. Über 40 Impulse zählte er fehlerfrei von 0 bis 15 und erneut von vorn.

Eine ALU aus denselben Bauteilen

Das Rechenwerk eines Prozessors, die arithmetisch-logische Einheit, führt die eigentlichen Berechnungen aus. Die 4-Bit-ALU zeigt das Prinzip mit 59 Gattern. Für jedes Bit berechnet sie parallel A + B, A − B, A AND B und A OR B. Zwei Operationsbits wählen über dieselbe AND-OR-Auswahl wie beim Multiplexer, welches Ergebnis die Ausgänge erreicht. 00 addiert, 01 subtrahiert mit der XOR-Reihe des Addierers/Subtrahierers, 10 ist AND und 11 OR.

Alle vier Ergebnisse werden ständig berechnet. Die Operationsbits wählen nur das sichtbare aus. So arbeiten auch echte ALUs. Deshalb ist ihr längster Pfad, hier 13 Gatterlaufzeiten, länger als der des Addierers allein. Bei 12 AND 10 haben 1100 und 1010 nur Bit 3 gemeinsam. Das Ergebnis ist 1000, also 8.

Wie lang ist eine Gatterlaufzeit?

Das Modell zählt Laufzeiten; reale Bauteile messen sie in Nanosekunden. Texas Instruments nennt für seine SN74HC00-NAND-Gatter bei 4,5 V typisch 9 ns, für ältere SN74LS00 9 bis 10 ns und für SN74AC00 bei 5 V etwa 5 ns. Ein Relais ist eine Million Mal langsamer: Laut Datenblatt braucht das Omron G5V-1 bis zu 5 ms zum Anziehen.

Multipliziert mit dem längsten Pfad ergibt das die Einschwingzeit. Ein 4-Bit-Ripple-Carry-Addierer braucht 9 Laufzeiten, mit Gattern ähnlich dem 74HC00 also etwa 81 ns. Das reicht für zwölf Millionen Additionen pro Sekunde. Mit Relais wären es 45 ms. Das Labor unter den Bedienelementen berechnet den Wert für die gerade gezeigte Schaltung. Ein moderner Prozessor addiert 64-Bit-Zahlen milliardenmal pro Sekunde, weil seine Gatter tausendfach schneller sind und seine Addierer Lookahead nutzen, nicht wegen einer anderen Logik.

Jede Schaltung selbst prüfen

Jede Schaltung wurde bei allen möglichen Eingängen mit ihrer Wahrheitstafel verglichen. Der 4-Bit-Addierer lieferte für alle 512 Kombinationen A + B + C0. Nach jeder der 262.144 möglichen Eingangsänderungen wurde das Ergebnis innerhalb von 9 Gatterlaufzeiten richtig. Der 8-Bit-Addierer wurde mit allen 131.072 Summen und 400.000 zufälligen Änderungen geprüft. Der Lookahead-Addierer wurde innerhalb von 4 Laufzeiten stabil, der Addierer/Subtrahierer innerhalb von 11, der Komparator innerhalb von 5, Multiplexer und Decoder innerhalb von 3. Die ALU blieb bei allen 1.048.576 Änderungen innerhalb von 13. Die Speicherschaltungen durchliefen Folgen: Setzen, Halten und Rücksetzen beim Latch, zufällige Takt- und Datenwerte beim Flipflop und 40 Impulse beim Zähler.

Einige Beispiele lassen sich auf der Platine nachvollziehen:

• 15 + 1 am Ripple-Addierer: Alle vier Überträge laufen durch, nach 8 Laufzeiten zeigen die LEDs 10000.
• 15 + 1 am Lookahead-Addierer: dasselbe Ergebnis nach 4 Laufzeiten.
• 5 + 2: Kein Übertrag, das Ergebnis 0111 (7) steht nach 2 Laufzeiten bereit.
• 5 − 7 am Addierer/Subtrahierer: 1110, also −2.

Unterschiede zum realen Chip

• Jedes Gatter hat dieselbe Laufzeit. In realer Logik ist XOR langsamer als NAND. Viele angesteuerte Eingänge verzögern ein Gatter stärker als ein einzelner. Temperatur und Versorgungsspannung verändern die Zeiten ebenfalls.
• Jeder Draht braucht unabhängig von seiner Länge 0,85 einer Gatterlaufzeit. Auf einer echten Platine sind kurze Leiterbahnen praktisch verzögerungsfrei; in einem Chip können lange Leitungen langsamer als Gatter sein.
• Signale sind exakt 0 oder 1. Reale Spannungen steigen und fallen über eine kurze Zeit. Rauschen, Wärme und Fan-out-Grenzen fehlen hier.
• Ein Gatter pro Chip. Echte Logikchips enthalten vier NAND oder sechs Inverter pro Gehäuse. Sie brauchen Versorgungsanschlüsse, Abblockkondensatoren und Pull-up-Widerstände, die diese Platine auslässt.
• Der Transistor auf dem Versuchstisch ist ein einzelner bipolarer Schalter. Die Transistorzahlen auf den Chips beziehen sich dagegen auf CMOS.

Von Booles Algebra zu Relaisaddierern

1854 veröffentlichte George Boole The Laws of Thought. Darin werden logische Aussagen durch Operationen ähnlich der Multiplikation und Addition verknüpft. Die Symbole 1 und 0 spielen eine besondere Rolle. Das Buch handelte vom Schlussfolgern, nicht von Maschinen.

Die Verbindung zu Schaltungen entstand 1937. Claude Shannon, Masterstudent am MIT, schrieb A Symbolic Analysis of Relay and Switching Circuits. Er zeigte, dass Schalter in Reihe und parallel denselben Regeln wie Booles Algebra folgen. Schaltungen konnten deshalb algebraisch statt durch Versuch und Irrtum entworfen und vereinfacht werden. Das letzte Kapitel enthielt mehrere Beispiele, darunter einen Binäraddierer. Ein Aufsatz aus der Arbeit erschien 1938 in den Transactions of the American Institute of Electrical Engineers und gewann den Alfred Noble Prize.

Im selben Jahr baute George Stibitz von Bell Labs einen Demonstrationsaddierer aus Relais. Nach dem Küchentisch, an dem er entstand, nannte er ihn Model K. Zehn Jahre später, im Dezember 1947, bauten John Bardeen und Walter Brattain bei Bell Labs in der Gruppe von William Shockley den ersten funktionierenden Transistor. Die drei teilten sich 1956 den Nobelpreis für Physik für ihre Halbleiterforschung und die Entdeckung des Transistoreffekts.

Von Relais zu Milliarden Transistoren

Die ersten Großrechner nutzten verfügbare Schalter. Konrad Zuses Z3 von 1941 hatte 2300 Relais. Der 1944 fertige Harvard Mark 1 nutzte 3500, synchronisiert durch eine fünfzig Fuß lange Nockenwelle. Colossus arbeitete ab Anfang 1944 in Bletchley Park mit 2500 Elektronenröhren. Der im Februar 1946 an der University of Pennsylvania vorgestellte ENIAC brauchte 18.000 Röhren und füllte einen Raum von 30 mal 50 Fuß, etwa 9 mal 15 Metern. Der TX-0 des MIT von 1956 war der erste frei programmierbare Universalrechner mit Transistoren. Jeder saß in einer steckbaren „Flasche“, damit er wie eine Röhre ausgetauscht werden konnte.

Dann wanderten die Gatter auf Silizium. Fairchild kündigte 1961 eine der ersten planaren integrierten Schaltungen an, ein Flipflop mit vier Transistoren und fünf Widerständen. Die TTL-Logikfamilie 7400 von Texas Instruments wurde ab 1966 in günstigen Kunststoffgehäusen verkauft und erreichte bald mehr als die Hälfte des Logikmarkts. Viele Bauteile, etwa der vierfache NAND SN7400, sind noch erhältlich. Der Apollo Guidance Computer flog erstmals 1968 auf Apollo 7. Er bestand überwiegend aus einem Chiptyp mit zwei NOR-Gattern mit je 3 Eingängen, mehreren tausend pro Computer.

Gordon Moore sagte 1965 eine jährliche Verdopplung der Bauteilzahl auf einem Chip voraus und änderte dies später auf alle zwei Jahre. Der Intel 4004 von 1971 vereinte einen vollständigen 4-Bit-Prozessor mit 2300 Transistoren auf einem Chip. Die Zeitleiste des Computer History Museum nennt 2250. Apples M1 von 2020 hat 16 Milliarden, etwa sieben Millionen Mal so viele. Die Blackwell-GPUs von NVIDIA aus dem Jahr 2024 enthalten 208 Milliarden. Auch darin übernehmen Addierer, Multiplexer und Flipflops wie auf dieser Platine die Rechenarbeit.