Deutsch
Menü

Ripple-Carry- vs. Carry-Lookahead- vs. Carry-Save-Addierer: Verzögerung, Fläche und Einsatz

Alle drei sind aus Volladdierern aufgebaute Addierer, behandeln den Übertrag aber unterschiedlich. Ein Ripple-Carry-Addierer schaltet Volladdierer in Reihe, sodass der Übertrag nacheinander vom niedrigsten zum höchsten Bit läuft; die Verzögerung wächst proportional zur Bitbreite n (O(n)). Ein Carry-Lookahead-Addierer berechnet alle Überträge parallel aus den Generate- und Propagate-Signalen jeder Stelle; mit hierarchischer Lookahead-Logik wächst die Verzögerung nur mit O(log n). Ein Carry-Save-Addierer fasst drei Zahlen ohne Weitergabe des Übertrags zu zwei Zahlen zusammen, einem Summenwort und einem Übertragswort; seine Verzögerung beträgt unabhängig von der Bitbreite eine Volladdiererstufe. Multiplizierer reduzieren die Teilprodukte mit Bäumen aus Carry-Save-Addierern (etwa Wallace-Trees) und addieren die beiden verbleibenden Zahlen mit einem schnellen Addierer.

MerkmalRipple-Carry-AddiererCarry-Lookahead-AddiererCarry-Save-Addierer
Ein- und AusgängeAddiert zwei Zahlen (und einen Übertragseingang) zu einer Summe und einem ÜbertragsausgangAddiert zwei Zahlen (und einen Übertragseingang) zu einer Summe und einem ÜbertragsausgangFasst drei Zahlen zu zwei Zahlen zusammen, dem Summenwort S und dem Übertragswort Cy (A + B + C = S + Cy)
Behandlung des ÜbertragsJeder Volladdierer wartet auf den Übertrag von unten und gibt ihn nacheinander nach oben weiterMit Generate g = a·b und Propagate p = a ⊕ b wird c(i+1) = g(i) + p(i)·c(i) aufgelöst, um die Überträge parallel zu berechnenÜberträge gehen nicht an die Nachbarstelle, sondern als um eine Stelle nach links verschobenes Wort an die nächste Stufe
Wachstum der VerzögerungO(n); im ungünstigsten Fall läuft der Übertrag vom niedrigsten bis zum höchsten BitO(log n) (mit hierarchischer Lookahead-Logik)O(1); eine Volladdiererstufe, unabhängig von der Bitbreite
Richtwerte bei 64 BitDer Übertrag durchläuft 64 VolladdiererDrei Ebenen aus 4-Bit-Blöcken; bei einem Parallel-Präfix-Addierer nach Kogge-Stone braucht die Übertragsberechnung log₂64 = 6 StufenEine Stufe entspricht der Verzögerung eines Volladdierers; ein Wallace-Tree, der 64 Teilprodukte auf zwei reduziert, braucht 10 Stufen
SchaltungsaufwandAm kleinsten: n Volladdierer für n BitGrößer um die Lookahead-Logik; schnellere Varianten brauchen mehr Gatter und Verdrahtung (bei Kogge-Stone etwa n log n)Eine Stufe besteht aus n Volladdierern ohne Übertragskette; ein ganzer Multipliziererbaum wächst mit der Zahl der Teilproduktbits (etwa n²)
Form des ErgebnissesGewöhnliche BinärzahlGewöhnliche BinärzahlRedundante Darstellung, aufgeteilt in Summen- und Übertragswort; für einen einzelnen Wert ist am Ende ein gewöhnlicher Addierer nötig
Typischer EinsatzKleine oder stromsparende Schaltungen, bei denen Geschwindigkeit unkritisch ist; in FPGAs oft mit dedizierter Übertragslogik (Carry Chain) aufgebautALUs von CPUs, Adressberechnung, Gleitkommaeinheiten, die abschließende Addition in MultiplizierernReduktion der Teilprodukte in Multiplizierern (Wallace- und Dadda-Trees), Akkumulation bei Multiplizier-Akkumulier-Operationen, Addition vieler Zahlen
Verwandte VerfahrenCarry-Skip- und Carry-Select-Addierer (bei Geschwindigkeit und Fläche dazwischen)Parallel-Präfix-Addierer (Kogge-Stone, Brent-Kung u. a.)4:2-Kompressoren, Kombination mit dem Booth-Algorithmus zur Verringerung der Teilprodukte

Die Zahlenwerte sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welche Variante?

