第5回: 乗算器(その1)

今回から2回ほどにわたって、掛け算をする回路、つまり乗算器についてみていきましょう。もちろん乗算は加算の繰り返しですが、非常によく使う演算なので、乗算器自体に関して、いろいろな工夫が知られています。

2進数の乗算

乗算の基本は、やはり筆算です。例えば4桁の2進数の掛け算「1001×0101」(10進数で、9×5=45)を次のように求めることができるでしょう。

    1001  ：被乗数(X)
×) 0101  ：乗数  (Y)
----------
    1001  ：部分積
   0000
  1001
 0000
---------
 0101101 (0x2d = 45(dec))

乗数Yの各桁に対して、被乗数Xを順番にずらして並べていき、最後にすべてを足すわけですが、途中の、被乗数Xを順番にずらしていった項を 部分積と呼びます。部分積を求めるのは簡単で、被乗数Yの、その桁が1であればXそのもの、その桁が0であれば0、となります。

一般に、N桁の被乗数Xと乗数Yを、次のように表現することにしましょう。

X = ∑_n=0^N-1 x_n・2ⁿ
Y = ∑_n=0^N-1 y_n・2ⁿ

つまり最上位ビット(MSB)がx_N-1, y_N-1で、最下位ビット(LSB)がx₀, y₀とするわけです。これを使うと、XとYの積Zは、次のように書くことができるでしょう。

Z = X・Y = (∑_n=0^N-1 x_n・2ⁿ) ・(∑_m=0^N-1 y_m・2^m) = ∑_m=0^N-1{ ∑_n=0^N-1 (x_n・y_m)}2^n+m

ちなみに筆算で書くと、例えば4桁の場合だとこんな感じです。

                                  x3      x2       x1     x0    被乗数X
                           ×)    y3      y2       y1     y0    乗数Y
                        ---------------------------------------
                                x3・y0  x2・y0  x1・y0  x0・y0  部分積0
                        x3・y1  x2・y1  x1・y1  x0・y1          部分積1
                x3・y2  x2・y2  x1・y2  x0・y2                  部分積2
        x3・y3  x2・y3  x1・y3  x0・y0                          部分積3
---------------------------------------------------------------
  z7      z6      z5      z4      z3      z2      z1      z0    積Z

並列乗算回路

もっとも直感的な乗算器の作り方は、この筆算をそのまま回路にする、というものです。つまり部分積x_i・y_jを求める回路と、上から下へ部分積を加算していく、という筆算の手順のとおりに並べる、という方法です。

(「VLSI工学-基礎・設計編-」(岩田、コロナ社)p.55より)
結局1桁の2進数の乗算は、AND演算そのものですから、それぞれの部分積x_i・y_jをANDゲートで求めつつ、上から下へ足していく加算を行う回路を並べていけばよいことになります。

この回路の部分積の加算の部分は、ちょっと工夫がしてあって、全加算器の入力が3つであることを使って、 1つの行(横並び)の中でキャリーの伝播をさせず、それを、次の行の全加算器の入力のひとつにつないであります。 (このような構成を、キャリー保存加算器(CSA)と呼びます) ただし最後(一番下)に、前の行(最後の部分積の和を求めている)から先送りされていたキャリーをすべて最後の結果に反映させる (キャリーの吸収と呼びます)必要がありますので、最後の行だけは、普通の多ビット加算器が必要になり、キャリー伝播加算器(RCA)やキャリー先見加算器(CLA)などが使われます(この例ではCLAを使っている)。このような構成の乗算器を並列乗算回路と呼びます。

並列乗算回路では、部分積の段数、つまり乗数Yの桁数分とほぼ等しい数だけ加算器が並びますので、この段数が、全体の演算時間を決めるもっとも大きな要因となります。

ブースのアルゴリズム

