2の補数の乗算(定数加算法)

[] [] []


乗算器のアルゴリズムといえばBaugh-Wooleyしかないと思っていたら、日本IBMの小林芳直氏がセミナーで定数加算法というのを説明していたのを聴いて、いろいろなやり方があるものだと思った。

定数加算法のアイデアは、異なるビット幅の加算をするとき、符号拡張しなくてすむように定数を分離するというものである。(符号拡張はファンアウトが大きいので動作速度が遅くなる)

すなわち、足すときは

引くときは

と定数を分離すると残りの部分は符号拡張しなくてよくなっている。また定数だけ別途計算しておける。

◇◇

乗算のときは、Baugh-Wooleyのアルゴリズムで既に符号拡張は不要になっているのであまりありがたみはないが、比較してみるとおもしろい。

(n+1)ビットと(m+1)ビットの2の補数の乗算は前項で計算したように

ここで第2項、第3項の引き算を足し算に直すのだが、前項とは違って次のようにする。まず第2項は

3項も同様にして

これらを代入すると、結局、次式が得られる。

例えば5ビット(n=4)3ビット(m=2)の乗算は次のようになる。


[] [] []