Ripple-Carry-Addierer
Für geringe Bitbreiten oder wenn Fläche und Leistungsaufnahme wichtiger sind als Geschwindigkeit. Der einfache, regelmäßige Aufbau lässt sich auf Bausteinen mit dedizierten schnellen Übertragspfaden wie FPGAs effizient umsetzen.
Carry-Lookahead-Addierer
Wenn eine einzelne Addition zweier Zahlen schnell abgeschlossen sein muss, typischerweise in ALUs von CPUs und in Addierern auf dem kritischen Pfad. Über die Hierarchie und die Wahl der Parallel-Präfix-Struktur wird die Stufenzahl gegen Fläche und Verdrahtung abgewogen.
Carry-Save-Addierer
Beim Addieren von drei oder mehr Zahlen. Er verringert die Anzahl der Zahlen, ohne auf Überträge zu warten, und führt nur am Ende eine Addition mit einem Carry-Lookahead- oder ähnlichen Addierer aus; das lohnt sich in Multiplizierern, die viele Teilprodukte addieren, und in MAC-Einheiten, die wiederholt akkumulieren.

Häufige Fragen

Wie groß ist der Unterschied zwischen O(n) und O(log n) in der Praxis?

Bei 64 Bit durchläuft der Übertrag eines Ripple-Carry-Addierers 64 Volladdierer, während ein Parallel-Präfix-Addierer nach Kogge-Stone die Überträge in log₂64 = 6 Stufen berechnet. Die Verzögerung pro Stufe unterscheidet sich je nach Schaltung, daher ist das kein einfaches Verhältnis, doch der Abstand wächst mit der Bitbreite, und für eine 64-Bit-Addition in einem Prozessor der GHz-Klasse ist ein Ripple-Carry-Addierer zu langsam.

Wie lässt sich der Carry-Save-Addierer mit Zahlen nachprüfen?

Man gibt die 4-Bit-Werte 5 (0101), 6 (0110) und 7 (0111) ein. Das Wort S aus den Summenbits jeder Stelle ist 0100 (4), das Wort Cy aus den Übertragsbits, um eine Stelle nach links verschoben, ist 1110 (14). 4 + 14 = 18, was 5 + 6 + 7 entspricht. Jede Stelle ist ein unabhängiger Volladdierer, daher wartet nichts auf einen Übertrag.

Wie ergibt sich die Stufenzahl eines Wallace-Trees?

In jeder Stufe fassen Carry-Save-Addierer drei Zahlen zu zwei zusammen, die Anzahl sinkt also pro Stufe auf etwa zwei Drittel. Bei h Teilprodukten bleiben nach einer Stufe 2⌊h/3⌋ + (h mod 3); 8 brauchen 4 Stufen, 16 brauchen 6, 32 brauchen 8 und 64 brauchen 10, bis zwei übrig sind. Die Stufenzahl wächst etwa mit dem Logarithmus der Bitbreite, und die Addition der beiden letzten Zahlen mit einem schnellen Addierer vervollständigt das Produkt.

Warum wird die vollständige Carry-Lookahead-Gleichung bei großen Bitbreiten nicht direkt verwendet?

Löst man die Übertragsgleichungen vollständig auf, kommen mit jeder höheren Stelle mehr Terme hinzu, und bald werden Gatter mit sehr vielen Eingängen nötig. Stattdessen bilden Blöcke von etwa 4 Bit ein Gruppen-Generate G und ein Gruppen-Propagate P, und die nächste Ebene verwendet darauf dieselbe Lookahead-Logik. Parallel-Präfix-Addierer verallgemeinern diese Idee.

Verständnis prüfen

Welcher Nachteil des Ripple-Carry-Addierers aus in Reihe geschalteten Volladdierern ist richtig?

  1. ANegative Zahlen können nicht verarbeitet werden
  2. BDa der Übertrag von unten nach oben der Reihe nach weitergegeben wird, wächst die Verzögerung proportional zur Bitzahl
  3. CDie Schaltungsgröße ändert sich auch bei steigender Bitzahl nicht
Antwort und Erläuterung anzeigen

Antwort: B. Da der Übertrag von unten nach oben der Reihe nach weitergegeben wird, wächst die Verzögerung proportional zur Bitzahl

Beim Ripple-Carry-Addierer wartet jeder Volladdierer auf den Übertrag der niedrigeren Stelle, bevor er rechnet; der Übertrag läuft also von der niedrigsten bis zur höchsten Stelle der Reihe nach, und die Verzögerung wächst proportional zur Bitzahl. Bei 64 Bit entspricht das der Verzögerung von 64 Volladdierer-Stufen, was für mit GHz getaktete CPUs zu langsam ist. Wegen der kleinen, einfachen Schaltung wird er dort eingesetzt, wo Geschwindigkeit nicht zählt. Zur Beschleunigung dienen Carry-Lookahead-, Carry-Select- und parallele Präfix-Addierer (z. B. Kogge-Stone).

