Prefix adder

60年くらい前, 東大物理学科高橋研究室でパラメトロン計算機PC-1を作っていたころ, 36ビットの並列加算器で, 高速に繰上げ(carry)したいという問題があった.

後藤さんはパラメトロンの多数決素子を巧妙に使い, 桁数に対して対数時間で繰上げを検出する回路を考案して, それを取り入れた.

先日出版されたDigital Design and Computer Architecture Arm Editionを眺めていたら, 同じような考えによる, Prefix Adderという回路の話があった. 今回は それが話題である.





この上の図が16ビットの二進数A_i, B_i (i=0,1,...,15)と下から来る繰上げC_inを足すときのCarry-Lookaheadの回路だ.

上の図の上段の白い四角, 中頃の黒い四角, 下段の角のとれた白い四角の説明が下の図である.

ある桁 i が, 下の桁 i-1 からの繰上げの有無に関係なく, 上の桁 i+1 へ繰上げを生じるとき, 繰上げをgenerateするということで, G_i=1, そうでないとき, G_i=0とする. A_iとB_iが共に1なら繰上げがあるから, G_i=A_iB_i.

ある桁 i が, 下の桁 i-1 からの繰上げを上の桁 i+1 へ伝えるとき, 繰上げをpropagateするということで, P_i=1, そうでないとき, P_i=0とする. A_iとB_iのいずれかが1なら繰上げがあるから, P_i=A_i+B_i.

そうすると, i からi+1へ出る繰上げC_iは

C_i=G_i+P_iC_i-1

になる. このGやPをPrefixという.

これは単一の桁についての話であったが, iからjの桁のブロックについても同じことがいえる. ただG_i, P_iの代わりにG_i:j, P_i:jのように書く.

そうだと思って上の図を見てみると, 左下のあたりに黒四角で左下隅に14:-1と書いたものがある. つまり15の桁への下全体のブロックからの繰上げはG_14:-1 (と, P_14:-1 と, C_in) で決るということを示す.

G_iとP_iがA_iとB_iとで書けたように, G_i:jとP_i:jがそのブロックを途中で分けたG_i:kとG_k+1:j, P_i:kとP_k+1:jで同じように書くと, G_i:jはi,k間で繰上げが出るか, k+1,j間で繰上げが出て, i,k間で繰上げが伝わるかだから, G_i:j=G_i:k+P_i,kG_k-1,j.

P_i:jはi,k間でもk-1,j間でも繰上げが伝わるかだから, P_i:j=P_i:kP_k-1:j.

ここまではDigital Designの本に書いてあることだ. 上の図のように半分, 半分と区間を分るにはi,jからkをどう決めればよいかは, この本には書いてない. そこがこの本とThe Art of Computer Programmingの違うところである. TAOCPならk(i,j)が詳しく記述してある筈だ.

しかしそう難しいことではなくて, λx(x>0)をxを二進法で表したとき, 最も左にある1のビット番号とすると, (λ1=0, λ2=1,λ3=1, λ4=2,...)

k=2^λ(i-j)+j

と簡単に得れれる. Schemeでシミュレートしてみたが, これで合っているようであった.