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  \mathcal{O}(log (n)) für die Schaltungsverzögerung und  \mathcal{O}(n) für die Schaltungsgröße. Der CLA-Addierer ist also ähnlich schnell wie ein Conditional Sum Addierer, dessen Verzögerung ebenfalls  \mathcal{O}(log (n)) beträgt, und braucht zugleich ähnlich einem Carry-Ripple-Addierer nur  \mathcal{O}(n) wenige Bauteile. Conditional Sum Addierer brauchen im Vergleich mit dem CLA-Addierer jedoch  \mathcal{O}(n^{log_2(3)}) mehr Bauteile, Carry-Ripple-Addierer weisen eine exponentiell größere Verzögerung von  \mathcal{O}(n) auf. Der CLA-Addierer ist dagegen asymptotisch schnell und günstig zugleich.

Funktionsweise[Bearbeiten]

Der CLA-Addierer ist eine spezielle Anwendung einer Parallelen Präfix Berechnung \operatorname{PP}_n^{\circ} welche sich durch eine Schaltung mit Kosten  \mathcal{O}(n) und Verzögerung  \mathcal{O}(log(n)) 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 \operatorname{Inc}_n addiert zu einer n-stelligen Binärzahl den Wert 1 und hat n Eingänge sowie n Ausgänge und einen weiteren Ausgang für einen etwaigen Übertrag beim höchsten Stellenwert.

\operatorname{Inc}_n\colon \{0,1\}^n \to \{0,1\}^{n+1}

\operatorname{Inc}_n(x_{n-1}\ldots x_0) = (y_{n}\ldots y_0)

Ein Übertrag von Stelle i zu i+1 tritt dabei nur dann auf, wenn alle x_0= \ldots = x_i = 1 sind, d. h. wenn die x_0\ldots x_i den Übertrag propagieren. Daher gilt beim Inkrementer für jedes Ergebnisbit y_{i+1} = 1 genau dann, wenn entweder x_0\ldots x_i propagieren oder x_{i+1} = 1 für 0\leq i<n.

Mittels einer Parallelen Präfix Berechnung \operatorname{PP}_n^{\wedge} kann man für alle i die Funktionen „ x_0\ldots x_i propagieren“  = x_0 \wedge x_1 \wedge \ldots \wedge x_i zugleich berechnen, indem man ausnutzt, dass die logische UND Funktion \wedge eine assoziative zweistellige Verknüpfung auf den binären Zahlen ist.

Parallele Präfix Berechnung[Bearbeiten]

Zu jeder assoziativen zweistelligen Verknüpfung {\circ}\colon A \times A\to A auf einer Menge A ist ihre n-stellige Parallele Präfix Funktion \operatorname{PP}_n^{\circ} wie folgt definiert:

\operatorname{PP}_n^{\circ}\colon A^n \to A^n

\operatorname{PP}_n^{\circ}(x_{n-1}\ldots x_0) = (y_{n-1}\ldots y_0) mit y_i = x_i\circ\ldots\circ x_0 für 0\leq i<n

Als Schaltung lässt sich \operatorname{PP}_{2n}^{\circ} rekursiv aus \operatorname{PP}_{n}^{\circ} konstruieren:

\operatorname{PP}_{1}^{\circ}(x_0) = (y_0) = (x_0)

Für \operatorname{PP}_{2n}^{\circ}(x_{2n-1},\ldots,x_0) = (y_{2n-1},\ldots,y_0) sei (y'_{n-1},\ldots,y'_{0}) = \operatorname{PP}_n^{\circ}(x_{2n-1}\circ x_{2n-2}, \ldots, x_1\circ x_0) dann gilt:

y_{2i+1} = y'_i für  0\leq i<n

y_{2i} = y'_{i-1}\circ x_{2i} für  0< i<n

y_{0} = x_0

Beispiel: für n=2 gilt folglich \operatorname{PP}_{2}^{\circ}(x_1,x_0) = (y_1,y_0) = (x_1\circ x_0, x_0)

CLA-Addierer[Bearbeiten]

Seien a_0\ldots a_{n-1} und b_0\ldots b_{n-1} die Ziffern der beiden zu addierenden Zahlen und c_{-1} der Eingangsübertrag. Mit c_i bezeichnet man das Übertragsbit von Stelle i zu Stelle i+1. Dann gilt für das i-te zu berechnende Summenbit s_i = a_i \oplus b_i \oplus c_{i-1}. Sofern alle Übertragsbits c_i bekannt sind, lassen sich die s_i parallel berechnen, mit konstanter Schaltungsverzögerung und linearen Bauteilkosten.

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

Man schreibt p_i = p_i(a,b) falls die i-te Stelle einen Übertrag propagiert:

p_i = a_i \oplus b_i für  0\leq i<n

Weiter schreibt man g_{i+1} = g_{i+1}(a,b) falls die i-te Stelle einen Übertrag generiert:

g_i = a_i \wedge b_i für  0\leq i<n

Sowohl Propagieren als auch Generieren lassen sich ohne Kenntnis der Überträge c_j, j\leq i berechnen!

Um alle Überträge c_i für 0\leq i<n zugleich effizient zu berechnen, definiert man eine assoziative Verknüpfung (Beweis Assoziativität durch Nachrechnen) \circ\colon \{0,1\}^2\times\{0,1\}^2\to \{0,1\}^2 die man in einer parallelen Präfix-Berechnung einsetzen kann:

(g',p') \circ (c,p) = (g'\vee p'\wedge c,p\wedge p')

Die beiden Komponenten erklären sich wie folgt. Es ist der Übertrag c_i=1, wenn die i-te Stelle generiert oder wenn die i-te Stelle propagiert und die i-1-te Stelle einen Übertrag hat, also wenn g_i\vee p_i\wedge c_{i-1}. Aufeinander folgende Stellen i,i-1 propagieren gemeinsam einen Übertrag, wenn p_i\wedge p_{i-1}=1 ist. Die Verknüpfung \circ eignet sich daher um alle c_i wie folgt zu berechnen; die d_i sind dabei reine Hilfsvariablen:

(c_i,d_i) = (g_i,p_i)\circ \ldots \circ (g_0,p_0) \circ (c_{-1},1). oder anders ausgedrückt:

((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))

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

s_i = p_i \oplus c_{i-1} für 0\leq i<n

s_n = c_{n-1}

Weblinks[Bearbeiten]

Literatur[Bearbeiten]

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