Warum ist ein Carry-Lookahead-Addierer (Übertragsvorausschau) schnell?

  1. AWeil die Bitzahl der Addition verringert wird
  2. BWeil die Taktfrequenz verdoppelt wird
  3. CWeil die Überträge aller Bits parallel aus den Eingängen berechnet werden, ohne auf die Weitergabe von unten zu warten
Antwort und Erläuterung anzeigen

Antwort: C. Weil die Überträge aller Bits parallel aus den Eingängen berechnet werden, ohne auf die Weitergabe von unten zu warten

Der Carry-Lookahead-Addierer nutzt für jedes Bit Generate G = A·B (erzeugt sicher einen Übertrag) und Propagate P = A⊕B (gibt den Übertrag der niedrigeren Stelle weiter) und berechnet die Überträge aller Stellen parallel aus den Eingängen: C1 = G0 + P0·C0, C2 = G1 + P1·G0 + P1·P0·C0 usw. Die Verzögerung wächst nur noch proportional zum Logarithmus der Bitzahl. Da die Ausdrücke jedoch lang werden, werden Blöcke von etwa 4 Bit hierarchisch kombiniert.

Welche Kombination aus Definition von Generate-Signal g und Propagate-Signal p (a, b sind die Eingänge der Stelle) und der Formel für den Übertrag c(i+1) zur nächsthöheren Stelle gilt für den Carry-Lookahead-Addierer?

  1. Ag = a + b, p = a・b, c(i+1) = p + g・c(i)
  2. Bg = a・b, p = a ⊕ b, c(i+1) = g + p・c(i)
  3. Cg = a ⊕ b, p = a・b, c(i+1) = g・p・c(i)
Antwort und Erläuterung anzeigen

Antwort: B. g = a・b, p = a ⊕ b, c(i+1) = g + p・c(i)

Sind a und b an der Stelle beide 1, entsteht unabhängig vom Übertrag von unten stets ein Übertrag, daher ist das Generate-Signal g = a・b. Ist nur eines von a und b 1, wird der Übertrag von unten unverändert nach oben weitergegeben, daher ist das Propagate-Signal p = a ⊕ b (teils auch OR). Es gilt also c(i+1) = g(i) + p(i)・c(i); entwickelt man dies, lassen sich die Überträge aller Stellen allein aus den g und p der Eingänge und dem niedrigsten Übertrag in einer zweistufigen Logik parallel bestimmen. Mit vertauschten Generate und Propagate lässt sich nicht korrekt rechnen.

  1. Was ist der Hauptgrund, warum in Multiplizierern Carry-Save-Addierer zum Aufsummieren vieler Teilprodukte verwendet werden?
  2. Welche Aussage zum Wallace-Tree in schnellen Multiplizierern ist korrekt?
  3. Welche Kombination von Eingängen eines Volladdierers ist richtig?

Übungsfragen zu Computerarithmetik

Wichtige Begriffe erklärt

Volladdierer
Schaltung, die zwei Bits und den Übertrag der niedrigeren Stelle addiert und Summe sowie Übertrag zur höheren Stelle ausgibt. Ohne Übertragseingang spricht man von einem Halbaddierer. In Reihe geschaltet ergeben sie einen Mehrbit-Addierer.
Carry-Lookahead-Addierer
Addierer, der aus Generate-Signal g = a·b und Propagate-Signal p = a ⊕ b jeder Stelle die Überträge parallel bestimmt, ohne auf die Weitergabe von unten zu warten. Auch bei vielen Bits geringe Verzögerung.
Carry-Save-Addierer
Addierer, der drei Zahlen ohne Übertragsweitergabe zu zwei Zahlen, „Summe“ und „Übertrag“, zusammenfasst. Er besteht nur aus nebeneinander angeordneten Volladdierern mit konstanter Verzögerung und dient in Multiplizierern zum Summieren vieler Teilprodukte.
Wallace-Tree
Struktur in Multiplizierern, die viele Teilprodukte mit einem Baum aus Carry-Save-Addierern parallel reduziert. Die Stufenzahl ist etwa logarithmisch in der Bitbreite, daher wird er in schnellen Multiplizierern eingesetzt. Zum Schluss werden zwei Zahlen mit einem normalen Addierer summiert.
Booth-Algorithmus
Multiplikationsverfahren, das die Bitfolge des Multiplikators z. B. in 2-Bit-Gruppen unterteilt und durch vorzeichenbehaftete Ziffern ersetzt, um die Zahl der Teilprodukte zu verringern. Beim Radix-4-Booth halbiert sich die Zahl der Teilprodukte etwa.
Kritischer Pfad
Pfad mit der größten Verzögerung in einer Schaltung, der die maximale Taktfrequenz bestimmt. In der STA ist er der Pfad mit dem kleinsten Slack; ein Design wird schneller, indem man zuerst seine Verzögerung verringert.

Verwandte Vergleiche