コンピュータアーキテクチャの話 (82) 負の部分積の処理

　

　Wallace Treeの入力数は上位の桁では減少すると書いたが、被乗数Mが正の数であるとしてもBooth Encoderを用いる場合は-Mとか-2Mを加算する必要がある。この場合、2の補数表示の負の数は上位に”1″が並ぶことになり、Wallace Treeの上位の桁での入力数は減少しない。また、被乗数として負の数を許容する場合も同様である。しかし、部分積が負の数であるということで、正の数である場合と較べて入力数が増加するのはもったいない、何とかカウンタエレメントを節約できないかということが考えられた。

　Boot 2アルゴリズムによる16ビット乗算の部分積を加算する構成。(出典:1994年発表のGary Bewick氏の博士論文)

　この図はGary Bewick氏の博士論文から引用させて戴いたものであるが、16ビットの2進数の乗算を2ビット単位で処理するBoothアルゴリズムで生成した9個の部分積の加算を行う構成を示している。この図でSと書かれたビットは部分積の符号ビットであり、＊S(図ではSの上にバー)はその否定である。

　最初と最後の部分積を別とすると、各部分積の最上位の上に1、＊Sを付加し、最下位にSを付加しており、部分積が正の場合は最上位の上に2ビットの”11″が加算されることになる。全部の部分積を合わせて考えると、部分積が全て正の場合は最下位の部分積の上位に”1111111″と1が並ぶことになる。そして、最下位の部分積の＊S,S,Sは”100″であり、これらを合わせると、無視される最上位ビットからの桁溢れ分を別にするとキャンセルしてゼロになってしまう。

　部分積が負の場合は、部分積と”10……1″が加算されるのであるが、”10……1″は”110…0″と較べると、それに-“0100…0″と”1″を加えたものである。-“0100…0″は”1111…100….0″であるので、図の中の●のビットとして-Mの場合はMの否定を用いると、結局、積の最上位まで”1″が連続して符号拡張された形式の-Mと”110…0″の和と等しい。”110…0″は正の部分積の場合と同様にキャンセルされてしまうので、結果として-Mが加算される形になっている。

　この方式を用いることにより、部分積の上に2ビット、下に1ビットの追加で負の部分積を扱うことができ、2の補数表示で積の最上位のビットまでの全てのビットを必要とする場合に較べてカウンタエレメントの個数を減らすことが出来る。