Carry-Lookahead-Addierer: Schneller als Ripple-Carry

Kurzfassung: Carry Lookahead schreibt die serielle Rekurrenz $C_{i+1}=G_i+P_iC_i$ mithilfe von Generate-/Propagate-Signalen pro Bit und Gruppe um. Ein kleiner flacher CLA kann mehrere Überträge unmittelbar aus den Operanden ausdrücken. Hierarchische und Parallel-Prefix-Varianten verringern die Übertragstiefe von linear in Richtung logarithmisch – auf Kosten zusätzlicher Zellen, Fan-out und Verdrahtung.

Ein 4-Bit-Ripple-Carry-Addierer ist unkompliziert: Verketten Sie vier Volladdierer und führen Sie jedes $C_{out}$ zum nächsten $C_{in}$. Seine Übertragsabhängigkeit im ungünstigsten Fall wächst mit der Wortbreite. Ob dieser Pfad das Timing einhält, hängt von Technologie, Taktziel, Zellbibliothek und umgebendem Datenpfad ab; die Breite allein macht einen Entwurf nicht „inakzeptabel“.

Carry-Lookahead-Addierer (CLAs) greifen die serielle Abhängigkeit an, indem sie Übertragsausdrücke aus Zwischensignalen herleiten, die unmittelbar aus den Operanden verfügbar sind.

Warum Ripple-Carry langsam ist

Rufen Sie sich die Volladdierer-Gleichungen in Erinnerung:

$S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

Die Summe $S_i$ hängt von $C_i$ ab. Der Übertrag $C_{i+1}$ hängt ebenfalls von $C_i$ ab. Die Abhängigkeitskette lautet also $C_0 \to C_1 \to C_2 \to \dots \to C_n$. Dauert eine einzelne Übertragsstufe $t_c$, beträgt die gesamte Additionszeit im ungünstigsten Fall ungefähr:

$T_{ripple} \approx n \cdot t_c + t_{sum}$

Die Abhängigkeit erster Ordnung ist linear zur Wortbreite. Absolute Nanosekunden erfordern eine spezifizierte Implementierung, daher sind Gatterlaufzeiten hier nur zum Vergleichen der Topologie nützlich. Das ist die Art von Ausbreitungsverzögerungsgrenze, die schnellere Übertragsnetze motiviert.

Generate und Propagate

Betrachten Sie die Übertragsgleichung erneut:

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

Der erste Term, $A_i B_i$, ist genau dann wahr, wenn beide Operandenbits 1 sind – dann erzeugt Stufe $i$ unabhängig davon, was an $C_i$ ankommt, unbedingt einen Carry-out. Definieren Sie:

$G_i = A_i \cdot B_i$

Dies ist das Generate-Signal – Stufe $i$ erzeugt selbst einen Übertrag.

Der zweite Term, $(A_i \oplus B_i) C_i$, sagt: Wenn genau eines der Operandenbits 1 ist, wird alles, was an $C_i$ ankommt, direkt weitergeleitet. Definieren Sie:

$P_i = A_i \oplus B_i$

Dies ist das Propagate-Signal – Stufe $i$ leitet jeden eingehenden Übertrag an ihren Ausgang weiter.

Die Übertragsgleichung vereinfacht sich zu:

$C_{i+1} = G_i + P_i \cdot C_i$

Das sind das UND-Gatter und das ODER-Gatter, die Sie bereits kennen und die genau das leisten, was ihre Wahrheitstabellen beschreiben – nur jetzt kombiniert zu einer Rekurrenz, die Sie auffalten können.

Die Übertragsrekurrenz auffalten

Setzen Sie die Rekurrenz in sich selbst ein. Beginnen Sie mit einem bekannten $C_0$:

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

Das Muster ist klar. Jeder Übertrag $C_{i+1}$ ist eine Sum-of-Products-Form über Generate- und Propagate-Signale der Stufen 0 bis $i$. Logisch hängt jeder Ausdruck nur von $G$, $P$ und $C_0$ ab, nicht von einem abgeschlossenen physischen Übergang im vorhergehenden Volladdierer. Physisch benötigen breite Produktterme und ihre Verdrahtung weiterhin endliche Gatter, Puffer und Routing.

Ein durchgerechnetes 4-Bit-Beispiel

Addieren Sie $A=1011_2$ (11) und $B=0110_2$ (6) mit $C_0=0$. Schreiben Sie die Bits mit dem niederwertigsten zuerst:

