(続)ブースのアルゴリズム

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

ブースのアルゴリズムによるQ1, Q2, QNの生成

ブースのアルゴリズムでは、まずYjの値からZjを求めるときに、 Yjの値、つまりy2j, y2j+1, y2j-1の値に応じて、 被乗数Xに対して、2jビットのシフト(Q1)、(2j+1)ビットのシフト(Q2)、 2の補数を求める(QN)、のいずれかの演算を組み合わせて Zjを求めました。 これは、逆に言えばy2j, y2j+1, y2j-1の値の組(8通り)に対して Q1, Q2, QNが0か1かを、組み合わせ論理回路で求めればよいわけです。 つまり次のような真理値表の組み合わせ論理回路を求めればよいわけです。 
y(2j+1) y(2j) y(2j-1) Y(j) | Q1 Q2 QN
---------------------------+---------
  0       0      0     0   |  0  0  0
  0       0      1     1   |  1  0  0
  0       1      0     1   |  1  0  0
  0       1      1     2   |  0  1  0
  1       0      0    -2   |  0  1  1
  1       0      1    -1   |  1  0  1
  1       1      0    -1   |  1  0  1
  1       1      1     0   |  0  0  0
これから、次のような論理式が導かれるでしょう。 この論理回路を、BTDセルと名づけて、次のような記号で かくことにしましょう。

部分積Zjの生成

続いて、部分積Zjの生成を行います。 と書くと、乗算の結果Zは と書くことができるのでした。 このZjを、X・Yjの部分を書き直して、次のように書くことにしましょう。 つまりANjが符号をあらわし、Aijがi桁目の数、であるわけです。

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

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

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

以上から、Q1, Q2, QNとANj, Aij, Cjは 次のような関係になるでしょう。
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
これから、ANj, Aij, Cjは次のような論理式になるでしょう。

このような論理回路のうち、符号をつくるANjをSIBセル、 残りをSELセルと名づけ、それぞれ次のような記号でかくことにしましょう。

まずはこれらのBTDセル, SIBセル, SELセルを並べて、 例えば6ビットの乗算器の部分積の生成は次のようになるでしょう。

乗数が6ビットなのに、部分積の段数が(6-2)/2+1 = 3段で済んでいることに 注意しましょう。

全体の構成

ここまでで部分積はそろっていますから、あとはこれをキャリー保存 加算器(CSA)で足すだけです。 ただし負の数があるので、ちょっと注意をする必要があります。 例えば6ビット×6ビットの乗算器の場合、乗算結果Zは 次のように書けるでしょう。
Z = Σj=02(-1・A6j・26 + Σi=05Aij2i + Cj)22j
= Σj=02{ Σj=05Aij2i + Cj}・22j - { A6224 + A6122 + A6020}・26
= Σj=02{ Σj=05Aij2i + Cj}・22j + { /A6224 + 1・23 + /A6122 + 1・21 + /A6020 + 1・20 } ・26
(※2の補数をとるために、各ケタごとに反転していることに注意)
= Σj=02{ A5j25 + A4j24 + A3j23 + A2j22 + A1j21 + A0j20 + Cj}・22j + Σj=02{ /A6j22j・26 } + 25・22・2 + (25 + 24) 22・1
これを次のようにビットごとにならべるとわかりやすいでしょうか。

これをそのまま回路にすると、次のようになるでしょう。

最後のキャリーの吸収はRCAを使っています。