Paralleladdierer mit Übertragsvorausberechnung
Der Paralleladdierer mit Übertragsvorausberechnung bzw. Carry-Look-Ahead-Addierer (kurz: CLA-Addierer) ist eine logische Schaltung zur Addition mehrstelliger Binärzahlen (siehe auch Addierwerk).

Der CLA-Addierer addiert zwei n-stellige Binärzahlen, verfügt also über 2·n Eingänge, sowie in der Regel über einen weiteren Übertragseingang. Da das Ergebnis einen etwaigen Übertrag enthalten kann, gibt es n+1 Ausgänge.
Der Vorteil des CLA-Addierers ist, dass die Verzögerung der Schaltung nur logarithmisch zur Zahl seiner Eingänge ist, bei zugleich nur linearer Zahl an Logikgattern gemessen an der Zahl seiner Eingänge. Seine Komplexität beträgt in der Landau-Notation ausgedrückt also  für die Schaltungsverzögerung und  für die Schaltungsgröße. Der CLA-Addierer ist also ähnlich schnell wie ein Conditional-Sum-Addierer, dessen Verzögerung ebenfalls  beträgt, und braucht zugleich ähnlich einem Carry-Ripple-Addierer nur  wenige Bauteile. Conditional-Sum-Addierer brauchen im Vergleich mit dem CLA-Addierer jedoch  mehr Bauteile, Carry-Ripple-Addierer weisen eine exponentiell größere Verzögerung von  auf. Der CLA-Addierer ist dagegen asymptotisch schnell und günstig zugleich.

Idee 

Ein Addierwerk kann einen Großteil seiner Berechnungen auch dann durchführen, wenn der eingehende Übertrag noch nicht vorliegt. Dazu werden die beiden Summanden zunächst ohne Berücksichtigung desselben addiert. Am Ergebnis kann dann direkt abgelesen werden, welche Wirkung der eingehende Übertrag auf den ausgehenden haben wird. Die Tabelle stellt den Zusammenhang am Beispiel eines 4-Bit Addierers dar.

Jedes Addierwerk zeigt an einem speziellen Ausgang an, ob es den eingehenden Übertrag absorbieren, propagieren oder einen solchen generieren wird. Dieser spezielle Ausgang ersetzt den Übertragsausgang eines gewöhnlichen Addierwerks. Der tatsächliche Übertrag kann dann aus dieser Information und dem eingehenden Übertrag leicht berechnet werden. Der große Vorteil dieses speziellen Ausgangs ist, dass er mit wenigen Logikgattern hierarchisch zusammengefasst werden kann, ohne dass die Summe erneut berechnet oder der tatsächliche Übertrag bekannt sein muss, wie nachfolgende Tabelle zeigt.

Funktionsweise 
Der CLA-Addierer ist eine spezielle Anwendung einer Parallelen Präfix Berechnung  welche sich durch eine Schaltung mit Kosten  und Verzögerung  implementieren lässt. Um die raffinierte Anwendung der Parallelen Präfix Berechnung leichter verständlich zu machen, wird zunächst ihre Anwendung am Beispiel eines schnellen Inkrementers dargelegt.

Schneller Inkrementer nach CLA-Art 
Ein Inkrementer  addiert zu einer -stelligen Binärzahl den Wert  und hat  Eingänge sowie  Ausgänge und einen weiteren Ausgang für einen etwaigen Übertrag beim höchsten Stellenwert.

Ein Übertrag von Stelle  zu  tritt dabei nur dann auf, wenn alle  sind, d. h. wenn die  den Übertrag propagieren. Daher gilt beim Inkrementer für jedes Ergebnisbit  genau dann, wenn entweder  propagieren oder  für .

Mittels einer Parallelen Präfix Berechnung  kann man für alle  die Funktionen „ propagieren“  zugleich berechnen, indem man ausnutzt, dass die logische UND Funktion   eine assoziative zweistellige Verknüpfung auf den binären Zahlen ist.

Parallele Präfix Berechnung 
Zu jeder assoziativen zweistelligen Verknüpfung  auf einer Menge  ist ihre -stellige Parallele Präfix Funktion  wie folgt definiert:

 mit  für 

Als Schaltung lässt sich  rekursiv aus  konstruieren:

Für  sei  dann gilt:

 für 
 für 

Beispiel: für  gilt folglich

CLA-Addierer 
Seien  und  die Ziffern der beiden zu addierenden Zahlen und  der Eingangsübertrag. Mit  bezeichnet man das Übertragsbit von Stelle  zu Stelle . Dann gilt für das -te zu berechnende Summenbit   . Sofern alle Übertragsbits  bekannt sind, lassen sich die  parallel berechnen, mit konstanter Schaltungsverzögerung und linearen Bauteilkosten.

Um die  zu berechnen, reicht es nicht wie beim Inkrementer allein zu prüfen, ob der Eingangsübertrag propagiert wird. Denn ein Übertrag wird an der -ten Stelle propagiert, wenn entweder  oder  sind, weiterhin wird ein Übertrag generiert, wenn .

Man schreibt  falls die -te Stelle einen Übertrag propagiert:

 für 

Weiter schreibt man  falls die -te Stelle einen Übertrag generiert:

 für 

Sowohl Propagieren als auch Generieren lassen sich ohne Kenntnis der Überträge  berechnen!

Um alle Überträge  für  zugleich effizient zu berechnen, definiert man eine assoziative Verknüpfung (Beweis Assoziativität durch Nachrechnen)  die man in einer parallelen Präfix-Berechnung einsetzen kann:

Die beiden Komponenten erklären sich wie folgt. Es ist der Übertrag , wenn die -te Stelle generiert oder wenn die -te Stelle propagiert und die -te Stelle einen Übertrag hat, also wenn . Aufeinander folgende Stellen  propagieren gemeinsam einen Übertrag, wenn  ist. Die Verknüpfung  eignet sich daher, um alle  wie folgt zu berechnen; die  sind dabei reine Hilfsvariablen:

, oder anders ausgedrückt:

Mit den nun vorliegenden Zwischenergebnissen lässt sich schließlich die Summe  von  und  einfach berechnen. Es gilt:

 für

Literatur 
 Jörg Keller, Wolfgang J. Paul: Hardware Design. Formaler Entwurf digitaler Schaltungen Teubner 1995/2005, ISBN 3-519-23047-X.

Weblinks 
 Ausführliche Einführung der Fachhochschule Flensburg

Digitale Schaltungstechnik
Numerische Mathematik
Computerarithmetik