Die Übertragsgleichungen ergeben $C_1=0$, $C_2=1$, $C_3=1$ und $C_4=1$. Das Lesen von $C_4S_3S_2S_1S_0$ liefert erwartungsgemäß $10001_2=17$. Die Arithmetik entspricht dem Ripple Carry; nur die Topologie des Übertragsnetzes ändert sich.

Gruppen-Generate und -Propagate

Definieren Sie für eine Bitgruppe von $i$ bis $j$ ein Gruppen-Propagate und ein Gruppen-Generate:

$P_{j:i}=P_jP_{j-1}\cdots P_i$

$G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$

Dann ist der Übertrag, der die Gruppe verlässt:

$C_{j+1}=G_{j:i}+P_{j:i}C_i$

Zwei benachbarte Gruppen lassen sich mit derselben Operation kombinieren:

Diese Assoziativität ist der Schlüssel zu Hierarchie und Parallel-Prefix-Addierern: Paare werden kombiniert, dann Paare von Paaren, wodurch ein Baum statt einer seriellen Kette entsteht.

Die 4-Bit-CLA-Architektur

Auf der Booleschen Ebene hat ein flacher 4-Bit-CLA drei Funktionen:

1. Generate-/Propagate-Schicht. $n$ UND-Gatter erzeugen $G_i = A_i B_i$ in einer Verzögerung; $n$ XOR-Gatter erzeugen $P_i = A_i \oplus B_i$ in einer Verzögerung. Diese Vorgänge laufen parallel.
2. Übertragsnetz. UND-ODER-Logik berechnet $C_1$ bis $C_4$ aus den aufgefalteten Formeln. Mit hypothetischen Gattern mit unbegrenztem Fan-in sieht dies nach zwei Logikebenen aus; eine reale Bibliothek zerlegt breite Terme, sodass Tiefe und Last mit der Breite zunehmen.
3. Summenschicht. $n$ XOR-Gatter erzeugen $S_i = P_i \oplus C_i$ in einer Verzögerung. (Beachten Sie: $S_i = A_i \oplus B_i \oplus C_i = P_i \oplus C_i$, sobald $P_i$ berechnet ist.)

Für vier Bits kann dies den Übertragsweg gegenüber einer Kette aus Volladdiererzellen verkürzen. Die flachen Gleichungen unbegrenzt zu erweitern, ist nicht praktikabel, weshalb größere CLAs Gruppen einführen.

Blockdiagramm eines 4-Bit-CLA

A0,B0 ─┬── XOR ── P0 ──┐                           ┌── XOR ── S0
       └── AND ── G0 ──┤                           │
                       │   ┌─── carry network ───┐ │
A1,B1 ─┬── XOR ── P1 ──┤   │                     │ ├── XOR ── S1
       └── AND ── G1 ──┤   │   computes          │ │
                       ├──>│   C1, C2, C3, C4    │─┤
A2,B2 ─┬── XOR ── P2 ──┤   │   from expanded     │ ├── XOR ── S2
       └── AND ── G2 ──┤   │                     │ │
                       │   │   carry expressions  │ │
                       │   └─────────────────────┘ │
A3,B3 ─┬── XOR ── P3 ──┤                           ├── XOR ── S3
       └── AND ── G3 ──┘                           │
                                                   └────────── C4
C0 ──────────────────────>┘

Fan-in, Verdrahtung und die versteckten Kosten

Für $C_4$ enthält der längste flache Ausdruck einen Produktterm mit fünf Eingängen, wenn $C_0$ einbezogen wird. Für $C_{16}$ hätte der entsprechende Term 17 Eingänge. Standardzellenbibliotheken bieten nur begrenzten Fan-in, und lange Leitungen sowie große Lasten erhöhen die Verzögerung. Ein wörtlich flacher CLA skaliert deshalb nicht elegant, obwohl sein Boolescher Ausdruck flach aussieht.

Die übliche Lösung ist Hierarchie. Bitgruppen – oft Blöcke aus vier Bits – berechnen Gruppen-$G$ und -$P$ und kombinieren diese Gruppen dann auf einer weiteren Ebene. Ein 16-Bit-Entwurf kann vier 4-Bit-Gruppen plus eine zweite Lookahead-Stufe verwenden. Parallel-Prefix-Addierer wenden die assoziative Gruppenoperation im gesamten Baum an.

Der Kompromiss lässt sich nicht in einer universellen Tabelle der Gatteranzahl erfassen:

Tatsächliche Verzögerung, Fläche und Energie müssen nach Mapping und physischer Implementierung gemessen werden. Eine Topologie, die bei abstrakten Gatterebenen gewinnt, kann nach Berücksichtigung von Überlastung, Puffern und Last verlieren.

