桁上げ保存加算器

桁上げ保存加算器（けたあげほぞんかさんき、Carry-save adder）^[1]^[2]は加算器の一種で、計算機などで3個以上の二進法 $n$ ビットの数の和を計算するのに使用される。他の加算器とは異なり、入力と同じサイズの二つの数（部分和ビットの列と桁上げビットの列）を出力する。

動機

次の和を考える:

   12345678
+  87654322
= 100000000

算術では、右から左に、"8+2=0, 桁上げ1"、"7+2+1=0, 桁上げ1"、"6+3+1=0, 桁上げ1"、のように和の最後まで計算を続ける。この方法では、右端の桁の結果はすぐにわかるものの、左端の桁の結果は、各桁の桁上げをその左に伝えていきながら、すべての桁の計算が終わるまでわからない。したがって、2個の $n$ 桁の数の加算には、たとえ並列処理のできる機械を用いたとしても、 $n$ に比例した時間がかかる。

電子工学的に2進数のビットを用いて言えば、このことは、 $n$ 個の1ビット加算器が自由に使えるとしても、桁上げが数の端から端まで伝播する可能性があるので、 $n$ に比例した時間が必要であることを意味する。この伝播が終わるまで、

加算の結果はわからない。
加算の結果がある値より大きいか小さいか（例えば正か負か）はわからない。

この遅延は、桁上げ先見加算器により緩和することができる。原理的には、この遅延を $\log n$ に比例する程度にまで減少させることはできるが、非常に大きな数に対しては当てはまらない。それは、桁上げ先見を実装しても、信号がチップ上を移動する距離が $n$ に比例して増加し、伝播遅延も同じ比率で増加するためである。公開鍵暗号に必要とされるような512ビットから2048ビットのような大きな数に対しては、桁上げ先見は力不足である。

基本的な着想

2進数の和の例を考える:
10111010101011011111000000001101 + 11011110101011011011111011101111

桁上げ保存算術は2進法に対して作用するものの、2進表記を捨てることによって動作する。この方法では、和は次のように桁ごとに計算される。
10111010101011011111000000001101 + 11011110101011011011111011101111 = 21122120202022022122111011102212

この表記は従来のものとは異なるが、結果は明白である。さらに、 $n$ 個の加算器（ここでは32個の全加算器）があれば、各桁の結果は他のどれにも依存しないので、結果を1クロックで計算することができる。

もし加算器が二つの数だけを加算して結果を生成する必要があるのであれば、桁上げ保存加算器は、その結果を2進数に変換する必要があり、そのときに桁上げが右から左に伝播するので、役には立たない。しかし、大きな整数の算術では、単純な加算は非常にまれな演算であり、加算器は乗算器内の部分和の累算に使用される。

桁上げ保存アキュムレータ

一桁につき2ビットの保存場所があるとすれば、各桁には0, 1, 2, 3の値を格納することができる。したがって明らかに、既にある桁上げ保存結果にもう一つの2進数を加算しても、この保存場所がオーバフローすることはない。しかし、さらにもう一つ加算するにはどうすればよいだろうか？

成功の鍵は、各部分加算の時点で、次の三つのビットを加えることである。

加えようとする数自身 0または1。
保存場所内が偶数なら0、奇数なら1。
右の桁が2未満なら0、2以上なら1。

言い換えれば、従来の加算と同じように、右の桁から桁上げを受けとり、左の桁に桁上げを渡している。しかし、左に渡す桁上げは、前回の計算の結果であって、今回の結果ではない。各クロックサイクルにおいて、桁上げは、従来の加算のように $n$ ステップではなく、1ステップしか移動する必要はない。

信号が長距離を移動する必要はないので、クロック周波数を上げることができる。

ただし、計算の最後には、結果を2進数に変換する必要が残っており、つまり事実上、従来の加算と同じように、桁上げが数の端から端まで移動する。しかし、もし512ビットの乗算を実行する過程で512回の加算をした後であれば、最後の変換コストは事実上512回の加算に分配され、各加算は最終的な"従来"の加算コストの1/512回分だけ負担することになる。

欠点

桁上げ保存加算の各ステージでは、

加算の結果はすぐにわかる。
加算の結果がある値より大きいか小さいか（例えば正か負か）は、やはりわからない。

後者については、モジュラ乗算（乗算後に除算を行い、その剰余のみを用いる演算）の実装に桁上げ保存加算器を用いる際に欠点となる。中間結果がその法より大きいか小さいかがわからなければ、法を引くかどうかが決まらないためである。

モンゴメリ乗算は、結果の右端の桁に依存する演算で、この解の一つである。とはいえ、桁上げ保存加算そのものと同様、固定的なオーバヘッドがあるので、連続したモンゴメリ乗算なら時間の節約になるが、1回だけであればそうはならない。幸い、冪乗は、事実上連続した乗算で、公開鍵暗号で最も頻繁に利用される演算である。

技術的詳細

桁上げ保存ユニットは $n$ 個の全加算器で構成され、それぞれは入力された3個の数の対応するビットのみに基づいて、単一の和と桁上げのビットを計算する。3個の $n$ ビットの数 a, b, c があるとき、このユニットは部分和 ps とシフト桁上げ sc を生成する:

ps_{i}=a_{i}\oplus b_{i}\oplus c_{i}

sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i})

全体の和は次のように計算される:

桁上げ列 sc を1ビット左シフトする。
部分和列 ps の先頭（最上位ビット）に0を付け加える。
桁上げ伝播加算器（順次桁上げ加算器）を用いてこれらを加算し、結果の $n+1$ ビットの値を生成する。

3個以上の数を加算するとき、桁上げ保存加算器の後に桁上げ伝播加算器を用いる方法は、桁上げ伝播加算器を二つ用いる方法より高速である。これは、桁上げ伝播加算器では、前の桁上げビットが生成されるまで和ビットを計算できず、そのため $n$ 個の全加算器の遅延に相当する遅延があるためである。これに対して、桁上げ保存加算器は、その出力値をすべて並列に生成し、そのため単一の全加算器と同じ遅延しかもたない。したがって、桁上げ保存加算器と桁上げ伝播加算器の合計の計算時間は（全加算器の遅延を単位として） $n+1$ であるのに対して、桁上げ伝播加算器2個では $2n$ となる。

脚注

[脚注の使い方]

^ Earle, J. G. et al アメリカ合衆国特許第 3,340,388号 "Latched Carry Save Adder Circuit for Multipliers" filed July 12, 1965
^ Earle, J. (March, 1965), “Latched Carry-Save Adder”, IBM Technical Disclosure Bulletin 7 (10): 909–910

[1] Earle, J. G. et al アメリカ合衆国特許第 3,340,388号 "Latched Carry Save Adder Circuit for Multipliers" filed July 12, 1965

[2] Earle, J. (March, 1965), “Latched Carry-Save Adder”, IBM Technical Disclosure Bulletin 7 (10): 909–910

[1]

[2]