符号付き乗算(定数加算法)
乗算器のアルゴリズムといえばBaugh-Wooleyしかないと思っていたら、日本IBMの小林芳直氏がセミナーで定数加算法というものを紹介していて、いろいろなやり方があるものだと思った。
◇
定数加算法のアイデアは、異なるビット幅の加算をするとき、符号拡張しなくてすむように定数を分離するというものである。(符号拡張はファンアウトが大きいので動作速度が遅くなる）
すなわち、足すときは
引くときは
と定数を分離すると残りの部分は符号拡張しなくてよくなっている。また定数同士は事前に計算しておける。
◇◇
乗算のときは、Baugh-Wooleyのアルゴリズムで既に符号拡張は不要になっているのでありがたみはないが、比較してみるとおもしろい。
(n+1)ビットと(m+1)ビットの符号付き乗算は前項で計算したように
ここで第2項、第3項の引き算を足し算に直すのだが、前項とは違って次のようにする。まず第2項は
第3項も同様にして
これらを代入すると、結局、次式が得られる。
例えば5ビット(n=4)と3ビット(m=2)の乗算は次のようになる。
|
a4 a3 a2 a1 a0 *) b2 b1 b0 ----------------------------------- ~(a4･b0) a3･b0 a2･b0 a1･b0 a0･b0 ~(a4･b1) a3･b1 a2･b1 a1･b1 a0･b1 ~(a3･b2)~(a2･b2)~(a1･b2)~(a0･b2) a4･a2 -1 1 1 ------------------------------------------------------ p7 p6 p5 p4 p3 p2 p1 p0 |