Jenseits des CLA: Parallel-Prefix-Addierer

Die Carry-Lookahead-Idee lässt sich verallgemeinern. Die Rekurrenz $C_{i+1} = G_i + P_i C_i$ ist unter einem eigenen Operator assoziativ – Sie können benachbarte Positionen paarweise kombinieren und dann Paare von Paaren in einem Baum. Dies ist die Familie der Parallel-Prefix-Addierer:

• Kogge–Stone – geringe Prefix-Tiefe und begrenzter logischer Fan-out, aber dichte Verdrahtung und viele Prefix-Knoten.
• Brent–Kung – weniger Prefix-Knoten und weniger Verdrahtung, dafür größere Tiefe.
• Han-Carlson, Ladner-Fischer, Sklansky – unterschiedliche Kompromisse bei Fan-out, Verdrahtungskomplexität und Tiefe.

Produktionsaddierer können zudem Prefix-Strukturen mischen, Sparsity verwenden oder Carry-Select-Logik um ausgewählte Gruppen herum einsetzen. Die Wahl erfolgt anhand eines konkreten Budgets für Timing, Fläche, Leistung und Routing; allein die Taktfrequenz eines Prozessors verrät seine Addierer-Topologie nicht.

Einen CLA in DigiSim implementieren

Sie können einen 4-Bit-CLA aus Grundelementen aufbauen: vier UND-Gatter für Generate, vier XOR-Gatter für Propagate, die obigen Übertragsgleichungen und vier abschließende XOR-Gatter für die Summe. Die höherstufigen Komponenten Addierer und 8-Bit-Addierer sind Verhaltensvereinfachungen; schließen Sie nicht auf ihre interne Architektur, sofern die Komponentendokumentation sie nicht festlegt.

Um die Topologie zu vergleichen, verketten Sie vier Volladdierer als Ripple Carry und bauen einen separaten 4-Bit-CLA. Überprüfen Sie zunächst alle Operanden-Kombinationen auf funktionale Gleichwertigkeit. Falls der Simulator Verzögerungen pro Gatter modelliert, vergleichen Sie dann die späteste Einschwingzeit nach einer Eingangsänderung. Sind seine Gatter ideal, zählen Sie stattdessen abhängige Logikebenen; eine ideale Wellenform kann Silicon-Timing nicht vorhersagen.

Häufige Fallstricke

• Übersehen, dass $P_i$ als XOR und nicht als ODER definiert ist. Beide Definitionen – $P_i = A_i + B_i$ oder $P_i = A_i \oplus B_i$ – erzeugen einen korrekten Übertrag, weil der Fall $A_i = B_i = 1$ bereits durch $G_i$ abgedeckt ist. XOR ist hier zweckmäßig, weil dieselbe Leitung die Summenstufe speist: $S_i = P_i \oplus C_i$. Bei ODER-definiertem $P_i$ ist diese Wiederverwendung nicht möglich; für die Summe ist dann ein separates XOR erforderlich.
• Die Fan-in-Skalierung unterschätzen. Eine flache 16-Bit-Erweiterung enthält einen Term mit 17 Literalen, wenn $C_0$ einbezogen wird. Praktische breite Entwürfe zerlegen oder gruppieren die Logik.
• Annehmen, dass ein CLA immer schneller ist. Bei schmalen Breiten kann eine Ripple-Implementierung flächenmäßig gewinnen und das Timing komfortabel einhalten. Es gibt keine architekturunabhängige Übergangsbreite.
• Kritische Pfade von Summe und Übertrag verwechseln. Die Tiefe des Übertragsnetzes dominiert die Gesamtverzögerung, doch das abschließende Summen-XOR fügt eine weitere Gatterverzögerung hinzu. Die Verzögerung als „Tiefe des Übertragsnetzes“ anzugeben, ist ein häufiger Fehler.

Wie es weitergeht

Fahren Sie mit Wie eine ALU funktioniert: Arithmetic Logic Unit From Gates fort und lesen Sie dann Booth-Multiplizierer erklärt für eine andere arithmetische Optimierung.

Um die zwei Addierer-Architekturen praktisch zu vergleichen, öffnen Sie die Volladdierer-mit-Übertrag-Vorlage, verketten vier Instanzen als Ripple-Carry-Addierer und beobachten die bitweise Übertragsausbreitung am Logikanalysator. Bauen Sie danach den äquivalenten 4-Bit-CLA aus den Gleichungen dieses Beitrags und messen Sie beide Schaltungen – der Unterschied ist der ganze Grund, warum Hochgeschwindigkeits-ALUs existieren.