ブースのアルゴリズム
乗算器の高速化のためには、部分積の段数を減らすことが効果的ですが、
そのためのうまい方法として、ブースのアルゴリズム (Booth's algorithm)
というものが知られています。
まず、被乗数Xと乗数Yを、N桁の符号つきの2進数で
次のようにあらわすことにします。
- X = -1・xN-12N-1 +
n=0N-2 xn・2n
- Y = -1・yN-12N-1 +
n=0N-2 yn・2n
ここで、やや唐突ですが、次のようなYjを考えましょう。
このようなYjに対して、次のようにYを求めることにしましょう。
たとえばj = 0, 1, 2を順番に足してみる(つまりN=6)と、
次のようになります。
- Y0・20 + Y1・22
+ Y2・24
= (y0 + y-1 - 2y1)・20
+ (y2 + y1 - 2y3)・22
+ (y4 + y3 - 2y5)・24
= -1・y5・25
+ n=04 yn・2n
ただしy-1 = 0とおきました。
つまり、もともとのYそのものとなるわけです。
一応証明しておきましょう。
- y2jの項はYjのみに含まれ、
Yを求める式ではy2j・22jとなる。
- y2j-1の項は、YjとYj+1に含まれ、
Yを求める式の中で、y2j-1が出てくる項は次のとおり。
Yj・22j + Yj+1・22(j+1)
→ (-2yj+1)・22j + yj+1・22(j+1)
= yj+1(22j+2-22j+1)
= yj+1・22j+1
- j=(N-2)/2のとき、Y(N-2)/2の最後には
-2yN-1という項があるが、
これが含まれる項は、
-2yN-1・2N-2 = -1・yN-1・2N-1
- 以上から、これらをすべて足したものは、Yとなる。
さてこのYの表現を使うと、Z = X・Yは次のように求められます。
- Z = X・j=0(N-2)/2Yj・22j
= j=0(N-2)/2Zj (とおくことにする)
ここでZjはj段目の部分積で、次のように書くことができます。
- Zj = X・Yjj・22j
= (-1・xN-12N-1 +
n=0N-2 xn・2n)
・(y2j + y2j-1 - 2y2j+1)・22j
つまり乗算結果Zを求めるためには、jを0から順に
XをYj・22j倍ずつして求めたZjを
足していけばよいわけです。
ポイントは、この加算が、(N-2)/2回、つまり普通に部分積を足していく場合の
半分程度の回数で済む、ということです。
これは、y2j +y2j-1 - 2y2j+1という項を
使って、1個とばしで部分積を足していく方法、と考えることができます。
このうち、Yjに含まれる
y2j, y2j-1, y2j+1の組み合わせは
8通りしかありませんから、それをまとめると次のようになるでしょう。
| y2j+1 | y2j | y2j-1 |
Yj |
Zj |
Zjを求める作業 |
Q1 | Q2 | QN |
| 0 | 0 | 0 | 0 | 0 |
何もしない |
0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
2j ビットシフト |
1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
2j ビットシフト |
1 | 0 | 0 |
| 0 | 1 | 1 | 2 | 0 |
(2j+1)ビットシフト |
0 | 1 | 0 |
| 1 | 0 | 0 | -2 | 0 |
(2j+1)ビットシフトし、2の補数 |
0 | 1 | 1 |
| 1 | 0 | 1 | -1 | 0 |
2j ビットシフトし、2の補数 |
1 | 0 | 1 |
| 1 | 1 | 0 | -1 | 0 |
2j ビットシフトし、2の補数 |
1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 |
何もしない |
0 | 0 | 0 |
ここで、Q1, Q2, QNは、Zjを求める作業で、
するべき操作を示す、次のような数値です。
- Q1=1のとき、2j ビットシフトする
- Q2=1のとき、(2j+1)ビットシフトする
- QN=1のとき、シフトし結果の2の補数を求める(=-1をかける)
このように乗算を行う方法を
ブースのアルゴリズム (Booth's algorithm)と呼びます。