(57)【要約】【課題】桁上げ信号の伝播時間を極力小さくして、処理の高速化を図る。【解決手段】基本乗算部１０１と部分和演算部１０２とから構成されてなり、基本乗算部１０１においてｍビットの乗数Ｙとｎビットの被乗数Ｘとの各デジット相互の乗算がなされて各々の積項がビット毎に部分和演算部１０２へ入力され、部分和演算部１０２においては、ビット毎に積項の和が求められ、さらに、その和の結果をビット毎に区分されて、再度ビット毎での複数の項の和が求められる演算処理が繰り返しなされることで、Ｘ×Ｙの最終値が得られるようになっている。【選択図】        図１
2004259091.tif 000002
【特許請求の範囲】
【請求項１】
ｎビットの２進数である乗数Ｙと、ｍビットの２進数である被乗数Ｘとの乗算値を求める演算処理方法であって、
前記乗数Ｙと被乗数Ｘのｉビット目のデジットをそれぞれＹｉ、Ｘｉとした場合に、数１における各々の積項Ｘｉ×ＹｉをＡＮＤ機能を有するＡＮＤ手段によりビット毎に求め、
【数１】
2004259091.tif 000010
しかる後、各々のビット毎における前記複数の積項の和を演算し、その演算結果を数２に示される如くにビット毎に区分し、
【数２】
2004259091.tif 000011
その各々のビット毎のデジットを表す複数の項の和を求め、その演算結果を再度ビット毎に区分し、前記複数の項の和を求めたと同様にして各々のビットにおける複数の項の和を求めることを繰り返して乗数Ｙと被乗数Ｘとの乗算結果を得ることを特徴とする演算処理方法。
【請求項２】
ｎビットの２進数である乗数Ｙと、ｍビットの２進数である被乗数Ｘとの乗算値を出力する並列乗算器であって、
前記乗数Ｙと被乗数Ｘのｉビット目のデジットをそれぞれＹｉ、Ｘｉとした場合に、デジット同士の乗算を行い、その乗算結果が数３
【数３】
2004259091.tif 000012
で表される如くにビット毎に得られるように２入力のＡＮＤ素子がｎ×ｍ個二次元的に配列されてなる基本乗算部と、
前記基本乗算部により得られた各々のビット毎における複数の積項の和を演算し、その演算結果を数４
【数４】
2004259091.tif 000013
に示される如くにビット毎に区分し、その各々のビット毎のデジットを表す複数の項の和を求め、その演算結果を再度ビット毎に区分し、前記複数の項の和を求めたと同様にして各々のビットにおける複数の項の和を求めることを繰り返して乗数Ｙと被乗数Ｘとの乗算結果を得るよう構成されてなる部分和演算部とを有してなることを特徴とする並列乗算器。
【請求項３】
前記部分和演算部は、前記基本乗算部により得られたビット毎における積項の数が所定数以上となるビットについては、当該積項の和を、予め定められた積項数毎に分割し、当該分割された部分についての積項の和である部分和を算出する加算回路を有すると共に、それら複数の部分和の総和を算出することで当該ビットのデジットを表す複数の項の和を算出するよう構成されてなることを特徴とする請求項２記載の並列乗算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル値の乗算器に係り、特に、並列乗算器における演算の高速化等を図ったものに関する。
【０００２】
【従来の技術】
従来、この種の乗算器としては、例えば、全加算器とＡＮＤ素子とから構成された基本単位となる乗算器（以下「乗算器セル」という）が、乗数のビット数と被乗数のビット数に応じて二次元的に配列され構成された並列乗算器が公知・周知となっている（例えば、特許文献１参照）。
【０００３】
【特許文献１】
特開平１−１８９７２４号公報（第３−５頁、第１−２図）
【０００４】
【発明が解決しようとする課題】
かかる従来の並列乗算器においては、乗算器セルにおいて生ずる桁上げ信号が、上位の乗算器セルへ、順次、伝播される構成となっているために、例えば、乗数のビット数をｍ、被乗数のビット数をｎとすれば、最大で（ｍ＋ｎ）個の桁上げ伝播遅延が生ずることとなり、乗数及び被乗数のビット数の積に比例して伝播遅延の増大を招き、そのため並列乗算器全体としての高速化が困難であるという問題があった。
本発明は、上記実状に鑑みてなされたもので、桁上げ信号の伝播時間を極力小さくして、処理の高速化を図った並列乗算方法及び並列乗算器を提供するものである。
【０００５】
【課題を解決するための手段】
上記発明の目的を達成するため、本発明に係る並列乗算方法は、
ｎビットの２進数である乗数Ｙと、ｍビットの２進数である被乗数Ｘとの乗算値を求める演算処理方法であって、
前記乗数Ｙと被乗数Ｘのｉビット目のデジットをそれぞれＹｉ、Ｘｉとした場合に、数５における各々の積項Ｘｉ×ＹｉをＡＮＤ機能を有するＡＮＤ手段によりビット毎に求め、
【数５】
2004259091.tif 000003
しかる後、各々のビット毎における前記複数の積項の和を演算し、その演算結果を数６に示される如くにビット毎に区分し、
【数６】
2004259091.tif 000004
その各々のビット毎のデジットを表す複数の項の和を求め、その演算結果を再度ビット毎に区分し、前記複数の項の和を求めたと同様にして各々のビットにおける複数の項の和を求めることを繰り返して乗数Ｙと被乗数Ｘとの乗算結果を得るよう構成されてなるものである。
【０００６】
また、上記発明の目的を達成するため、本発明に係る並列乗算器は、
ｎビットの２進数である乗数Ｙと、ｍビットの２進数である被乗数Ｘとの乗算値を出力する並列乗算器であって、
前記乗数Ｙと被乗数Ｘのｉビット目のデジットをそれぞれＹｉ、Ｘｉとした場合に、デジット同士の乗算を行い、その乗算結果が数７
【数７】
2004259091.tif 000005
で表される如くにビット毎に得られるように２入力のＡＮＤ素子がｎ×ｍ個二次元的に配列されてなる基本乗算部と、
前記基本乗算部により得られた各々のビット毎における複数の積項の和を演算し、その演算結果を数８
【数８】
2004259091.tif 000006
に示される如くにビット毎に区分し、その各々のビット毎のデジットを表す複数の項の和を求め、その演算結果を再度ビット毎に区分し、前記複数の項の和を求めたと同様にして各々のビットにおける複数の項の和を求めることを繰り返して乗数Ｙと被乗数Ｘとの乗算結果を得るよう構成されてなる部分和演算部とを有してなるものである。
【０００７】
かかる構成においては、４個程度の複数の項の和の演算の繰り返しを行いビット毎のデジットが算出できるように構成されているので、従来と異なり、演算による桁上げ信号の伝播を、論理ゲートの数で精々３程度に抑えることができ、そのため演算処理の高速化が図られることとなるものである。
【０００８】
【発明の実施の形態】
以下、本発明の実施の形態における並列乗算方法及び並列乗算器について、図１乃至図８を参照しつつ説明する。
なお、以下に説明する部材、配置等は本発明を限定するものではなく、本発明の趣旨の範囲内で種々改変することができるものである。
最初に、本発明の実施の形態における並列乗算器の全体構成について図１及び図２を参照しつつ説明する。
この発明の実施の形態における並列乗算器は、ｎビットの乗数Ｙとｍビットの被乗数Ｘとの乗算を行うためのもので、本実施の形態においては、ｎ＝ｍ＝１６の場合の構成例について説明する。
本発明の実施の形態における並列乗算器は、基本乗算部１０１と、部分和演算部１０２とに大別されてなるものである。
基本乗算部１０１は、デジット同士の演算を行う複数のＡＮＤ手段としてのＡＮＤセル１１−１〜１１６−１６が二次元に配列されて構成されたものとなっている。
まず、ｎビットの乗数Ｙとｍビットの被乗数Ｘとの乗算は、Ｙ及びＸの各デジットを、例えば、それぞれ最下位ビットから順に、Ｘ０、Ｘ１、Ｘ２、・・・Ｘｍ，Ｙ０、Ｙ１、Ｙ２、・・・Ｙｎと表現し、その乗算を行い、その演算結果を２のべき数毎に括ると、（Ｘ０・Ｙ０）２０、（Ｘ０・Ｙ１＋Ｘ１・Ｙ０）２１、（Ｘ０・Ｙ２＋Ｘ１・Ｙ１＋Ｘ２・Ｙ０）２２、・・・と、順次、２ｍ＋ｎまでの項を得ることができ、ＸとＹとの乗算は、下記する数式９の如くに現すことができる。
【０００９】
【数９】
2004259091.tif 000007
【００１０】
基本乗算部１０１は、この数式９における個々のＸｉ・Ｙｊを演算する部分であり、ｎ＝ｍ＝１６の場合には、１６×１６個のＡＮＤセル１１−１〜１１６−１６が設けられることとなる。
図２には、図１において多数の符号を付することによる図面の見難さを避けるために基本乗算部１０１のみが示されており、ＡＮＤセル１１−１〜１１６−１６について同図を参照しつつ説明すれば、まず、図２においては、図が煩雑になるのを回避するため、ＡＮＤ１１−１〜１１６−１６の符号は代表的なものにのみ付したものとなっている。
同図において、符号１１−１が付されたＡＮＤセルは、Ｘ０とＹ０が入力され、その乗算値が算出されるものとなっている。そして、このＡＮＤセル１１−１が右上端となるように図２を見た状態において、ＡＮＤセル１１−１の左側へ順にＡＮＤセル１１−２〜１１−１６が配設されている。このＡＮＤセル１１−２〜１１−１６には、ＡＮＤセル１１−１と同様に、Ｙの最下位ビットのデジットＹ０が入力されると共に、ＡＮＤセル１１−２にはＸ１が、ＡＮＤセル１１−３にはＸ２が、ＡＮＤセル１１−４にはＸ３が、・・・、ＡＮＤセル１１−１６にはＸ１５というように、Ｘの各デジットが最下位ビットの次の上位ビットのデジットから順に入力されるものとなっている。なお、図２においては、図示の煩雑さを回避するため、ＡＮＤセル１１−２〜１１−１６に入力されるＸ，Ｙの各ビットの配線は図示を省略してある。
【００１１】
次に、ＡＮＤセル１２−１〜１２−１６には、いずれにもデジットＹ１が入力されると共に、ＡＮＤセル１２−１〜１２−１６にはＸの各々のデジットＸ０〜Ｘ１５が、上述のＡＮＤセル１１−１〜１１−１６と同様に、最下位ビットのデジットＸ０から順に対応するＡＮＤセルに入力されるようになっている。
残りのＡＮＤセル１３−１〜１１６−１６についても、基本的には上述したと同様であるので、以下、簡潔に詳細すれば、ＡＮＤセル１３−１〜１３−１６にはＹ２が、ＡＮＤセル１４−１〜１４−１６にはＹ３が、ＡＮＤセル１５−１〜１５−１６にはＹ４が、ＡＮＤセル１６−１〜１６−１６にはＹ５が、ＡＮＤセル１７−１〜１７−１６にはＹ６が、ＡＮＤセル１８−１〜１８−１６にはＹ７が、ＡＮＤセル１９−１〜１９−１６にはＹ８が、ＡＮＤセル１１０−１〜１１０−１６にはＹ９が、ＡＮＤセル１１１−１〜１１１−１６にはＹ１０が、ＡＮＤセル１１２−１〜１１２−１６にはＹ１１が、ＡＮＤセル１１３−１〜１１３−１６にはＹ１２が、ＡＮＤセル１１４−１〜１１４−１６にはＹ１３が、ＡＮＤセル１１５−１〜１１５−１６にはＹ１４が、ＡＮＤセル１１６−１〜１１６−１６にはＹ１５が、それぞれ入力されると共に、Ｘ０〜Ｘ１５がそれぞれ対応するＡＮＤセルへ入力されるようになっている。すなわち、ＡＮＤセルの例えば、符号１１−１〜１１−１６を例に採れば、ハイフン”−”の後の添字の最小値、具体的には、”１”から昇順に最下位ビットＸ０、その上位ビットのデジットＸ１・・・と順に対応するＡＮＤセルへ入力されるものとなっている。
【００１２】
そして、これらＡＮＤセル１１−１〜１１６−１６の演算結果は、先の数式９における２のべき数が同一、換言すれば、同一ビット毎に区分されて部分和演算部１０２へ入力されるようになっている。すなわち、例えば、先の数式９において、２１の項は、（Ｘ０・Ｙ１＋Ｘ１・Ｙ０）２１となるが、ＡＮＤセル１２−１によって得られる演算結果Ｘ０・Ｙ１と、ＡＮＤセル１１−２によって得られる演算結果Ｘ１・Ｙ０とが２１の項の構成要素として部分和演算部１０２へ入力されるようになっている。
図２においては、ＡＮＤセル１１−１が右端上となるように図２を見た場合に紙面縦方向に位置するＡＮＤセルの演算結果が、数式９において丁度２のべき数が同一となる項の集合となっている。
【００１３】
次に、部分和演算部１０２について説明する。
本発明の実施の形態における部分和演算部１０２は、図３に示されたように、第１の部分和演算部（図３においては「ＣＡＬ（１）」と表記）５１と、第２の部分和演算部（図３においては「ＣＡＬ（２）」と表記）５２、第３の部分和演算部（図３においては「ＣＡＬ（３）」と表記）５３とに大別されて構成されたものとなっている。
第１の部分和演算部５１は、先に述べたように２０、２１、２２、・・・と同一のビット毎に入力されたＡＮＤセル１１−１〜１１６−１６における演算結果について、ビット毎の部分和が算出されるようになっているものである。
すなわち、まず、２０のデジットは、Ｘ０・Ｙ０のみからなるので、既にＡＮＤセル１１−１により得られているＸ０・Ｙ０の演算結果そのものがこの２０のデジットにおける値となるので、この第１の部分和演算部５１における特段の演算は行われない。
次に、２１のデジットは、先の数式９から２つの積項の和（Ｘ０・Ｙ１＋Ｘ１・Ｙ０）によって表されるものとなっていることから、これら２つの積項和を求める必要があるので、ＡＮＤセル１２−１から入力された演算結果Ｘ０・Ｙ１と、ＡＮＤセル１１−２から入力された演算結果Ｘ１・Ｙ０との和が演算されることとなる。このような２個の積項和は、具体的には例えば、公知・周知の構成を有してなる全加算器（フルアダー）を用いての演算が好適である。
【００１４】
次に、２２のデジットは、先の数式９から３つの積項の和（Ｘ２・Ｙ０＋Ｘ１・Ｙ１＋Ｘ０・Ｙ２）によって表されるものとなっていることから、これら３つの積項の和を求める必要があるので、ＡＮＤセル１１−３から入力された演算結果Ｘ２・Ｙ０と、ＡＮＤセル１２−２から入力された演算結果Ｘ１・Ｙ１と、ＡＮＤセル１３−１から入力された演算結果Ｘ０・Ｙ２との和が演算されることとなる。なお、このような３つの積項和の場合も、上述の２つの積項和を求める場合と同様、全加算器（フルアダー）を用いた公知・周知の加算回路を用いての演算が好適である。
次に、２３のデジットは、先の数式９から４つの積項の和（Ｘ３・Ｙ０＋Ｘ２・Ｙ１＋Ｘ１・Ｙ２＋Ｘ０・Ｙ３）によって表されるものとなっていることから、これらの和を演算する必要がある。ここで、本発明の実施の形態においては、この２３のデジットを含めて４個以上の積項和の演算については、次述するような回路を用いて演算がなされるようになっている。
【００１５】
以下に、４個以上の積和の演算処理と、それに用いられる回路構成について、図４乃至図７を参照しつつ説明する。
まず、ｔビット目（ｔ＝ｉ＋ｊ）における積項和を求める場合の基本的な処理手順について説明する。例えば、本発明の実施の形態において最も積項和の数が多い１５ビット目、ｔ＝ｉ＋ｊ＝１５（２１５）を例に採り説明すれば、この場合、先の基本乗算部１０１から第１の部分和演算部５１へ入力されて求められる積項和は、次のように数式１０で表される。
【００１６】
【数１０】
2004259091.tif 000008
【００１７】
この１５ビット目は、積項数が１６個と多いために、図４に示されたように、ｊ＝０〜３、４〜７、８〜１１、１２〜１５と、４個の積項毎の和、すなわち部分和を求め、その部分和をさらに足し合わせることで当該ビットにおける全ての積項の和が求めるられるものとなっている。
そして、４個の積項についての部分和には、図５及び図６に示された加算回路４１がそれぞれ用いられるものとなっている。
以下、図５及び図６を参照しつつこの加算回路４１について説明すれば、まず、この加算回路４１は、この加算回路４１による演算結果の最下位ビットＳ（ＰＯ）が求められる下位演算部４１Ａと、桁上がりによる上位２ビットが求められる上位演算部４１Ｂとに大別されて構成されたものとなっている。
下位演算部４１Ａ及び上位演算部４１Ｂ共に、共通の４つの入力端子Ｋ０，Ｋ１，Ｋ２，Ｋ３が設けられたものとなっており、後述するようにこれら４つの入力端子Ｋ０，Ｋ１，Ｋ２，Ｋ３へ加算演算の対象となる信号が印加されるようになっている。
【００１８】
まず、下位演算部４１Ａは、８個のＡＮＤ素子２〜９と、１個のＯＲ素子１８とを有して構成されたものとなっている（図５参照）。
第１乃至第４のＡＮＤ素子２〜５はいずれも、１つの負論理入力端子と３つの正論理入力端子を有して構成されたものとなっている。
また、第５乃至第８のＡＮＤ素子６〜９はいずれも、３つの負論理入力端子と１つの正論理入力端子とを有して構成されたものとなっている。
そして、第１乃至第４のＡＮＤ素子２〜５の負論理入力端子が、順に入力端子Ｋ０、Ｋ１、Ｋ２、Ｋ３とされている。
さらに、第１のＡＮＤ素子２の負論理入力端子は、第２、第３、第４及び第５のＡＮＤ素子３，４，５，６の正論理入力端子及び第６、第７及び第８のＡＮＤ素子７，８，９の負論理入力端子に接続されたものとなっている。
【００１９】
また、第１のＡＮＤ素子２の正論理入力端子の１つは、第３、第４及び第６のＡＮＤ素子４，５，７の正論理入力端子の１つに接続されると共に、第５、第７及び第８のＡＮＤ素子６，８，９の負論理入力端子の１つに接続されたものとなっている。
さらに、第１のＡＮＤ素子２の２つ目の正論理入力端子は、第２、第４及び第７のＡＮＤ素子３，５，８の正論理入力端子に接続されると共に、第５、第６及び第８のＡＮＤ素子６，７，９の負論理入力端子に接続されたものとなっている。
またさらに、第１のＡＮＤ素子２の３つ目の正論理入力端子は、第２、第３及び第８のＡＮＤ素子３，４，９の正論理入力端子に接続されると共に、第５、第６及び第７のＡＮＤ素子６，７，８の負論理入力端子に接続されたものとなっている。
そして、これら第１乃至第８のＡＮＤ素子２〜９の出力端子は、これら第１乃至第８のＡＮＤ素子２〜９に対応した数の正論理入力端子を有してなる第１のＯＲ素子１８の入力端子にそれぞれ接続されたものとなっており、この第１のＯＲ素子１８の出力は、この加算回路４１による演算結果の最下位ビットＳ（ＰＯ）とされるものとなっている（図５参照）。
【００２０】
次に、上位演算部４１Ｂについて説明すれば、この上位演算部４１Ｂは、８個のＡＮＤ素子１０〜１７と、１個のＯＲ素子１９とを有して構成されたものとなっている（図６参照）。
第９乃至第１４のＡＮＤ素子１０〜１５と第１６のＡＮＤ素子１７は、いずれも２つの正論理入力端子を有してなるものとなっている。そして、第９乃至第１２のＡＮＤ素子１０〜１３の一方の正論理入力端子は、順に、入力端子Ｋ０、Ｋ１、Ｋ２、Ｋ３とされている。
そして、第９のＡＮＤ素子１０の入力端子Ｋ０とされている一方の正論理入力端子は、第１１、第１２及び第１５のＡＮＤ素子１２，１３，１６の正論理入力端子に接続されたものとなっている。また、第９のＡＮＤ素子１０の他方の正論理入力端子は、第１３及び第１５のＡＮＤ素子１４，１６の正論理入力端子に接続されたものとなっている。
【００２１】
また、第１０のＡＮＤ素子１１の他方の正論理入力端子は、第１３、第１４及び第１５のＡＮＤ素子１４，１５，１６の正論理入力端子に接続されたものとなっている。
さらに、第１２のＡＮＤ素子１３の入力端子Ｋ３とされた正論理入力端子は、第１４及び第１５のＡＮＤ素子１５，１６の正論理入力端子に接続されたものとなっている。
そして、第１５のＡＮＤ素子１６の出力端子に得られる出力信号は、この加算回路４１における先の最下位ビットＳ０（Ｐ０）の１つ上のビットである第１の桁上げビット出力Ｃ１（Ｐ１）とされるようになっていると共に、この出力端子は、第１６のＡＮＤ素子１７の他方の正論理入力端子に接続されたものとなっている（図６参照）。
また、第９乃至第１４のＡＮＤ素子１０〜１５の出力端子は、これら第９及び第１４のＡＮＤ素子１０〜１５に対応した数の正論理入力端子を有してなる第２のＯＲ素子１９の入力端子にそれぞれ接続されたものとなっている。
【００２２】
またさらに、第２のＯＲ素子１９の出力端子は、第１６のＡＮＤ素子１７の一方の正論理入力端子に接続されたものとなっている。
そして、第１６のＡＮＤ素子１７の出力端子は、先の第１の桁上げビット出力Ｃ１（Ｐ１）の上位ビットである第２の桁上げビット出力Ｃ２（Ｐ２）が得られるものとなっている。
【００２３】
図７には、上述の構成を有してなる加算回路４１の真理値表が示されており、以下、同図について説明する。
まず、Ｋ０〜Ｋ３が全て零の場合、当然ながら出力Ｓ０、Ｃ１、Ｃ２はいずれも零である（図７の（１）の行参照）。
次に、Ｋ０〜Ｋ３のいずれか１つが”１”である場合、出力Ｓ０（Ｐ０）のみが”１”となる（図７の（２）〜（５）の行参照）。
また、Ｋ０〜Ｋ３のいずれか２つが”１”である場合、出力Ｃ１（Ｐ１）のみが”１”となる（図７の（６）〜（１１）の行参照）。
さらに、Ｋ０〜Ｋ３のいずれか３つが”１”である場合、出力Ｓ０（Ｐ０），Ｃ１（Ｐ１）が共に”１”となる（図７の（１２）〜（１５）の行参照）。
そして、Ｋ０〜Ｋ３のいずれもが”１”である場合、出力Ｃ２（Ｐ１）のみが”１”となる（図７の（１６）の行参照）。
【００２４】
次に、かかる構成を有してなる加算回路４１を用いた部分和を求める演算について、基本乗算部１０１から部分和演算部１０２へ入力されるｔ＝１５ビット目についての部分和演算を例に採り、図４乃至図６を参照しつつ説明する。
この１５ビット目は、既に述べたように、積項数が１６個であるために、４個の積項毎に、図５及び図６に示された加算回路４１によってそれぞれの４個の積項和（部分和）が求められる。
例えば、Ｘｔ・Ｙ０・２ｔ＋Ｘｔ−１・Ｙ１・２ｔ＋Ｘｔ−２・Ｙ２・２ｔ＋Ｘｔ−３・Ｙ３・２ｔの部分和は、Ｘｔ・Ｙ０、Ｘｔ−１・Ｙ１、Ｘｔ−２・Ｙ２、Ｘｔ−３・Ｙ３がそれぞれ加算回路４１の入力端子Ｋ０，Ｋ１，Ｋ２，Ｋ３へ入力されて加算結果が得られることとなる。ここで、この加算結果は、最大で２ビットの桁上げが生じ、全体として最大で３ビットで表される値となる。この最大で３ビットとなる演算結果を文字式で表すと、図４に示されたように、先の（Ｘｔ・Ｙ０＋Ｘｔ−１・Ｙ１＋Ｘｔ−２・Ｙ２＋Ｘｔ−３・Ｙ３）を例に採れば、上位ビットから順に、Ｕｔ，２０−３・２ｔ＋２、Ｕｔ，１０−３・２ｔ＋１、Ｕｔ，００−３・２ｔ、と表されることとなる（図４の符号Ｉ参照）。ここで、Ｕは、デジットの値を便宜的に表すもので、その添え字について例えば、最上ビットにおける”ｔ，２１−３”を例に採り説明すれば、「ｔ」は、この部分和が、基本乗算部１０１から第１の部分和演算部５１に入力されたいずれのデジットのものであるのか、すなわち、本発明の実施の形態における例で言えば、２０〜２３０のいずれのビットの部分和であるのかを示し、カンマで区切られた次の数値、例えば、”２０−３”における”２”は、Ｕの値が、（Ｘｔ・Ｙ０＋Ｘｔ−１・Ｙ１＋Ｘｔ−２・Ｙ２＋Ｘｔ−３・Ｙ３）の部分和によって得られる２ビットの桁上げの内の２ビット目のものであることを、そして”２”の添字”０−３”は、いずれの部分和であるかを意味し、この場合は、先の数式１０においてｊ＝０〜３となる積項である（Ｘｔ・Ｙ０＋Ｘｔ−１・Ｙ１＋Ｘｔ−２・Ｙ２＋Ｘｔ−３・Ｙ３）の部分和であることを意味するものとなっている。
【００２５】
したがって、”Ｕｔ，１０−３・２ｔ＋１”における”Ｕｔ，１０−３”は、Ｕの値がｔビット目の部分和の内、ｊ＝０〜３の部分和によって得られた２ビットの桁上げの内の最初の１ビット目の値であることを意味することとなる。
また、”Ｕｔ，００−３・２ｔ”における”Ｕｔ，００−３”は、Ｕの値がｔビット目の部分和の内、ｊ＝０〜３の部分和によって得られたｔビット目の値であることを意味する。
以下、数式１０のｊ＝４〜７の部分和、ｊ＝８〜１１の部分和、ｊ＝１２〜１５の部分和は、同様にしてそれぞれ設けられた加算回路４１によって演算算出され、それぞれの演算結果は、図４において符号Ｉ〜ＩＶが付されたように表されるものとなる。なお、これら各々におけるＵの添字の意味は、ｊ＝０〜３の部分和を例に採り説明したものと基本的に同一であるので、個々の演算結果についてのここでの詳細な説明は省略することとする。
【００２６】
そして、上述のようにして求められた部分和の総和が求められることとなる。すなわち、図４に示された例では、部分和の総和の内、最下位ビットの総和、すなわち、Ｕｔ，００−３・２ｔ＋Ｕｔ，０４−７・２ｔ＋Ｕｔ，０８−１１・２ｔ＋Ｕｔ，０１２−１５・２ｔの値が、”Ｕ０ｔ，００−１５・２ｔ”と表されており、また、部分和の総和の内、第１の桁上げビットの総和、すなわち、Ｕｔ，１０−３・２ｔ＋１＋Ｕｔ，１４−７・２ｔ＋１＋Ｕｔ，１８−１１・２ｔ＋１＋Ｕｔ，１１２−１５・２ｔ＋１の値が、”Ｕ１ｔ，００−１５・２ｔ＋１”と表されている（図４の符号Ｖ参照）。そして、このビットの総和には、最下位ビットからの桁上げが加算されることとなるが、図４においては、その桁上げ値が”Ｕ０ｔ，１０−１５・２ｔ＋１”と表されて示されている（図４の符号Ｖ参照）。
さらに、部分和の総和の内、第２の桁上げビットの総和、すなわち、Ｕｔ，２０−３・２ｔ＋２＋Ｕｔ，２４−７・２ｔ＋２＋Ｕｔ，２８−１１・２ｔ＋２＋Ｕｔ，２１２−１５・２ｔ＋２の値が、”Ｕ２ｔ，００−１５・２ｔ＋２”と表されている（図４の符号Ｖ参照）。そして、これに更に、先の最下位ビットからの桁上げによる値”Ｕ０ｔ，２０−１５・２ｔ＋２”と、第１の桁上げビットの総和”Ｕ１ｔ，００−１５・２ｔ＋１”と最下位ビットからの桁上げ値”Ｕ０ｔ，１０−１５・２ｔ＋１”との和により生ずる桁上げ値”Ｕ１ｔ，１０−１５・２ｔ＋２”が加算されることが示されている（図４の符号Ｖ参照）。
【００２７】
そして、この部分和の総和においては、第３の桁上げビット、第４の桁上げビットが生じるが、まず、第３の桁上げビット、すなわち、２ｔ＋３で表されるビットの値は、第１の桁上げビット、換言すれば、２ｔ＋１で表されるビットからの桁上げによる値”Ｕ１ｔ，２０−１５・２ｔ＋３”と第２の桁上げビット、換言すれば、２ｔ＋２で表されるビットからの桁上げによる値”Ｕ２ｔ，１０−１５・２ｔ＋３”との和として求められることとなる（図４の符号Ｖ参照）。
また、第４の桁上げビット、すなわち、２ｔ＋４で表されるビットの値は、第２の桁上げビットからの桁上げによる値”Ｕ２ｔ，２０−１５・２ｔ＋４”となる（図４の符号Ｖ参照）。
なお、これらの演算は、最大でも例えば、２ｔ＋２で表されるビットで三項の和（Ｕ２ｔ，００−１５・２ｔ＋２＋Ｕ１ｔ，１０−１５・２ｔ＋２＋Ｕ０ｔ，２０−１５・２ｔ＋２）であるので、全加算器を用いた公知・周知の加算回路によって演算されるようになっている。
そして、結局、図４に示された１６個の積項の総和は、５ビットで表現可能の値となる。図４においては、その５ビットの値を最上位ビットから順に、Ｐｔ，４・２ｔ＋４、Ｐｔ，３・２ｔ＋３、Ｐｔ，２・２ｔ＋２、Ｐｔ，１・２ｔ＋１、Ｐｔ，０・２ｔ＋１、と表している（図４の符号ＶＩ参照）。
【００２８】
第１の部分和演算部５１における演算は、上述したように積項数が２又は３個となるビットについては、その積項の和は、公知・周知の全加算器を用いた加算回路による演算によって求められる一方、積項の数が４個以上となるビットについては、４個ずつ積項を分割して、それぞれの部分和が図５及び図６で示されたような加算回路４１によって求められ、その求められた部分和の総和がさらに公知・周知の全加算器を用いた加算回路によって求められるようになっている。
結局、本発明の実施の形態における例の場合、第１の部分和演算部５１における演算結果は、ビット毎に纏めると図８に示されたようにＰ０，０〜Ｐ３０，０となる。ここで、Ｐａ，ｂの添字について説明すれば、ａは、そのＰの値が生じたビットを表し、ｂは、その値が桁上げによるものであるか否かを表すものとなっている。すなわち、”Ｐ１，０”は、２１のデジットの値であることを意味し、”Ｐ１，１”は、２１のデジットの部分和で生じた１ビット分の桁上げであることを意味し、これは、結局、１つ上のビット２２のデジット”Ｐ２，０”へ加算されるものとなる（図８参照）。また、例えば、”Ｐ３，２”のようにｂ＝２は、２ビット分の桁上げであることを意味する。したがって、この”Ｐ３，２”は、元々は２３のビットの部分和によるものであるが、２ビット分の桁上がりであるので、２５のビットの値に加算されることとなる（図８参照）。
結局、この第１の部分和演算部５１によって得られる演算結果は、下記する数式１１の如くに表されるものとなる。
【００２９】
【数１１】
2004259091.tif 000009
【００３０】
上述のようにして第１の部分和演算部５１で得られた複数のＰｉ，ｋは、第２の部分和演算部５２へ入力されるようになっている。
【００３１】
第２の部分和演算部５２は、第１の部分和演算部５１から入力された複数のＰｉ，ｋを図８に示されたようにビット毎に区分し、ビット毎における複数のＰｉ，ｋの和を求めるよう構成されてなるものである。そして、この第２の部分和演算部５２における部分和を求める回路構成は、基本的に先の第１の部分和演算部５１と同様に、２又は３個のＰｉ，ｋの和となるビットについては、公知・周知の全加算器を用いた加算回路による演算によってその値が求められるよう構成されてなる一方、Ｐｉ，ｋの数が４個以上となるビットについては、４個ずつに区分して、先の図５及び図６で示されたような加算回路４１によってそれぞれの区分毎に和を求め、その後、各区分毎の演算結果の総和を演算するよう構成されたものとなっている。
例えば、図８における２１８のビットを例に採れば、このビットのデジットは、Ｐ１８，０＋Ｐ１７，１＋Ｐ１６，２＋Ｐ１５，３＋Ｐ１４，４と表されるが、４つの項、例えば、Ｐ１８，０＋Ｐ１７，１＋Ｐ１６，２＋Ｐ１５，３については、図５及び図６に示された構成を有してなる加算回路４１により求め、その加算結果と残りのＰ１４，４との加算は、全加算器を用いた公知・周知の構成の加算回路により求められるようになっている。
そして、この第２の部分和演算部５２における演算結果は、先の第１の部分和演算部５１の場合と同様に下位ビットからの桁上げを含めて２０〜２３１のビットにおいて生じ、図８においてはＱ０，０〜Ｑ３０，１と表され該当するビットに区分されている。
【００３２】
そして、第３の部分和演算部５３において、このＱ０，０〜Ｑ３０，１のビット毎の部分和が求められるようになっている。なお、この第３の部分和演算部５３の構成、機能は基本的に上述した第２の部分和演算部５２と同一であるのでここでの再度の詳細な説明は省略することとなる。
このようにして、ｎビットの乗数Ｙとｍビットの被乗数Ｘとの乗算値を求める際に、先の数式９に基づいて個々のデジットの積の和の形式に展開したものについて、ビット毎の積項の和を順次算出してゆくようにし、この際、積項の数が４個以上となる場合には、４個ずつに区分し、それぞれの和、すなわち部分和を得た後、それら部分和の総和を求めるという演算処理を繰り返してゆくことで、桁上げの伝播が多数の素子に渡ってゆくことによる演算時間の高速化の困難性という従来の並列乗算器における問題を回避することができることとなるものである。
すなわち、本発明の実施の形態において説明したように、例えば、１６ビットの乗算において、４個づつの積項の和を求めるようにすると、桁上げ信号の伝播は、論理ゲートの数で言えば高々３段程度で済み、その積項和の演算を４、５回繰り返すことにより最終の乗算結果を得ることができる。そのため、並列乗算器全体でも、ゲート数２０段以下の桁上げ信号の伝播で最終の乗算結果を得ることができる。これに対して、従来の並列乗算器においては、本発明の実施の形態と同様に１６ビットの乗算の場合、３２ビット以上の桁上げ信号の伝播が避けられなかった。すなわち、従来の並列乗算器において、桁上げ信号は、論理ゲート数で言えば、１ビット当たりのゲート段数を３として、３×３２＝９６段程度の論理ゲートの伝播を回避することはできなかった。
【００３３】
したがって、本発明の実施の形態における並列乗算器においては、従来の並列乗算器に比して桁上げ信号が伝播する論理ゲートの段数が大凡１／４以下に低減されるため、演算処理時間の格段の高速化が図られることとなるものである。
そして、この桁上げ信号の伝播における論理ゲートの段数の低減は、乗数Ｙと被乗数Ｘのビット長が、例えば、３２×３２ビット、６４×６４ビットと大きくなるに従い、一層顕著となる。
なお、上述の発明の実施の形態においては、基本乗算部１０１及び部分和演算部１０２共に、ＡＮＤ素子等の公知・周知のいわゆる論理素子の組み合わせによって回路構成した例を挙げたが、このような構成に限定される必要は無いことは勿論であり、例えば、公知・周知のマイクロコンピュータ（ＣＰＵ）や同様な機能を有してなる素子を用いて、本発明の実施の形態おいて説明したような基本乗算部１０１及び部分和演算部１０２の機能をいわゆるソフトウェア処理によって実行できるようにして構成しても良いものである。
【００３４】
【発明の効果】
以上、述べたように、本発明によれば、精々４乃至５個程度の積項の和を求める演算処理を繰り返すことで乗数Ｙと被乗数Ｘの乗算値が得られるよう構成したので、従来と異なり、桁上げ信号の伝播を大幅に低減することができ、そのため、演算処理の高速化が実現できるという効果を奏するものである。また、回路構成としても、加算回路を主として比較的簡単に構成されるので、小型化が容易であり、特に、いわゆるマイクロプロセッサなどのキーコンポーネントとして用いる場合には、高速で、かつ、小型のＬＳＩを容易に実現することができるという効果を奏するものである。
【図面の簡単な説明】
【図１】本発明の実施の形態における並列乗算器の基本的な構成例を示す構成図である。
【図２】図１に示された並列乗算器を構成する基本乗算部の構成のみを示す構成図である。
【図３】図１に示された並列乗算器を構成する部分和演算部の基本的な構成例を示す構成図である。
【図４】本発明の実施の形態における部分和演算部における部分和の演算手順を説明する説明図である。
【図５】４個の積項の部分和に用いられる加算器を構成する下位演算部の構成例を示す構成図である。
【図６】４個の積項の部分和に用いられる加算器を構成する上位演算部の構成例を示す構成図である。
【図７】図５及び図６に示された構成を有してなる加算器の真理値を説明する説明図である。
【図８】図３に示された部分和演算部を構成する第２及び第３の部分和演算部における演算を説明する説明図である。
【符号の説明】
４１…加算回路
５１…第１の部分和演算部
５２…第２の部分和演算部
５３…第３の部分和演算部
１０１…基本乗算部
１０２…部分和演算部
【図１】
2004259091.tif 000014
【図２】
2004259091.tif 000015
【図３】
2004259091.tif 000016
【図４】
2004259091.tif 000017
【図５】
2004259091.tif 000018
【図６】
2004259091.tif 000019
【図７】
2004259091.tif 000020
【図８】
2004259091.tif 000021