Lernen › Thema 7

Binäraddierer: Halbaddierer, Volladdierer und Ripple-Carry-Addierer

8 Min. Lesezeit · bitGateLab-Team

Addieren ist die wichtigste Operation eines Computers: Damit wird subtrahiert, multipliziert, es werden Speicheradressen berechnet und Ereignisse gezählt. Hier baust du einen Addierer von Grund auf: zuerst den Halbaddierer für ein Bit, dann den Volladdierer, der einen Übertrag annimmt, danach den mehrstelligen Addierer in Kaskade und zum Schluss siehst du, wie dieselbe Schaltung mit dem Zweierkomplement subtrahiert.

Binär von Hand addieren

Für die Addition zweier Bits gibt es vier Regeln: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 und 1 + 1 = 10₂, also 0 mit einem Übertrag von 1 in die nächste Spalte. Kommt zusätzlich ein Übertrag an, gilt 1 + 1 + 1 = 11₂: Ergebnis 1 und Übertrag 1. Wie im Dezimalsystem addiert man Spalte für Spalte von rechts nach links und gibt den Übertrag nach links weiter.

Halbaddierer

Der Halbaddierer addiert zwei Bits, A und B, und liefert zwei Ausgänge: die Summe S und den Übertrag C.

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Die Spalte S ist die Tabelle eines XOR und die Spalte C die eines AND. Daher gilt:

S = A ⊕ B C = AB

Halbaddierer: Das XOR liefert die Summe S und das AND den Übertrag C. Die Punkte markieren, wo sich jeder Eingang zu den beiden Gattern verzweigt.

Er heißt „halb“, weil er keinen Eingang für den Übertrag aus einer vorherigen Spalte hat und deshalb nur für das niederwertigste Bit taugt.

Volladdierer

Der Volladdierer addiert drei Bits: A, B und den Übertragseingang C_in. Er liefert die Summe S und den Übertragsausgang C_out. Beachte, dass das Paar (C_out, S) binär die Anzahl der Einsen an den Eingängen angibt.

A	B	C_in	C_out	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

S ist 1, wenn eine ungerade Anzahl von Einsen anliegt: S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in. C_out ist 1, wenn zwei oder mehr Einsen anliegen: C_out = Σm(3, 5, 6, 7), vereinfacht ist das die Mehrheitsfunktion:

C_out = AB + AC_in + BC_in

Wenn du im Karnaugh-Diagramm von S Blöcke bilden willst, wirst du sehen, dass keine 1 einen Nachbarn mit 1 hat: Das ist das für das XOR typische Schachbrettmuster, das sich als Summe von Produkten nicht vereinfachen lässt.

Volladdierer aus zwei Halbaddierern

Praktisch lässt er sich aufbauen, indem man zwei Halbaddierer und ein OR hintereinanderschaltet:

Erster Halbaddierer: P = A ⊕ B und G = AB.
Zweiter Halbaddierer, mit P und C_in: S = P ⊕ C_in und ein Teilübertrag P·C_in.
C_out = G + P·C_in = AB + (A ⊕ B)C_in.

Dieser Ausdruck ist gleichwertig mit der Mehrheitsfunktion: Sind A und B gleich 1, liefert AB bereits den Übertrag; ist genau einer von beiden 1, hängt der Übertrag von C_in ab. G nennt man das Generate-Signal (Übertrag erzeugen) und P das Propagate-Signal (Übertrag weiterleiten).

Ripple-Carry-Addierer

Um Zahlen mit n Bits zu addieren, schaltet man n Volladdierer in eine Reihe: Der Ausgang C_out jeder Stufe wird zum C_in der nächsten. Der C_in der ersten Stufe wird auf 0 gelegt, und der C_out der letzten ist der Endübertrag. Diese Struktur heißt Addierer mit durchlaufendem Übertrag oder Ripple-Carry-Addierer, weil sich der Übertrag wie eine Welle von Stufe zu Stufe „fortpflanzt“. In der 74HC-Familie gibt es einen IC, der vier so verschaltete Volladdierer enthält (den 74HC283).

Beispiel 1: 1011 + 0110 mit einem 4-Bit-Addierer. Dezimal ist das 11 + 6.

Stufe	A_i	B_i	C_in	S_i	C_out
0	1	0	0	1	0
1	1	1	0	0	1
2	0	1	1	0	1
3	1	0	1	0	1

Summe: S₃S₂S₁S₀ = 0001 mit Endübertrag 1, also 10001₂ = 17. Richtig: 11 + 6 = 17, das passt nicht in 4 Bits, deshalb erscheint der Endübertrag.

Der Preis ist die Zeit. Stufe 3 kann ihr endgültiges Ergebnis erst liefern, wenn der Übertrag von Stufe 2 eingetroffen ist, die ihrerseits auf den von Stufe 1 wartet. Braucht jede Stufe zwei Gatterebenen, um ihren Übertrag zu erzeugen, dann benötigt ein Addierer mit n Bits im ungünstigsten Fall etwa 2n Gatterlaufzeiten. Für 64 Bits ist das zu langsam, deshalb verwenden Prozessoren Addierer mit Carry-Lookahead, die die Überträge aus den Signalen G und P parallel berechnen. Im Zeitdiagramm des Simulators kannst du sehen, wie sich die Ausgänge schrittweise ändern, bis sie stabil sind.

