続いて3ビット同士の掛け算の回路を考えます。0から7までの2数の掛け算です。最初に足し算を繰り返して答えを出す方法を考えます。例えば4 x 3 = 4 + 4 + 4 = 12 のように被乗数(4)を乗数の数だけ(3回)足す回路です。
その回路の一例が図2-10です。見にくくてすいません。これは決して綺麗な回路ではないし効率もよくないでしょうが、説明のしやすさを優先しています。左側に入力が6つあり、上3つが被乗数、下3つが乗数の入力 (いずれも下から1ビット目～3ビット目)です。仕組みは被乗数にとりあえず1～7回足したものを用意しておいて、マルチプレクサを使って乗数でセレクトして目的の結果を出力しています。
図2-10. 足し算を繰り返す方式の乗算回路
図2-11. x1からx7の結果を出力するワイヤ
図2-11は上記の回路の一部を拡大したものですが、沢山の加算器がありますが、赤の四角で囲ったワイヤの部分がそれぞれ、被乗数を1回足した結果, 2回足した結果, 3回足した結果, …, 6回足した結果になっています(図2-11は被乗数が7のときの例. 赤い矢印部分が7回足した結果)。
そして用意された6個の各マルチプレクサの入力に1～7回足した結果が配線されています。乗数はマルチプレクサのセレクタに配線され、1～7回足された結果のうち選択された1つ(つまり選択した乗数)の結果が右側に出力される仕組みになっています。
この方法は3ビット同士の掛け算くらいなら良いですが、桁数が増えると回路が膨大な大きさになってすぐ破綻することは想像に難くないでしょう。
※全加算器の入力の1つが0v(GND)になっているものがありますが、勿論これらは半加算器に取り換えることもできます。
上記の乗算回路は桁数が増えるほど加算器も指数関数的な数が必要になるため、大きな桁数に使うのは難しそうです。 そうであれば、順序回路つまりDフリップフロップを使って同じ回路で繰り返し足し算を行えれば、それほど加算器を増やさなくても桁数を増やせそうです。この考え方を使った回路を図2-12に組んでみました。
図2-12. Dフリップフロップを使った乗算回路
使い方ですが、左側の6つのインプットに「3ビットの被乗数」と「3ビットの乗数」をセットし、一番下にあるスイッチを入れると計算が始まります。被乗数がクロックごとに足され、乗数に達すると足し算が止まるようになっています。例えば2×3なら2→4→6とクロックごとに2が加算されゆき、最後に6が右側に出力され変化が止まります。 回路はシンプルになりましたが、この回路も(加算器は少なくて済みますが)乗数が大きくなればなるほど計算が終わるまでに(クロック数ぶん)時間がかかることになります。
なお乗数を入力する下側の3ビットは0から7までインクリメントするカウンタ回路に繋がっており、カウンタの数が乗数の入力と同じになると(xor＋orゲートの出力がlowとなり)、足し算を止める仕組みになっています。
またトランジスタのレベルに戻って考えると、トランジスタ単体でもゲートやベースに電荷がたまって動作するようになる(=信号を次に伝える)までには(わずかな)時間がかかります。従ってトランジスタがいくつも直列に繋がるような回路では結果が出力されるまでに時間が多く掛かることになります。クロック周期が早すぎると、結果が出力される前に次のクロックが始まってしまうことも考えられます。こうなると正しい結果が得られないため、クロック周波数は組み合わせ回路が結果を出力するまでにかかる時間より十分に遅い必要があります。Dフリップフロップから次のDフリップフロップまでの組み合わせ回路のなかでも最も時間がかかる経路をクリティカルパスと言いますが、このクリティカルパスをなるべく短くすることも回路設計の上で大変重要になります。
なお図2-12の疑似コードを書くと以下のようになると思います。a = (被乗数: 0~7の整数)
b = (乗数: 0~7の整数)
i = 0
total = 0
while(1) {
if(i != b) {
total = total + a
i++
}
print(total)
}
クロックごとにwhileの中身が繰り返され、iが乗数(b)に達するまでtotalに被乗数(a)が加算されます。
筆算を模した組み合わせ回路を作ることも可能です。図2-13は4ビット同士(まで)の乗算回路です。
これまでの回路と同様に左側に4ビットずつの入力があり、右側に8ビットの出力があります。
図2-13. 筆算を模した乗算回路
回路の仕組みを図2-14にまとめています。右側に2進数での1011 x 1101の筆算を示していますが、 色付きのボックスの部分が左の回路図の対応する色のAND回路の出力になっています(ビットの組み合わせ分(4 x 4 =) 16個あります)。 筆算の茶色の①～③に示した範囲の足し算の結果が、回路図の茶色の①～③の出力に対応します。
計算結果は10001111となり、10進数にすると 11 x 13 = 143 で正しい結果が導かれているのが分かります。
図2-14. 筆算を模した回路の仕組み
つまり、掛け算をするにも色々な方法がありますが、どの方法にしても回路図に落とし込もうと思って頑張れば可能なのです。 勿論ゲートの数が現実的でなかったり、計算に必要なクロック回数が膨大で現実的でなかったりもしますが、工夫次第、 つまりアルゴリズム次第で効率的な回路図を描くことも可能です。究極的には(実は)プログラミングで記述可能なことは電子回路に置き換えることが可能なのです。
なお、今回示したような単純な乗算回路では桁数が多いと特に加算部分のキャリーを待つ必要があるため時間がかかります。 それを高速化する方法として、ウォレス木型乗算器などの方法があるそうです。