(57)【特許請求の範囲】
【請求項１】
２進数Ｎビット（Ｎは任意のビット数）の乗数から２次のブースエンコード結果を生成するブースエンコーダと、
２次のブース理論及び符号拡張方式を用いて、２進数Ｍビット（Ｍは任意のビット数）の被乗数及び前記ブースエンコード結果から部分積を生成・加算し、２個の中間積に圧縮して出力する乗算アレイと、
前記２個の中間積と前記累積データとを加算して２個の出力に絞る桁上げ保存加算器と、
前記桁上げ保存加算器からの前記２個の出力を加算して（Ｍ＋Ｎ）ビットの積和演算結果及びキャリーアウトを生成する桁上げ伝搬加算器と、
前記被乗数及び前記乗数から前記積を生成するときに（Ｍ＋Ｎ）ビットを超えるオーバーフローが発生するか否かを予測するオーバーフロー予測回路と、
前記オーバーフロー予測回路が、オーバーフローが発生しないと予測したときに前記桁上げ伝搬加算器で生成されたキャリーアウトをそのまま出力し、オーバーフローが発生すると予測したときに前記桁上げ伝搬加算器で生成されたキャリーアウトを出力させない飽和処理手段と
を有することを特徴とする積和演算回路。
【請求項２】
前記オーバーフロー予測回路は、
前記被乗数がすべて０の場合を検出するオールゼロ検出部と、
前記乗数から２次のブースエンコード結果を生成する予測用ブースエンコード部とを有し、
前記被乗数がすべて０の時にはオーバーフローが発生しないと予測し、
前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を含まないときには、オーバーフローが発生しないと予測し、
前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を複数個含むときには、オーバーフローが発生すると予測し、
前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を１個のみ含むときにおいて、−１又は−２の出力が最上位で出力される第１の場合にはオーバーフローが発生しないと予測し、−１又は−２の出力よりも上位の出力がすべて０で出力される第２の場合にはオーバーフローが発生しないと予測し、前記第１及び第２の場合以外の第３の場合にはオーバーフローが発生すると予測する
ことを特徴とする請求項１に記載の積和演算回路。
【請求項３】
前記オーバーフロー予測回路は、オーバーフローが発生すると予測したときに１を出力し、オーバーフローが発生しないと予測したときに０を出力し、
前記飽和処理手段は、前記オーバーフロー予測回路の出力と前記桁上げ伝搬加算器で生成されたキャリーアウトとを入力とする排他的論理和素子である
ことを特徴とする請求項１又は２のいずれかに記載の積和演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、並列乗算器等に用いられる積和演算回路に係り、詳細には、例えば２次ブース（Booth）理論及び符号拡張方式の乗算器を用いた積和演算回路に関する。
【０００２】
【従来の技術】
乗算器はディジタル演算処理装置において加算器、遅延回路とともに最も基本的な回路の１つであり、集積度の向上によりＭｂｉｔ×Ｎｂｉｔ乗算を一気に実行する並列乗算器も既にオンチップ化されている。並列乗算器の基本的な構造は、被乗数に乗数の１ｂｉｔを掛け合わせた結果得られる部分積生成と、生成された部分積を乗数ｂｉｔの重みに従って桁を合わせ加算する積和演算回路からなる。
【０００３】
従来のこの種の積和演算回路としては、例えば「ディジタルＣＭＯＳの回路設計」コロナ社，ｐ１８４〜ｐ１９１に記載されたものがある。
【０００４】
乗算アレイの構造を符号拡張の扱いの差により、主に３パターンの区分が広く知られており、最も単純な構造の符号拡張方式と、上記文献による符号伝搬方式及び符号生成方式（符号不拡張方式）である。
【０００５】
従来、乗算器を用いた積和演算器では累積を計算する際のオーバーフローを検出することが困難であった。累積計算時のオーバーフロー発生は後のデータの値が全く不正確となるため、信号処理等の処理ではオーバーフローは避けなければならない。これを避けるには演算実行毎にオーバーフローの発生の有無をチェックする必要がある。さらには、オーバーフローが発生した時には、計算結果を正又は負の最大値に抑える飽和演算を行う場合もある。何れにしても積和演算においてオーバーフローの検出を行うということは極めて重要なことであり、この処理を高速かつハード量を少なく実行することが望まれる。
【０００６】
本来、（Ｍｂｉｔ×Ｎｂｉｔ）の乗算を行い、（Ｍ＋Ｎ）ｂｉｔの積を得る場合、（Ｍ＋Ｎ）ｂｉｔを超えるオーバーフローを発生することはない。しかし、符号拡張方式の乗算アレイ部において、２次のブース（Booth）理論を用いた場合、部分積加算時に符号拡張部の加算によりキャリーアウトが発生することがある。これは２次のブース理論により、「−１」あるいは「−２」とエンコードされた場合の部分積は、被乗数の２の補数を（Ｍ＋Ｎ）ｂｉｔに符号（この場合、１）拡張するためである。ちなみに、更に「−２」にエンコードされた場合は１ｂｉｔ上位側にシフトする。
【０００７】
この場合、出力される桁上げ出力を無視するために、乗算アレイ部では、（Ｍ／２）個の部分積を２個の中間積に圧縮し、それらを２入力桁上げ伝搬加算器に入力し、その加算和を積として得ておき、２入力桁上げ伝搬加算器によって得た積と累積データを加算するためにはもう１つ別の２入力桁上げ伝搬加算器を用意し、その加算器に積と累積データを入力していた。
【０００８】
図４は上述した飽和演算機能付き積和演算回路の回路構成図である。
【０００９】
図４において、積和演算回路１０は、ブースエンコーダ１１、乗算アレイ１２及び２入力加算器１３，１４から構成される。
【００１０】
上記ブースエンコーダ１１は、２次のブース（Booth）理論を用いるために、乗数のうち隣り合う３ｂｉｔを選択条件とするブースエンコードを行うためのものである。
【００１１】
上記乗算アレイ１２は、被乗数にブースエンコーダ１１によりエンコードされた乗数を掛け合わせて部分積を生成する。
【００１２】
上記２入力加算器１３は、乗算アレイ１２からの部分積を加算するための加算器である。
【００１３】
上記２入力加算器１４は、２入力加算器１３からの積に累積データを加算するための加算器である。
【００１４】
このように、積和演算回路１０では、累積の計算を２入力加算器１３，１４を２段直列接続し、後段の２入力加算器１４で累積データを加算し出力された積和演算結果からオーバーフローの判定を行っていた。
【００１５】
【発明が解決しようとする課題】
しかしながら、このような従来の積和演算回路１０にあっては、累積データを加算するために２つの２入力加算器１３，１４を備えた構成となっていたため、回路規模が大きくなり、かつ遅延性能への影響も大きく動作周波数の改善が難しいという問題点があった。
【００１６】
この問題を改善するためには、２入力加算器の入力側に全加算器を設け、この全加算器で２個の中間積と累積データを加算して出力を２本に絞り、この出力を加算する方法を用いればよい。ところが、これまでは積和演算時に発生する桁上げ出力が、積生成時に生じる無視するべきオーバーフロー発生の要素を２個の中間積が含んでいるため、オーバーフロー出力が不正確となりそのまま全加算器に入力することはできなかった。
【００１７】
本発明は、積生成時の不要なオーバーフロー発生を予測することができ、飽和演算機能付き符号拡張方式の積和演算回路においても２入力加算器を２つ別々の回路で必要とせず、遅延性能及び積和演算のスループットを高めることができる積和演算回路を提供することを目的とする。
【００１８】
【課題を解決するための手段】
本発明に係る積和演算回路は、２進数Ｎビット（Ｎは任意のビット数）の乗数から２次のブースエンコード結果を生成するブースエンコーダと、２次のブース理論及び符号拡張方式を用いて、２進数Ｍビット（Ｍは任意のビット数）の被乗数及び前記ブースエンコード結果から部分積を生成・加算し、２個の中間積に圧縮して出力する乗算アレイと、前記２個の中間積と前記累積データとを加算して２個の出力に絞る桁上げ保存加算器と、前記桁上げ保存加算器からの前記２個の出力を加算して（Ｍ＋Ｎ）ビットの積和演算結果及びキャリーアウトを生成する桁上げ伝搬加算器と、前記被乗数及び前記乗数から前記積を生成するときに（Ｍ＋Ｎ）ビットを超えるオーバーフローが発生するか否かを予測するオーバーフロー予測回路と、前記オーバーフロー予測回路が、オーバーフローが発生しないと予測したときに前記桁上げ伝搬加算器で生成されたキャリーアウトをそのまま出力し、オーバーフローが発生すると予測したときに前記桁上げ伝搬加算器で生成されたキャリーアウトを出力させない飽和処理手段とを有するものである。
【００１９】
また、前記オーバーフロー予測回路が、前記被乗数がすべて０の場合を検出するオールゼロ検出部と、前記乗数から２次のブースエンコード結果を生成する予測用ブースエンコード部とを有し、前記被乗数がすべて０の時にはオーバーフローが発生しないと予測し、前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を含まないときには、オーバーフローが発生しないと予測し、前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を複数個含むときには、オーバーフローが発生すると予測し、前記被乗数がすべて０の時以外で、且つ、前記予測用ブースエンコード部によるブースエンコード結果が−１又は−２の出力を１個のみ含むときにおいて、−１又は−２の出力が最上位で出力される第１の場合にはオーバーフローが発生しないと予測し、−１又は−２の出力よりも上位の出力がすべて０で出力される第２の場合にはオーバーフローが発生しないと予測し、前記第１及び第２の場合以外の第３の場合にはオーバーフローが発生すると予測する構成としてもよい。
【００２０】
また、前記オーバーフロー予測回路が、オーバーフローが発生すると予測したときに１を出力し、オーバーフローが発生しないと予測したときに０を出力し、前記飽和処理手段は、前記オーバーフロー予測回路の出力と前記桁上げ伝搬加算器で生成されたキャリーアウトとを入力とする排他的論理和素子である構成としてもよい。
【００２３】
【発明の実施の形態】
本発明に係る積和演算回路は、２次ブース（Booth）理論及び符号拡張方式の乗算器を用いた（Ｍｂｉｔ×Ｎｂｉｔ）＋（Ｍ＋Ｎ）ｂｉｔの積和演算回路に適用することができる。
【００２４】
図１は本発明の第１の実施形態に係る積和演算回路の構成図である。図１に示す積和演算回路は符号拡張方式の乗算アレイを用いた積和演算回路に適用した例である。
【００２５】
図１において、積和演算回路１００は、入力端子１０１，１０２，１０３、ブースエンコーダ１０４、オーバーフロー予測回路１０５（オーバーフロー予測手段）、乗算アレイ１０６、桁上げ保存加算器１０７、２入力加算器１０８、排他的論理和ゲート１０９及び出力端子１１０，１１１から構成される。入力端子１０１には被乗数が、入力端子１０２には乗数が、入力端子１０３には累積データがそれぞれ入力され、出力端子１１０から積和演算結果が、出力端子１１１からオーバーフローが出力される。
【００２６】
上記桁上げ保存加算器１０７及び２入力加算器１０８は、全体として加算手段１１２を構成する。
【００２７】
上記ブースエンコーダ１０４は、入力された乗数により２次ブースエンコードを行い、エンコード結果（＋２，＋１，０，−１，−２）を出力する。
【００２８】
上記オーバーフロー予測回路１０５は、被乗数及び乗数に基づいて積生成時に不要なオーバーフローが発生するか否かを予測し、不要なオーバーフローが発生するときは「１」を、発生しないときは「０」を出力する。
【００２９】
上記乗算アレイ１０６は、符号拡張方式の乗算アレイ部であり、被乗数とブースエンコーダ１０４からの出力により（Ｍ／２）個の部分積を生成・加算し、２個の中間積に圧縮して出力する。
【００３０】
上記桁上げ保存加算器１０７は、乗算アレイ１０６から出力された２個の中間積と累積データを加算して出力を２本に絞る。
【００３１】
上記２入力加算器１０８は、桁上げ保存加算器１０７からの２本の出力を加算する（Ｍ＋Ｎ）ｂｉｔの最終桁上げ伝搬加算器であり、加算和を積和演算結果として出力し、（Ｍ＋Ｎ）ｂｉｔを超えるキャリーアウトも出力する。
【００３２】
上記排他的論理和ゲート１０９は、オーバーフロー予測回路１０５からの出力と２入力加算器１０８のキャリーアウト出力との排他的論理和をとりその排他的論理和出力をオーバーフローとして出力する。
【００３３】
このように、積和演算回路１００は、２次のブース理論を用いてブースエンコードを行うブースエンコーダ１０４と、被乗数とブースエンコーダ１０４からの出力により（Ｍ／２）個の部分積を生成・加算し、２個の中間積に圧縮して出力する乗算アレイと１０６と、被乗数及び乗数に基づいて積生成時に不要なオーバーフローが発生するか否かを予測するオーバーフロー予測回路１０５と、乗算アレイ１０６から出力された２個の中間積と累積データを加算して出力を２本に絞る桁上げ保存加算器１０７と、桁上げ保存加算器１０７からの２本の出力を加算し、加算和を積和演算結果として出力し、（Ｍ＋Ｎ）ｂｉｔを超えるキャリーアウトも出力する２入力加算器１０８と、オーバーフロー予測回路１０５からの出力と２入力加算器１０８のキャリーアウト出力との排他的論理和をとる排他的論理和ゲート１０９とを備えて構成する。
【００３４】
図２は上記オーバーフロー予測回路１０５の回路構成を示す図であり、このオーバーフロー予測回路１０５の回路動作は後述する図３のフローで示される。
【００３５】
図２において、オーバーフロー予測回路１０５は、入力端子２０１，２０２、ＡＬＬ０検出回路２０３（ＡＬＬ０検出手段）、ブースマイナス判定回路２０４、２進木・逆２進木ＡＮＤ回路２０５、ブースマイナス・１連続性判定回路２０６、ブースマイナスカウンタ２０７、２入力ＡＮＤ回路２０８，２０９、４入力ＯＲ回路２１０、ＡＮＤ回路２１１及び出力端子２１２から構成される。入力端子２０１には被乗数が、入力端子２０２には乗数がそれぞれ入力され、出力端子２１２からはオーバーフローが出力される。
【００３６】
上記ブースマイナス判定回路２０４、２進木・逆２進木ＡＮＤ回路２０５、ブースマイナス・１連続性判定回路２０６、ブースマイナスカウンタ２０７、２入力ＡＮＤ回路２０８，２０９、４入力ＯＲ回路２１０及びＡＮＤ回路２１１は、全体として判定手段２１３を構成する。
【００３７】
上記ＡＬＬ０検出回路２０３は、入力された被乗数がＡＬＬ０の場合は「１」を出力し、ＡＬＬ０でない場合は「０」を出力する。
【００３８】
上記ブースマイナス判定回路２０４は、Ｎ／２組のＡＮＤＮＲとインバータから構成され、該当する入力３ｂｉｔをブースエンコーダ１０４に入力した際に「−１」あるいは「−２」がブースエンコーダ１０４から出力される場合に「１」を出力する。
【００３９】
上記２進木・逆２進木ＡＮＤ回路２０５は、入力された乗数において最上位ｂｉｔから各奇数ｂｉｔまでの「１」の連続性の判定を行う。論理的には、最上位ｂｉｔから各奇数ｂｉｔまでの乗数を入力とする（Ｎ／２−１）出力の多入力ＡＮＤ回路となるが、２進木・逆２進木構造を採用することにより、効率的に実現することが可能である。また、乗数入力は最上位ｂｉｔ（ここでは、０）から最下位から２ｂｉｔ目（ここでは、Ｎ−３）までである。
【００４０】
上記ブースマイナス・１連続性判定回路２０６は、ブースマイナス判定回路２０４のＮ／２本の出力のうち最上位の出力を除いた（Ｎ／２−１）本とブースマイナス判定回路２０４からの（Ｎ／２−１）本の出力を入力とし、それぞれの入力を上位側から２入力ＡＮＤに入力し、出力される（Ｎ／２−１）本の信号のＯＲ論理をとることでブースマイナスを出力したエンコーダ入力より上位の乗数がＡＬＬ１である場合を検出する。
【００４１】
上記ブースマイナスカウンタ２０７は、ブースマイナス判定回路２０４の出力するＮ／２ｂｉｔの信号に含まれる「１」の個数をカウントし、０個、１個、複数個の３つのパターンに分類し、それぞれに対応する端子に「１」を出力し、他の端子には「０」を出力する。
【００４２】
上記２入力ＡＮＤ回路２０８は、ブースマイナスカウンタ２０７の「＝１」出力を入力とブースマイナス・１連続性判定回路２０６の出力を入力とし、ブースマイナスが１個であり、ブースマイナスを出力したエンコーダ入力より上位の乗数がＡＬＬ１である場合を検出する。
【００４３】
上記２入力ＡＮＤ回路２０９は、ブースマイナスカウンタ２０７の「＝１」出力を入力とブースマイナス・１連続性判定回路２０６の出力を入力とし、ブースマイナスが１個であり、ブースマイナスを出力したエンコーダが最上位のエンコーダである場合を検出する。
【００４４】
上記４入力ＯＲ回路２１０は、ブースマイナスカウンタ２０７の「≧２」出力と２入力ＡＮＤ回路２０８の否定及び２入力ＡＮＤ回路２０９の否定を入力とし、被乗数がＡＬＬ０ではない時のオーバーフローを検出する。
【００４５】
上記ＡＮＤ回路２１１は、ＡＬＬ０検出回路２０３の出力の否定と４入力ＯＲ回路２１０の出力を入力とし、積生成時に発生する不要なオーバーフローを出力する。
【００４６】
次に、上述のように構成された積和演算回路１００の動作を説明する。
【００４７】
本積和演算回路１００は、乗算には２次ブース理論と符号拡張方式を採用した乗算アレイを用い、かつ積結果と累積結果の加算器に対し、オーバーフロー予測回路１０５を設け、累積計算時に発生するオーバーフロー検出を行うことにより累積用３入力加算器を桁上げ保存加算器と２入力加算器で構成可能にしたことを特徴としている。
【００４８】
まず、積和演算回路１００の全体動作を説明し、次いで図３のフローチャートを参照しながらオーバーフロー予測回路１０５の動作について説明する。
【００４９】
図１に示すように、入力端子１０１に被乗数、入力端子１０２に乗数、入力端子１０３に累積データがそれぞれ入力されると、
ブースエンコーダ１０４は、入力された乗数により２次ブースエンコードを行い、エンコード結果（＋２，＋１，０，−１，−２）を乗算アレイ１０６に出力する。
【００５０】
一方、入力端子１０１，１０２に入力された被乗数、乗数はオーバーフロー予測回路１０５にも入力され、オーバーフロー予測回路１０５は、後述するように被乗数及び乗数に基づいて積生成時に不要なオーバーフローが発生するか否かを予測し、不要なオーバーフローが発生するときは「１」を、発生しないときは「０」を出力する。
【００５１】
乗算アレイ１０６では、符号拡張方式により、被乗数とブースエンコーダ１０４からの出力により（Ｍ／２）個の部分積を生成・加算し、２個の中間積に圧縮して桁上げ保存加算器１０７に出力する。桁上げ保存加算器１０７では、乗算アレイ１０６から出力された２個の中間積に、入力端子１０３から入力された累積データを加算して出力を２本に絞り２入力加算器１０８に出力する。
【００５２】
２入力加算器１０８では、桁上げ保存加算器１０７からの２本の出力を桁上げ加算し、積和演算結果（Ｍ＋Ｎ）ｂｉｔを出力端子１１０から出力するとともに、（Ｍ＋Ｎ）ｂｉｔを超えるキャリーアウトを排他的論理和ゲート１０９に出力する。排他的論理和ゲート１０９は、オーバーフロー予測回路１０５からの出力と２入力加算器１０８のキャリーアウト出力との排他的論理和をとりその排他的論理和出力をオーバーフローとして出力する。
【００５３】
以下、図３のフローチャートを参照しながらオーバーフロー予測回路１０５の動作を説明する。
【００５４】
図３はオーバーフロー予測回路１０５の動作を示すフローチャートであり、図２に示すオーバーフロー予測回路１０５の各部に対応する動作部分は破線で囲んでいる。
【００５５】
図３に示すフローチャートは、以下１．及び２．のような判定を段階的に行っていることを示している。なお、図中、ＳＴはフローの各ステップを示す。
【００５６】
１．被乗数がＡＬＬ０の時
オーバーフローが発生することはない。
【００５７】
２．被乗数がＡＬＬ０ではない時
(1)乗数をブースエンコードした結果、−１、−２を出力するエンコーダがない場合
オーバーフローが発生することはない。
【００５８】
(2)乗数をブースエンコードした結果、−１、−２を出力するエンコーダが複数個ある場合
オーバーフローが発生する。
【００５９】
(3)乗数をブースエンコードした結果、−１、−２を出力するエンコーダが１個のみの場合
・−１、−２が最上位で出力される時は、オーバーフローが発生することはない。
【００６０】
・−１、−２を出力するエンコーダよりも上位のエンコーダが全て「０」の時は、オーバーフローが発生することはない。なお、この場合、−１、−２を出力したエンコーダよりも上位のエンコーダの入力は、全て「１」でなければならない。エンコーダ出力が「０」となるケースはエンコーダの全出力が「０」の場合とエンコーダの全出力が「１」の場合があるが、全入力が「０」の場合は−１、−２を出力するエンコーダの１つ上位のエンコーダ出力が「０」とはなり得ないためである。
【００６１】
・上記以外の場合、オーバーフローが発生する。
【００６２】
具体的には、図３において、まず、ステップＳＴ１で入力端子２０１からＡＬＬ０検出回路２０３に被乗数Ｂ＝ｂ0，ｂ1，…，ｂn-1（但し、ｂn＝０。また、ｎは語長を表す。）１．被乗数がＡＬＬ０の時を入力し、ステップＳＴ２で数１に示す式に従って入力された被乗数ＢのＡＬＬ０をとり、ステップＳＴ３でＡＬＬ０か（Ｚ＝１か）否かを判別する。上記ステップＳＴ２及びステップＳＴ３の処理は図２のＡＬＬ０検出回路２０３に相当し、入力された被乗数ＢがＡＬＬ０の場合は「１」を出力し、ＡＬＬ０でない場合は「０」を出力することになる。
【００６３】
【数１】
0003710193.tif 000002
【００６４】
ステップＳＴ３でＺ＝１と判別したときは被乗数ＢがＡＬＬ０であるからオーバーフローが発生することはないと判断しステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終える。
【００６５】
ステップＳＴ３でＺ＝０と判別したときは被乗数ＢがＡＬＬ０でない時であるから上述したように乗数のブースエンコードの結果として、オーバーフローが発生する可能性があると判断してステップＳＴ５に進む。ステップＳＴ５では、入力端子２０２からブースマイナス判定回路２０４に乗数Ａ＝ａ0，ａ1，…，ａn-1（但し、ａn＝０。また、ｎは語長を表す。）を入力し、ステップＳＴ６でステップＳＴ７のブースマイナス判定をｉ≦ｎ／２−１（ｎは語長）になるまでループさせる。
【００６６】
すなわち、ステップＳＴ７で数２に示す式に従って、入力された乗数Ａについて入力３ｂｉｔをブースエンコーダ１０４に入力した際に「−１」あるいは「−２」がブースエンコーダ１０４から出力される計算を行い、「−１」あるいは「−２」が出力される時の個数ｙiをｉ≦ｎ／２−１の各奇数ｂｉｔまで繰り返す。
【００６７】
上記ステップＳＴ６及びステップＳＴ７の処理は図２のブースマイナス判定回路２０４に相当し、該当する乗数入力３ｂｉｔをブースエンコーダ１０４に入力した際に「−１」あるいは「−２」がブースエンコーダ１０４から出力される場合に「１」を出力することになる。ここで、ブースエンコーダ１０４は、入力された乗数により２次ブースエンコードを行い、エンコード結果（＋２，＋１，０，−１，−２）を乗算アレイ１０６に出力している。
【００６８】
【数２】
0003710193.tif 000003
【００６９】
ステップＳＴ８では、数３に示す式に従って、入力３ｂｉｔをブースエンコーダ１０４に入力した際に「−１」あるいは「−２」がブースエンコーダ１０４から出力される場合に「１」を出力する際の個数ｙiをカウントし、ステップＳＴ９でこのカウントをｎ／２−１になるまで繰り返す。
【００７０】
【数３】
0003710193.tif 000004
【００７１】
ステップＳＴ１０で上記個数ｙiをｎ／２−１になるまで繰り返した結果の総数ｘが０か（ｘ＝０か）、１か（ｘ＝１か）、複数か（ｘ≧２か）を判別する。上記ステップＳＴ８〜ステップＳＴ１０の処理は図２のブースマイナスカウンタ２０７に相当し、ブースマイナス判定回路２０４の出力するＮ／２ｂｉｔの信号に含まれる「１」の個数をカウントし、０個、１個、複数個の３つのパターンに分類し、それぞれに対応する端子に「１」を出力し、他の端子には「０」を出力する。ここで、０個、１個、複数個の３つのパターンに分類しているのは、上述したように、被乗数がＡＬＬ０ではない時において、乗数をブースエンコードした結果、−１、−２を出力するエンコーダの有無、又はその個数によってオーバーフローが発生する、若しくは発生しないことを判別するためである。
【００７２】
ステップＳＴ１０でｘ＝０と判別したときには、被乗数がＡＬＬ０ではないが−１、−２を出力するエンコーダがない場合であるからオーバーフローが発生することはないと判断してステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終える。
【００７３】
ステップＳＴ１０でｘ＝０と判別したときには、ステップＳＴ１１でブースエンコーダ１０４の「−１」あるいは「−２」の最初の個数ｙ0が「１」であるか（ｙ0＝１か）否かを判別し、ｙ0＝１のときは−１、−２を出力するエンコーダが１個のみの場合であるが−１、−２が最上位で出力される時であるからオーバーフローが発生することはないと判断してステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終える。上記ステップＳＴ１１の処理は図２のブースマイナス・１連続性判定回路２０６に相当する。
【００７４】
ここで、図２に示すように、２進木・逆２進木ＡＮＤ回路２０５の２進木・逆２進木構造により、最上位ｂｉｔ（ここでは、０）から最下位から各奇数ｂｉｔまでの「１」の連続性が判定され、ブースマイナス・１連続性判定回路２０６が、ブースマイナス判定回路２０４のＮ／２本の出力のうち最上位の出力を除いた（Ｎ／２−１）本とブースマイナス判定回路２０４からの（Ｎ／２−１）本の出力を入力とし、それぞれの入力を上位側から２入力ＡＮＤ２０８，２０９に入力し、出力される（Ｎ／２−１）本の信号のＯＲ論理をとることでブースマイナスを出力したエンコーダ入力より上位の乗数がＡＬＬ１である場合を検出するようにする。
【００７５】
図３のフローに戻って、ステップＳＴ１１でｙ0＝１でないと判別したときは、ブースマイナスの個数ｙ1，ｙ2，…，ｙ(n/2)-1が１（ｙ1，ｙ2，…，ｙ(n/2)-1＝１）の該当するステップＳＴ１２〜ステップＳＴ１４に分岐する。
【００７６】
ｙ1＝１のときはステップＳＴ１２で乗数ａ0とａ1が「０」か「１」かを判別し、ａ0とａ1が「０」のときは−１、−２を出力するエンコーダよりも上位のエンコーダが全て「０」の時であるからオーバーフローが発生することはないと判断してステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終え、ａ0とａ1が「１」のときはオーバーフローが発生すると判断してステップＳＴ１５に進んでオーバーフロー予測回路１０５の処理を終える。
【００７７】
ｙ2＝１のときはステップＳＴ１３で乗数ａ0，ａ1，ａ2及び3ａが「０」か「１」かを判別し、ａ0，ａ1，ａ2及びａ3が「０」のときは−１、−２を出力するエンコーダよりも上位のエンコーダが全て「０」の時であるからオーバーフローが発生することはないと判断してステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終え、ａ0，ａ1，ａ2及びａ3が「１」のときはオーバーフローが発生すると判断してステップＳＴ１５に進んでオーバーフロー予測回路１０５の処理を終える。
【００７８】
ｙ(n/2)-1＝１のときはステップＳＴ１４で乗数ａ0，ａ1，ａ2及びａn-3が「０」か「１」かを判別し、ａ0，ａ1，ａ2及びａn-3が「０」のときは−１、−２を出力するエンコーダよりも上位のエンコーダが全て「０」の時であるからオーバーフローが発生することはないと判断してステップＳＴ４に進んでオーバーフロー予測回路１０５の処理を終え、ａ0，ａ1，ａ2及びａn-3が「１」のときはオーバーフローが発生すると判断してステップＳＴ１５に進んでオーバーフロー予測回路１０５の処理を終える。
【００７９】
上記ステップＳＴ１２〜ステップＳＴ１４の処理は全体として図２のブースマイナス・１連続性判定回路２０６、ブースマイナスカウンタ２０７、２入力ＡＮＤ回路２０８，２０９、４入力ＯＲ回路２１０及びＡＮＤ回路２１１に相当する。すなわち、２入力ＡＮＤ回路２０８が、ブースマイナスカウンタ２０７の「＝１」出力を入力とブースマイナス・１連続性判定回路２０６の出力を入力とし、ブースマイナスが１個であり、ブースマイナスを出力したエンコーダ入力より上位の乗数がＡＬＬ１である場合を検出し、また２入力ＡＮＤ回路２０９が、ブースマイナスカウンタ２０７の「＝１」出力を入力とブースマイナス・１連続性判定回路２０６の出力を入力とし、ブースマイナスが１個であり、ブースマイナスを出力したエンコーダが最上位のエンコーダである場合を検出し、さらに４入力ＯＲ回路２１０が、ブースマイナスカウンタ２０７の「≧２」出力と２入力ＡＮＤ回路２０８の否定及び２入力ＡＮＤ回路２０９の否定を入力とし、被乗数がＡＬＬ０ではない時のオーバーフローを検出するものである。
【００８０】
そして、ＡＮＤ回路２１１が、ＡＬＬ０検出回路２０３の出力の否定と４入力ＯＲ回路２１０の出力を入力とし、積生成時に発生する不要なオーバーフローを出力する。
【００８１】
以上説明したように、本実施形態に係る積和演算回路１００は、２次のブース理論を用いてブースエンコードを行うブースエンコーダ１０４と、被乗数とブースエンコーダ１０４からの出力により（Ｍ／２）個の部分積を生成・加算し、２個の中間積に圧縮して出力する乗算アレイと１０６と、被乗数及び乗数に基づいて積生成時に不要なオーバーフローが発生するか否かを予測するオーバーフロー予測回路１０５と、乗算アレイ１０６から出力された２個の中間積と累積データを加算して出力を２本に絞る桁上げ保存加算器１０７と、桁上げ保存加算器１０７からの２本の出力を加算し、加算和を積和演算結果として出力し、（Ｍ＋Ｎ）ｂｉｔを超えるキャリーアウトも出力する２入力加算器１０８と、オーバーフロー予測回路１０５からの出力と２入力加算器１０８のキャリーアウト出力との排他的論理和をとる排他的論理和ゲート１０９とを備え、オーバーフロー予測回路１０５が、入力された被乗数がＡＬＬ０であること、及び乗数のブースエンコード結果について、−１、−２を出力するエンコーダの数、若しくは−１、−２を出力する場合のビット位置を基にオーバーフローを予測する構成となっているので、積生成時の不要なオーバーフロー発生を予測することができ、飽和演算機能付き符号拡張方式の積和演算回路１００において、従来例のように２入力加算器を２つ別々の回路で必要とせず、遅延性能及び積和演算のスループットを高めることができる。
【００８２】
すなわち、従来例では累積データを加算するための２つの２入力加算器１３，１４が必要であり、回路規模が大きくなり、かつ遅延性能への影響も大きく動作周波数の改善が難しく、また、これを回避するための２入力加算器の入力側に全加算器を設ける方法も２次のブース理論を用いることからオーバーフロー発生が発生する可能性があり出力が不正確となりそのまま全加算器に入力することはできなかった。これに対し、本実施形態に係る積和演算回路１００では、オーバーフロー予測回路１０５によって、積生成時の不要なオーバーフロー発生を予測することができ、飽和演算機能付き符号拡張方式の積和演算回路１００においても２入力加算器１０８は１個で済み、遅延性能及び積和演算のスループットを高めることができる。
【００８３】
なお、上述の実施形態では、２次ブース理論及び符号拡張方式の乗算器を用いた（Ｍｂｉｔ×Ｎｂｉｔ）＋（Ｍ＋Ｎ）ｂｉｔの積和演算回路に適用した例であるが、加算手段の累積計算時にオーバーフローの発生予測を行い得るオーバーフロー予測手段を備えるものであればどのような積和演算回路に適用してもよい。例えば、部分積の生成に２次のブース理論を用いない並列乗算器に用いることもできる。
【００８４】
また、上記積和演算回路１００及びオーバーフロー予測回路１０５を構成する各種回路及びゲート回路の種類や数、種類接続状態などは前述した上述の実施形態に限られないことは言うまでもなく、積和演算回路１００全体がＤＳＰ等を構成する算術回路の一部であってもよい。
【００８５】
さらに、上述の各実施形態では、並列乗算器等に用いられる積和演算回路に適用しているが、（Ｍｂｉｔ×Ｎｂｉｔ）＋（Ｍ＋Ｎ）ｂｉｔの積和演算を行う回路であればどのような装置にも適用することもできる。
【００８６】
【発明の効果】
本発明に係る積和演算回路では、被乗数と乗数から部分積を生成・加算し、中間積に圧縮して出力する乗算アレイと、被乗数及び乗数に基づいて積生成時にオーバーフローが発生することを予測するオーバーフロー予測手段と、乗算アレイから出力された中間積と累積データを加算し、該加算和を積和演算結果として出力するとともに、（Ｍ＋Ｎ）ビットを超えるキャリーアウトも出力する加算手段とを備えて構成しているので、積生成時の不要なオーバーフロー発生を予測することができ、飽和演算機能付き符号拡張方式の積和演算回路においても２入力加算器を２つ別々の回路で必要とせず、遅延性能及び積和演算のスループットを高めることができる。
【図面の簡単な説明】
【図１】本発明を適用した実施形態に係る積和演算回路の構成図である。
【図２】上記積和演算回路のオーバーフロー予測回路の回路構成図である。
【図３】上記積和演算回路のオーバーフロー予測回路の動作を説明するためのタイミングチャートである。
【図４】従来の積和演算回路の構成図である。
【符号の説明】
１００  積和演算回路、１０１，１０２，１０３，２０１，２０２  入力端子、１０４  ブースエンコーダ、１０５  オーバーフロー予測回路（オーバーフロー予測手段）、１０６  乗算アレイ、１０７  桁上げ保存加算器、１０８  ２入力加算器、１０９  排他的論理和ゲート、１１０，１１１，２１２  出力端子、１１２  加算手段１１２、２０３  ＡＬＬ０検出回路（ＡＬＬ０検出手段）、２０４  ブースマイナス判定回路、２０５  ２進木・逆２進木ＡＮＤ回路、２０６  ブースマイナス・１連続性判定回路、２０７  ブースマイナスカウンタ、２０８，２０９  ２入力ＡＮＤ回路、２１０  ４入力ＯＲ回路、２１１  ＡＮＤ回路、２１３  判定手段
【図１】
0003710193.tif 000005
【図２】
0003710193.tif 000006
【図３】
0003710193.tif 000007
【図４】
0003710193.tif 000008