Paralleladdierer mit Übertragsvorausberechnung - LinkFang.de





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.

Funktionsweise

Der CLA-Addierer ist eine spezielle Anwendung einer Parallelen Präfix Berechnung [math]\operatorname{PP}_n^{\circ}[/math] welche 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\ltn[/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\ltn[/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\ltn [/math]

[math]y_{2i} = y'_{i-1}\circ x_{2i} [/math] für [math] 0\lt i\ltn [/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\ltn [/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\ltn [/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\ltn[/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]((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\ltn[/math]

[math]s_n = c_{n-1}[/math]

Weblinks

Literatur

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

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Paralleladdierer mit Übertragsvorausberechnung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.