(57)【要約】【課題】遅延時間を短縮したリダクションアレイ技術を提供する。【解決手段】部分積のビットストリームを積算し、キャリーセーブ出力対を生成する方法あるいは装置が提供される。この方法あるいは装置は、キャリーアウト出力対の一部であるセーブ出力Ｓを、ブール論理式  Ｓ＝ｄ３  ＸＯＲ  （（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））に従って生成する。ここで、ｄ０、ｄ１、ｄ２、ｄ３は、４つの部分積のビットストリームであり、Ｃｉｎは、同じ部分積リダクションアレイ内の隣接する圧縮回路からのキャリー入力である。【選択図】図５
2007234005.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも３つの部分積のビットストリームを受け、キャリーセーブ出力対を生成する４対２圧縮回路であって、
４つの部分積のビットストリームをｄ０、ｄ１、ｄ２、ｄ３とし、同じ部分積リダクションアレイ内の隣接する圧縮回路からのキャリー入力のビットストリームをＣｉｎとするとき、
前記キャリーアウト出力対の一部であるセーブ出力Ｓを、ブール論理式
Ｓ＝ｄ３  ＸＯＲ  （（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））
に従って生成する論理ゲートを備えることを特徴とする４対２圧縮回路。
【請求項２】
ｄｉを、ｄ０、ｄ１、ｄ２あるいはｄ３のいずれかとしたとき、
前記キャリーセーブ出力対の一部であるキャリー出力Ｃを、
（ｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が真のとき、ブール論理式
Ｃ＝ｄｉ  ｏｒ  Ｃｉｎ
に従って生成し、
（ｉｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が偽のとき、ブール論理式
Ｃ＝ｄ３
に従って生成するマルチプレクサ回路をさらに備えることを特徴とする請求項１に記載の４対２圧縮回路。
【請求項３】
同じ部分積リダクションアレイ内の隣接する圧縮回路に受け渡すべきキャリー出力Ｃｏｕｔを、ブール演算式
Ｃｏｕｔ＝ｄ０・ｄ１＋ｄ１・ｄ２＋ｄ０・ｄ３
に従って生成する多数決回路をさらに備えることを特徴とする請求項１または２に記載の４対２圧縮回路。
【請求項４】
部分積を積算するリダクションアレイであって、
３つの部分積のビットストリームを受け、第１のキャリーセーブ出力対Ｃ１、Ｓ１を生成する３対２圧縮回路と、
第１の４つの部分積のビットストリームを受け、第２のキャリーセーブ出力対Ｃ２、Ｓ２を生成する第１の４対２圧縮回路と、
第２の４つの部分積のビットストリームを受け、第３のキャリーセーブ出力対Ｃ３、Ｓ３を生成する第２の４対２圧縮回路と、
を備え、
前記３対２圧縮回路のキャリー出力Ｃ１は、前記第１の４対２圧縮回路に対する前記部分積の入力のひとつとして結合され、前記３対２圧縮回路のキャリー出力Ｓ１は、前記第２の４対２圧縮回路に対する前記部分積の入力のひとつとして結合されることを特徴とするリダクションアレイ。
【請求項５】
前記第１、第２の４対２圧縮回路の少なくともひとつは、４つの部分積のビットストリームをｄ０、ｄ１、ｄ２、ｄ３とし、隣接する圧縮回路からのキャリー入力のビットストリームをＣｉｎとするとき、
前記キャリーセーブ出力対の一部である前記セーブ出力Ｓを、ブール論理式
Ｓ＝ｄ３  ＸＯＲ  （（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））
に従って生成することを特徴とする請求項４に記載のリダクションアレイ。
【請求項６】
前記第１、第２の４対２圧縮回路の少なくともひとつは、ｄｉを、ｄ０、ｄ１、ｄ２あるいはｄ３のいずれかとしたとき、
前記キャリーセーブ出力対の一部であるキャリー出力Ｃを、
（ｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が真のとき、ブール論理式
Ｃ＝ｄｉ  ｏｒ  Ｃｉｎ
に従って生成し、
（ｉｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が偽のとき、ブール論理式
Ｃ＝ｄ３
に従って生成するマルチプレクサ回路をさらに備えることを特徴とする請求項５に記載のリダクションアレイ。
【請求項７】
隣接する圧縮回路に受け渡すべきキャリー出力Ｃｏｕｔを、ブール演算式
Ｃｏｕｔ＝ｄ０・ｄ１＋ｄ１・ｄ２＋ｄ０・ｄ３
に従って生成する多数決回路をさらに備えることを特徴とする請求項５に記載のリダクションアレイ。
【請求項８】
４つの部分積のビットストリームを積算し、キャリーセーブ出力対を生成する方法であって、
前記４つの部分積のビットストリームをｄ０、ｄ１、ｄ２、ｄ３とし、同じ部分積リダクションアレイ内の隣接する圧縮回路からのキャリー入力のビットストリームをＣｉｎとするとき、
前記キャリーアウト出力対の一部であるセーブ出力Ｓを、ブール論理式
Ｓ＝ｄ３  ＸＯＲ  （（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））
に従って生成するステップを備えることを特徴とする方法。
【請求項９】
ｄｉを、ｄ０、ｄ１、ｄ２あるいはｄ３のいずれかとしたとき、
前記キャリーセーブ出力対の一部であるキャリー出力Ｃを、
（ｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が真のとき、ブール論理式
Ｃ＝ｄｉ  ｏｒ  Ｃｉｎ
に従って生成し、
（ｉｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が偽のとき、ブール論理式
Ｃ＝ｄ３
に従って生成するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
同じ部分積リダクションアレイ内の隣接する圧縮回路に受け渡すべきキャリー出力Ｃｏｕｔを、ブール演算式
Ｃｏｕｔ＝ｄ０・ｄ１＋ｄ１・ｄ２＋ｄ０・ｄ３
に従って生成するステップをさらに備えることを特徴とする請求項８または９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブース乗算器あるいはアレイ乗算器などで生成される部分積を合成するための装置および方法に関する。
【背景技術】
【０００２】
情報処理システム等によって実行される多くの処理は、２進数の乗算を必要とする。乗算関数では、被乗数（multiplicand）と乗数（multiplier）が存在する。よく知られるように、２進数の乗算は、まず、被乗数が乗数の第１ビットと掛け合わされる。つづいて、被乗数が乗数の第２ビットと掛け合わされ、その結果得られた値が、１桁シフトされて、積同士が加算される。このプロセスが、乗数のすべてのビットが被乗数と掛け合わせられるまで繰り返される。
【０００３】
被乗数と、乗数のある１ビットとを掛け合わせて得られる積は、部分積と呼ばれる。２進数の乗算と被乗数を掛け合わせて生成される部分積は、ブール符号化アルゴリズムあるいはアレイ乗算器などを利用して生成される。最終的な積は、もっとも右の桁から左の桁へと桁上げしながら、部分積を積算することにより生成される。
【０００４】
部分積を積算するための従来の手法は、多くの処理サイクルを必要とした。２つのＮビットの２進数の加算の計算量は、Ｏ（ｌｏｇ２（Ｎ））に比例するため、単純な加算は、和を算出するために好ましい手法とはいえない。乗算のプロセスにおいて部分積の加算を実行するための先行技術として多くのキャリーセーブ型の加算手法が存在する。これらのキャリーセーブ型の加算手法は、３ビットの数をＣ（carry）およびＳ（sum）で表される２ビットの数に変換する。この変換は、３対２圧縮と呼ばれる。３対２圧縮器は、４対２圧縮器などのより高次の圧縮器を形成するために、カスケード接続される場合もある。３対２圧縮器および４対２圧縮器は、さらに高次の圧縮器を形成するためにカスケード接続される場合があり、これらはリダクションアレイ（reduction array）と呼ばれる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
リダクションアレイの伝搬遅延は、とりわけ多くの部分積が計算される場合に演算処理システムのスループットに非常に大きな影響を与える。
【０００６】
本発明は、かかる課題に鑑みてなされたものであり、その目的のひとつは、遅延時間を短縮したリダクションアレイ技術の提供にある。
【課題を解決するための手段】
【０００７】
本発明のある態様によれば、４つの部分積のビットストリームを積算し、キャリーセーブ出力対を生成する方法あるいは装置が提供される。この方法もしくは装置は、４つの部分積のビットストリームをｄ０、ｄ１、ｄ２、ｄ３とし、同じ部分積リダクションアレイ内の隣接する圧縮回路からのキャリー入力のビットストリームをＣｉｎとするとき、キャリーアウト出力対の一部であるセーブ出力Ｓを、ブール論理式
Ｓ＝ｄ３  ＸＯＲ  （（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））
に従って生成する。
【０００８】
ある態様の方法もしくは装置は、ｄｉを、ｄ０、ｄ１、ｄ２あるいはｄ３のいずれかとしたとき、キャリーセーブ出力対の一部であるキャリー出力Ｃを、
（ｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が真のとき、ブール論理式
Ｃ＝ｄｉ  ｏｒ  Ｃｉｎ
に従って生成してもよい。また、
（ｉｉ）  （ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）が偽のとき、ブール論理式
Ｃ＝ｄ３
に従って生成してもよい。なお、本明細書において小文字で記される「ｏｒ」は、論理和ではなく、いずれかであることを示す。
【０００９】
ある態様の方法もしくは装置は、同じ部分積リダクションアレイ内の隣接する圧縮回路に受け渡すべきキャリー出力Ｃｏｕｔを、ブール演算式
Ｃｏｕｔ＝ｄ０・ｄ１＋ｄ１・ｄ２＋ｄ０・ｄ３
に従って生成してもよい。
【００１０】
ある態様の別の態様によれば、部分積を積算するリダクションアレイの装置あるいは方法が提供される。この装置あるいは方法は、３つの部分積のビットストリームを受け、第１のキャリーセーブ出力対Ｃ１、Ｓ１を生成する３対２圧縮回路と、第１の４つの部分積のビットストリームを受け、第２のキャリーセーブ出力対Ｃ２、Ｓ２を生成する第１の４対２圧縮回路と、第２の４つの部分積のビットストリームを受け、第３のキャリーセーブ出力対Ｃ３、Ｓ３を生成する第２の４対２圧縮回路と、を備える。３対２圧縮回路のキャリー出力Ｃ１は、第１の４対２圧縮回路に対する部分積の入力のひとつとして結合され、３対２圧縮回路のキャリー出力Ｓ１は、第２の４対２圧縮回路に対する部分積の入力のひとつとして結合される。
【００１１】
なお、本明細書において、ＸＯＲは排他的論理和、ＯＲは和を表現するものとする。
【００１２】
なお、以上の構成要素の任意の組合せや、本発明の構成要素や表現を、方法、装置、システムなどの間で相互に置換したものもまた、本発明の態様として有効である。
【発明を実施するための最良の形態】
【００１３】
以下、本発明を好適な実施の形態をもとに図面を参照しながら説明する。各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付するものとし、適宜重複した説明は省略する。また、実施の形態は、発明を限定するものではなく例示であって、実施の形態に記述されるすべての特徴やその組み合わせは、必ずしも発明の本質的なものであるとは限らない。
【００１４】
図１は、２つの２進数の積を生成するために、部分積を生成してこれらを積算する実施の形態に係る乗算回路１００の構成を示すブロック図である。乗算回路１００は、符号化回路１０２およびセレクタ回路１０４を含む部分積回路１０１と、リダクションアレイ回路１２０と、を備える。当業者であれば、本明細書の説明によって、乗算回路１００の設計指針に応じて、異なる構成の部分積回路１０１が利用可能であることを理解できよう。たとえば、従来の、あるいは将来において開発されるであろうブースアルゴリズムあるいはアレイ乗算器を、部分積回路１０１の実装に利用することができる。
【００１５】
好ましい実施の形態において、符号化回路１０２は、それぞれ、乗数１０６に含まれるビットの組（基数２の２進数）を、各ビットの組ごとに基数４の数を表現する符号化されたビットに変換し、信号線１０８に出力する。ブース符号化アルゴリズムは、基数２の乗数を、基数４の乗数であって、｛−２、−１、−０、１、２｝からなるデジタル値の集合のいずれかの数を表現する乗数に変換する。その結果、部分積の個数は１／２に減少する。
セレクタ回路１０４は、信号線１０８上の符号化されたビットの組を受けるとともに、被乗数および乗数の部分積の各ビットを生成するために、被乗数１１０に含まれるビットの組を受ける。好ましい実施の形態において、セレクタ回路１０４はマルチプレクサとして機能し、それぞれのセレクタ動作は、被乗数に含まれる基数２のビットの組を入力（すなわち被セレクト信号）として受け、乗数に含まれる基数２のビットの組をセレクト信号として利用する。ある乗数に含まれる基数２のビットの組に対するセレクタ動作の出力の集合は、部分積となる。
【００１６】
乗算回路１００は、最終回路１１２をさらに備える。最終回路１１２は、リダクションアレイ回路１２０からキャリー出力Ｃおよびセーブ出力Ｓを受け、乗数１０６および被乗数１１０の最終的な積を生成する。キャリーセーブ型の加算手法では、最終回路１１２は２Ｃ＋Ｓを算術演算し、最終的な積を生成する。
【００１７】
図２は、図１のリダクションアレイ回路１２０の詳細な構成を示すブロック図である。リダクションアレイ回路１２０は、複数の圧縮回路１２２、１２４、１２６、１２８を含む。各圧縮回路は、部分積回路１０１により生成されたいくつかの部分積のビットストリームを受け、部分積ごとにキャリーセーブ出力対を出力する。圧縮回路１２２、１２４、１２６それぞれは、リダクションアレイ回路１２０の初段に配置され、中間キャリーセーブ出力対を生成し、最終段の圧縮回路、すなわち圧縮回路１２８は、最終的なキャリーセーブ出力を生成する。
【００１８】
好ましい形態において、３対２圧縮回路１２４は、３つの部分積のビットストリームを受け、第１のキャリーセーブ出力対Ｃ１、Ｓ１を生成する。３つの部分積が入力される３対２圧縮回路１２４の端子は、ｄ０、ｄ１、ｄ２である。
【００１９】
第１の４対２圧縮回路１２２は、第１の４つの部分積のビットストリームを受け、第２のキャリーセーブ出力対Ｃ２、Ｓ２を生成する。４つの部分積が入力される端子は、ｄ０、ｄ１、ｄ２、ｄ３であるが、本実施の形態において、入力端子ｄ３は、それ自体は部分積のビットストリームを受け取らず、かわりに、入力端子ｄ３には、３対２圧縮回路１２４から出力されるキャリー出力Ｃ１が入力される。また、リダクションアレイ回路１２０は、第２の４つの部分積のビットストリームを受け、第３のキャリーセーブ出力対Ｃ３、Ｓ３を生成する第２の４対２圧縮回路１２６を備える。第１の４対２圧縮回路１２２と同様に、第２の４対２圧縮回路１２６は、その入力端子ｄ３に部分積のビットストリームを受けず、３対２圧縮回路１２４から出力されるセーブ出力Ｓ１を受ける。
【００２０】
後述するように、本実施の形態に係るリダクションアレイ回路１２０によれば、それぞれの圧縮回路による信号の伝搬を速めることができ、乗算回路１００のスループットを改善することができる。
【００２１】
図３は、図２の３対２圧縮回路１２４の好適かつ詳細な構成を示す回路図である。当業者であれば、図３の回路図は説明のための例示であって、本発明の範囲において、従来のあるいは将来において利用可能な別の３対２圧縮回路が利用可能であることは理解されよう。３対２圧縮回路１２４の機能は図４に示される。図４は、３対２圧縮回路１２４の入力ｘ、ｙ、ｚと、キャリーセーブ出力Ｃ、Ｓの関係を示す真理値表である。この真理値表から、３対２圧縮回路１２４のデジタル論理は、以下の式で表されることが明らかとなる。
ｘ＋ｙ＋ｚ＝２Ｃ＋Ｓ
したがって、たとえば、３対２圧縮回路１２４への入力ｘ、ｙ、ｚが１、１、１の場合、３対２圧縮回路１２４は、２Ｃ＋Ｓ＝３となるＣおよびＳを生成する。すなわち、Ｃ＝１、Ｓ＝１である。同様の解析が、その他のｘ、ｙ、ｚの組み合わせに適用できる。
【００２２】
図３の具体的な構成について説明する。３対２圧縮回路１２４は、多数決回路１３０と、キャリーセーブ出力それぞれを生成するための組み合わせ論理機能を実行する複数のデジタル論理ゲート１３２と、を備える。具体的には、多数決回路１３０は、キャリー出力Ｃを生成する。キャリー出力Ｃは、以下のブール論理式で表される。
Ｃ＝ｘ・ｙ＋ｙ・ｚ＋ｘ・ｚ
論理ゲート１３２は、以下のブール演算式にしたがって、セーブ出力Ｓを生成する。
Ｓ＝ｚ  ＸＯＲ  （ｘ  ＸＯＲ  ｙ）
ここで、単位遅延の考え方を導入すると、多数決回路１３０の信号伝搬遅延は、１．０、論理ゲート１３２の信号伝搬遅延は１．５＋１．５＝３．０と表現することができる。これらのリダクションアレイ回路１２０の伝搬遅延については、後に考察する。
【００２３】
図５は、図２の４対２圧縮回路１２２、１２６、１２８の好適かつ詳細な構成を示す回路図である。説明のため、図５の回路は、４対２圧縮回路１２２の詳細な論理回路を表現している。４対２圧縮回路１２２は、多数決回路１３０、複数の論理ゲート１３３、１３４、１３６、１３８、マルチプレクサ回路１４０を備える。多数決回路１３０は、図３において説明した方法と実質的に同様の方法の機能を有する。具体的には、多数決回路１３０は、リダクションアレイ回路１２０内で隣接する圧縮回路に入力されるキャリー出力Ｃｏｕｔを生成する。キャリー出力Ｃｏｕｔは、以下の式によって表現される。
Ｃｏｕｔ＝ｄ０・ｄ１＋ｄ１・ｄ２＋ｄ０・ｄ３
なお、４対２圧縮回路１２８としては、図５の回路に代えて従来の図６の回路を使用してもよい。
【００２４】
複数の論理ゲート１３３、１３４、１３６および１３８は、論理ゲート１３８が以下のブール演算式にもとづいたセーブ出力Ｓを生成するように接続される。
Ｓ＝ｄ３  ＸＯＲ（（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ））
ここで、Ｃｉｎは、リダクションアレイ回路１２０内で隣接する圧縮回路から出力されるビットストリームのキャリー入力である。
【００２５】
マルチプレクサ回路１４０は、論理ゲート１３６の出力を利用して制御され、マルチプレクサ回路１４０の出力は、キャリー出力Ｃｏｕｔとなる。マルチプレクサ回路１４０の第１の入力は、ｄｉまたはＣｉｎであり、第２の入力は、ｄ３である。参照符号ｄｉは、４対２圧縮回路１２２に入力される部分積を特定するものであり、すなわち、ｄ０、ｄ１、ｄ２のいずれかである。論理ゲート１３６の出力信号は、次のブール論理式で表される。
（ｄ０  ＸＯＲ  ｄ１）  ＸＯＲ  （ｄ２  ＸＯＲ  Ｃｉｎ）
マルチプレクサ回路１４０の出力は、論理ゲート１３６の出力が真（＝１、すなわちハイレベル）のとき、
Ｃ＝ｄｉ  ｏｒ  Ｃｉｎ
となる。ここで「ｏｒ」は、いずれか一方であることを示す。すなわち、Ｃは、ｄ０〜ｄ２もしくはＣｉｎのいずれか１つを示す。反対に、マルチプレクサ回路１４０の出力は、論理ゲート１３６の出力が偽（＝０、すなわちローレベル）のとき、
Ｃ＝ｄ３
となる。なお、図２のリダクションアレイ回路１２０には、３つの４対２圧縮回路が含まれるが、すべての４対２圧縮回路について、（ｄｉ  ｏｒ  Ｃｉｎ）としてどの信号を設定するかは同一とする。
【００２６】
図２および図５を参照しながら、伝搬遅延について考察する。多数決回路１３０の伝搬遅延は、上述のように１．０と表現したとする。入力ｄ０、ｄ１、ｄ２からセーブ出力Ｓまでの伝搬遅延は、各論理ゲート１３３、１３４、１３６、１３８に対応する伝搬遅延１．５を用いて表現される。入力ｄ０、ｄ１、ｄ２からセーブ出力Ｓまでの全伝搬遅延は４．５となる。したがって、４対２圧縮回路１２２内の最長の伝搬遅延は、キャリー入力Ｃｉｎを供給するリダクションアレイ回路１２０内の隣接する圧縮回路の部分積の入力を、４対２圧縮回路１２２に割り当てることにより定めることができる。本実施の形態において、４対２圧縮回路のような隣接する圧縮回路からのキャリー出力Ｃｏｕｔは、４対２圧縮回路１２２のキャリー入力Ｃｉｎとなっている。上述したように、多数決回路１３０への部分積の入力から、Ｃｏｕｔ信号線までの伝搬遅延は、１．０と表される。４対２圧縮回路１２２のＣｉｎ信号線への信号入力に伝搬遅延をあてはめると、４対２圧縮回路１２２全体の遅延は、５．５となる。４対２圧縮回路１２２のその他の経路は、いずれも５．５より小さくなっている。
【００２７】
以下で説明するように、リダクションアレイ回路１２０の各ステージごとの５．５という伝搬遅延は、従来のリダクションアレイ回路に比べて短くなっている。
【００２８】
図６は、従来の４対２圧縮回路の詳細な回路図である。なお、図６の４対２圧縮回路と、図５の４対２圧縮回路は、共通する回路トポロジが存在するものの、図６の４対２圧縮回路のキャリーセーブ出力Ｃ、Ｓのブール論理式は、図５の４対２圧縮回路１２２とは異なっている。
【００２９】
図７は、従来のリダクションアレイ回路のブロック図である。図７において、複数の３対２圧縮回路１２４および従来の４対２圧縮回路１２９が、図２の回路と圧縮比が実質的に同等となるように接続されている。３対２圧縮回路１２４（図３）の論理ゲート１３２の伝搬遅延は３．０であり、図７のリダクションアレイ回路の２つのステージ（４対２圧縮回路１２９までの）が部分積にもたらす伝搬遅延は６．０である。したがって、上述した本実施の形態に係るリダクションアレイ回路１２０の伝搬遅延５．５は、従来のリダクションアレイ回路に対して、著しく改善されたものとなっている。これは、図１の乗算回路１００において乗数１０６と被乗数１１０の乗算を実行する上で、大変な優位性をもたらす。
【００３０】
本明細書において説明した方法あるいは装置はたとえば、現在において利用可能であり、あるいは将来において開発される標準的なデジタル回路、アナログ回路、マイクロプロセッサ、デジタル信号処理回路、ソフトウェアやファームウェアを実行可能なプロセッサ、プログラム可能なデジタル機器やシステム、プログラム可能なアレイ論理デバイス、あるいはこれらの組み合わせなどの公知の技術を利用することにより実現される。
【００３１】
実施の形態にもとづき、本発明を説明したが、実施の形態は、本発明の原理、応用を示しているにすぎず、実施の形態には、請求の範囲に規定された本発明の思想を離脱しない範囲において、多くの変形例や配置の変更が可能である。
【図面の簡単な説明】
【００３２】
【図１】２つの２進数の積を生成するために、部分積を生成してこれらを積算する実施の形態に係る乗算回路の構成を示すブロック図である。
【図２】図１のリダクションアレイ回路の詳細な構成を示すブロック図である。
【図３】図２の３対２圧縮回路の好適かつ詳細な構成を示す回路図である。
【図４】３対２圧縮回路の入力ｘ、ｙ、ｚと、キャリーセーブ出力の関係を示す真理値表である。
【図５】図２の４対２圧縮回路の好適かつ詳細な構成を示す回路図である。
【図６】従来の４対２圧縮回路の詳細な回路図である。
【図７】従来のリダクションアレイ回路のブロック図である。
【符号の説明】
【００３３】
１００  乗算回路、  １０１  部分積回路、  １０２  符号化回路、  １０４  セレクタ回路、  １０８  信号線、  １２０  リダクションアレイ回路、  １３０  多数決回路、  １３２  論理ゲート、  １４０  マルチプレクサ回路、  ２０２Ａ  第１回路、  ２０２Ｂ  第２回路、  ２０２Ｃ  第３回路、  ２０２Ｄ  第４回路、  １１２  最終回路。
【図１】
2007234005.tif 000003
【図２】
2007234005.tif 000004
【図３】
2007234005.tif 000005
【図４】
2007234005.tif 000006
【図５】
2007234005.tif 000007
【図６】
2007234005.tif 000008
【図７】
2007234005.tif 000009