第10回: 乗算器(その3)

ブースのアルゴリズムを使った乗算器の設計(続)

部分積Z_jの生成

• Z_j = X・Y_j・2^2j

• Z = Σ_j=0^(N-2)/2Z_j

• Z_j = (-1・A_Nj・2^N + Σ_i=0^N-1A_ij・2ⁱ + C_j)・2^2j

まずA_Njは符号ですから、QN=0のときにはZ_jの符号はXの符号と同じであり、 逆にQN=1のときにはY_jが負となるためにXの符号を反転させる必要があります。

同様に、Q1=1のときにはXを2jビットシフトさせるのですが、 このZ_jの式には、2jビットシフトさせる2^2jがすでにありますから、 j桁目、つまりA_ijは、Xのj桁目x_jと同じになります。 しかしQ2=1のときには、Xを(2j+1)ビットシフトさせる必要があるので、 結果としてj桁目のA_ijは、Xの(j-1)桁目x_j-1と同じになります。

さらにQN=1のとには、A_ijを求めるのに 2の補数をとらなければなりませんから、A_ijを反転させ(1の補数)、 全体に1を加える必要があります。

以上から、Q1, Q2, QNとA_Nj, A_ij, C_jは 次のような関係になるでしょう。

Q1	Q2	QN	ANj	Aij	Cj
0	0	0	0	0	0
1	0	0	xN-1	xi	0
0	1	0	xN-1	xi-1	0
0	1	1	/xN-1	/xi-1	1
1	0	1	/xN-1	/xi	1

これから、A_Nj, A_ij, C_jは次のような論理式になるでしょう。

• A_Nj = /{ /(Q1 + Q2) + /(QNx_N-1) }
• A_ij = /{ /(Q1・x_i)・/(Q2・x_i-1) } QN
• C_j = QN

全体の構成

ワレスの木

この「和」を求める操作を、何ビットかをまとめて行ってしまうと、 結果として部分積を求める全加算器の段数を減らすことができます。

何ビット分をまとめるかによって構成は変わってきますが、 3〜9ビット分について、まとめてみました。 このような回路をワレスの木 (Wallace Tree)と呼びます。 (ビット数が4以上の場合には、加算の結果が{C, S}の2ビットを超えるので、 キャリー入力CIとキャリー出力COがあることに注意) 何ビット分まとめるか、は、回路規模や演算速度などから 選択することになります。

このワレスの木を部分積の和のところに使った回路を 例として「眺めて」おくことにしましょう。 例えば四角で囲ったところに、(6入力の)ワレスの木が 使われていることがわかります。

(出典: 榎本忠義「CMOS集積回路」p.169より抜粋) ※クリックすると大きくなります

乗算器の設計例