Paralleladdierer mit Übertragsvorausberechnung
aus Wikipedia, der freien Enzyklopädie
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit, ihn zu verbessern, und entferne anschließend diese Markierung. |
Der Paralleladdierer mit Übertragsvorausberechnung bzw. Carry-Look-Ahead-Addierer (kurz: CLA-Addierer) ist ein elektronischer Baustein zur Addition mehrstelliger Binärzahlen (siehe auch Addiernetz).
Der CLA-Addierer addiert zwei n-stellige Binärzahlen, verfügt also über 2·n Eingänge. Da das Ergebnis einen etwaigen Übertrag enthalten kann, gibt es n+1 Ausgänge.
Während beim Carry-Ripple-Addierer die Bits der beiden Summanden zwar parallel addiert werden, die etwaigen Überträge aber sequentiell von Volladdierer zu Volladdierer weitergereicht werden, ist die Laufzeit recht hoch. Der CLA-Addierer dagegen verfügt über eine spezielle Logik, die die Überträge bereits im ersten Additionsschritt ermittelt. Dies ist allerdings mit einem größeren Schaltungsaufwand verbunden.
Ein CLA-Addierer mit n Bit Wortbreite benötigt unter anderem ein Und-Gatter und ein Oder-Gatter mit n Eingängen. Gatter mit vielen Eingängen haben meist hohe Verzögerungszeiten beim Schalten, weshalb CLA-Addierer nur bei kleinen Wortbreiten effektiv sind.
[Bearbeiten] Funktionsweise
a und b sind die Summanden. g (generate: generieren, erzeugen) gibt an, ob an einer Stelle ein Übertrag erzeugt wird. p (propagate: propagieren, verbreiten) gibt an, ob an einer Stelle der Übertrag von der vorherigen Stelle weitergegeben wird oder ob der Übertrag absorbiert wird (1 = wird weitergegeben, 0 = wird absorbiert). s (sum) ist die Summe und c (carry) der Übertrag.
- g(i) = a(i) AND b(i)
- p(i) = a(i) XOR b(i)
- s(i) = p(i) XOR c(i)
- c0 = 0
- c1 = g0
- c2 = g1 OR (p1 AND g0)
- c3 = g2 OR (p2 AND g1) OR (p2 AND p1 AND g0)
- ...
Erklärung in Worten am Beispiel c3: An der 3ten Stelle gibt es einen Übertrag, wenn die 2. Stelle einen Übertrag erzeugt, oder wenn die 2. Stelle den von der 1. Stelle erzeugten Übertrag weitergibt, oder wenn die 2. und 1. Stelle den von der 0ten Stelle erzeugten Übertrag weitergibt.
Im 3-Bit-CLA-Addierer in der Abbildung wurde c0 weggelassen, da dieses stets 0 ist. s0 ist somit immer gleich p0.
[Bearbeiten] Conditional Sum Addition
Die Conditional Sum Addition stammt ursprünglich von Sklansky. Er versuchte, die nur in linearer Zeit arbeitenden Carry-Ripple-Addierer zu verbessern. Technisch kann er kaum als "Verbesserung", d.h. Weiterentwicklung des CLA-Addieres angesehen werden, da er auf einem völlig anderen Konstruktionsprinzip basiert.
Das Prinzip:
- Die eingehenden Bit-Folgen werden rekursiv halbiert, bis nur noch 1 Bit große Stücke übrig sind.
- Diese werden addiert.
- Jetzt werden die Ergebnisse wieder rekursiv addiert.
Das Problem, das bei diesem Verfahren auftritt, ist, dass man nicht weiß, ob die weniger signifikanten Additionen einen Überlauf haben, wenn die 1 Bit großen Stücke parallel addiert werden. Um dieses Problem zu lösen, werden einfach alle Additionen sowohl mit als auch ohne Überlauf ausgeführt und je nach Vorgänger dann das richtige Ergebnis ausgewählt.
Durch dieses Prinzip ist es möglich, in logarithmischer Zeit zu addieren.
