Paralleladdierer mit Übertragsvorausberechnung

(Weitergeleitet von Carry-Look-Ahead)

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

4-Bit-Carry-Look-Ahead-Addierer mit Carry-In und Carry-Out

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.

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.

Zusammenhang zwischen ein- und ausgehenden Überträgen eines 4-Bit Addierwerks
Summe ohne Berücksichtigung
des eingehenden Übertrags
eingehender ausgehender Bemerkung
Übertrag
00000 bis 01110 beliebig 0 Der eingehende Übertrag wird absorbiert.
01111 0 0 Der eingehende Übertrag wird unverändert propagiert.
1 1
10000 bis 11110 beliebig 1 Ein Übertrag wird immer generiert.

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.

Zusammenfassung zweier Addierwerke zu einem breiteren Addierwerk
höherwertiges
Addierwerk
niederwertiges
Addierwerk
zusammengefasstes
Addierwerk
absorbiert beliebig absorbiert
generiert beliebig generiert
propagiert absorbiert absorbiert
generiert generiert
propagiert propagiert

Funktionsweise

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

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