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 <math> \mathcal{O}(\log (n)) </math> für die Schaltungsverzögerung und <math> \mathcal{O}(n) </math> für die Schaltungsgröße. Der CLA-Addierer ist also ähnlich schnell wie ein Conditional-Sum-Addierer, dessen Verzögerung ebenfalls <math> \mathcal{O}(\log (n)) </math> beträgt, und braucht zugleich ähnlich einem Carry-Ripple-Addierer nur <math> \mathcal{O}(n) </math> wenige Bauteile. Conditional-Sum-Addierer brauchen im Vergleich mit dem CLA-Addierer jedoch <math> \mathcal{O}(n^{\log_2(3)}) </math> mehr Bauteile, Carry-Ripple-Addierer weisen eine exponentiell größere Verzögerung von <math> \mathcal{O}(n) </math> 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.
| 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.
| höherwertiges Addierwerk |
niederwertiges Addierwerk |
zusammengefasstes Addierwerk |
|---|---|---|
| absorbiert | beliebig | absorbiert |
| generiert | beliebig | generiert |
| propagiert | absorbiert | absorbiert |
| generiert | generiert | |
| propagiert | propagiert |
Funktionsweise
Der CLA-Addierer ist eine spezielle Anwendung einer Parallelen Präfix-Berechnung <math>\operatorname{PP}_n^{\circ}</math>, die sich durch eine Schaltung mit Kosten <math> \mathcal{O}(n) </math> und Verzögerung <math> \mathcal{O}(\log(n)) </math> 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 <math>\operatorname{Inc}_n</math> addiert zu einer <math>n</math>-stelligen Binärzahl den Wert <math>1</math> und hat <math>n</math> Eingänge sowie <math>n</math> Ausgänge und einen weiteren Ausgang für einen etwaigen Übertrag beim höchsten Stellenwert.
- <math>\operatorname{Inc}_n\colon \{0,1\}^n \to \{0,1\}^{n+1}</math>
- <math>\operatorname{Inc}_n(x_{n-1}\ldots x_0) = (y_{n}\ldots y_0)</math>
Ein Übertrag von Stelle <math>i</math> zu <math>i+1</math> tritt dabei nur dann auf, wenn alle <math>x_0= \ldots = x_i = 1</math> sind, d. h. wenn die <math>x_0\ldots x_i</math> den Übertrag propagieren. Daher gilt beim Inkrementer für jedes Ergebnisbit <math>y_{i+1} = 1</math> genau dann, wenn entweder <math>x_0\ldots x_i</math> propagieren oder <math>x_{i+1} = 1</math> für <math>0\leq i<n</math>.
Mittels einer Parallelen Präfix-Berechnung <math>\operatorname{PP}_n^{\wedge}</math> kann man für alle <math>i</math> die Funktionen „<math> x_0\ldots x_i</math> propagieren“ <math> = x_0 \wedge x_1 \wedge \ldots \wedge x_i</math> zugleich berechnen, indem man ausnutzt, dass die logische UND Funktion <math>\wedge</math> eine assoziative zweistellige Verknüpfung auf den binären Zahlen ist.
Parallele Präfix Berechnung
Zu jeder assoziativen zweistelligen Verknüpfung <math>{\circ}\colon A \times A\to A</math> auf einer Menge <math>A</math> ist ihre <math>n</math>-stellige Parallele Präfix-Funktion <math>\operatorname{PP}_n^{\circ}</math> wie folgt definiert:
- <math>\operatorname{PP}_n^{\circ}\colon A^n \to A^n</math>
- <math>\operatorname{PP}_n^{\circ}(x_{n-1}\ldots x_0) = (y_{n-1}\ldots y_0)</math> mit <math>y_i = x_i\circ\ldots\circ x_0</math> für <math>0\leq i<n</math>
Als Schaltung lässt sich <math>\operatorname{PP}_{2n}^{\circ}</math> rekursiv aus <math>\operatorname{PP}_{n}^{\circ}</math> konstruieren:
- <math>\operatorname{PP}_{1}^{\circ}(x_0) = (y_0) = (x_0) </math>
Für <math>\operatorname{PP}_{2n}^{\circ}(x_{2n-1},\ldots,x_0) = (y_{2n-1},\ldots,y_0)</math> sei <math>(y'_{n-1},\ldots,y'_{0}) = \operatorname{PP}_n^{\circ}(x_{2n-1}\circ x_{2n-2}, \ldots, x_1\circ x_0)</math> dann gilt:
- <math>y_{2i+1} = y'_i</math> für <math> 0\leq i<n </math>
- <math>y_{2i} = y'_{i-1}\circ x_{2i} </math> für <math> 0< i<n </math>
- <math>y_{0} = x_0 </math>
Beispiel: für <math>n=2</math> gilt folglich <math>\operatorname{PP}_{2}^{\circ}(x_1,x_0) = (y_1,y_0) = (x_1\circ x_0, x_0). </math>
CLA-Addierer
Seien <math>a_0\ldots a_{n-1}</math> und <math>b_0\ldots b_{n-1}</math> die Ziffern der beiden zu addierenden Zahlen und <math>c_{-1}</math> der Eingangsübertrag. Mit <math>c_i</math> bezeichnet man das Übertragsbit von Stelle <math>i</math> zu Stelle <math>i+1</math>. Dann gilt für das <math>i</math>-te zu berechnende Summenbit <math>s_i = a_i</math> <math>\oplus</math> <math>b_i \oplus c_{i-1}</math>. Sofern alle Übertragsbits <math>c_i</math> bekannt sind, lassen sich die <math>s_i</math> parallel berechnen, mit konstanter Schaltungsverzögerung und linearen Bauteilkosten.
Um die <math>c_i</math> zu berechnen, reicht es nicht wie beim Inkrementer allein zu prüfen, ob der Eingangsübertrag propagiert wird. Denn ein Übertrag wird an der <math>i</math>-ten Stelle propagiert, wenn entweder <math>a_i=1</math> oder <math>b_i=1</math> sind, weiterhin wird ein Übertrag generiert, wenn <math>a_i=b_i=1</math>.
Man schreibt <math>p_i = p_i(a,b)</math>, falls die <math>i</math>-te Stelle einen Übertrag propagiert:
- <math>p_i = a_i \oplus b_i</math> für <math> 0\leq i<n </math>
Weiter schreibt man <math>g_{i+1} = g_{i+1}(a,b)</math>, falls die <math>i</math>-te Stelle einen Übertrag generiert:
- <math>g_i = a_i \wedge b_i</math> für <math> 0\leq i<n </math>
Sowohl Propagieren als auch Generieren lassen sich ohne Kenntnis der Überträge <math>c_j, j\leq i</math> berechnen.
Um alle Überträge <math>c_i</math> für <math>0\leq i<n</math> zugleich effizient zu berechnen, definiert man eine assoziative Verknüpfung (Beweis Assoziativität durch Nachrechnen) <math>\circ\colon \{0,1\}^2\times\{0,1\}^2\to \{0,1\}^2</math>, die man in einer parallelen Präfix-Berechnung einsetzen kann:
- <math>(g',p') \circ (c,p) = (g'\vee p'\wedge c,p\wedge p')</math>
Die beiden Komponenten erklären sich wie folgt. Es ist der Übertrag <math>c_i=1</math>, wenn die <math>i</math>-te Stelle generiert oder wenn die <math>i</math>-te Stelle propagiert und die <math>i-1</math>-te Stelle einen Übertrag hat, also wenn <math>g_i\vee p_i\wedge c_{i-1}</math>. Aufeinander folgende Stellen <math>i,i-1</math> propagieren gemeinsam einen Übertrag, wenn <math>p_i\wedge p_{i-1}=1</math> ist. Die Verknüpfung <math>\circ</math> eignet sich daher, um alle <math>c_i</math> wie folgt zu berechnen; die <math>d_i</math> sind dabei reine Hilfsvariablen:
- <math>(c_i,d_i) = (g_i,p_i)\circ \ldots \circ (g_0,p_0) \circ (c_{-1},1)</math>, oder anders ausgedrückt:
- <math display="inline">((c_{n-1},d_{n-1}),\ldots,(c_{-1},d_{-1})) = \operatorname{PP}_{n+1}^{\circ}((g_{n-1},p_{n-1}),\ldots,(g_0,p_0),(c_{-1},1))</math>
Mit den nun vorliegenden Zwischenergebnissen lässt sich schließlich die Summe <math>s</math> von <math>a</math> und <math>b</math> einfach berechnen. Es gilt:
- <math>s_i = p_i \oplus c_{i-1}</math> für <math>0\leq i<n</math>
- <math>s_n = c_{n-1}</math>
Literatur
- Jörg Keller, Wolfgang J. Paul: Hardware Design. Formaler Entwurf digitaler Schaltungen Teubner 1995/2005, ISBN 3-519-23047-X.