第6回: 乗算器(その2)
ブースのアルゴリズムを使った乗算器の設計
ブースのデコーダ
ブースのアルゴリズムでは、まずYjの値からZjを求めるときに、
Yjの値、つまりy2j, y2j+1, y2j-1の値に応じて、
被乗数Xに対して、2jビットのシフト(A)、(2j+1)ビットのシフト(B)、
2の補数を求める(M)、のいずれかの演算を組み合わせて
Zjを求めました。
これは、逆に言えばy2j, y2j+1, y2j-1の値の組(8通り)に対して
A, B, Mが0か1かを、組み合わせ論理回路で求めればよいわけです。
つまり次のような真理値表の組み合わせ論理回路を求めればよいわけです。
y(2j+1) y(2j) y(2j-1) Y(j) | A B M
---------------------------+---------
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
これから、次のような論理式が導かれるでしょう。
- A = y2j
y2-1
- B = (y2j+1y2j)・/(y2jy2j-1)
- M = y2j+1・/(y2j・y2j-1)
この論理回路を、ブースのデコーダと呼び、次のようなブロック図で
描くことにしましょう。
部分積Zjの生成
続いて、部分積Zjの生成を行います。
と書くと、乗算の結果Zは
と書くことができるのでした。
このZjを、X・Yjの部分を書き直して、次のように書くことにしましょう。
- Zj = (-1・ANj・2N + Σi=0N-1Aij・2i + Cj)・22j
つまりANjが符号をあらわし、Aijがi桁目の数、であるわけです。
まずANjは符号ですから、M=0のときにはZjの符号はXの符号と同じであり、
逆にM=1のときにはYjが負となるためにXの符号を反転させる必要があります。
同様に、A=1のときにはXを2jビットシフトさせるのですが、
このZjの式には、2jビットシフトさせる22jがすでにありますから、
i桁目、つまりAijは、Xのi桁目xiと同じになります。
しかしB=1のときには、Xを(2j+1)ビットシフトさせる必要があるので、
結果としてi桁目のAijは、Xの(i-1)桁目xi-1と同じになります。
さらにM=1のとには、Aijを求めるのに
2の補数をとらなければなりませんから、Aijを反転させ(1の補数)、
全体に1を加える必要があります。
以上から、A, B, MとANj, Aij, Cjは
次のような関係になるでしょう。
| A | B | M | 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 = /{ /(A + B) + /(MxN-1) }
- Aij = /{ /(A・xi)・/(B・xi-1) } M
- Cj = M
このような論理回路のうち、符号をつくる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を使っています。
ワレスの木
並列乗算回路では、ブースのアルゴリズムを使った場合も含めて、
部分積の「和」をビットごとに求めているわけですが、
この「和」は、「全加算器という3つの数I1, I2, I3を足して、
和SとキャリーCを求める」操作、と見ることができます。
(「VLSI工学-基礎・設計編-」(岩田、コロナ社)p.56より)
この「和」を求める操作を、何ビットかをまとめて行ってしまうと、
結果として部分積を求める全加算器の段数を減らすことができます。
何ビット分をまとめるかによって構成は変わってきますが、
4〜6ビット分についてまとめると上の図のようになります。
このような回路をワレスの木 (Wallace Tree)と呼びます。
(ビット数が4以上の場合には、加算の結果が{C, S}の2ビットを超えるので、
キャリー入力Ciとキャリー出力Cがあることに注意)
何ビット分まとめるか、は、回路規模や演算速度などから
選択することになります。
(「CMOS集積回路」(榎本忠義, 培風館)p.169より)
このワレスの木を部分積の和のところに使った回路を
例として「眺めて」おくことにしましょう。
例えば四角で囲ったところに、(6入力の)ワレスの木が
使われていることがわかります。
乗算器の設計例
ここまで、いろいろな乗算器の設計方法をみてきました。
最後に、3種類設計した例を並べて比較をしてみましょう。
| 乗算器A | 乗算器B | 乗算器C |
| 構成(部分積生成) | 2次ブース | 2次ブース | 2次ブース |
| 構成(部分積加算) | CSA | Wallace木 | Wallace木 |
| 構成(桁上げ吸収) | BCLA | BCLA | CLA |
| 最高動作周波数[MHz] | 134.6 | 156.3 | 83.2 |
| MOSFET数(部分積生成)[個] | 3,328 | 3,328 | 3,328 |
| MOSFET数(部分積加算)[個] | 3,780 | 3,136 | 3,136 |
| MOSFET数(桁上げ吸収)[個] | 1,990 | 1,990 | 1,376 |
| MOSFET数(全体)[個] | 9,098 | 8,454 | 7,840 |
(「CMOS集積回路」(榎本忠義, 培風館)p.175より)
(「VLSI工学-基礎・設計編-」(岩田、コロナ社)p.56より)