Subtrahieren mit demselben Addierer

Wie im Thema Zahlensysteme erklärt, ist im Zweierkomplement das Negative von B gleich B + 1. Also gilt:

A − B = A + B + 1

Dazu genügt es, an jedes Bit von B ein XOR zu setzen, dessen anderer Eingang an einer Steuerleitung M liegt, und M auch mit dem C_in der ersten Stufe zu verbinden. Mit M = 0 lassen die XOR-Gatter B durch und C_in = 0: Die Schaltung addiert. Mit M = 1 invertieren die XOR-Gatter B und C_in = 1 steuert das „+1“ bei: Die Schaltung subtrahiert.

Beispiel 2: Subtraktionen mit 4 Bits.

9 − 5: A = 1001, B = 0101, B = 1010. 1001 + 1010 + 1 = 1 0100. Der Endübertrag wird verworfen: 0100 = 4.
5 − 9: A = 0101, B = 1001, B = 0110. 0101 + 0110 + 1 = 0 1100. Kein Endübertrag. 1100 bedeutet im Zweierkomplement −8 + 4 = −4.

Beim Subtrahieren vorzeichenloser Zahlen zeigt der Endübertrag an, ob geborgt werden musste: 1 bedeutet A ≥ B und 0 bedeutet A < B.

Bei vorzeichenbehafteten Zahlen erkennt man den Überlauf mit einem einzigen XOR: V = C₃ ⊕ C₄, wobei C₃ der Übertrag ist, der in die letzte Stufe hineingeht, und C₄ der, der aus ihr herauskommt. Sind sie verschieden, passt das Ergebnis nicht in 4 Bits mit Vorzeichen.

Häufige Fehler

In den mittleren Stufen einen Halbaddierer zu verwenden. Jede Stufe, die einen Übertrag empfängt, braucht einen Volladdierer.
Den C_in der ersten Stufe offen zu lassen. Er muss zum Addieren auf 0 liegen oder in einem Addierer-Subtrahierer an M.
Den Endübertrag mit dem Überlauf zu verwechseln. Bei vorzeichenbehafteten Zahlen wird der Endübertrag verworfen; den Überlauf erkennt man mit C₃ ⊕ C₄.
Beim Subtrahieren das „+1“ zu vergessen und nur die Inverter anzuschließen: Das Ergebnis ist dann um eins zu klein.
S = A + B + C_in mit OR zu schreiben. Die Summe eines Bits ist ein XOR, kein OR.

Probiere es im Simulator aus

Einen Addierer im Editor aufzubauen ist die beste Brücke zwischen Gattern und Arithmetik. Beginne mit einem Bit und arbeite dich bis zu vier Bits hoch.

Platziere zwei Eingänge, ein XOR und ein AND und verbinde sie wie in der Zeichnung des Halbaddierers. Erzeuge seine Wahrheitstabelle.
Baue einen Volladdierer aus zwei Halbaddierern und einem OR auf und prüfe seine 8 Zeilen anhand der Tabelle in diesem Artikel.
Kopiere den Volladdierer viermal und verkette die Überträge. Lege den ersten C_in auf 0.
Stelle die Eingänge auf 1011 und 0110 und prüfe, ob der Ausgang 0001 mit Endübertrag 1 ist.
Öffne das Zeitdiagramm, ändere einen Eingang so, dass der Übertrag alle vier Stufen durchlaufen muss (zum Beispiel 1111 + 0001), und beobachte, wie sich die Ausgänge stabilisieren.

Übungen

Berechne S und C_out eines Volladdierers mit A = 1, B = 0, C_in = 1.
Lösung
Es liegen zwei Einsen an: S = 0 und C_out = 1 (1 + 0 + 1 = 10₂).
Addiere 0111 + 0101 mit einem 4-Bit-Addierer und gib die Überträge jeder Stufe an.
Lösung
Stufe 0: 1 + 1 = 0, Übertrag 1. Stufe 1: 1 + 0 + 1 = 0, Übertrag 1. Stufe 2: 1 + 1 + 1 = 1, Übertrag 1. Stufe 3: 0 + 0 + 1 = 1, Übertrag 0. Ergebnis 1100 = 12 (7 + 5).
Berechne mit einem 4-Bit-Addierer-Subtrahierer 6 − 3 und gib an, welchen Wert M hat.
Lösung
M = 1. 0110 + 1100 + 1 = 1 0011. Der Übertrag wird verworfen: 0011 = 3.
Gibt es bei 0111 + 0101 einen Überlauf, wenn man die Werte als vorzeichenbehaftete 4-Bit-Zahlen deutet?
Lösung
Ja. 7 + 5 = 12 passt nicht in den Wertebereich von −8 bis +7. Das Ergebnis 1100 würde als −4 gelesen. Die Überträge sind C₃ = 1 und C₄ = 0, und V = 1 ⊕ 0 = 1.