(57)【要約】【課題】乗算回路における電流発生を抑止するとともに演算時間を短縮する。【解決手段】  入力値生成部は所定のデコード単位ごとに被乗数データおよび乗数データを区切って、区切られた被乗数データおよび乗数データの複数の部分乗算結果を、区切られた被乗数データおよび乗数データよりも広いデータ幅を有する固定値から所定ビット数だけ異なる値を示すデコードデータとして生成する。乗算部は、入力値生成部によって生成された複数の部分乗算結果のデコードデータを、対応する桁のデコード単位ごとに加算することによって、デコードされた乗算データを生成する。エンコーダは、乗算部によって生成されたデコードされた乗算データをデコード単位ごとにエンコードすることによって、被乗数データと乗数データとの間の乗算結果を出力する。【選択図】図１
2012043405.tif 000002
【特許請求の範囲】
【請求項１】
所定のデコード単位ごとに被乗数データおよび乗数データを区切って、前記区切られた被乗数データおよび乗数データの複数の部分乗算結果を、前記区切られた被乗数データおよび乗数データよりも広いデータ幅を有する固定値から所定ビット数だけ異なる値を示すデコードデータとして生成する入力値生成部と、
前記入力値生成部によって生成された前記複数の部分乗算結果のデコードデータを、対応する桁の前記デコード単位ごとに加算することによって、デコードされた乗算データを生成する乗算部と、
前記乗算部によって生成された前記デコードされた乗算データをデコード単位ごとにエンコードすることによって、前記被乗数データと前記乗数データとの間の乗算結果を出力するエンコーダと
を具備する乗算回路。
【請求項２】
前記乗算部は、前記複数の部分乗算結果のデコードデータとして前記固定値が入力されている間は前記デコードされた乗算データとして前記固定値を出力する請求項１記載の乗算回路。
【請求項３】
前記区切られた被乗数データの３倍値を演算して生成する３倍値演算部をさらに具備し、
前記入力値生成部は、前記乗数データの所定のフィールドに基づいて選択信号を生成し、前記選択信号に従って、前記区切られた被乗数データ、当該区切られた被乗数データを１ビット左シフトすることにより得られた２倍値、および、前記３倍値の何れかを前記デコードデータとして生成する
請求項１記載の乗算回路。
【請求項４】
前記入力値生成部は、前記乗数データの所定のフィールドに基づいて選択信号を生成し、前記選択信号に従って前記区切られた被乗数データの「−２倍」、「−１倍」、「０倍」、「＋１倍」または「＋２倍」の何れかを前記デコードデータとして生成する
請求項１記載の乗算回路。
【請求項５】
リセット信号を出力する同期制御部をさらに具備し、
前記入力値生成部は、前記リセット信号に同期して前記複数の部分乗算結果を生成する
請求項１記載の乗算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、乗算回路に関する。詳しくは、被乗数と乗数との間で乗算を行う乗算回路に関する。
【背景技術】
【０００２】
一般に、乗算回路は、ハーフアダー（ＨＡ：Half Adder）やフルアダー（ＦＡ：Full Adder）の加算器をマトリクス状に配置して構成される。ここで、以下の被乗数Ａと乗数Ｂを想定する。
Ａ＝a7×27＋a6×26＋a5×25＋a4×24＋a3×23＋a2×22＋a1×21＋a0 ＝Σam×2m
Ｂ＝b7×27＋b6×26＋b5×25＋b4×24＋b3×23＋b2×22＋b1×21＋b0 ＝Σan×2n
【０００３】
ＨＡまたはＦＡをマトリクス状に配置して、被乗数および乗数の各係数の部分積（am×bn）を入力することにより、各入力に基づいてＨＡおよびＦＡが動作を開始し、乗算結果を出力する。ＨＡおよびＦＡでは、通常の場合、データとキャリーの各経路で遅延時間が異なるため、入力信号がほぼ同時に確定したとしても、遅延差が生じてしまう。ＨＡおよびＦＡの一方の入力は上の段のＨＡおよびＦＡの出力となっているため、各ＨＡおよびＦＡの出力は上の段から下の段へ向けて順番に確定していく。そして、ＨＡおよびＦＡの加算出力とキャリー出力の遅延差が、下の段へ行くに従って積算されていき、下の段ではＨＡおよびＦＡの各入力値はそれぞれいくつかの中間値に遷移した後、最終的な入力値に遷移する。結果的に、その出力も幾つかの中間値に遷移した後で、最終的な演算結果に遷移する。この過程において、消費電流の増加が発生する。
【０００４】
乗算回路に使用される加算器ＨＡおよびＦＡは、ＣＳＡ（Carry Save Adder）の構成を採り、その出力は、加算結果とキャリー出力を各々持っているため、演算の最終段では、キャリーの処理が必要となる。このため、最終段に配置された１段の加算器列によって、上の段のＣＳＡマトリクスからの演算出力およびキャリー出力が加算され、演算結果のキャリー出力を上位ビット側のＦＡの入力としてキャリー処理が行われる。これは、ＣＰＡ（Carry Propagate Adder）と呼ばれる加算器であり、キャリーの伝播時間によりその処理時間が決まる。
【０００５】
演算時間の仕様は、演算のワーストケースでの演算時間として定義される。具体的には、下位の"a1×b0"と"a0×b1"との加算でキャリーが発生し、これが下段の加算器に伝播していき、最下段のキャリー処理回路で上位ビット側に次々と伝播していき、最終的に最上位の加算器に到達するまでの時間で定義される。例えば、８ビットの乗算回路の演算時間は、７段の加算器アレイおよび最終段の７ビットのキャリー処理回路を通る経路により定義され、ほぼ１４個のＦＡの遅延時間に相当する。
【０００６】
ここまでは８ビットの乗算回路を想定していたが、プロセッサ等のバス幅の拡大に伴い、乗算回路も３２ビットや６４ビットのものが用いられる様になってきている。このとき、使用されるＨＡやＦＡの個数は、乗算回路のビット幅の比率のほぼ２乗で増加し、それに伴って加算器（ＨＡおよびＦＡ）アレイの下段では、２つまたは３つの演算値入力の遅延差がさらに積算される。そして、これに伴って中間値への遷移の回数も増え、結果的に消費電流が増加する。また、加算器アレイが大きくなったことに伴って、最も遅延パスの大きい経路は、乗算器のビット幅の比率で増加する。
【０００７】
このような消費電流や演算時間の増大に関する問題を解決する手法として、ブース（ブース）のアルゴリズムや、ワレスツリー（Wallace Tree）構成が提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−２１２７６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ブースのアルゴリズムは、例えばＲａｄｉｘ−４のブースエンコーダを用いて、拡張した乗数Ｂにおいて着目する３ビットの値に基づいて、被乗数Ａから生成する−２Ａ乃至＋２Ａまでの値を選択して、加算していくものである。これにより、加算器アレイの縦方向の段数が半分近くに削減されて演算時間が短縮され、また、ＨＡやＦＡの削減に伴って消費電流が削減される。しかも、２Ａはビットシフト、負の値は２の補数によって生成することできる。
【００１０】
しかし、従来構成ではＨＡやＦＡの加算器は部分積の有効データがある部分のみ配置すればよかったが、２の補数を用いてブースのアルゴリズムを適用する場合、有効データより上位３ビットに「１」を埋める必要が生じる。そのため、有効データの上位側にも３ビット分のフラグ演算のためのＨＡやＦＡを配置する必要が生じる。そして、負値が選択された場合、演算に用いられるデータはビット反転でよいが、有効データの最下位で「＋１」を実行する必要があり、そのためのＨＡやＦＡも下位ビット側に必要となる。これらにより、加算器列の段数は半分近くになり、演算時間の短縮には効果があるが、ＨＡやＦＡの個数は半減にはならないため、消費電流の効果は縦方向の演算遅延が低減されたことによる効果のみとなる。
【００１１】
ワレスツリーを用いた構成は、加算器マトリクスにおいて各ビットで上段からシリアルに実行されていた加算を、パラレルに実行することにより、縦方向の演算時間を削減するものである。通常の乗算回路ではひし形状に加算器が配置され、この中で加算器の数が最も多く、演算に最も時間を要するのは、中央部分のビットの計算である。例えば、８ビットの乗算回路の中央部分のビットの計算にワレスツリーを適用すると、従来構成で７段の加算器遅延で実行されていた演算処理を、４段の加算器処理で実行することができ、縦方向の演算遅延を半分近くに削減することができる。この構成は、ブースのアルゴリズムを用いた構成にも適用でき、遅延を３段分に短縮することができる。これは乗算回路のビット幅が大きくなるに従って、削減効果は大きくなる。
【００１２】
ここで、演算時間は、「キャリー処理回路までの縦方向の加算器の段数」と「キャリー処理回路での横方向の加算器の段数」の合計で決まる。すなわち、
乗算演算時間＝加算器回路遅延×縦方向の段数
＋キャリー処理回路遅延×横方向の段数
である。ブースのアルゴリズムおよびワレスツリーは、ともに前者の削減効果だけであり、後者の処理時間は短縮されていない。また、ワレスツリーの構成では、前者の列単位の加算器動作を並列に行うことにより演算時間の削減を図っているが、この構成では同時に動作するＨＡやＦＡの数が増加するため、この時間短縮効果と反比例して消費電流は増加してしまう。それに対して、後者のキャリー処理回路では、下位ビットから加算器が１個ずつ動作し、その演算処理時の動作電流は前者の処理時に比べて格段に少ない。キャリールックアヘッド（Carry Look Ahead）を用いて、下位のキャリーを高速演算して上位の加算回路のキャリー入力に供給し、上位の加算の確定時間を短縮する方法も考えられる。しかし、キャリールックアヘッドは、入力される加算値が同時に確定する場合に有効であり、入力の確定タイミングが一定ではない値を入力とするキャリー処理回路では、本来の効果を期待することができない。
【００１３】
本技術はこのような状況に鑑みて生み出されたものであり、乗算回路における電流発生を抑止するとともに演算時間を短縮することを目的とする。
【課題を解決するための手段】
【００１４】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、所定のデコード単位ごとに被乗数データおよび乗数データを区切って、上記区切られた被乗数データおよび乗数データの複数の部分乗算結果を、上記区切られた被乗数データおよび乗数データよりも広いデータ幅を有する固定値から所定ビット数だけ異なる値を示すデコードデータとして生成する入力値生成部と、上記入力値生成部によって生成された上記複数の部分乗算結果のデコードデータを、対応する桁の上記デコード単位ごとに加算することによって、デコードされた乗算データを生成する乗算部と、上記乗算部によって生成された上記デコードされた乗算データをデコード単位ごとにエンコードすることによって、上記被乗数データと上記乗数データとの間の乗算結果を出力するエンコーダとを具備する乗算回路である。これにより、デコードデータを用いて乗算を行うことによって回路内の信号の中間値への変化を抑制するという作用をもたらす。
【００１５】
また、この第１の側面において、上記乗算部は、上記複数の部分乗算結果のデコードデータとして上記固定値が入力されている間は上記デコードされた乗算データとして上記固定値を出力するように構成してもよい。これにより、乗算データを一旦リセットするという作用をもたらす。
【００１６】
また、この第１の側面において、上記区切られた被乗数データの３倍値を演算して生成する３倍値演算部をさらに具備し、上記入力値生成部は、上記乗数データの所定のフィールドに基づいて選択信号を生成し、上記選択信号に従って、上記区切られた被乗数データ、当該区切られた被乗数データを１ビット左シフトすることにより得られた２倍値、および、上記３倍値の何れかを上記デコードデータとして生成するようにしてもよい。これにより、３倍値を利用することによって乗算に要する段数を削減するという作用をもたらす。
【００１７】
また、この第１の側面において、上記入力値生成部は、上記乗数データの所定のフィールドに基づいて選択信号を生成し、上記選択信号に従って上記区切られた被乗数データの「−２倍」、「−１倍」、「０倍」、「＋１倍」または「＋２倍」の何れかを上記デコードデータとして生成するようにしてもよい。これにより、ブースのアルゴリズムを利用して乗算に要する段数を削減するという作用をもたらす。
【００１８】
また、この第１の側面において、リセット信号を出力する同期制御部をさらに具備し、上記入力値生成部は、上記リセット信号に同期して上記複数の部分乗算結果を生成するようにしてもよい。これにより、データのビット間を同期させるという作用をもたらす。
【発明の効果】
【００１９】
本技術によれば、乗算回路における電流発生を抑止するとともに演算時間を短縮することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】第１の実施の形態における乗算回路の全体構成例を示す図である。
【図２】本技術における２進数データとデコードデータとの対応関係例を示す図である。
【図３】第１の実施の形態における入力値生成部３０１の構成例を示す図である。
【図４】第１の実施の形態における乗算部４０１およびエンコーダ６００の構成例を示す図である。
【図５】第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの構成例を示す図である。
【図６】第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの真理値表の例を示す図である。
【図７】第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの動作タイミング例を示す図である。
【図８】第１の実施の形態における乗算部４０１のフルアダーＤＦＡの構成例を示す図である。
【図９】第１の実施の形態における乗算部４０１のフルアダーＤＦＡの真理値表の例を示す図である。
【図１０】第１の実施の形態における乗算部４０１のフルアダーＤＦＡの動作タイミング例を示す図である。
【図１１】第１の実施の形態における乗算部４０１のフルアダーＤＦＡ'の構成例を示す図である。
【図１２】第１の実施の形態における乗算部４０１のフルアダーＤＦＡ'の真理値表の例を示す図である。
【図１３】第１の実施の形態における乗算部４０１のキャリー処理回路の構成例を示す図である。
【図１４】第１の実施の形態におけるエンコーダ６００の構成例を示す図である。
【図１５】第１の実施の形態における乗算回路の動作例を示す図である。
【図１６】第２の実施の形態における乗算回路の全体構成例を示す図である。
【図１７】第２の実施の形態における入力値生成部３０２の構成例を示す図である。
【図１８】第２の実施の形態における乗算部４０２およびエンコーダ６００の構成例を示す図である。
【図１９】第２の実施の形態における乗算回路の動作例を示す図である。
【図２０】第３の実施の形態における乗算回路の全体構成例を示す図である。
【図２１】第３の実施の形態における３倍値演算部２００の第１の構成例を示す図である。
【図２２】第３の実施の形態における入力値生成部３０３の構成例を示す図である。
【図２３】第３の実施の形態における乗算部４０３およびエンコーダ６００の構成例を示す図である。
【図２４】第３の実施の形態における３倍値演算部２００の第２の構成例を示す図である。
【図２５】第３の実施の形態における３倍値演算部２００の第２の構成例における第１の部分回路を示す図である。
【図２６】第３の実施の形態における３倍値演算部２００の第２の構成例における第１の部分回路の真理値表の例を示す図である。
【図２７】第３の実施の形態における３倍値演算部２００の第２の構成例における第２の部分回路を示す図である。
【図２８】第３の実施の形態における３倍値演算部２００の第２の構成例における第２の部分回路の真理値表の例を示す図である。
【図２９】第３の実施の形態における３倍値演算部２００の第３の構成例を示す図である。
【図３０】第４の実施の形態における乗算回路の全体構成例を示す図である。
【図３１】第４の実施の形態における乗算部４０４およびエンコーダ６００の概略構成例を示す図である。
【図３２】第４の実施の形態における乗算部４０４およびエンコーダ６００の詳細構成例を示す図である。
【図３３】第５の実施の形態における乗算回路の全体構成例を示す図である。
【図３４】第５の実施の形態における入力値生成部３０５の構成例を示す図である。
【図３５】第５の実施の形態における乗算部４０５およびエンコーダ６００の構成例を示す図である。
【図３６】第５の実施の形態における乗算部４０５のＷＴ回路の構成例を示す図である。
【図３７】第５の実施の形態におけるカウントデコーダＣＤの構成例を示す図である。
【図３８】第５の実施の形態における合成処理に関する概念図である。
【図３９】第５の実施の形態における合成回路４５０を付加したＤＦＡ回路の構成例を示す図である。
【図４０】第５の実施の形態における合成回路４５０の真理値表の例を示す図である。
【図４１】第６の実施の形態における積和演算回路の全体構成例を示す図である。
【図４２】第６の実施の形態において想定する積和演算回路の概略構成例を示す図である。
【図４３】３２ビット乗算を８ビット毎に区切って乗算する多倍長乗算の演算フローの一例を示す図である。
【図４４】第６の実施の形態における積和演算部５０１およびエンコーダ６００の構成例を示す図である。
【図４５】第７の実施の形態における積和演算回路の全体構成例を示す図である。
【図４６】第７の実施の形態において想定する積和演算回路の概略構成例を示す図である。
【図４７】第７の実施の形態における積和演算部５０２およびエンコーダ６００の構成例を示す図である。
【図４８】第６および７の実施の形態における積和演算のタイミングを比較するための図である。
【発明を実施するための形態】
【００２１】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（基本構成例）
２．第２の実施の形態（ブースのアルゴリムの適用例）
３．第３の実施の形態（３Ａ事前計算の適用例）
４．第４の実施の形態（ブースのアルゴリムとワレスツリーの適用例）
５．第５の実施の形態（縦方向へのワレスツリー適用例）
６．第６の実施の形態（多倍長乗算への適用例：キャリーを組み込む例）
７．第７の実施の形態（多倍長乗算への適用例：キャリーを別サイクルで行う例）
【００２２】
＜１．第１の実施の形態＞
［乗算回路の全体構成］
図１は、第１の実施の形態における乗算回路の全体構成例を示す図である。この乗算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、入力値生成部３０１と、乗算部４０１と、エンコーダ６００と、同期制御部７００とを備えている。
【００２３】
被乗数レジスタ１１０は、被乗数Ａのデータを保持するレジスタである。乗数レジスタ１２０は、乗数Ｂのデータを保持するレジスタである。被乗数レジスタ１１０および乗数レジスタ１２０が入力値を保持するタイミングを示すクロック信号ＣＬＫは同期制御部７００から供給される。なお、ここでは被乗数レジスタ１１０および乗数レジスタ１２０として８ビットずつのレジスタを想定している。
【００２４】
入力値生成部３０１は、乗算部４０１に対する入力値を生成するものである。この第１の実施の形態では、入力値生成部３０１は、被乗数Ａおよび乗数Ｂのデータをデコードして乗算部４０１に供給する。デコードデータを生成するタイミングを示すリセット信号ＲＳＴは同期制御部７００から供給される。
【００２５】
乗算部４０１は、入力値生成部３０１から供給された被乗数Ａおよび乗数Ｂのデコードデータを乗算し、その乗算結果のデコードデータを生成する演算器である。なお、乗算部４０１は、特許請求の範囲に記載の乗算部の一例である。
【００２６】
エンコーダ６００は、乗算部４０１によって生成された乗算結果データをエンコードして、被乗数Ａと乗数Ｂとの間の乗算結果を出力するものである。
【００２７】
同期制御部７００は、被乗数レジスタ１１０および乗数レジスタ１２０が値を保持するタイミングを示すクロック信号ＣＬＫと、デコードデータを生成するタイミングを示すリセット信号ＲＳＴとを供給することにより同期制御を行うものである。
【００２８】
図２は、本技術における２進数データとデコードデータとの対応関係例を示す図である。被乗数Ａまたは乗数Ｂが２進数データであることを想定して、２ビットずつに区切ると、「００」、「０１」、「１０」、「１１」の４通りの値を示す。これに対し、入力値生成部３０１によってデコードされたデコードデータは４ビットであり、それぞれ「０００１」、「００１０」、「０１００」、「１０００」に対応する。また、デコードデータ「００００」は固定値であり、何れの２進数データにも対応しない。後述するように、乗算部４０１内の各演算器は一旦、デコードデータ「００００」を出力し、その後、「０００１」、「００１０」、「０１００」、「１０００」の何れか１つを出力する。すなわち、各演算器において、固定値「００００」を介して各値に遷移させることにより、４ビットのうち１ビットのみが変化するようにすることができる。
【００２９】
［入力値生成部の構成］
図３は、第１の実施の形態における入力値生成部３０１の構成例を示す図である。ここでは、８ビットの被乗数Ａ（２進数表記：ａ０乃至ａ７）および乗数Ｂ（２進数表記：ｂ０乃至ｂ７）を想定し、乗数Ｂについては２ビット分（ｂ(2n)およびｂ(2n+1)）を代表して示している（ｎは０から３の整数）。
【００３０】
この入力値生成部３０１にはリセット信号ＲＳＴが入力されており、乗算開始直後にリセット信号ＲＳＴはハイレベルに設定される。これにより、入力値生成部３０１は、４ゲート分の回路遅延の後に４ビット毎のデコードデータＤとして「００００」を出力する。そして、リセット信号ＲＳＴがローレベルに設定されると、有効なデコードデータＤが出力されるようになる。この入力値生成部３０１によって生成されたデコードデータＤは乗算部４０１に供給される。４ビット毎のデコードデータＤは、被乗数Ａを２ビットずつに区切ったものと乗数Ｂの各ビットとの部分積に対応している。
【００３１】
［乗算部の構成］
図４は、第１の実施の形態における乗算部４０１およびエンコーダ６００の構成例を示す図である。乗算部４０１は、６個のハーフアダーＤＨＡと、２３個のフルアダーＤＦＡと、キャリー処理回路（２つのＤＣＡ２）とを備えている。ハーフアダーは、キャリー入力のない加算器である。フルアダーは、キャリー入力のある加算器である。乗算部４０１内のハーフアダー、フルアダーおよびキャリー処理回路は、何れもデコードデータを扱うものである。ハーフアダーおよびフルアダーに入力されるデコードデータＤは、入力値生成部３０１から供給される。入力値生成部３０１から乗算部４０１の各加算器に供給されるデコードデータＤの対応関係は図３および図４に図示するとおりである。
【００３２】
エンコーダ６００は、乗算部４０１によって生成されたデコードデータを４ビットずつに区切って２ビットずつの２進数データを出力する。
【００３３】
［ハーフアダーの構成］
図５は、第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの構成例を示す図である。図６は、第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの真理値表の例を示す図である。このハーフアダーＤＨＡは、２つのデコードデータ４ビットａおよびｂを入力とし、デコードデータ４ビットの加算結果ｘ３乃至ｘ０および１ビットの桁上げ（キャリー）Ｃoutを出力する。このハーフアダーＤＨＡは、２つの信号入力をＡＮＤ−ＮＯＲゲートで受けて負論理の中間値を生成して、それを反転して出力する。このハーフアダーＤＨＡのデータパスは、遅延２ゲート分に相当する。また、桁上げＣoutを出力するまでのパスも遅延２ゲート分に相当する。すなわち、加算結果出力とキャリー出力は同じ遅延時間になる。
【００３４】
このハーフアダーＤＨＡでは、入力ａまたはｂの少なくとも何れか一方が固定値「００００」であれば、出力も固定値「００００」となる。また、入力ａまたはｂの何れも固定値「００００」でなければ、両者の加算結果を出力する。加算結果がデコードデータ「１０００」を超える場合には、桁上げＣoutが「１」を示す。これにより、入力信号に遅延差があっても、出力は中間値に遷移することはなく、それに伴う消費電流の増加も起こらない。
【００３５】
図７は、第１の実施の形態における乗算部４０１のハーフアダーＤＨＡの動作タイミング例を示す図である。入力ａおよびｂの両者が有効な値（固定値「００００」以外）を示すようになってから２ゲート分の遅延後に、有効な加算結果を示すようになる。図７（ａ）は、入力ａが先に有効な値を示す場合であり、図７（ｂ）は、入力ｂが先に有効な値を示す場合である。
【００３６】
［フルアダーの構成］
図８は、第１の実施の形態における乗算部４０１のフルアダーＤＦＡの構成例を示す図である。図９は、第１の実施の形態における乗算部４０１のフルアダーＤＦＡの真理値表の例を示す図である。このフルアダーＤＦＡは、２つのデコードデータ４ビットａおよびｂ、桁上げＣinを入力とし、デコードデータ４ビットの加算結果ｘ３乃至ｘ０および１ビットの桁上げＣoutを出力する。このフルアダーＤＦＡは、２つの信号入力をＡＮＤ−ＮＯＲゲートで受けて負論理の中間値を生成し、キャリー入力が「０」の場合は負論理の中間値を反転出力し、「１」の場合はそれを上位ビット側にローテートシフトした後に反転出力する。このフルアダーＤＦＡのデータパスは、遅延２ゲート分に相当する。また、桁上げＣoutを出力するまでのパスも遅延２ゲート分に相当する。すなわち、加算結果出力とキャリー出力は同じ遅延時間になる。
【００３７】
このフルアダーＤＦＡでは、入力ａまたはｂの少なくとも何れか一方が固定値「００００」であれば、出力も固定値「００００」となる。また、入力ａまたはｂの何れも固定値「００００」でなければ、入力ａおよびｂの加算結果にさらに桁上げＣinを加算した加算結果を出力する。加算結果がデコードデータ「１０００」を超える場合には、桁上げＣoutが「１」を示す。これにより、入力信号に遅延差があっても、出力は中間値に遷移することはなく、それに伴う消費電流の増加も起こらない。
【００３８】
図１０は、第１の実施の形態における乗算部４０１のフルアダーＤＦＡの動作タイミング例を示す図である。入力ａおよびｂの両者が有効な値（固定値「００００」以外）を示すようになってから２ゲート分の遅延後に、有効な加算結果を示すようになる。図１０（ａ）は、入力ａが最後に有効な値を示す場合である。図１０（ｂ）は、入力ａおよびｂのあとから桁上げＣinが「１」を示すようになった場合である。
【００３９】
図１１は、第１の実施の形態における乗算部４０１のフルアダーＤＦＡ'の構成例を示す図である。図１２は、第１の実施の形態における乗算部４０１のフルアダーＤＦＡ'の真理値表の例を示す図である。図４のＤＦＡ'54、ＤＦＡ'66は、上段から受け取る値がキャリーのみであり、加算値のデコードデータのうち上位２ビットが「０」に固定されるため、回路構成を工夫することにより回路規模の増加を抑えている。
【００４０】
［キャリー処理回路の構成］
図１３は、第１の実施の形態における乗算部４０１のキャリー処理回路の１つ（ＤＣＡ２）の構成例を示す図である。上述のようにキャリー処理回路は２つのＤＣＡ２（ＤＣＡ２48およびＤＣＡ２68）から構成される。図１３（ａ）は１つのＤＣＡ２を簡略表示したものである。図１３（ｂ）は１つのＤＣＡ２の内部構成例である。このＤＣＡ２は、図１３（ａ）に示すように、２つのキャリーアダーＤＣＡを含んで構成される。このＤＣＡ２は、デコードデータ８ビット（ａＬおよびａＨ）、２ビットデータｂ（ｂＬおよびｂＨ）、１ビットの桁上げＣinを入力とする。そして、デコードデータ８ビットの加算結果（ｄ０Ｌ乃至ｄ３Ｌおよびｄ０Ｈ乃至ｄ３Ｈ）および１ビットの桁上げＣoutを出力する。このキャリー処理回路のＤＣＡ２の入力ａからのデータパスは、遅延２ゲート分に相当する。
【００４１】
一般に、乗算器は、マトリクス状に配置されたＣＳＡ（Carry Save Adder）とその後に配置されるＣＰＡ（Carry Propagate Adder）とにより構成される。ＣＳＡマトリクスの入力に加算値がセットされると、各ＣＳＡは動作を開始し、マトリクスの上の段から下の段に向かって演算結果は確定していく。そして、ＣＳＡの最終段の出力が確定すると、その下のＣＰＡでＣＳＡ列からのデータとキャリーを足して乗算結果を下位ビットから確定させていく。これに対し、本開示の技術では、デコードデータを演算に用いるため、キャリー処理回路のデータ入力はデコードデータとする必要がある。これには前述したＤＨＡおよびＤＦＡのキャリー出力を加算値入力の一方の入力ｄ１に接続し、その反転信号をｄ０に接続する構成を採れば同じ構成を用いることができる。
【００４２】
ＤＨＡおよびＤＦＡは、上述のように、加算結果およびキャリー出力をともに２段の論理演算で出力する。すなわち、１段目では、２つのデコード値から負論理の加算値および負論理のキャリーをロジック回路で生成する。２段目では、キャリー入力が「０」の場合、１段目の負論理の加算値を反転出力する。キャリー入力が「１」の場合、負論理の加算結果をローテートシフトして反転出力する。そして、演算結果が「３」かつキャリー入力が「１」である場合、または、１段目からのキャリーがある場合には、キャリーを出力する。
【００４３】
マトリクス状に配置されたＣＳＡからの出力は、ほぼ同じタイミングで最下段のＣＰＡで構成されたキャリー処理回路に入力される。そのため、各キャリー処理回路の１段目の出力はほぼ同じタイミングで確定する。そして、キャリー処理回路の２段目の動作が下位ビット側から上位ビット側に確定していき、これが乗算時間の後半の時間を決定する。
【００４４】
ＤＦＡでは反転させたキャリー入力で２段目の処理を動作させているが、ＤＣＡ２では２つのＤＦＡを配置し、キャリー処理回路の１つ目は正論理で、２つ目は負論理で動作させる構成を採る。これにより、２つのキャリー処理回路により２ゲート遅延でキャリー出力することが可能となる。キャリー処理回路では、必要となるのは出力のキャリー結果で、途中のキャリー結果は使用しないため、中間値が反転値であっても問題ない。これにより、キャリー処理回路でのキャリーの遅延は、ＤＦＡの半分となり、乗算演算時間のうちキャリー処理に要する時間が短縮される。
【００４５】
［エンコーダの構成］
図１４は、第１の実施の形態におけるエンコーダ６００の構成例を示す図である。このエンコーダ６００は、乗算部４０１によって生成されたデコードデータを４ビットずつに区切って２ビットずつの２進数データを出力する。このエンコーダ６００のデータパスは、遅延２ゲート分に相当する。
【００４６】
［乗算回路の動作］
図１５は、第１の実施の形態における乗算回路の動作例を示す図である。同期制御部７００は、演算開始直後にリセット信号ＲＳＴを所定期間ハイレベルにする。これにより、入力値生成部３０１の４ゲート分の回路遅延経過後に、各加算器へのデコード入力は全て「００００」となる。そのため、乗算器を構成する各ＤＨＡおよびＤＦＡの少なくとも一方の入力は「００００」となり、加算器の回路遅延の２ゲート遅延後に全てのＤＨＡおよびＤＦＡのデコード出力は「００００」になり、キャリー出力も「０」となる。
【００４７】
リセット信号ＲＳＴがローレベルになると、入力値生成部３０１の出力は、被乗数Ａの各２ビットのデコードデータとして乗算部４０１に供給される。このとき、乗算部４０１の加算器マトリクスの２段目以降のＤＦＡの一方の入力は入力値生成部３０１からの加算値となるが、他方の入力が上段のＤＨＡまたはＤＦＡからの演算結果「００００」であるため、２段目以降のＤＦＡの出力は「００００」のままである。そして、加算器の演算時間である２ゲート遅延後に１段目の出力が確定して下段に加算結果が出力されると、２段目の加算器が動作を開始し、演算時間経過後に出力が確定して３段目に出力される。以下同様に、加算器の演算時間が経過する度に加算器出力が中間値に変化することなく「００００」から演算結果に変化し、この変化により次の段の加算器列が動作を開始する。
【００４８】
演算が加算器マトリクスの最終段まで到達すると、最終段の加算器列からのデコードされた加算結果およびキャリーが確定した値となる。そして、キャリー処理回路により、加算器マトリクスからのデコードされた加算結果とキャリーとの加算が行われる。ここで、キャリー処理回路のＤＣＡ２は２個直列に配置され、その処理時間は４ビットのバイナリ値に対して４ゲート遅延であり、このキャリー処理時間に関しては従来構成の少なくとも半分に短縮される。演算結果はデコードデータであるため、エンコーダ６００により、バイナリデータに変換されて出力される。
【００４９】
このように、第１の実施の形態によれば、演算結果にかかわらず４本の信号線のうち１本だけが必ず「１」に変化し、これが次の段の加算器の動作を開始させる。しかも、演算結果とキャリーの生成時間が同じであるため、次の段の加算器での入力に遅延差は生じにくく、仮に遅延差があったとしても、両加算値入力がデコードデータにならないと演算を開始しないように構成されている。さらに、ＤＨＡおよびＤＦＡはともに、データの加算処理の部分とキャリー処理の部分とで構成されているが、加算処理の部分はデコードデータの生成回路は同じ構成であるため、演算結果の値にかかわらず動作電流の差異は小さい。これにより、被乗数Ａおよび乗数Ｂの値にかかわらず乗算部４０１の動作電流の変動は小さく、従来のバイナリ動作の乗算回路と比べてその変動は小さく抑えられる。そして、演算時間の構成要素のキャリー処理時間は、キャリー処理回路としてＤＣＡ２の構成を用いることにより、少なくとも従来構成の半分に短縮される。
【００５０】
＜２．第２の実施の形態＞
［乗算回路の全体構成］
図１６は、第２の実施の形態における乗算回路の全体構成例を示す図である。この乗算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、入力値生成部３０２と、乗算部４０２と、エンコーダ６００と、同期制御部７００とを備えている。入力値生成部３０２および乗算部４０２以外の構成は、第１の実施の形態のものと同様であるため、詳細な説明を省略する。
【００５１】
入力値生成部３０２は、乗算部４０２に対する入力値を生成するものである。この第２の実施の形態では、入力値生成部３０２は、第１の実施の形態と比べて、ブースデコーダを有する点が異なる。すなわち、入力値生成部３０２は、乗数Ｂのデータに対してブースデコーディングし、被乗数Ａおよび乗数Ｂのデータをデコードして乗算部４０２に供給する。
【００５２】
乗算部４０２は、入力値生成部３０２から供給された被乗数Ａおよび乗数Ｂのデコードデータを乗算し、その乗算結果のデコードデータを生成する演算器である。なお、乗算部４０２は、特許請求の範囲に記載の乗算部の一例である。
【００５３】
［入力値生成部の構成］
図１７は、第２の実施の形態における入力値生成部３０２の構成例を示す図である。ここでは、８ビットの被乗数Ａ（２進数表記：ａ０乃至ａ７）および乗数Ｂ（２進数表記：ｂ０乃至ｂ７）を想定し、乗数Ｂについては３ビット分（ｂ(2m)、ｂ(2m+1)、ｂ(2m+2)）を代表して示している（ｍは０から４の整数）。
【００５４】
ブースのアルゴリズムを用いる場合、拡張した乗数Ｂの所定のフィールドである３ビットの値をブースデコーダによってデコードして選択信号を生成する。この選択信号に従って、被乗数Ａの「−２倍」、「−１倍」、「０倍」、「＋１倍」または「＋２倍」の何れかの中から加算値を選択して、乗算部４０２の加算器に設定する。第２の実施の形態では、加算値の絶対値が「０」、「１Ａ」、「２Ａ」の何れであるかを乗数Ｂの３ビットから判断して、対応する値を入力値生成部３０２に取り込み、その後、乗数Ｂの３ビットから加算値の符号を判断する。そして、正の場合はそのままの値に対して、負の場合は取り込んだ値を反転した上で、入力値生成部３０２において図２のデコードデータへのデコードを行い、乗算部４０２の加算器マトリクスの入力値として供給する。
【００５５】
［乗算部の構成］
図１８は、第２の実施の形態における乗算部４０２およびエンコーダ６００の構成例を示す図である。乗算部４０２は、２個のハーフアダーＤＨＡと、２３個のフルアダーＤＦＡと、キャリー処理回路（２つのＤＣＡ２）とを備えている。ハーフアダーおよびフルアダーに入力されるデコードデータＤは、入力値生成部３０２から供給される。入力値生成部３０２から乗算部４０２の各加算器に供給されるデコードデータＤの対応関係は図１７および図１８に図示するとおりである。ハーフアダー、フルアダーおよびＤＣＡ２の内容は、上述の第１の実施の形態について説明したものと同様である。また、エンコーダ６００も、上述の第１の実施の形態について説明したものと同様である。
【００５６】
［乗算回路の動作］
図１９は、第２の実施の形態における乗算回路の動作例を示す図である。第２の実施の形態においても、第１の実施の形態の場合と同様に、リセット信号ＲＳＴを乗算開始のタイミングで所定期間ハイレベルにして、加算器マトリクスへの入力値を固定値「００００」にする。これにより、加算器マトリクスの加算器の出力は全て固定値「００００」となる。その後、加算器マトリクスへの供給値は加算値となるが、２段目以降の加算器は、その入力の一方は上段からの固定値「００００」であるため、演算を開始せず、その下段への出力は固定値「００００」のままである。上段の演算が終了して、その演算結果がデコード値になって初めて加算器は演算を開始し、加算器の演算遅延後に下段に演算結果が出力され、この加算器は動作を停止する。この過程で、出力が中間値を出力することはなく、中間値遷移による余分な電流を消費しない。そして、加算器マトリクスの演算が終了後の、キャリーの処理では ＤＣＡ２を２つ配置し、キャリー処理時間は従来構成の少なくとも半分に短縮される。
【００５７】
このように、第２の実施の形態によれば、ブースのアルゴリズムを用いることにより、乗算部の加算器マトリクスの段数を半分近くに削減することができる。また、演算に必要な加算値について、ビットシフトで対応できる被乗数Ａの２倍値までで対応することができる。しかしながら、ブースのアルゴリズムでは負の値を用いるため、２の補数生成のための「１」加算および負の場合の上位の「１」拡張に伴う上位の加算処理も必要となり、加算器マトリクスの１列の加算器の個数が増えてしまう。そして、それに伴って消費電流も増えるという問題がある。そこで、乗算の加算器マトリクスの段数を半分にする方法として、被乗数Ａの３倍値（３Ａ）を事前計算して、乗数Ｂの２ビット値に応じて対応する値（０、Ａ、２Ａ、３Ａ）から１つを選択して加算する方法を、以下の第３の実施の形態として開示する。
【００５８】
＜３．第３の実施の形態＞
［乗算回路の全体構成］
図２０は、第３の実施の形態における乗算回路の全体構成例を示す図である。この乗算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、３倍値演算部２００と、入力値生成部３０３と、乗算部４０３と、エンコーダ６００と、同期制御部７００とを備えている。３倍値演算部２００、入力値生成部３０３および乗算部４０３以外の構成は、第１の実施の形態のものと同様であるため、詳細な説明を省略する。
【００５９】
３倍値演算部２００は、被乗数Ａの３倍値（３Ａ）を演算して入力値生成部３０２に出力するものである。具体的な構成例については後述する。
【００６０】
入力値生成部３０３は、乗算部４０３に対する入力値を生成するものである。この第３の実施の形態では、入力値生成部３０３は、第１の実施の形態と比べて、３Ａ事前計算値を入力とする点が異なる。
【００６１】
乗算部４０３は、入力値生成部３０３から供給された被乗数Ａおよび乗数Ｂのデコードデータを乗算し、その乗算結果のデコードデータを生成する演算器である。なお、乗算部４０３は、特許請求の範囲に記載の乗算部の一例である。
【００６２】
［３倍値演算部の構成］
図２１は、第３の実施の形態における３倍値演算部２００の第１の構成例を示す図である。この３倍値演算部２００は、８ビットの被乗数Ａ（２進数表記：ａ０乃至ａ７）を入力として、１０ビットの３倍値（３Ａ、２進数表記：ａ０'乃至ａ９'）を出力することを想定している。この３倍値演算部２００の第１の構成例では、ａ１'へ通じる経路からａ８'へ至るまでの経路において１０ゲート分の遅延を要する。
【００６３】
［入力値生成部の構成］
図２２は、第３の実施の形態における入力値生成部３０３の構成例を示す図である。ここでは、８ビットの被乗数Ａ、１０ビットの３倍値（３Ａ）、および、乗数Ｂ（２進数表記：ｂ０乃至ｂ７）を想定し、乗数Ｂについては２ビット分（ｂ(2n)およびｂ(2n+1)）を代表して示している（ｎは０から３の整数）。
【００６４】
この第３の実施の形態における入力値生成部３０３では、乗数Ｂの所定のフィールドである２ビットの値に基づいて選択信号が生成される。そして、被乗数Ａ、２Ａまたは３Ａの何れかが選択されてデコードデータとして出力される。２Ａの値は被乗数Ａを左シフトすることにより得られる。３Ａの値は３倍値演算部２００から供給される。
【００６５】
この構成例では、被乗数Ａまたは乗数Ｂが更新されると、３Ａの事前計算が開始され、同時にリセット信号ＲＳＴがハイレベルとなり、加算器マトリクスへ供給されるデコードデータは全て固定値「００００」となる。これにより、２ゲート遅延後に加算器マトリクスの出力は全て固定値「００００」に変化する。そして、３Ａの事前計算時間にマージンを見込んだ時間が経過した後、リセット信号ＲＳＴがローレベルに設定される。これにより、乗数の２ビットをデコードした選択信号ＳＥＬ＿１Ａ乃至ＳＥＬ＿３Ａがアクティブとなる。乗数の２ビットが「００」の場合は、３本の選択信号はいずれもローレベルで、入力値生成部３０３への取り込み値はなく、デコード出力はｄ０のみがハイレベルとなる。乗数の２ビットが「０１」の場合は、選択信号ＳＥＬ＿１Ａのみがハイレベルとなり、乗数Ａがそのままデコードされて加算器マトリクスへ供給される。乗数の２ビットが「１０」の場合は、選択信号ＳＥＬ＿２Ａのみがハイレベルとなり、乗数Ａを１ビットだけ上位側にシフトさせ、ＬＳＢを「０」とした値がデコード回路に入力される。この場合、取り込み値は「２Ａ」となり、各々デコードされて加算器マトリクスへ供給される。乗数の２ビットが「１１」の場合は、選択信号ＳＥＬ＿３Ａのみがハイレベルとなり、事前計算した「３Ａ」の値が選択されて加算値生成回路に取り込まれ、デコードされて加算器マトリクスへ供給される。
【００６６】
［乗算部の構成］
図２３は、第３の実施の形態における乗算部４０３およびエンコーダ６００の構成例を示す図である。乗算部４０３は、４個のハーフアダーＤＨＡと、８個のフルアダーＤＦＡと、キャリー処理回路（２つのＤＣＡ２）とを備えている。ハーフアダーおよびフルアダーに入力されるデコードデータＤは、入力値生成部３０３から供給される。入力値生成部３０３から乗算部４０３の各加算器に供給されるデコードデータＤの対応関係は図２２および図２３に図示するとおりである。ハーフアダー、フルアダーおよびＤＣＡ２の内容は、上述の第１の実施の形態について説明したものと同様である。また、エンコーダ６００も、上述の第１の実施の形態について説明したものと同様である。
【００６７】
第３の実施の形態では、演算の開始でリセット信号ＲＳＴが所定期間ハイレベルとなることにより、乗算部４０２内の加算器の全ての入力は固定値「００００」になる。これにより、加算器の演算遅延後、加算器の全ての出力は固定値「００００」になる。その後、加算器への入力値はデコードされた加算値となるが、２段目以降の加算器の入力値は、上段の加算器の出力である固定値「００００」であるため、演算動作を開始しない。上段の加算器の動作が終了し、その出力が固定値「００００」から演算結果であるデコードデータに変化した段階で、それを一方の入力とする加算器が演算動作を開始する。そして、加算器の演算遅延が経過した後、その出力は固定値「００００」から演算結果であるデコードデータに変化して下段の加算器に出力し、その加算器は動作を終了するとともに、下段の加算器は動作を開始する。
【００６８】
この過程で、加算器は上段からの出力に基づく演算を行ってその結果を下段に出力して動作を停止し、中間値を出力することはなく、余分な電流を消費しない。さらに、加算器マトリクスの加算器列の加算器の数はブースのアルゴリズムを用いた場合に比べて少なく、段数も１段少ないため、ブースのアルゴリズムを用いた場合に比べて加算器数が減ることによる消費電流の削減効果が期待できる。
【００６９】
このように、被乗数Ａの３倍値（３Ａ）を事前計算して、乗数の２ビット値に応じて対応する値を加算する演算方法は、回路構成および消費電流の点で優れている。しかし、３Ａの事前計算に要する時間は、８ビット乗算の場合は１０ゲート遅延程度であるが、１６ビット乗算の場合は１８ゲート遅延、３２ビット乗算の場合は３４ゲート遅延、そして、６４ビット乗算の場合は６６ゲート遅延程度を要する。すなわち、乗算対象となるデータのビット幅が増加するにつれて、乗算時間に対する事前計算の時間が無視できなくなる。そこで、これを改善する方法として、事前計算の３Ａ演算は元々の値とそれを１ビット上位側にシフトした値との加算という限定された加算であることを利用した構成例を、次に説明する。
【００７０】
［３倍値演算部の他の構成］
図２４乃至２８は、第３の実施の形態における３倍値演算部２００の第２の構成例を示す図である。この３倍値演算部２００の第２の構成例は、８ビットの被乗数Ａ（２進数表記：ａ０乃至ａ７）を入力として、１０ビットの３倍値（３Ａ、２進数表記：ａ０'乃至ａ９'）を出力することを想定している。
【００７１】
この３倍値演算部２００の第２の構成例では、４ビット単位で演算し、この演算回路からＣＬＡ（Carry Look Ahead）演算に用いられるＧ（Generate）信号とＰ（Propagate）信号も生成する。そして、各４ビット演算単位からのＧおよびＰ信号を用いてキャリーを事前演算で生成して、それを用いて各４ビット演算単位の演算結果のキャリー処理をする。これにより、３Ａの演算時間を短縮する構成が実現できる。
【００７２】
図２９は、第３の実施の形態における３倍値演算部２００の第３の構成例を示す図である。この３倍値演算部２００の第３の構成例は、１６ビットの被乗数Ａ（２進数表記：ａ０乃至ａ１５）を入力として、１８ビットの３倍値（３Ａ、２進数表記：ａ０'乃至ａ１７'）を出力することを想定している。この３倍値演算部２００の第３の構成例は、４ビット単位で演算する点で第２の構成例と同様である。
【００７３】
この３倍値演算部２００の第３の構成例では、１６ビットの被乗数の３倍値の事前計算を、７ゲート遅延で終了することができる。先読みするキャリーを増やしても、同じ遅延時間で事前計算を終了することができる。しかし、先読みするキャリーを増やすと、ＣＬＡ演算に要する演算素子の入力数は増え、例えば３２ビットの被乗数の３倍値の事前計算を行う場合、８入力のＮＡＮＤ回路またはＮＯＲ回路が必要となる。さらに、６４ビットの場合は、１６入力のＮＡＮＤ回路またはＮＯＲ回路が必要となって、現実的ではなくなる。現実的な方法として、例えば６４ビットの被乗数の３倍値の事前計算をする場合、演算を上位下位の３２ビットずつの演算に分け、下位３２ビットの演算結果からのキャリーを上位３２ビット演算のキャリー入力とする構成を採ることができる。この場合、上位３２ビットの演算結果は、下位３２ビットの演算結果より２ゲート遅延だけ遅れて確定するが、この９ゲート遅延は問題とならないレベルと考えられる。
【００７４】
このように、第３の実施の形態によれば、被乗数Ａの３倍値（３Ａ）を事前計算することにより、加算器マトリクスの段数を削減し、加算器の数を減少させることができる。
【００７５】
＜４．第４の実施の形態＞
［乗算回路の全体構成］
図３０は、第４の実施の形態における乗算回路の全体構成例を示す図である。この乗算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、入力値生成部３０２と、乗算部４０４と、エンコーダ６００と、同期制御部７００とを備えている。乗算部４０４以外の構成は、第２の実施の形態のものと同様であるため、詳細な説明を省略する。
【００７６】
乗算部４０４は、入力値生成部３０２から供給された被乗数Ａおよび乗数Ｂのデコードデータを乗算し、その乗算結果のデコードデータを生成する演算器である。この乗算部４０４は、ブースのアルゴリズムを適用した構成に対してワレスツリーを適用することにより構成される。なお、乗算部４０４は、特許請求の範囲に記載の乗算部の一例である。
【００７７】
なお、入力値生成部３０２は、第２の実施の形態におけるものと同様であり、第１の実施の形態と比べて、ブースデコーダを有する点が異なる。
【００７８】
［乗算部の構成］
図３１および図３２は、第４の実施の形態における乗算部４０４およびエンコーダ６００の構成例を示す図である。この乗算部４０４は、入力値生成部３０２においてブースのアルゴリズムが適用されたことを前提として、加算器マトリクスにおいてワレスツリーおよびフルアダーを構成している。入力値生成部３０２から乗算部４０４の各ワレスツリーまたはフルアダーに供給されるデコードデータＤの対応関係は図１７、図３１および図３２に図示するとおりである。
【００７９】
この第４の実施の形態においては演算段数の変化はなく、加算器マトリクスでの演算時間の短縮効果は得られない。ただし、この第４の実施の形態では、デコード単位内でのビット間のキャリーが内在されるため、ビット間のキャリー信号が不要となり、消費電流の削減効果はある。
【００８０】
＜５．第５の実施の形態＞
［乗算回路の全体構成］
図３３は、第５の実施の形態における乗算回路の全体構成例を示す図である。この第５の実施の形態における乗算回路は、加算マトリクスのデータを縦に見てワレスツリーにより加算するものである。この乗算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、入力値生成部３０５と、乗算部４０５と、エンコーダ６００と、同期制御部７００とを備えている。入力値生成部３０５および乗算部４０５以外の構成は、第１の実施の形態のものと同様であるため、詳細な説明を省略する。
【００８１】
入力値生成部３０５は、乗算部４０５に対する入力値を生成して乗算部４０５に供給するものである。乗算部４０５は、入力値生成部３０５から供給された入力値の乗算結果を算出して、その乗算結果のデコードデータを生成する演算器である。なお、乗算部４０５は、特許請求の範囲に記載の乗算部の一例である。
【００８２】
［入力値生成部の構成］
図３４は、第５の実施の形態における入力値生成部３０５の構成例を示す図である。ここでは、８ビットの被乗数Ａ（２進数表記：ａ０乃至ａ７）および乗数Ｂ（２進数表記：ｂ０乃至ｂ７）を想定している。この第５の実施の形態では、被乗数Ａおよび乗数Ｂの各ビットの部分積が生成され、乗算部４０５の加算器マトリクスに対する入力値とされる。
【００８３】
［乗算部の構成］
図３５は、第５の実施の形態における乗算部４０５およびエンコーダ６００の構成例を示す図である。乗算部４０５は、４個のバイナリデータのハーフアダーと、４個のバイナリデータのフルアダーと、５個のデコードデータのハーフアダーと、８個のデコードデータのフルアダーと、１個のＯＲ回路とを備えている。また、この乗算部４０５は、１９個のカウントデコーダＣＤと、１個のデコーダＤｅｃと、５個の合成回路と、５個のＤＣＡとを備えている。
【００８４】
カウントデコーダＣＤは、ビット列単位で３ビット毎に「１」の数をカウントして、そのデコード値を生成するカウントアンドデコード回路である。デコーダＤｅｃは、図２に示したように、２進数データからデコードデータへのデコードを行うデコード回路である。合成回路は、各ビットを加算する際に２ビットずつで重なり合うビットを合成するものである。
【００８５】
図３６（ａ）は、図３５において最も処理の多い８ビットの処理をする部分であるＷＴ＿７の回路構成を示す図である。従来構成では、７個の加算器で構成され、下位ビット側からのキャリー入力および上位ビット側へのキャリー出力はともに５本である。これに対して、この第５の実施の形態では、カウントデコーダＣＤが３個配置され、この回路で３ビットの入力値からデコードデータを生成し、ＤＦＡへ供給されることにより加算処理が実行される。ＤＦＡ加算器の個数は３個であり、下位ビット側からのキャリー入力および上位ビット側へのキャリー出力はともに２本である。これは、ＤＦＡ回路が２ビットのデコードデータの加算回路であり、デコード単位内のビット間のキャリーは内在させているためである。これにより、従来構成のＦＡでは、３ビットのデータ入力に対して１本のキャリー出力が発生するが、ＤＦＡ構成では最大で７ビットのデータ入力に対して１本のキャリー出力が発生することになる。したがって、上位ビットへのキャリー出力および下位ビットからのキャリー入力の本数が減り、それに伴ってキャリー処理のための加算器の個数が減り、キャリー処理に伴う加算器での消費電流が削減される。
【００８６】
この演算は、各演算対象ビットの縦の加算を行うが、演算結果は２ビットのデコードデータとなり、演算の最後において隣接するビットの２ビットデコードデータとの加算処理を行う必要がある。このため、隣接する両隣のデータから値を合成する処理と、合成結果と加算する処理とが最後に配置されている。この例では、最初にカウントデコーダＣＤにおいてデコード値に変換したデータで加算処理を行い、最後に隣接するデータからの合成値と加算処理する必要がある。この処理は必ず実行する必要のある処理であるが、乗算するデータのビット数が多くなるに従って、この合成および加算の処理時間の比率は小さくなり、演算時間の短縮効果は大きくなる。
【００８７】
図３６（ｂ）は、加算するビット数が１６ビットの場合の回路構成を示す図である。従来のようにバイナリの加算器によって処理した場合には、例えば、加算器の個数は１６個で、下位ビットからのキャリー入力および上位ビットへのキャリー出力はともに１５本であり、これが加算器の数が多い一因となっている。それに対して、本技術を適用した場合、４個のカウントデコーダＣＤと５個のＤＦＡ回路および１個の合成回路によって構成され、下位からのキャリー入力および上位へのキャリー出力はともに４本で、従来構成に比べて格段に少ない。
【００８８】
この第５の実施の形態では、各ビットで所定ビットの１の個数（ＨＷ：Hamming Weight）を計数した値をデコードデータに変換して、デコードデータでの演算を行う。そして、キャリー処理回路の直前でビット重みのあるデコードデータに変換して、キャリー処理を行う。
【００８９】
図３７は、第５の実施の形態におけるカウントデコーダＣＤの構成例を示す図である。この第５の実施の形態では縦方向でデコードデータを生成するが、この場合、演算対象のビット重みは同じであるため、例えば３ビットを加算して、その加算結果をデコードして入力値として用いる。この例では、カウントデコーダＣＤは、３ビットの２進数データＣｉｎ＿０乃至Ｃｉｎ＿２を入力として、４ビットのデコードデータｄ０乃至ｄ３を出力する。また、このカウントデコーダＣＤの出力段には、演算前に出力を固定値「００００」に制御するためのリセット信号ＲＳＴが入力されている。
【００９０】
乗算開始時に、カウントデコーダＣＤにおいて、リセット信号ＲＳＴを所定期間ローレベルとし、カウントデコーダＣＤの出力のデコードデータを固定値「００００」に制御することにより、ＤＦＡ回路ツリーの出力を一旦、固定値「００００」に制御する。これにより、ＤＦＡの各入力は固定値「００００」に設定され、リセット信号ＲＳＴがハイレベルとされた後、ＤＦＡは２つの入力が固定値「００００」からともにデコードデータになってはじめて出力値が固定値「００００」からデコードデータに変化する。そして、デコードデータは下段のＤＦＡに入力され、中間値への遷移が発生しないように制御される。これらにより、加算器等の回路素子の数はこの例では約３分の２になり、さらに中間値への遷移も抑えられることにより、消費電流の削減効果は大きくなる。
【００９１】
図３８は、第５の実施の形態における合成処理に関する概念図である。第５の実施の形態では、各ビットの加算結果は、２ビットのデコード値とキャリーであり、隣接するビットの演算結果と重なる演算結果がある。そのため、演算の最終段階において、隣接するビットの演算結果からの合成値との加算処理を行って、キャリー処理回路へ入力する値を生成する合成処理が必要となる。
【００９２】
ここで、ビットｂnの加算結果の２ビットのデコードデータに着目すると、この値は、ビットｂn-1の加算結果のデコード値の上位側の値とｂn+1の加算結果の下位側の値と重なっている。そのため、対応する２つのデコードデータからの合成により加算値を生成し、ビットｂnの加算結果のデコードデータと加算処理する。
【００９３】
図３９は、第５の実施の形態における合成回路４５０を付加したＤＦＡ回路の構成例を示す図である。この図は、図８のＤＦＡ回路に対して合成回路４５０を付加した構成となっている。合成回路４５０は、各ビットを加算する際に２ビットずつで重なり合うビットを合成するものである。図３５の各加算器による加算結果は、隣接する加算結果と１ビットずつ重なっている。そのため、隣接する加算結果から合成により演算結果を生成し、デコードデータの結果を得る。図４０は、第５の実施の形態における合成回路４５０の真理値表の例を示す図である。
【００９４】
このように、第５の実施の形態によれば、従来では縦のビットの値に対して行われていた処理が、横のビットの値に対しての演算に変換される。そして、この変換により、キャリー処理回路での処理に、上述の他の実施の形態の構成例を適用することができ、高速なキャリー処理が可能となり、ここでも処理時間の短縮効果を得ることができる。
【００９５】
＜６．第６の実施の形態＞
［積和演算回路の全体構成］
図４１は、第６の実施の形態における積和演算回路の全体構成例を示す図である。この第６の実施の形態は、多倍長乗算を想定したものであり、積和演算の途中結果を保持しながら加算を行う。この第６の実施の形態における積和演算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、３倍値演算部２００と、入力値生成部３０３と、積和演算部５０１と、エンコーダ６００と、同期制御部７００とを備えている。この第６の実施の形態における積和演算回路は、第３の実施の形態における乗算回路をベースにしたものであり、積和演算部５０１以外の構成は、第３の実施の形態のものと同様である。なお、積和演算部５０１は、特許請求の範囲に記載の乗算部の一例である。
【００９６】
例えば、公開鍵暗号では、その演算過程で複数回の乗算処理が行われる。この公開鍵暗号は、乗算器のビット幅より遥かに大きい値をべき乗剰余演算して暗号化ならびに復号化の処理を行う暗号である。例えば、３２ビットの乗算を行う場合で、乗算器の幅が８ビットの場合、図４２に示すように８ビットの乗算器の下に１８ビットの加算器およびレジスタを配置される。被乗数および乗数はメモリに格納され、必要に応じてメモリから取り出されて乗算器にセットされる。各ワードの演算終了後に、乗算結果がメモリに格納される。
【００９７】
図４３は、３２ビット乗算を８ビット毎に区切って乗算する多倍長乗算の演算フローの一例を示す図である。まず、ステップ１では、被乗数Ａ０と乗数Ｂ０をメモリから取り出して乗算し、演算結果をレジスタに格納する。格納された値のうち下位８ビットは、多倍長乗算の最下位ワードとしてメモリに出力される。ステップ２では、被乗数Ａ１と乗数Ｂ０をメモリから取り出して乗算し、その演算結果を、レジスタ値を８ビット下位側にシフトした値と加算する。その加算結果はレジスタに格納される。ステップ３では、被乗数Ａ０と乗数Ｂ１をメモリから取り出して乗算し、その演算結果を同じビットのレジスタ値と加算し、その演算結果をレジスタに格納する。格納された値のうち下位８ビットは、多倍長乗算の下位２番目のワードとしてメモリに出力される。ステップ４では、被乗数Ａ２と乗数Ｂ０をメモリから取り出して乗算し、その演算結果を、レジスタ値を８ビット下位側にシフトした値と加算して、その加算結果をレジスタに格納する。ステップ５では、被乗数Ａ１と乗数Ｂ１をメモリから取り出して乗算し、その演算結果を同じビットのレジスタ値と加算して、その演算結果をレジスタに格納する。ステップ６では、被乗数Ａ０と乗数Ｂ２をメモリから取り出して乗算し、その演算結果を同じビットのレジスタ値と加算して、その演算結果をレジスタに格納する。格納された値のうち下位８ビットは、多倍長乗算の下位３番目のワードとしてメモリに出力される。以後、同様な操作が繰り返される。
【００９８】
この多倍長乗算の各サイクルの積和演算において、乗算器内では加算器マトリクスの加算とキャリー処理によって乗算結果を生成し、その乗算結果に対して直前までの加算結果と加算してキャリー処理して、そのサイクルでの演算処理を実行している。
【００９９】
多倍長乗算では、必ず積和演算が必要であるため、暗号等の多倍長乗算器を設計する場合、積和演算の途中結果である加算値も、乗算器の加算器マトリクスでの演算対象に加える構成を採用することができる。その構成例を図４４に示す。
【０１００】
［積和演算部の構成］
図４４は、第６の実施の形態における積和演算部５０１およびエンコーダ６００の構成例を示す図である。積和演算部５０１は、５個のハーフアダーＤＨＡと、１５個のフルアダーＤＦＡと、キャリー処理回路（２つのＤＣＡ２）と、８個の４ビットレジスタＲｅｇと、８個のスイッチと、２ビットカウンタと、デコーダとを備えている。同じ３倍値演算を前提とした第３の実施の形態と比較して、加算器マトリクスの下部の各デコード単位に１個のＤＦＡが追加され、最下段にはレジスタが配置されている。ハーフアダーおよびフルアダーに入力されるデコードデータＤは、入力値生成部３０３またはスイッチから供給される。入力値生成部３０３から積和演算部５０１の各加算器に供給されるデコードデータＤの対応関係は図２２および図４４に図示するとおりである。ハーフアダー、フルアダーおよびＤＣＡ２の内容は、上述の第１の実施の形態について説明したものと同様である。また、エンコーダ６００も、上述の第１の実施の形態について説明したものと同様である。
【０１０１】
レジスタは、積和演算の途中結果を格納するものである。スイッチは、対応するＤＦＡに供給する入力値を切り替えるものである。すなわち、ＤＦＡ入力は、一方は上段のＤＦＡからの乗算結果であり、他方はスイッチを介して同じデコード単位のデコードデータと乗算器のビット数分上位のデコード単位のデコードデータの何れかが入力される。このスイッチは、桁ワードが切り替わる時のみｂ側を選択する。例えば、上述のステップ１、３、５または６の場合にはスイッチのａ側が選択され、ステップ２または４の場合にはスイッチのｂ側が選択される。この構成では、キャリー処理は１回でよくなり、消費電流および演算時間が改善される。
【０１０２】
ワレスツリー構成の乗算回路の場合、加算器マトリクスの段数と処理できるビット数との関係は１対１ではなく、その段数で処理できるビット数には幅があるため、加算対象のビット数が１ビット増えても、必ずしも加算器列の段数が１段増える訳ではない。したがって、乗算器の幅によっては、加算器列の段数や加算器の数を増やすことなく積和演算の途中結果の加算を組み込むことができる場合があり、通常の乗算と同じ演算時間で積和演算を実行できる可能性がある。
【０１０３】
このように、第６の実施の形態によれば、積和演算回路により多倍長乗算を実行することができる。この第６の実施の形態の積和演算回路による多倍長乗算の１サイクルの演算時間は、次式により表される。
積和演算時間＝加算器マトリクス演算時間＋キャリー処理時間
ここで、加算器マトリクスの演算回路にワレスツリー構成を用いない場合は、加算器マトリクス演算時間およびキャリー処理時間は次式のようになる。
加算器マトリクス演算時間＝ＤＦＡ演算時間×ＤＦＡ段数
キャリー処理時間＝所定ビット単位のキャリー処理時間
×（乗算器のビット数／所定ビット）
これに対し、ワレスツリー構成を用いる場合、加算器マトリクス演算時間のみが以下のように短縮される。
加算器マトリクス演算時間＝ＣＤｅｃ処理時間
＋ＤＦＡ演算時間×ＤＦＡ最大段数＋ビット間合成処理時間
これを動作電流の観点から見た場合、キャリー処理回路においては下位ビットからシリアルに実行されるため、加算器マトリクスの処理に比べて消費電流が極めて少ない。
【０１０４】
多倍長乗算で用いられる積和演算回路は、プロセッサ等から演算命令が発行されると、コントローラまたはソフトウェアにより所定回数の積和演算が連続して実行され、このときの最大動作周波数は、上述の積和演算時間の逆数が上限となる。この最大動作周波数を上げるための構成について次に説明する。
【０１０５】
＜７．第７の実施の形態＞
［積和演算回路の全体構成］
図４５は、第７の実施の形態における積和演算回路の全体構成例を示す図である。この第７の実施の形態における積和演算回路は、被乗数レジスタ１１０と、乗数レジスタ１２０と、３倍値演算部２００と、入力値生成部３０３と、積和演算部５０２と、エンコーダ６００と、同期制御部７００とを備えている。この第７の実施の形態における積和演算回路は、積和演算部５０２以外の構成は、第６の実施の形態のものと同様である。なお、積和演算部５０２は、特許請求の範囲に記載の乗算部の一例である。
【０１０６】
この第７の実施の形態における積和演算部５０２では、図４６のように加算器マトリクスとキャリー処理回路の間にレジスタ列の位置を配置する。この構成の場合、乗算のビット幅（１ワード）より大きいビットの各デコード単位で、１個のキャリーの保存のためのレジスタも必要となる。
【０１０７】
［積和演算部の構成］
図４７は、第７の実施の形態における積和演算部５０２およびエンコーダ６００の構成例を示す図である。積和演算部５０２は、５個のハーフアダーＤＨＡと、１５個のフルアダーＤＦＡと、キャリー処理回路（２つのＤＣＡ２）と、８個の４ビットレジスタＲｅｇと、８個のスイッチと、５個のキャリーレジスタＣＲと、２ビットカウンタと、デコーダとを備えている。すなわち、この第７の実施の形態における積和演算部５０２は、第６の実施の形態の積和演算部５０１と比較して、５個のキャリーレジスタＣＲが追加された点が異なる。このキャリーレジスタＣＲは、デコードデータのレジスタの位置を移動したことに伴って必要となったものであり、デコード単位で１個のキャリーを保存するためのレジスタである。
【０１０８】
［積和演算回路の動作］
図４８は、第６および７の実施の形態における積和演算のタイミングを比較するための図である。第６の実施の形態では、図４８（ａ）のように、加算器マトリクスの乗算、レジスタＣ値の加算およびキャリー処理が逐次に行われる。これに対し、第７の実施の形態では、図４８（ｂ）のように、加算器マトリクスの乗算が終了すると、演算結果はレジスタに取り込まれる。このとき、下位ワードはキャリー処理の必要もなく、演算結果は確定している。そして、加算器マトリクスでは次の乗算が実行されているのと並行して、レジスタに取り込まれた上位ワードでデコードデータとキャリー値とからキャリー処理の演算が実行され、演算結果は加算器マトリクスの入力の１つに供給される。キャリー処理の処理時間は、加算器マトリクスの演算が最終段に達する時間より短いことが望ましい。この構成を採ることにより、積和演算の処理時間のうち、キャリー処理の時間は見えなくなり、かつ、サイクル内で増加する消費電流はキャリー処理の電流だけであるため、消費電流は僅かに増加するが、動作周波数をかなり高くすることが可能となる。加算器マトリクスをワレスツリーによって構成する場合、ワレスツリーの最終段近くでキャリー処理回路からの加算値を加算する構成を採れば、ワレスツリー構成でもこの効果を実現することができる。
【０１０９】
このように、第７の実施の形態によれば、加算器マトリクスとキャリー処理回路の間にレジスタを配置することにより、キャリー処理時間を見えなくすることができ、多倍長乗算の動作周波数を高くすることができる。
【０１１０】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１１１】
なお、本技術は以下のような構成もとることができる。
（１）所定のデコード単位ごとに被乗数データおよび乗数データを区切って、前記区切られた被乗数データおよび乗数データの複数の部分乗算結果を、前記区切られた被乗数データおよび乗数データよりも広いデータ幅を有する固定値から所定ビット数だけ異なる値を示すデコードデータとして生成する入力値生成部と、
前記入力値生成部によって生成された前記複数の部分乗算結果のデコードデータを、対応する桁の前記デコード単位ごとに加算することによって、デコードされた乗算データを生成する乗算部と、
前記乗算部によって生成された前記デコードされた乗算データをデコード単位ごとにエンコードすることによって、前記被乗数データと前記乗数データとの間の乗算結果を出力するエンコーダと
を具備する乗算回路。
（２）前記乗算部は、前記複数の部分乗算結果のデコードデータとして前記固定値が入力されている間は前記デコードされた乗算データとして前記固定値を出力する前記（１）に記載の乗算回路。
（３）前記区切られた被乗数データの３倍値を演算して生成する３倍値演算部をさらに具備し、
前記入力値生成部は、前記乗数データの所定のフィールドに基づいて選択信号を生成し、前記選択信号に従って、前記区切られた被乗数データ、当該区切られた被乗数データを１ビット左シフトすることにより得られた２倍値、および、前記３倍値の何れかを前記デコードデータとして生成する
前記（１）または（２）に記載の乗算回路。
（４）前記入力値生成部は、前記乗数データの所定のフィールドに基づいて選択信号を生成し、前記選択信号に従って前記区切られた被乗数データの「−２倍」、「−１倍」、「０倍」、「＋１倍」または「＋２倍」の何れかを前記デコードデータとして生成する
前記（１）または（２）に記載の乗算回路。
（５）リセット信号を出力する同期制御部をさらに具備し、
前記入力値生成部は、前記リセット信号に同期して前記複数の部分乗算結果を生成する
前記（１）から（５）のいずれかに記載の乗算回路。
【符号の説明】
【０１１２】
１１０  被乗数レジスタ
１２０  乗数レジスタ
２００  ３倍値演算部
３０１、３０２、３０３、３０５  入力値生成部
４０１、４０２、４０３、４０４、４０５  乗算部
４５０  合成回路
５０１、５０２  積和演算部
６００  エンコーダ
７００  同期制御部
【図１】
2012043405.tif 000003
【図２】
2012043405.tif 000004
【図３】
2012043405.tif 000005
【図４】
2012043405.tif 000006
【図５】
2012043405.tif 000007
【図６】
2012043405.tif 000008
【図７】
2012043405.tif 000009
【図８】
2012043405.tif 000010
【図９】
2012043405.tif 000011
【図１０】
2012043405.tif 000012
【図１１】
2012043405.tif 000013
【図１２】
2012043405.tif 000014
【図１３】
2012043405.tif 000015
【図１４】
2012043405.tif 000016
【図１５】
2012043405.tif 000017
【図１６】
2012043405.tif 000018
【図１７】
2012043405.tif 000019
【図１８】
2012043405.tif 000020
【図１９】
2012043405.tif 000021
【図２０】
2012043405.tif 000022
【図２１】
2012043405.tif 000023
【図２２】
2012043405.tif 000024
【図２３】
2012043405.tif 000025
【図２４】
2012043405.tif 000026
【図２５】
2012043405.tif 000027
【図２６】
2012043405.tif 000028
【図２７】
2012043405.tif 000029
【図２８】
2012043405.tif 000030
【図２９】
2012043405.tif 000031
【図３０】
2012043405.tif 000032
【図３１】
2012043405.tif 000033
【図３２】
2012043405.tif 000034
【図３３】
2012043405.tif 000035
【図３４】
2012043405.tif 000036
【図３５】
2012043405.tif 000037
【図３６】
2012043405.tif 000038
【図３７】
2012043405.tif 000039
【図３８】
2012043405.tif 000040
【図３９】
2012043405.tif 000041
【図４０】
2012043405.tif 000042
【図４１】
2012043405.tif 000043
【図４２】
2012043405.tif 000044
【図４３】
2012043405.tif 000045
【図４４】
2012043405.tif 000046
【図４５】
2012043405.tif 000047
【図４６】
2012043405.tif 000048
【図４７】
2012043405.tif 000049
【図４８】
2012043405.tif 000050