Paralleladdierer mit Übertragsvorausberechnung

Überblick und Bedeutung

Ein Paralleladdierer mit Übertragsvorausberechnung, auch Carry-Look-Ahead-Addierer oder kurz CLA-Addierer, ist eine logische Schaltung zur Addition mehrstelliger Binärzahlen. Er addiert zwei n-stellige Binärzahlen und besitzt daher 2·n Eingänge. In der Regel kommt ein Eingang für einen eingehenden Übertrag hinzu. Da bei der Addition ein weiterer Übertrag entstehen kann, hat die Schaltung n+1 Ausgänge.

Der entscheidende Vorteil besteht darin, dass die Überträge nicht nacheinander durch alle Stellen laufen müssen. Stattdessen werden sie mit einer parallelen Präfix-Berechnung vorausberechnet. Dadurch beträgt die Schaltungsverzögerung nur O(log(n)), während die Schaltungsgröße, also die Zahl der benötigten Logikgatter, O(n) beträgt.

Ein Conditional-Sum-Addierer erreicht ebenfalls eine Verzögerung von O(log(n)), benötigt aber O(n^{log₂(3)}) Bauteile. Ein Carry-Ripple-Addierer benötigt zwar nur O(n) Bauteile, besitzt jedoch eine Verzögerung von O(n). Der CLA-Addierer verbindet somit asymptotisch geringe Verzögerung mit linearer Schaltungsgröße.

Grundidee der Übertragsvorausberechnung

Ein Addierwerk kann einen großen Teil der Addition ausführen, bevor der eingehende Übertrag bekannt ist. Dazu addiert es die beiden Summanden zunächst ohne diesen Übertrag. Am vorläufigen Ergebnis lässt sich erkennen, wie sich ein später eintreffender Übertrag auf den ausgehenden Übertrag auswirkt.

Bei einem 4-Bit-Addierwerk gelten drei Fälle:

• Liegt die vorläufige Summe zwischen 00000 und 01110, ist der ausgehende Übertrag unabhängig vom eingehenden Übertrag 0. Der eingehende Übertrag wird absorbiert.

• Bei der vorläufigen Summe 01111 wird der eingehende Übertrag unverändert weitergegeben: Aus 0 wird ein ausgehender Übertrag 0, aus 1 ein ausgehender Übertrag 1. Der Übertrag wird propagiert.

• Liegt die vorläufige Summe zwischen 10000 und 11110, ist der ausgehende Übertrag unabhängig vom eingehenden Übertrag 1. Ein Übertrag wird generiert.

Ein spezieller Ausgang des Addierwerks zeigt deshalb an, ob es einen Übertrag absorbiert, propagiert oder generiert. Diese Information kann hierarchisch für mehrere Teiladdierer zusammengefasst werden, ohne die Summe erneut zu berechnen oder den tatsächlichen Übertrag bereits zu kennen. Absorbiert der höherwertige Teil, absorbiert auch die Zusammenfassung. Generiert er, generiert auch die Zusammenfassung. Propagiert er, übernimmt die Zusammenfassung das Verhalten des niederwertigen Teils. Zwei propagierende Teile propagieren gemeinsam.

Parallele Präfix-Berechnung

Die Übertragsvorausberechnung beruht auf einer parallelen Präfix-Funktion. Für jede assoziative zweistellige Verknüpfung ∘: A×A→A auf einer Menge A ist sie definiert durch

PP_n^∘: A^n→A^n

PP_n^∘(x_{n−1}…x_0)=(y_{n−1}…y_0), wobei y_i=x_i∘…∘x_0 für 0≤i<n gilt.

„Assoziativ“ bedeutet, dass die Klammerung das Ergebnis nicht verändert. Deshalb können Teilresultate hierarchisch und parallel verbunden werden. Die Schaltung lässt sich mit Kosten O(n) und einer Verzögerung O(log(n)) implementieren.

Die rekursive Konstruktion beginnt mit PP_1^∘(x_0)=(y_0)=(x_0). Für PP_{2n}^∘ werden zunächst benachbarte Eingaben paarweise verknüpft. Ist

(y'{n−1},…,y'0)=PP_n^∘(x{2n−1}∘x{2n−2},…,x_1∘x_0),

