(57)【要約】【課題】加算器に入力されるデータ数を減らし、しかも乗算装置の演算速度を高速化することが目的とされる。【解決手段】乗算装置は、デコーダ１０１及び加算器１０２を備える。デコーダ１０１は、第０ビット乃至第（２ｍ−１）ビットｂ0〜ｂ2m-1、付加ビットｂ2m、信号生成部ｇ0〜ｇm及び部分積生成部Ｇ0〜Ｇmを有する。付加ビットｂ2mは、符号なし乗数Ｙについては値０を、符号付き乗数Ｙについては乗数Ｙの最上位ビットである第（２ｍ−１）ビットｂ2m-1と同じ値を採る。信号生成部ｇj（０≦ｊ≦ｍ−１）は乗数Ｙから乗数信号ｔj及び加算信号Ｓjを生成し、信号生成部ｇmは乗数Ｙから乗数信号ｔmを生成する。部分積生成部Ｇj（０≦ｊ≦ｍ）は乗数信号ｔjと被乗数Ｘとに基づいて部分積Ｐjを生成する。加算器１０２は、部分積Ｐ0と、加算信号Ｓj-1を下位側に１ビット離して従えた部分積Ｐjとを加算する。【選択図】図１
2006301685.tif 000002
【特許請求の範囲】
【請求項１】
２ｍビット長（ｍ；自然数）の乗数の最下位２ビットに対応する第０の加算信号及び第０の乗数信号を生成する第０の信号生成部と、
前記乗数の第（２ｊ＋１），２ｊ，（２ｊ−１）ビットに対応する第ｊの加算信号とともに第ｊの乗数信号を生成する第ｊ（１≦ｊ≦ｍ−１の整数）の信号生成部と、
前記乗数の最上位ビット及び付加ビットに対応する第ｍの乗数信号を生成する第ｍの信号生成部と、
被乗数と前記第０乃至前記第ｍの前記乗数信号とを用いてそれぞれ第０乃至第ｍの部分積を生成する部分積生成部と、
前記第０の前記部分積と、前記第１乃至前記第ｍの前記乗算信号に基づいてビットがずれて、前記第０乃至前記第（ｍ−１）の前記加算信号をそれぞれ下位側に１ビット離して従える前記第１乃至前記第ｍの前記部分積とを加算する加算器と
を備え、
前記付加ビットは、符号なしの前記乗数については値０を採り、符号付きの前記乗数については前記乗数の最上位ビットの値と同じ値を採る、乗算装置。
【請求項２】
前記第０乃至前記第（ｍ−１）の前記信号生成部は、ブースのアルゴリズムに従って前記第０乃至前記第（ｍ−１）の前記加算信号及び前記第０乃至前記第（ｍ−１）の前記乗数信号を生成する、請求項１記載の乗算装置。
【請求項３】
前記加算器はワレス・ツリーに従って加算演算を行う、請求項１または請求項２記載の乗算装置。
【請求項４】
前記加算器は、キャリー保存加算器を含む、請求項１乃至請求項３のいずれか一つに記載の乗算装置
【請求項５】
前記自然数ｍは、これを２倍して１だけ加えたものを２で割った値以上で最小の整数が３の倍数となる、請求項１乃至請求項４のいずれか一つに記載の乗算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は乗算装置に関し、例えばワレス・ツリーを用いた乗算装置に関する。
【背景技術】
【０００２】
従来から被乗数と乗数との乗算演算を行う乗算装置では、ブースのアルゴリズムを用いることで、乗数について所定の長さのビット毎に部分積を生成し、これを加算器で加算することで乗算結果を得ている。
【０００３】
なお、本発明に関連する技術を以下に示す。
【０００４】
【特許文献１】特開平８−３０５５５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、従来の乗算装置では、部分積の符号に対応した少なくとも一つのデータを生成し、これを加算器に入力する必要がある。このため、当該データの分だけ加算器における演算時間が長くなり、乗算装置の演算速度が遅くなるおそれがあった。
【０００６】
上記特許文献１では、乗数の最上位ビットから生成される部分積と、上記データとを選択して加算器に入力することで、加算器に入力されるデータ数が増加することを回避している。しかし、当該選択には、セレクタが用いられているため、加算器での演算速度の遅延は回避されるものの、セレクタでの選択に要する時間だけ乗算装置の演算速度が遅くなる。
【０００７】
本発明は上述した事情に鑑みてなされたものであり、加算器に入力されるデータ数を減らし、しかも乗算装置の演算速度を高速化することが目的とされる。
【課題を解決するための手段】
【０００８】
この発明にかかる乗算装置は、第０乃至第ｍの信号生成部と、部分積生成部と、加算器とを備える。前記第０の前記信号生成部は、２ｍビット長（ｍ；自然数）の乗数の最下位２ビットに対応する第０の加算信号及び第０の乗数信号を生成する。前記第ｊ（１≦ｊ≦ｍ−１の整数）の前記信号生成部は、前記乗数の第（２ｊ＋１），２ｊ，（２ｊ−１）ビットに対応する第ｊの加算信号とともに第ｊの乗数信号を生成する。前記第ｍの前記信号生成部は、前記乗数の最上位ビット及び付加ビットに対応する第ｍの乗数信号を生成する。前記部分積生成部は、被乗数と前記第０乃至前記第ｍの前記乗数信号とを用いてそれぞれ第０乃至第ｍの部分積を生成する。前記加算部は、前記第０の前記部分積と、前記第１乃至前記第ｍの前記乗算信号に基づいてビットがずれて、前記第０乃至前記第（ｍ−１）の前記加算信号をそれぞれ下位側に１ビット離して従える前記第１乃至前記第ｍの前記部分積とを加算する。前記付加ビットは、符号なしの前記乗数については値０を採り、符号付きの前記乗数については前記乗数の最上位ビットの値と同じ値を採る。
【発明の効果】
【０００９】
この発明にかかる乗算装置によれば、付加ビット及び乗数の最上位ビットに基づいて第ｍの乗数信号が生成されるので、乗数が符号付きである場合と符号なしである場合のいずれであるかを選択するための論理回路が不要である。しかも部分積のうち第１乃至第ｍの部分積はそれぞれ第０乃至第（ｍ−１）の加算信号を下位ビットとして従えるので、第１乃至第（ｍ−１）の加算信号の総和を第０乃至第ｍの部分積の生成とは別途に生成する必要がなく、加算器にｍ＋１個の部分積を入力するだけで良い。よって、乗算装置の演算速度が高速化される。
【発明を実施するための最良の形態】
【００１０】
実施の形態１．
図１は、本実施の形態にかかる乗算装置を概念的に示すブロック図である。当該乗算装置は、デコーダ１０１及び加算器１０２を備える。デコーダ１０１には、２進数で表された被乗数Ｘと乗数Ｙとが入力される。乗数Ｙは２ｍビット長を有する。一方、被乗数Ｘのビット長には２ｍビット長以外のビット長が採用できる。ここで、符号ｍは自然数を表し、以下同様である。
【００１１】
デコーダ１０１は、第０ビット乃至第（２ｍ−１）ビットｂ0〜ｂ2m-1、付加ビットｂ2m、信号生成部ｇ0〜ｇm及び部分積生成部Ｇ0〜Ｇmを有する。
【００１２】
第０ビット乃至第（２ｍ−１）ビットｂ0〜ｂ2m-1の各々は、入力された乗数Ｙに基づいて値０または値１を採る。
【００１３】
付加ビットｂ2mは、符号なしの乗数Ｙについては値０を採り、符号付きの乗数Ｙについては乗数Ｙの最上位ビットである第（２ｍ−１）ビットｂ2m-1と同じ値を採る。具体的には、付加ビットｂ2m及び第（２ｍ−１）ビットｂ2m-1は、符号なしの乗数Ｙについてはそれぞれ値０，１を採り、符号付きの乗数Ｙについては乗数が正の場合にはそれぞれ値０，０を、負の場合にはそれぞれ値１，１を採る。
【００１４】
図１では、付加ビットｂ2mが第（２ｍ−１）ビットｂ2m-1の上位に付加されているが、これとは異なる位置に付加されても良い。
【００１５】
信号生成部ｇj（０≦ｊ≦ｍ−１）はそれぞれ、乗数Ｙから乗数信号ｔj及び加算信号Ｓjを生成する。信号生成部ｇmは、乗数Ｙから乗数信号ｔmを生成する。ここで、符号ｊは整数を表し、以下同様である。
【００１６】
部分積生成部Ｇj（０≦ｊ≦ｍ）には乗数信号ｔjと被乗数Ｘとがそれぞれ入力され、これらに基づいて部分積生成部Ｇjは部分積Ｐjを出力する。
【００１７】
加算器１０２には部分積Ｐj（０≦ｊ≦ｍ）が入力される。このとき、部分積Ｐ0以外の部分積Ｐjは、後述するように加算信号Ｓj-1を従える。加算器１０２は、部分積Ｐ0を含む全ての部分積Ｐjを加算して、被乗数Ｘと乗数Ｙとの乗算結果Ｒを出力する。
【００１８】
乗数信号ｔj（０≦ｊ≦ｍ−１）、加算信号Ｓj及び部分積Ｐjに関し、以下に具体的に説明する。乗数信号ｔm及び部分積Ｐmについては後述する。
【００１９】
信号生成部ｇj（１≦ｊ≦ｍ−１）は、ブースのアルゴリズムに従って、第（２ｊ＋１），２ｊ，（２ｊ−１）ビットを用いて演算を行う。演算の結果として１０進数表記で−２，−１，０，１，２のいずれかが得られる。
【００２０】
信号生成部ｇ0は、最下位２ビットである第０ビット及び第１ビットのそれぞれの値を用いて演算を行う。演算の結果として１０進数表記で−２，−１，０，１のいずれかが得られる。例えば、信号生成部ｇ0は、第０ビット及び第１ビットの数値と、第０ビットの下位側に付加されて値０を採るビットとを用いて、ブースのアルゴリズムに従って演算を行ってもよく、図１でこの場合が示されている。
【００２１】
演算の結果が２のとき、信号生成部ｇj（１≦ｊ≦ｍ−１）は、部分積生成部Ｇjに被乗数Ｘを（２ｊ＋１）ビットだけ上位へとシフトさせる信号を乗数信号ｔjとして生成する。乗数信号ｔjが入力された部分積生成部Ｇjは、被乗数Ｘを（２ｊ＋１）ビットだけ上位へとシフトさせ、これを部分積Ｐjとして出力する。
【００２２】
演算の結果が１のとき、信号生成部ｇj（０≦ｊ≦ｍ−１）は、部分積生成部Ｇjに被乗数Ｘを２ｊビットだけ上位へとシフトさせる信号を乗数信号ｔjとして生成する。乗数信号ｔjが入力された部分積生成部Ｇjは、被乗数Ｘを２ｊビットだけ上位へとシフトさせ、これを部分積Ｐjとして出力する。
【００２３】
演算の結果が０のとき、信号生成部ｇj（０≦ｊ≦ｍ−１）は、部分積生成部Ｇjに部分積Ｐjとして０を出力させる信号を生成する。
【００２４】
演算の結果が−１のとき、信号生成部ｇj（０≦ｊ≦ｍ−１）は、部分積生成部Ｇjに被乗数Ｘを２ｊビットだけ上位へとシフトさせ、これを反転させる信号を乗数信号ｔjとして生成する。乗数信号ｔjが入力された部分積生成部Ｇjは、被乗数Ｘを２ｊビットだけ上位へとシフトさせて反転させ、これを部分積Ｐjとして出力する。
【００２５】
演算の結果が−２のとき、信号生成部ｇj（０≦ｊ≦ｍ−１）は、部分積生成部Ｇjに被乗数Ｘを（２ｊ＋１）ビットだけ上位へとシフトさせ、これを反転させる信号を乗数信号ｔjとして生成する。乗数信号ｔjが入力された部分積生成部Ｇjは、被乗数Ｘを（２ｊ＋１）ビットだけ上位へとシフトさせて反転させ、これを部分積Ｐjとして出力する。
【００２６】
演算の結果が２、１及び０のいずれかである場合には、乗数信号ｔj（０≦ｊ≦ｍ−１）の生成に並行して信号生成部ｇjは、第（２ｊ＋１）ビットを０とする信号を加算信号Ｓjとして生成する。この加算信号Ｓjが生成された場合には、部分積Ｐj+1は、第（２ｊ＋１）ビットが０とされて加算器１０２に入力される。
【００２７】
演算の結果が−１または−２である場合には、乗数信号ｔj（０≦ｊ≦ｍ−１）の生成に並行して信号生成部ｇjは、第（２ｊ＋１）ビットを１とする信号を加算信号Ｓjとして生成する。この加算信号Ｓjが生成された場合には、部分積Ｐj+1は、第（２ｊ＋１）ビットが１とされて、加算器１０２に入力される。
【００２８】
演算の結果の値がいずれの場合であっても、これらの内容は、部分積Ｐj+1が加算信号Ｓjを下位側に１ビット離して従えると把握できる。
【００２９】
乗数信号ｔm及び部分積Ｐmに関し、以下に具体的に説明する。
【００３０】
信号生成部ｇmは、付加ビットｂ2m及び第（２ｍ−１）ビットｂ2m-1を用いて演算を行う。具体的には、付加ビットｂ2m及び第（２ｍ−１）ビットｂ2m-1が値１，１または値０，０を採る場合には、信号生成部ｇmは、部分積生成部Ｇmに部分積Ｐmとして０を出力させる信号を生成する。
【００３１】
値０，１を採る場合には、信号生成部ｇmは、部分積生成部Ｇmに被乗数Ｘを２ｍビットだけ上位へとシフトさせる信号を乗数信号ｔmとして生成する。乗数信号ｔmが入力された部分積生成部Ｇmは、被乗数Ｘを２ｍビットだけ上位へとシフトさせ、これを部分積Ｐmとして出力する。
【００３２】
上述した乗算装置によれば、付加ビットｂ2m及び乗数の最上位ビット第（２ｍ−１）ビットｂ2m-1に基づいて乗数信号ｔmが生成されるので、乗数が符号付きである場合と符号なしである場合のいずれであるかを選択するための論理回路が不要である。しかも部分積Ｐj（０≦ｊ≦ｍ）のうち部分積Ｐ0以外の部分積Ｐjは加算信号Ｓj-1を従えるので、加算信号Ｓj-1の総和を部分積Ｐjの生成とは別途に生成する必要がなく、加算器１０２にｍ＋１個の部分積Ｐjを入力するだけで良い。よって、乗算装置の演算速度が高速化される。
【００３３】
図２は、乗数Ｙの範囲（２2m＞Ｙ≧−２2m-1）と付加ビットｂ2m及び第（２ｍ−１）ビットｂ2m-1がそれぞれ採る値との関係を示している。値０，１は２2m>Ｙ≧２2m-1の範囲に、値０，０は２2m-1＞Ｙ≧０の範囲に、値１，１は０＞Ｙ≧−２2m-1の範囲にそれぞれ対応する。
【００３４】
なお、図２では−２2m-1＞Ｙ≧−２2mの範囲についても示されており、この範囲には値１，０が対応する。しかし、付加ビットｂ2m及び乗数の最上位ビット第（２ｍ−１）ビットｂ2m-1がそれぞれ値１，０を採る場合には、乗数Ｙの範囲を拡張できる一方、乗算装置の演算速度が高速化できない。
【００３５】
実施の形態２．
本実施の形態では、加算器１０２がワレス・ツリーに従って加算演算を行う場合が説明される。
【００３６】
図３は、加算器１０２の加算演算で用いられるワレス・ツリーであって、ｍ＝８の場合を概念的に示す。加算器１０２には、９個の部分積Ｐj（０≦ｊ≦８）が入力される。
【００３７】
ワレス・ツリーは、第１次加算器２１１〜２１３、第２次加算器２２１，２２２、第３次加算器２３１及び第４次加算器２４１で構成される。
【００３８】
第１次加算器乃至第４次加算器はいずれも３入力２出力の加算素子である。３入力２出力の加算素子には、例えばキャリー保存加算器（ＣＳＡ）が採用でき、以下について同様である。
【００３９】
第１次加算器２１１には部分積Ｐ0〜Ｐ2、第１次加算器２１２には部分積Ｐ3〜Ｐ5、第１次加算器２１３には部分積Ｐ6〜Ｐ8がそれぞれ入力される。
【００４０】
第２次加算器２２１には、第１次加算器２１１の２出力の両方と、第２次加算器２１２の２出力の一方とが入力される。第２次加算器２２２には、第１次加算器２１２の２出力の他方と、第１次加算器２１３の２出力の両方とが入力される。
【００４１】
第３次加算器２３１には、第２次加算器２２１の２出力の両方と、第２次加算器２２２の２出力の一方とが入力される。
【００４２】
第４次加算器２４１には、第３次加算器２３１の２出力の両方と、第２次加算器２２２の２出力の他方とが入力される。
【００４３】
第４次加算器２４１の２出力は乗算結果Ｒとして、加算器１０２から出力される。
【００４４】
第１次加算器２１１〜２１３での加算演算は並行して行うことができ、これが図３では第１ステージとして示されている。同様に、第２次加算器２２１，２２２、第３次加算器２３１及び第４次加算器２４１での加算演算が、図３では第２ステージ乃至第４ステージとしてそれぞれ示されている。第１乃至第４ステージでの演算は、いずれの一の演算についても他の演算と並行して行うことができない。よって、ｍ＝８の場合には、ワレス・ツリーには４つのステージが必要とされる。
【００４５】
図３との比較のために、例えば１０個の部分積Ｐj（０≦ｊ≦９）が加算器１０２に入力される場合のワレス・ツリーを図４に概念的に示す。当該ワレス・ツリーは、第１次加算器２１１〜２１３、第２次加算器２２１，２２２、第３次加算器２３１、第４次加算器２４１及び第５次加算器２５１で構成される。第１次加算器乃至第５次加算器はいずれも３入力２出力の加算素子であり、第１次加算器乃至第４次加算器については、ツリー構造が図３で示されるものと同じである。
【００４６】
第５次加算器には、第４次加算器２４１の２出力の両方と、部分積Ｐ9とが入力される。第５次加算器２５１の２出力は乗算結果Ｒとして、加算器１０２から出力される。
【００４７】
図４では、第５次加算器２５１の加算演算が、第５ステージとして示されている。第５ステージは、第１乃至第４ステージでの演算と並行して行うことはできない。よって、１０個の部分積Ｐj（０≦ｊ≦９）が入力されるワレス・ツリーでは、５つのステージが必要とされる。
【００４８】
よって、加算器１０２に入力される部分積が９個の場合には、それが１０個の場合に比べて、ワレス・ツリーで必要とされるステージ数を一つ少なくすることができる。これにより、加算器１０２での演算時間を短縮することができ、以って乗算装置での演算速度を高速化できる。
【００４９】
より一般的には、実施の形態１で説明した乗算装置によればｍ＋１個の部分積Ｐj（０≦ｊ≦ｍ）が加算器１０２に入力され、加算器１０２はワレス・ツリーに従って部分積Ｐjの加算演算を行う。
【００５０】
特に、自然数ｍが式（１）を満たす場合、具体的にはｍ＝８、３２、１２８、２５６、３２０、５１２、２０４８、・・・の場合には、上述したと同様に、ｍ＋２個の部分積が加算器１０２に入力される場合に比べて、ステージ数を一つ少なくすることができる。ここで、Ｃｅｉｌ［  ］は、［  ］内の値以上であって最小の整数を表す。また、符号ｋは整数を表す。
【００５１】
【数１】
2006301685.tif 000003
【００５２】
実施の形態３．
図５は、加算器１０２の加算演算に用いられるツリーであって、ｍ＝１６の場合を概念的に示す。加算器１０２には、１７個の部分積Ｐj（０≦ｊ≦１６）が入力される。
【００５３】
ツリーは、いずれも３入力２出力の加算素子である第１次加算器乃至第１５次加算器３０１〜３１５で構成される。
【００５４】
第１次加算器３０１には部分積Ｐ0〜Ｐ2が入力される。第ｊ次加算器３０ｊ（２≦ｊ≦１５）には、第ｉ次加算器３０ｉ（ｉ＝ｊ−１）の２出力の両方と、部分積Ｐj+1とが入力される。第１５次加算器３１５の２出力は乗算結果Ｒとして、加算器１０２から出力される。
【００５５】
第１次加算器乃至第１５次加算器３０１〜３１５での加算演算は、いずれの一の加算演算についても他の加算演算と並行して行うことができないので、ツリーには１５個のステージが必要とされる。
【００５６】
図５との比較のために、例えば１８個の部分積Ｐj（０≦ｊ≦１７）が加算器１０２に入力される場合のツリーを図６に概念的に示す。当該ツリーは、いずれも３入力２出力の加算素子である第１次加算器乃至第１６次加算器３０１〜３１６で構成される。第１次加算器乃至第１５次加算器３０１〜３１５については、ツリー構造が図５で示されるものと同じである。
【００５７】
第１６次加算器３１６には、第１５次加算器３１５の２出力の両方と、部分積Ｐ16とが入力される。第１６次加算器３１６の２出力は乗算結果Ｒとして、加算器１０２から出力される。
【００５８】
第１６次加算器３１６の加算演算は、第１次加算器乃至第１５次加算器３０１〜３１５の加算演算と並行して行うことができないので、図６で示されるツリーには１６個のステージが必要とされる。
【００５９】
よって、加算器１０２に入力される部分積が１７個である場合には、それが１８個である場合に比べて、ツリーで必要とされるステージ数を一つ少なくすることができる。
【００６０】
より一般的には、実施の形態１で説明した乗算装置によればｍ＋１個の部分積Ｐj（０≦ｊ≦ｍ）が加算器１０２に入力され、加算器１０２はステージ数が（ｍ−１）であるツリーに従って部分積Ｐjの加算演算を行う。このより、ｍ＋２個の部分積が加算器１０２に入力される場合に比べて、ステージ数を一つ少なくすることができる。
【図面の簡単な説明】
【００６１】
【図１】実施の形態１で説明される、乗算装置を概念的に示すブロック図である。
【図２】乗数の範囲と付加ビット及び第（２ｍ−１）ビットの値との関係を示す図である。
【図３】実施の形態２で説明される、ワレス・ツリーを概念的に示す図である。
【図４】１０個の部分積を入力した場合に採用されるワレス・ツリーを示す図である。
【図５】実施の形態３で説明される、ツリーを概念的に示す図である。
【図６】１８個の部分積を入力した場合に採用されるツリーを示す図である。
【符号の説明】
【００６２】
１０２  加算器、Ｘ  被乗数、Ｙ  乗数、ｇ0〜ｇm  信号生成部、Ｇ0〜Ｇm  部分積生成部、ｔ0〜ｔm  乗数信号、Ｓ0〜Ｓm-1  加算信号、Ｐ0〜Ｐm-1  部分積。
【図１】
2006301685.tif 000004
【図２】
2006301685.tif 000005
【図３】
2006301685.tif 000006
【図４】
2006301685.tif 000007
【図５】
2006301685.tif 000008
【図６】
2006301685.tif 000009