Conditional-Sum-Addition

Betrachtet man eine zwei Zahlen als Bit-Folgen der Länge 3n, wobei n eine natürliche Zahl ist, so kann man diese Zahlen leicht nach dem allgemeinen Schuladditionsalgorithmus addieren.

Benutzt man jedoch Conditional Sum Addition, so kann man etwas "Zeit sparen" und zwar in dem man das Problem in Teilprobleme aufteilt. Die Idee, die dahinter steckt, basiert auf der Tatsache, dass man bei Bit-Folgen immer nur einen Übertrag von 1 oder 0 haben kann. Man berechnet also während man die Summe der ersten 2n Bit berechnet gleichzeitig die Summe der letzten n Bit, und zwar für Übertrag 1 bwz. 0 so muss man das Ergebnis nur noch für den tatsächlichen Übertrag ergänzen.

Diese beiden berechneten Summen sind die Eingänge eines n - Bit Multiplexers. Das select - Bit ist der Übertrag der vorherigen Summe. Teilt man die Ursprungswörter immer in der Mitte erhält man eine logarithmische Tiefe. Die Kosten sind jedoch logarithmisch - linear, also mehr als beim Carry-Ripple-Addierer.

Siehe auch: Carry-Ripple-Addierer, Carry-Look-Ahead, Halbaddierer, Volladdierer Vorlage:Stub