桁上げ保存加算器
From Wikipedia, the free encyclopedia
次の和を考える:
12345678 + 87654322 = 100000000
算術では、右から左に、"8+2=0, 桁上げ1"、"7+2+1=0, 桁上げ1"、"6+3+1=0, 桁上げ1"、のように和の最後まで計算を続ける。この方法では、右端の桁の結果はすぐにわかるものの、左端の桁の結果は、各桁の桁上げをその左に伝えていきながら、すべての桁の計算が終わるまでわからない。したがって、2個の桁の数の加算には、たとえ並列処理のできる機械を用いたとしても、に比例した時間がかかる。
電子工学的に2進数のビットを用いて言えば、このことは、個の1ビット加算器が自由に使えるとしても、桁上げが数の端から端まで伝播する可能性があるので、に比例した時間が必要であることを意味する。この伝播が終わるまで、
- 加算の結果はわからない。
- 加算の結果がある値より大きいか小さいか（例えば正か負か）はわからない。
この遅延は、桁上げ先見加算器により緩和することができる。原理的には、この遅延をに比例する程度にまで減少させることはできるが、非常に大きな数に対しては当てはまらない。それは、桁上げ先見を実装しても、信号がチップ上を移動する距離がに比例して増加し、伝播遅延も同じ比率で増加するためである。公開鍵暗号に必要とされるような512ビットから2048ビットのような大きな数に対しては、桁上げ先見は力不足である。
基本的な着想
2進数の和の例を考える:
10111010101011011111000000001101
+ 11011110101011011011111011101111
桁上げ保存算術は2進法に対して作用するものの、2進表記を捨てることによって動作する。この方法では、和は次のように桁ごとに計算される。
10111010101011011111000000001101
+ 11011110101011011011111011101111
= 21122120202022022122111011102212
この表記は従来のものとは異なるが、結果は明白である。さらに、個の加算器（ここでは32個の全加算器）があれば、各桁の結果は他のどれにも依存しないので、結果を1クロックで計算することができる。
もし加算器が二つの数だけを加算して結果を生成する必要があるのであれば、桁上げ保存加算器は、その結果を2進数に変換する必要があり、そのときに桁上げが右から左に伝播するので、役には立たない。しかし、大きな整数の算術では、単純な加算は非常にまれな演算であり、加算器は乗算器内の部分和の累算に使用される。
桁上げ保存アキュムレータ
一桁につき2ビットの保存場所があるとすれば、各桁には0, 1, 2, 3の値を格納することができる。したがって明らかに、既にある桁上げ保存結果にもう一つの2進数を加算しても、この保存場所がオーバフローすることはない。しかし、さらにもう一つ加算するにはどうすればよいだろうか？
成功の鍵は、各部分加算の時点で、次の三つのビットを加えることである。
- 加えようとする数自身 0または1。
- 保存場所内が偶数なら0、奇数なら1。
- 右の桁が2未満なら0、2以上なら1。
言い換えれば、従来の加算と同じように、右の桁から桁上げを受けとり、左の桁に桁上げを渡している。しかし、左に渡す桁上げは、前回の計算の結果であって、今回の結果ではない。各クロックサイクルにおいて、桁上げは、従来の加算のようにステップではなく、1ステップしか移動する必要はない。
信号が長距離を移動する必要はないので、クロック周波数を上げることができる。
ただし、計算の最後には、結果を2進数に変換する必要が残っており、つまり事実上、従来の加算と同じように、桁上げが数の端から端まで移動する。しかし、もし512ビットの乗算を実行する過程で512回の加算をした後であれば、最後の変換コストは事実上512回の加算に分配され、各加算は最終的な"従来"の加算コストの1/512回分だけ負担することになる。
