乗算回路の話

ALUには基本的に加算、減算、論理演算がサポートされていますが、乗算や除算は演算量も多く複雑な処理を必要とされるため、実際には回路として実装されない場合もあります。浮動小数演算も同様です。

しかしながら、Amdahlの法則によると、使用頻度が中程度の演算でも、速度が遅ければ、全体の性能に悪影響を及ぼすため、こうした演算も回路として実装される方が望ましいと言えます。今回はこれらの内、乗算回路に焦点を当てていきます。

2進数の筆算

まずは、2進数の掛け算について考えます。以下の掛け算を例にします。

110_{2} \times 101_{2} = 11110_{2}

$110_{2} \times 101_{2} = 11110_{2}$

通常、人間が複数桁同士の掛け算をする時には筆算を行いますが、以下のようになります。

私たちは一連の操作を機械的に行っていますが、具体的には次のような計算を行っていると考えることができます。

図から分かるように、二桁目以降は被乗数の下桁に0を追加しながら乗数と掛け算を行っています。回路上では、この操作はビットシフトによって達成することができます。さらに、使用する数字は二種類しかなく、乗算ステップは以下のどちらかしかありません。

前節で分かったことを率直に回路に直すと以下のようになります。なお、乗数及び被乗数は32bitとして考えています。また、計算は入力がどちらも正であることを前提としています。

以下では図に示す番号と対応させながら説明します。

ここで、被乗数が64bitに拡張されているのは被乗数は32bit分だけ左にシフトされるため、オーバーフローを防ぐ必要があるためです。積結果やALUについても同様です。