Conditional-Sum-Addition
Der Conditional-Sum-Addierer (kurz: CSA) ist eine elektronische Schaltung zur Addition mehrstelliger Binärzahlen (siehe auch Addiernetz).
Der CSA addiert zwei n-stellige Binärzahlen, verfügt also über 2n Eingänge. Da das Ergebnis einen etwaigen Übertrag enthalten kann, gibt es n+1 Ausgänge.
Beim Carry-Ripple-Addierer werden die Bits der beiden Summanden zwar parallel addiert, die etwaigen Überträge aber sequentiell von Volladdierer zu Volladdierer weitergereicht, daher ist die Laufzeit recht hoch. Der CSA dagegen berechnet die Summe nach dem Teile-und-herrsche-Prinzip. Da aber noch ungewiss ist, ob ein Übertrag vorhanden ist, muss alles doppelt berechnet werden (mit und ohne Übertrag). Über eine Logik werden die richtigen Ergebnisse ausgewählt.
Funktionsweise
- 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 Übertrag 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 Übertrag ausgeführt und je nach Vorgänger dann das richtige Ergebnis ausgewählt.
Durch dieses Prinzip ist es möglich, in nahezu logarithmischer Zeit zu addieren.