www.wikidata.de-de.nina.az

Paralleladdierer mit übertragsvorausberechnung Der bzw Carry Look Ahead Addierer kurz CLA Addierer ist eine logische Sch

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

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.

Idee Bearbeiten

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:

Als Schaltung lässt sich rekursiv aus konstruieren:

Für sei dann gilt:

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:

Weiter schreibt man falls die -te Stelle einen Übertrag generiert:

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:

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

Literatur Bearbeiten

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Paralleladdierer mit Ubertragsvorausberechnung bzw Carry Look Ahead Addierer kurz CLA Addierer ist eine logische Schaltung zur Addition mehrstelliger Binarzahlen siehe auch Addierwerk 4 Bit Carry Look Ahead Addierer mit Carry In und Carry Out Der CLA Addierer addiert zwei n stellige Binarzahlen verfugt also uber 2 n Eingange sowie in der Regel uber einen weiteren Ubertragseingang Da das Ergebnis einen etwaigen Ubertrag enthalten kann gibt es n 1 Ausgange Der Vorteil des CLA Addierers ist dass die Verzogerung der Schaltung nur logarithmisch zur Zahl seiner Eingange ist bei zugleich nur linearer Zahl an Logikgattern gemessen an der Zahl seiner Eingange Seine Komplexitat betragt in der Landau Notation ausgedruckt also O log n displaystyle mathcal O log n fur die Schaltungsverzogerung und O n displaystyle mathcal O n fur die Schaltungsgrosse Der CLA Addierer ist also ahnlich schnell wie ein Conditional Sum Addierer dessen Verzogerung ebenfalls O log n displaystyle mathcal O log n betragt und braucht zugleich ahnlich einem Carry Ripple Addierer nur O n displaystyle mathcal O n wenige Bauteile Conditional Sum Addierer brauchen im Vergleich mit dem CLA Addierer jedoch O n log 2 3 displaystyle mathcal O n log 2 3 mehr Bauteile Carry Ripple Addierer weisen eine exponentiell grossere Verzogerung von O n displaystyle mathcal O n auf Der CLA Addierer ist dagegen asymptotisch schnell und gunstig zugleich Inhaltsverzeichnis 1 Idee 2 Funktionsweise 2 1 Schneller Inkrementer nach CLA Art 2 2 Parallele Prafix Berechnung 2 3 CLA Addierer 3 Literatur 4 WeblinksIdee BearbeitenEin Addierwerk kann einen Grossteil seiner Berechnungen auch dann durchfuhren wenn der eingehende Ubertrag noch nicht vorliegt Dazu werden die beiden Summanden zunachst ohne Berucksichtigung desselben addiert Am Ergebnis kann dann direkt abgelesen werden welche Wirkung der eingehende Ubertrag auf den ausgehenden haben wird Die Tabelle stellt den Zusammenhang am Beispiel eines 4 Bit Addierers dar Zusammenhang zwischen ein und ausgehenden Ubertragen eines 4 Bit Addierwerks Summe ohne Berucksichtigungdes eingehenden Ubertrags eingehender ausgehender Bemerkung Ubertrag 00000 bis 01110 beliebig 0 Der eingehende Ubertrag wird absorbiert 01111 0 0 Der eingehende Ubertrag wird unverandert propagiert 1 1 10000 bis 11110 beliebig 1 Ein Ubertrag wird immer generiert Jedes Addierwerk zeigt an einem speziellen Ausgang an ob es den eingehenden Ubertrag absorbieren propagieren oder einen solchen generieren wird Dieser spezielle Ausgang ersetzt den Ubertragsausgang eines gewohnlichen Addierwerks Der tatsachliche Ubertrag kann dann aus dieser Information und dem eingehenden Ubertrag leicht berechnet werden Der grosse Vorteil dieses speziellen Ausgangs ist dass er mit wenigen Logikgattern hierarchisch zusammengefasst werden kann ohne dass die Summe erneut berechnet oder der tatsachliche Ubertrag bekannt sein muss wie nachfolgende Tabelle zeigt Zusammenfassung zweier Addierwerke zu einem breiteren Addierwerk hoherwertigesAddierwerk niederwertigesAddierwerk zusammengefasstesAddierwerk absorbiert beliebig absorbiert generiert beliebig generiert propagiert absorbiert absorbiert generiert generiert propagiert propagiertFunktionsweise BearbeitenDer CLA Addierer ist eine spezielle Anwendung einer Parallelen Prafix Berechnung PP n displaystyle operatorname PP n circ nbsp welche sich durch eine Schaltung mit Kosten O n displaystyle mathcal O n nbsp und Verzogerung O log n displaystyle mathcal O log n nbsp implementieren lasst Um die raffinierte Anwendung der Parallelen Prafix Berechnung leichter verstandlich zu machen wird zunachst ihre Anwendung am Beispiel eines schnellen Inkrementers dargelegt Schneller Inkrementer nach CLA Art Bearbeiten Ein Inkrementer Inc n displaystyle operatorname Inc n nbsp addiert zu einer n displaystyle n nbsp stelligen Binarzahl den Wert 1 displaystyle 1 nbsp und hat n displaystyle n nbsp Eingange sowie n displaystyle n nbsp Ausgange und einen weiteren Ausgang fur einen etwaigen Ubertrag beim hochsten Stellenwert Inc n 0 1 n 0 1 n 1 displaystyle operatorname Inc n colon 0 1 n to 0 1 n 1 nbsp Inc n x n 1 x 0 y n y 0 displaystyle operatorname Inc n x n 1 ldots x 0 y n ldots y 0 nbsp Ein Ubertrag von Stelle i displaystyle i nbsp zu i 1 displaystyle i 1 nbsp tritt dabei nur dann auf wenn alle x 0 x i 1 displaystyle x 0 ldots x i 1 nbsp sind d h wenn die x 0 x i displaystyle x 0 ldots x i nbsp den Ubertrag propagieren Daher gilt beim Inkrementer fur jedes Ergebnisbit y i 1 1 displaystyle y i 1 1 nbsp genau dann wenn entweder x 0 x i displaystyle x 0 ldots x i nbsp propagieren oder x i 1 1 displaystyle x i 1 1 nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp Mittels einer Parallelen Prafix Berechnung PP n displaystyle operatorname PP n wedge nbsp kann man fur alle i displaystyle i nbsp die Funktionen x 0 x i displaystyle x 0 ldots x i nbsp propagieren x 0 x 1 x i displaystyle x 0 wedge x 1 wedge ldots wedge x i nbsp zugleich berechnen indem man ausnutzt dass die logische UND Funktion displaystyle wedge nbsp eine assoziative zweistellige Verknupfung auf den binaren Zahlen ist Parallele Prafix Berechnung Bearbeiten Zu jeder assoziativen zweistelligen Verknupfung A A A displaystyle circ colon A times A to A nbsp auf einer Menge A displaystyle A nbsp ist ihre n displaystyle n nbsp stellige Parallele Prafix Funktion PP n displaystyle operatorname PP n circ nbsp wie folgt definiert PP n A n A n displaystyle operatorname PP n circ colon A n to A n nbsp PP n x n 1 x 0 y n 1 y 0 displaystyle operatorname PP n circ x n 1 ldots x 0 y n 1 ldots y 0 nbsp mit y i x i x 0 displaystyle y i x i circ ldots circ x 0 nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp Als Schaltung lasst sich PP 2 n displaystyle operatorname PP 2n circ nbsp rekursiv aus PP n displaystyle operatorname PP n circ nbsp konstruieren PP 1 x 0 y 0 x 0 displaystyle operatorname PP 1 circ x 0 y 0 x 0 nbsp Fur PP 2 n x 2 n 1 x 0 y 2 n 1 y 0 displaystyle operatorname PP 2n circ x 2n 1 ldots x 0 y 2n 1 ldots y 0 nbsp sei y n 1 y 0 PP n x 2 n 1 x 2 n 2 x 1 x 0 displaystyle y n 1 ldots y 0 operatorname PP n circ x 2n 1 circ x 2n 2 ldots x 1 circ x 0 nbsp dann gilt y 2 i 1 y i displaystyle y 2i 1 y i nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp y 2 i y i 1 x 2 i displaystyle y 2i y i 1 circ x 2i nbsp fur 0 lt i lt n displaystyle 0 lt i lt n nbsp y 0 x 0 displaystyle y 0 x 0 nbsp Beispiel fur n 2 displaystyle n 2 nbsp gilt folglich PP 2 x 1 x 0 y 1 y 0 x 1 x 0 x 0 displaystyle operatorname PP 2 circ x 1 x 0 y 1 y 0 x 1 circ x 0 x 0 nbsp CLA Addierer Bearbeiten Seien a 0 a n 1 displaystyle a 0 ldots a n 1 nbsp und b 0 b n 1 displaystyle b 0 ldots b n 1 nbsp die Ziffern der beiden zu addierenden Zahlen und c 1 displaystyle c 1 nbsp der Eingangsubertrag Mit c i displaystyle c i nbsp bezeichnet man das Ubertragsbit von Stelle i displaystyle i nbsp zu Stelle i 1 displaystyle i 1 nbsp Dann gilt fur das i displaystyle i nbsp te zu berechnende Summenbit s i a i displaystyle s i a i nbsp displaystyle oplus nbsp b i c i 1 displaystyle b i oplus c i 1 nbsp Sofern alle Ubertragsbits c i displaystyle c i nbsp bekannt sind lassen sich die s i displaystyle s i nbsp parallel berechnen mit konstanter Schaltungsverzogerung und linearen Bauteilkosten Um die c i displaystyle c i nbsp zu berechnen reicht es nicht wie beim Inkrementer allein zu prufen ob der Eingangsubertrag propagiert wird Denn ein Ubertrag wird an der i displaystyle i nbsp ten Stelle propagiert wenn entweder a i 1 displaystyle a i 1 nbsp oder b i 1 displaystyle b i 1 nbsp sind weiterhin wird ein Ubertrag generiert wenn a i b i 1 displaystyle a i b i 1 nbsp Man schreibt p i p i a b displaystyle p i p i a b nbsp falls die i displaystyle i nbsp te Stelle einen Ubertrag propagiert p i a i b i displaystyle p i a i oplus b i nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp Weiter schreibt man g i 1 g i 1 a b displaystyle g i 1 g i 1 a b nbsp falls die i displaystyle i nbsp te Stelle einen Ubertrag generiert g i a i b i displaystyle g i a i wedge b i nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp Sowohl Propagieren als auch Generieren lassen sich ohne Kenntnis der Ubertrage c j j i displaystyle c j j leq i nbsp berechnen Um alle Ubertrage c i displaystyle c i nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp zugleich effizient zu berechnen definiert man eine assoziative Verknupfung Beweis Assoziativitat durch Nachrechnen 0 1 2 0 1 2 0 1 2 displaystyle circ colon 0 1 2 times 0 1 2 to 0 1 2 nbsp die man in einer parallelen Prafix Berechnung einsetzen kann g p c p g p c p p displaystyle g p circ c p g vee p wedge c p wedge p nbsp Die beiden Komponenten erklaren sich wie folgt Es ist der Ubertrag c i 1 displaystyle c i 1 nbsp wenn die i displaystyle i nbsp te Stelle generiert oder wenn die i displaystyle i nbsp te Stelle propagiert und die i 1 displaystyle i 1 nbsp te Stelle einen Ubertrag hat also wenn g i p i c i 1 displaystyle g i vee p i wedge c i 1 nbsp Aufeinander folgende Stellen i i 1 displaystyle i i 1 nbsp propagieren gemeinsam einen Ubertrag wenn p i p i 1 1 displaystyle p i wedge p i 1 1 nbsp ist Die Verknupfung displaystyle circ nbsp eignet sich daher um alle c i displaystyle c i nbsp wie folgt zu berechnen die d i displaystyle d i nbsp sind dabei reine Hilfsvariablen c i d i g i p i g 0 p 0 c 1 1 displaystyle c i d i g i p i circ ldots circ g 0 p 0 circ c 1 1 nbsp oder anders ausgedruckt c n 1 d n 1 c 1 d 1 PP n 1 g n 1 p n 1 g 0 p 0 c 1 1 displaystyle 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 nbsp Mit den nun vorliegenden Zwischenergebnissen lasst sich schliesslich die Summe s displaystyle s nbsp von a displaystyle a nbsp und b displaystyle b nbsp einfach berechnen Es gilt s i p i c i 1 displaystyle s i p i oplus c i 1 nbsp fur 0 i lt n displaystyle 0 leq i lt n nbsp s n c n 1 displaystyle s n c n 1 nbsp Literatur BearbeitenJorg Keller Wolfgang J Paul Hardware Design Formaler Entwurf digitaler Schaltungen Teubner 1995 2005 ISBN 3 519 23047 X Weblinks BearbeitenAusfuhrliche Darstellung bei der Hochschule Flensburg Abgerufen von https de wikipedia org w index php title Paralleladdierer mit Ubertragsvorausberechnung amp oldid 243232138