Arithmetik-Schaltungen: Addierer und Multiplizierer

Der einfachste arithmetische Baustein ist der Halbaddierer, der zwei einzelne Bits addiert und dabei eine Summe (XOR der Eingänge) und einen Übertrag (AND der Eingänge) liefert. Da beim Verketten mehrerer Bitstellen jedoch auch ein Übertrag aus der vorherigen Stelle berücksichtigt werden muss, verwendet man in der Praxis den Volladdierer, der drei Eingänge (die beiden zu addierenden Bits A und B sowie den Übertrag C_in aus der vorherigen Stelle) zu einer Summe und einem Übertrag C_out verrechnet. Ein Volladdierer lässt sich aus zwei Halbaddierern und einem zusätzlichen OR-Gatter aufbauen und benötigt in einer typischen CMOS-Standardzelle etwa 20 bis 28 Transistoren.

Die Boolesche Gleichung C_out = (A AND B) OR (C_in AND (A XOR B)) lässt sich anschaulich als Mehrheitsentscheid lesen: C_out wird genau dann 1, wenn mindestens zwei der drei Eingänge (A, B, C_in) auf 1 liegen – ganz unabhängig davon, welche zwei das sind. Bei A=1, B=1, C_in=0 etwa liefert bereits A AND B den Übertrag; bei A=1, B=0, C_in=1 sind A und B unterschiedlich (A XOR B = 1), und C_in AND (A XOR B) liefert ihn stattdessen. Die Summe dagegen ist 1, wenn eine ungerade Anzahl der drei Eingänge 1 ist (1 oder 3 von 3) – exakt das Verhalten einer dreifachen XOR-Verknüpfung.

Reiht man mehrere Volladdierer aneinander, wobei der Übertragsausgang jeder Stelle zum Übertragseingang der nächsthöheren Stelle wird, entsteht der einfachste Mehrbit-Addierer: der Carry-Ripple-Addierer.

Beim Carry-Ripple-Addierer muss der Übertrag nacheinander durch alle Bitstellen "durchsickern" (daher der Name), bevor das Endergebnis feststeht. Ein konkretes Beispiel verdeutlicht das: Bei der 4-Bit-Addition 0111 + 0001 entsteht an Stelle 0 zunächst C_out,0=1 (da A₀=B₀=1); dieser Übertrag muss an Stelle 1 ankommen, bevor dort Sum₁ und C_out,1 feststehen, dieser wiederum an Stelle 2, und so weiter – erst wenn der Übertrag alle vier Stufen durchlaufen hat, liegt das korrekte Endergebnis 1000 vollständig an. Bei einem 32-Bit-Addierer durchläuft das Übertragssignal im ungünstigsten Fall alle 32 Volladdiererstufen nacheinander, wodurch die Verzögerung linear mit der Bitbreite wächst.

Der Carry-Lookahead-Addierer löst dieses Problem, indem er für jede Bitstelle i im Voraus zwei Hilfssignale berechnet: Generate G_i = A_i AND B_i (an dieser Stelle entsteht immer ein Übertrag, unabhängig vom Eingangsübertrag) und Propagate P_i = A_i XOR B_i (ein eingehender Übertrag würde durchgereicht). Daraus lässt sich jeder Übertrag direkt als Summe von Produkttermen ausdrücken, etwa C₁ = G₀ + P₀C₀, C₂ = G₁ + P₁G₀ + P₁P₀C₀, C₃ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀ – jeder Übertrag hängt also nur noch von den Eingangsbits selbst ab, nicht mehr vom sequenziell berechneten Vorgänger-Übertrag, und lässt sich mit einer festen, kleinen Gatterlaufzeit parallel für alle Stellen berechnen. Da die Anzahl der UND-Eingänge (Fan-in) mit jeder weiteren Bitstelle wächst, werden reale Lookahead-Addierer meist in Blöcken von 4 Bit aufgebaut und die Blocküberträge auf einer zweiten Lookahead-Ebene kombiniert, um den Fan-in begrenzt zu halten – ein Kompromiss, der die logarithmische statt konstante Verzögerung erklärt, aber auf Kosten eines deutlich höheren Flächen- und Verdrahtungsaufwands, wie er in vielen Bereichen des digitalen Schaltungsentwurfs auftritt.