Paralleladdierer mit Übertragsvorausberechnung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
4-Bit-Carry-Look-Ahead-Addierer mit Carry-In und Carry-Out

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.

Funktionsweise[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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

Weblinks[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

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