„Conditional-Sum-Addition“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
→Funktionsweise: "Überlauf" -> "Übertrag"; "Schwierigkeit" entfernt |
Keine Bearbeitungszusammenfassung |
||
| Zeile 3: | Zeile 3: | ||
Der CSA 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. |
Der CSA 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 CSA dagegen berechnet die Summe nach dem [[Teile und herrsche (Informatik)|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. |
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 CSA dagegen berechnet die Summe nach dem [[Teile und herrsche (Informatik)|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 ([[Multiplexer]]) werden die richtigen Ergebnisse ausgewählt. |
||
== Funktionsweise == |
== Funktionsweise == |
||
Version vom 13. November 2010, 21:57 Uhr
Der Conditional Sum Addierer (kurz: CSA) ist ein elektronischer Baustein zur Addition mehrstelliger Binärzahlen (siehe auch Addiernetz).
Der CSA 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 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 (Multiplexer) 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.