2の補数の乗算(Baugh-Wooley)

[] [] []


新入社員のころ最初の仕事が乗算器の回路設計だった。今は、FPGAに乗算器が専用ハードウェアとして埋め込まれており、大抵は論理合成できてしまうので、乗算器を設計する人はいないと思うが、前項で示した2の補数の式(2の補数)を使った計算例として紹介する。以下の計算はBaugh-Wooleyのアルゴリズムとして知られているもので、「Computer Arithmetic(Hwang)によっている。

(n+1)ビットと(m+1)ビットの2の補数の乗算を式で書くと

ここで第2項、第3項が引き算になっているので、これを足し算に直したい。

そのため、

を使って第2項、第3項を書き換えると

ここで、まだ第1項に引き算があるので足し算に直すため

を使って書き換えると、結局、次式が得られる。

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


[] [] []