Rechnen
Halbaddierer, Volladdierer, Ripple-Carry: so addiert ein Computer
Computer addieren so, wie du es in der Schule gelernt hast: Spalte für Spalte, mit Übertrag in die nächste. Der einzige Unterschied: In jeder Spalte steht nur 0 oder 1. Dadurch werden die Regeln so kurz, dass man sie aus Logikgattern bauen kann.
Zählen im Binärsystem
Im Dezimalsystem ist jede Stelle zehnmal so viel wert wie die rechts daneben: Einer, Zehner, Hunderter. Im Binärsystem ist jede Stelle doppelt so viel wert: 1, 2, 4, 8, 16 und so weiter. Die Zahl 13 ist 8 + 4 + 1, also 1101. Acht Bits ergeben ein Byte, und das fasst jede ganze Zahl von 0 bis 255.
Schriftlich addieren
Für die binäre Addition musst du dir nur vier Fakten merken: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 und 1 + 1 = 10, also „schreibe 0, Übertrag 1“. Kommt ein Übertrag in eine Spalte, in der schon zwei Einsen stehen, ergibt das 1 + 1 + 1 = 11: schreibe 1, Übertrag 1. Das ist schon der ganze Algorithmus. Probier es unten aus, indem du auf die Bits von A und B klickst.
Der Halbaddierer: eine Spalte, zwei Bits
Die einfachste Addierschaltung kümmert sich um eine Spalte ohne eingehenden Übertrag. Sie nimmt zwei Bits und liefert eine zweistellige Antwort: ein Summenbit S für diese Spalte und ein Übertragsbit Ü (englisch Carry) für die nächste.
| A | B | Ü | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Schau dir die beiden Ausgangsspalten einzeln an. Jede ist eine Wahrheitstabelle, die du vielleicht schon kennst, etwa von der Seite über Logikgatter. Zu erkennen, welche Gatter das sind, ist die halbe Miete beim Bau eines Halbaddierers. Die andere Hälfte ist ein Rätsel im Spiel – deshalb hören wir hier auf.
Der Volladdierer: eine Spalte, drei Bits
Jede Spalte außer der rechten kann einen Übertrag bekommen. Eine echte Spalte addiert also drei Bits: A, B und den eingehenden Übertrag Üein. Das Ergebnis ist höchstens 3 (binär 11), zwei Ausgangsbits reichen also weiterhin.
| A | B | Üein | Üaus | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Zwei Muster lohnen einen zweiten Blick. S ist 1, wenn eine ungerade Anzahl der Eingänge 1 ist. Üaus ist 1, wenn mindestens zwei davon 1 sind – eine Mehrheitsentscheidung. Der Volladdierer ist eine kleine, sehr gut erforschte Schaltung, und die kleinste reine NAND-Version ist ein klassisches Optimierungsziel.
Ripple-Carry: die Spalten verketten
Stell acht Volladdierer nebeneinander, verbinde jeweils den ausgehenden Übertrag mit dem eingehenden des nächsten, und du hast einen 8-Bit-Addierer. Das ist ein Ripple-Carry-Addierer (auch Carry-Ripple-Addierer) – genau das schriftliche Verfahren, nur in Hardware.
Einfach und klein – aber mit einem Haken. Die oberste Spalte kann sich erst festlegen, wenn der Übertrag aus der Spalte darunter angekommen ist, und die wartet wiederum auf ihre Nachbarin, und so weiter. Im schlimmsten Fall, etwa bei 1 plus 11111111, muss ein Übertrag nacheinander durch jede Spalte laufen. Die Verzögerung wächst mit der Bitbreite: Ein 64-Bit-Ripple-Addierer ist achtmal so langsam wie ein 8-Bit-Addierer.
Schnellere Addierer
Weil fast alles, was eine CPU tut, irgendwo addiert (Adressen, Schleifenzähler, Vergleiche), haben Entwickler viel Mühe in diese Übertragskette gesteckt. Carry-Lookahead-, Carry-Select- und Präfix-Addierer (Kogge–Stone, Brent–Kung und andere) investieren mehr Gatter, um viele Überträge gleichzeitig zu berechnen. So wächst die Verzögerung nur noch ungefähr mit dem Logarithmus der Breite statt mit der Breite selbst. Der klassische Tausch Fläche gegen Tempo – und eine der optionalen Herausforderungen im Spiel.
Überlauf und Übertrag
Acht Bits fassen 0 bis 255. Addierst du 200 und 100, braucht das richtige Ergebnis 300 neun Bits. Ein 8-Bit-Addierer behält die unteren acht Bits (300 − 256 = 44) und setzt seinen ausgehenden Übertrag. CPUs merken sich den im Carry-Flag, damit Programme Additionen über mehrere Wörter verketten können. Bei vorzeichenbehafteten Zahlen ist das Warnsignal ein anderes, denn dort besteht das Problem darin, vom größten positiven Wert in den negativsten zu kippen. Das Zweierkomplement erklärt, warum derselbe Addierer auch mit negativen Zahlen funktioniert – und warum CPUs deshalb kein eigenes Subtrahierwerk für vorzeichenbehaftete Zahlen brauchen.