桁上げ保存加算器
2進数の和の例を考える: 10111010101011011111000000001101 + 11011110101011011011111011101111
桁上げ保存算術は2進法に対して作用するものの、2進表記を捨てることによって動作する。この方法では、和は次のように桁ごとに計算される。 10111010101011011111000000001101 + 11011110101011011011111011101111 = 21122120202022022122111011102212
この表記は従来のものとは異なるが、結果は明白である。さらに、 n {\displaystyle n} 個の加算器(ここでは32個の全加算器)があれば、各桁の結果は他のどれにも依存しないので、結果を1クロックで計算することができる。
もし加算器が二つの数だけを加算して結果を生成する必要があるのであれば、桁上げ保存加算器は、その結果を2進数に変換する必要があり、そのときに桁上げが右から左に伝播するので、役には立たない。しかし、大きな整数の算術では、単純な加算は非常にまれな演算であり、加算器は乗算器内の部分和の累算に使用される。
一桁につき2ビットの保存場所があるとすれば、各桁には0, 1, 2, 3の値を格納することができる。したがって明らかに、既にある桁上げ保存結果にもう一つの2進数を加算しても、この保存場所がオーバフローすることはない。しかし、さらにもう一つ加算するにはどうすればよいだろうか?
成功の鍵は、各部分加算の時点で、次の三つのビットを加えることである。
加えようとする数自身 0または1。
保存場所内が偶数なら0、奇数なら1。
右の桁が2未満なら0、2以上なら1。
言い換えれば、従来の加算と同じように、右の桁から桁上げを受けとり、左の桁に桁上げを渡している。しかし、左に渡す桁上げは、前回の計算の結果であって、今回の結果ではない。各クロックサイクルにおいて、桁上げは、従来の加算のように n {\displaystyle n} ステップではなく、1ステップしか移動する必要はない。
信号が長距離を移動する必要はないので、クロック周波数を上げることができる。
ただし、計算の最後には、結果を2進数に変換する必要が残っており、つまり事実上、従来の加算と同じように、桁上げが数の端から端まで移動する。しかし、もし512ビットの乗算を実行する過程で512回の加算をした後であれば、最後の変換コストは事実上512回の加算に分配され、各加算は最終的な"従来"の加算コストの1/512回分だけ負担することになる。