dann gilt:

• y_{2i+1}=y'_i für 0≤i<n,

• y_{2i}=y'{i−1}∘x{2i} für 0<i<n,

• y_0=x_0.

Für n=2 ergibt sich beispielsweise PP_2^∘(x_1,x_0)=(x_1∘x_0,x_0).

Schneller Inkrementer als Vorbild

Ein Inkrementer Inc_n addiert zu einer n-stelligen Binärzahl den Wert 1. Er besitzt n Eingänge, n Ausgänge für die Ergebnisstellen und einen weiteren Ausgang für einen möglichen Übertrag am höchsten Stellenwert:

Inc_n: {0,1}^n→{0,1}^{n+1}

Inc_n(x_{n−1}…x_0)=(y_n…y_0).

Ein Übertrag von Stelle i zu Stelle i+1 entsteht genau dann, wenn x_0=…=x_i=1 ist. Die Stellen x_0…x_i propagieren den bei der Addition von 1 entstehenden Übertrag dann vollständig. Entsprechend gilt für y_{i+1}=1 genau dann, wenn entweder x_0…x_i den Übertrag propagieren oder x_{i+1}=1 ist, für 0≤i<n.

Alle Bedingungen „x_0…x_i propagieren“ können gleichzeitig als Präfixe

x_0∧x_1∧…∧x_i

berechnet werden. Dazu verwendet man PP_n^∧, weil die logische UND-Verknüpfung ∧ assoziativ ist. Dieses einfachere Beispiel zeigt das Grundprinzip, das beim CLA-Addierer auf Propagierungs- und Generierungsinformationen erweitert wird.

Berechnung im CLA-Addierer

Die Bits der beiden Summanden seien a_0…a_{n−1} und b_0…b_{n−1}; c_{−1} bezeichnet den Eingangsübertrag. c_i ist der Übertrag von Stelle i zu Stelle i+1. Sind alle Überträge bekannt, können die Summenbits parallel mit konstanter zusätzlicher Verzögerung und linearen Bauteilkosten berechnet werden:

s_i=a_i⊕b_i⊕c_{i−1}.

Für jede Stelle werden zunächst zwei vom Übertrag unabhängige Informationen bestimmt. Das Propagierungsbit

p_i=a_i⊕b_i für 0≤i<n

zeigt an, ob die Stelle einen eingehenden Übertrag weitergibt. Das Generierungsbit

g_i=a_i∧b_i für 0≤i<n

zeigt an, ob die Stelle selbst einen Übertrag erzeugt. Im Text wird die Generierungsinformation zuvor auch als g_{i+1}=g_{i+1}(a,b) bezeichnet; die anschließend verwendeten Formeln indizieren sie als g_i.

Zur gemeinsamen Berechnung aller Überträge wird auf Paaren aus Generierungs- und Propagierungsbit die assoziative Verknüpfung

(g′,p′)∘(c,p)=(g′∨(p′∧c),p∧p′)

definiert. Die erste Komponente beschreibt den resultierenden Übertrag: Er ist 1, wenn die betrachtete Stelle selbst generiert oder wenn sie propagiert und aus dem niedrigeren Teil ein Übertrag kommt. Die zweite Komponente ist 1, wenn beide zusammengefassten Bereiche einen Übertrag propagieren.

Damit werden alle Überträge gleichzeitig berechnet:

(c_i,d_i)=(g_i,p_i)∘…∘(g_0,p_0)∘(c_{−1},1).

Die d_i sind reine Hilfsvariablen. Gleichwertig lässt sich die gesamte Rechnung schreiben als

((c_{n−1},d_{n−1}),…,(c_{−1},d_{−1}))=PP_{n+1}^∘((g_{n−1},p_{n−1}),…,(g_0,p_0),(c_{−1},1)).

Nach der Präfix-Berechnung stehen alle benötigten Überträge bereit. Die endgültige Summe folgt aus

s_i=p_i⊕c_{i−1} für 0≤i<n

und

s_n=c_{n−1}.

So werden die Überträge hierarchisch statt nacheinander bestimmt; daraus ergeben sich die logarithmische Verzögerung O(log(n)) und die lineare Schaltungsgröße O(n).