乗算器の高速化のためには、部分積の段数を減らすことが効果的ですが、そのためのうまい方法として、ブースのアルゴリズム (Booth's algorithm) というものが知られています。

まず、被乗数Xと乗数Yを、N桁の符号つきの2進数で次のようにあらわすことにします。

X = -1・x_N-12^N-1 + ∑_n=0^N-2 x_n・2ⁿ
Y = -1・y_N-12^N-1 + ∑_n=0^N-2 y_n・2ⁿ

念のため確認しておくと、2の補数で負の数を表すと、例えば3桁の場合、最上位ビットx₂が0の場合と1の場合を並べて比べてみると、次のようになります。

  x2=0(正の数)  x2=1(負の数)
----------------------------
  000 (0)       100 (-4)
  001 (1)       101 (-3)
  010 (2)       110 (-2)
  011 (3)       111 (-1)

つまり最上位ビットx_3-1が0の数から、 -4 = -1・2^3-1をひくと、最上位ビットx_3-1だけを1にした数、になっていますから、先の式のように、「-1・x_N-12^N-1」という項を含めて、負の数と正の数をまとめて表すことができるわけです。

ここで、やや唐突ですが、次のようなY_jを考えましょう。

Y_j = y_2j +y_2j-1 - 2y_2j+1

このようなY_jに対して、次のようにYを求めることにしましょう。

Y = ∑_j=0^(N-2)/2 Y_j・2^2j

たとえばj = 0, 1, 2を順番に足してみる(つまりN=6)と、次のようになります。

Y₀・2⁰ + Y₁・2² + Y₂・2⁴ = (y₀ + y_-1 - 2y₁)・2⁰ + (y₂ + y₁ - 2y₃)・2² + (y₄ + y₃ - 2y₅)・2⁴
= -1・y₅・2⁵ + ∑_n=0⁴ y_n・2ⁿ

ただしy_-1 = 0とおきました。つまり、もともとのYそのものとなるわけです。一応証明しておきましょう。

y_2jの項はY_jのみに含まれ、 Yを求める式ではy_2j・2^2jとなる。
y_2j-1の項は、Y_jとY_j+1に含まれ、 Yを求める式の中で、y_2j-1が出てくる項は次のとおり。
Y_j・2^2j + Y_j+1・2^2(j+1) → (-2y_j+1)・2^2j + y_j+1・2^2(j+1) = y_j+1(2^2j+2-2^2j+1) = y_j+1・2^2j+1
j=(N-2)/2のとき、Y_(N-2)/2の最後には -2y_N-1という項があるが、これが含まれる項は、 -2y_N-1・2^N-2 = -1・y_N-1・2^N-1
以上から、これらをすべて足したものは、Yとなる。

さてこのYの表現を使うと、Z = X・Yは次のように求められます。

Z = X・∑_j=0^(N-2)/2Y_j・2^2j = ∑_j=0^(N-2)/2Z_j (とおくことにする)

ここでZ_jはj段目の部分積で、次のように書くことができます。

Z_j = X・Y_j・2^2j = (-1・x_N-12^N-1 + ∑_n=0^N-2 x_n・2ⁿ) ・(y_2j + y_2j-1 - 2y_2j+1)・2^2j

つまり乗算結果Zを求めるためには、jを0から順に XをY_j・2^2j倍ずつして求めたZ_jを足していけばよいわけです。

ポイントは、この加算が、(N-2)/2回、つまり普通に部分積を足していく場合の半分程度の回数で済む、ということです。これは、y_2j +y_2j-1 - 2y_2j+1という項を使って、1個とばしで部分積を足していく方法、と考えることができます。

このうち、Y_jに含まれる y_2j, y_2j-1, y_2j+1の組み合わせは 8通りしかありませんから、それをまとめると次のようになるでしょう。

y_2j+1 y_2j y_2j-1 Y_j Z_j Z_jを求める作業 A B M

0 0 0 0 0 何もしない 0 0 0

0 0 1 1 X・2^2j 2j ビットシフト 1 0 0

0 1 0 1 X・2^2j 2j ビットシフト 1 0 0

0 1 1 2 X・2^2j+1 (2j+1)ビットシフト 0 1 0

1 0 0 -2 -X・2^2j+1 (2j+1)ビットシフトし、2の補数 0 1 1

1 0 1 -1 -X・2^2j 2j ビットシフトし、2の補数 1 0 1

1 1 0 -1 -X・2^2j 2j ビットシフトし、2の補数 1 0 1

1 1 1 0 0 何もしない 0 0 0

ここで、A, B, Mは、Z_jを求める作業で、するべき操作を示す、次のような数値です。

A=1のとき、2j ビットシフトする
B=1のとき、(2j+1)ビットシフトする
M=1のとき、シフトし結果の2の補数を求める(=-1をかける)

このように乗算を行う方法を ブースのアルゴリズム (Booth's algorithm)と呼びます。

ブースのアルゴリズムの例

ブースのアルゴリズムを使って、乗算を実際にやってみましょう。たとえば6桁で、X = -9, Y = +25 の積を求めてみましょう。

まずX, Yを2進数で求めると次のようになります。

X = 11 0111 = x₅x₄x₃x₂x₁x₀
Y = 01 1001 = y₅y₄y₃y₂y₁y₀

いまの場合、N=6ですから、j は0～(N-2)/2、つまり0～2まで求めればよく、Y_jは次のようになるでしょう。

j	y_2j+1	y_2j	y_2j-1	Y_j	Z_j
0	0	1	0	1	X・2⁰
1	1	0	0	-2	-2X・2²
2	0	1	1	2	2X・2⁴

このZ_jをすべて加算すると、次のようになるでしょう。

Z0 =                  11111110111 (11桁にあわせる)
Z1 = -2・  11011100 = 00001001000 (11桁にあわせる)
Z2 =  2・1101110000 = 11011100000
----------------------------------
                      11100011111

この求められた結果は、2進数で2の補数の00011100001 = 225の負の数=-225ですから、たしかに-9×25 = -225となっていることがわかります。

配布資料(第5回・第6回) (PDF形式)