(57)【特許請求の範囲】
【請求項１】
ｉ進法で符号化された被乗数Ｘと乗数Ｙの乗算結果Ｕ＝Ｘ×Ｙを求める乗算器であって、
最初にＵ＝Ｘとし、前記乗数ＹがｉＳで割り切れるか否かを判定し、
前記乗数ＹがｉＳで割り切れる場合には、前記Ｕをその最上位ビット側へＳビットシフトして、そのシフト結果を新たなＵとすると共に、Ｙ／ｉＳを新たなＹとする一方、
前記乗数ＹがｉＳで割り切れない場合には、当該乗数Ｙからｉより小さな数ｊを減算した（Ｙ−ｊ）または乗数Ｙに前記ｊを加算した（Ｙ＋ｊ）を新たにＹとした後、この新たな乗数ＹがｉＳで割り切れる場合には、前記Ｕをその最上位ビット側へＳビットシフトし、そのシフト結果にＸ×ｊを加算または減算したものを新たなＵとすると共に、Ｙ／ｉＳを新たなＹとし、
以下、前記乗数ＹがｉＳで割り切れる場合と、乗数ＹがｉＳで割り切れない場合との処理を、前記Ｓを順次減じながら繰り返してゆき、Ｙがｉより小さくなった時点におけるＵを被乗数Ｘと乗数Ｙの乗算結果として出力するよう構成されてなることを特徴とする乗算器。
【請求項２】
被乗数Ｘと乗数Ｙとの乗算結果を算出する乗算器であって、パラレルデータが入力されて、外部から入力された所定のシフト信号に応じて前記パラレルデータに対してシフトを施して出力するシフタと、
前記シフタの出力データに前記被乗数Ｘを加算又は減算して出力する加減算回路とを一組として、
所定の条件の下で決定された段数ｍに対応して前記加減算回路の出力側に次段のシフタと加減算回路の一組が接続されるようにして前記シフタ及び加減算回路の組がｍ段縦列的に接続されて乗算器が構成され、
各々の段のシフタに入力される前記シフト信号は、当該各々の段に応じて定められるシフト量に応じたものであり、当該各々の段のシフト量は、
前記被乗数Ｘと乗数Ｙとがｉ進法で符号化されたものである場合、
前記乗数ＹがＹ＝（・・・（（（２Ｓ１±１）２Ｓ２±１）２Ｓ３±１）・・・）２Ｓｍ±１）と表し得た場合において、当該式中における２の指数部のそれぞれの値であり、当該式中の最も内側の括弧内の２の指数部の値を始めとして各々の指数部の値が、第１のシフタから順に各々のシフタのシフト量として割り当てられるものであり、
前記段数ｍは、前記シフト量として得られる２の指数部の個数に対応するものであることを特徴とする乗算器。
【請求項３】
被乗数Ｘと乗数Ｙとの乗算結果を算出する乗算器であって、２組のパラレルデータの入力を可能として、外部から入力される制御信号に応じて前記２組のパラレルデータのいずれか一方を選択して出力する入力セレクタと、
前記入力セレクタからのパラレルデータが入力されて、外部から順に入力される所定のシフト信号に応じて前記パラレルデータに対してシフトを施して出力するシフタと、
前記シフタからのパラレルデータ出力に対して前記被乗数Ｘを加算又は減算して、その演算結果をパラレル出力する加減算回路と、
前記加減算回路のパラレル出力データに対して所定の遅延時間の遅延を施して出力し、出力段は、前記入力セレクタの一方の入力段に接続されてなる遅延素子とを具備し、
前記入力セレクタには、他方の入力段に前記被乗数Ｘがパラレル入力され、当該被乗数Ｘが選択出力されるべく制御信号が入力された後は、所定間隔で前記遅延素子からのパラレルデータが（ｍ−１）回選択出力されるよう前記制御信号が印加される一方、
前記シフタには、入力セレクタから新たなパラレルデータの入力がなされる度毎に、所定の条件の下で求められたシフト量に対応するシフト信号が入力されるようになっており、
前記各々のシフト量は、
前記被乗数Ｘと乗数Ｙとがｉ進法で符号化されたものである場合、
前記乗数ＹがＹ＝（・・・（（（２Ｓ１±１）２Ｓ２±１）２Ｓ３±１）・・・）２Ｓｍ±１）と表し得た場合において、当該式中における２の指数部のそれぞれの値であり、当該式中の最も内側の括弧内の２の指数部の値を始めとして順に各々のシフト量として割り当てられるものであり、
前記ｍは、前記シフト量として得られる２の指数部の個数に対応するものであり、
前記加減算回路からのｍ回目の出力を前記被乗数Ｘと乗数Ｙとの乗算結果として得ることを特徴とする乗算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタルデータの乗算を行う乗算器に係り、特に、高速化を図ったものに関する。
【０００２】
【従来の技術】
従来、ディジタルデータの乗算回路としては、例えば、図４に示されたようなリップルキャリー形並列乗算器と称されるものが公知・周知となっている。
この図４に示されたリップルキャリー形並列乗算器は、４×３ビットの演算用の回路構成例であり、基本的に同一の回路構成を有してなる１２個の単位乗算回路ＵＭを用いて構成されたものとなっている。
すなわち、単位乗算回路ＵＭは、図５に示されたようにいわゆるフルアダー回路ＦＡを中心に構成されたものである。
かかる構成を有するリップルキャリー形並列乗算器は、被乗数Ｘがｍビット、乗数Ｙがｎビットの場合に、ｎ×ｍ個の単位乗算回路ＵＭを必要とするものである。
なお、図４において、単位乗算回路ＵＭの後の２桁の数字からなる添字は、行と列を表す組み合わせとなっている。すなわち、一桁目の数字が行を、２桁目の数字が列を、それぞれ表すものとなっている。たとえば、ＵＭ２１は、一行目、第２列目の単位乗算回路であることを意味するものとなっている。
【０００３】
また、ディジタルデータの乗算回路の他の例としては、図６に示されたように直並列乗算器が公知・周知となっている。
すなわち、この直並列乗算器は、フルアダー回路ＦＡと、遅延素子DLとを主たる構成要素としてなるもので、被乗数Ｘが１ビット単位で、各々のフルアダー回路ＦＡで乗数Ｙと演算され、Ｙ1ビット側から時系列的にＹ4ビット側へと演算結果が伝達されてゆき乗算出力Ｚが得られるようになっているものである。
【０００４】
【発明が解決しようとする課題】
しかしながら、上述したいずれの乗算器においても、被乗数Ｘ、あるいは乗数Ｙのビット単位での乗算が実行され、各ビットの演算結果が伝搬されて、最終的な乗算結果を得るような構成であるため、ビット数が増えるに従い演算時間が長くなる傾向があり、特に、高速化を要求されるようなディジタル信号処理装置には不向きであるばかりか、扱うビット数の増加に従い回路構成が複雑になり、高価格となるという問題があった。
【０００５】
本発明は、上記実状に鑑みてなされたもので、比較的簡易な構成で、高速演算が可能な乗算器を提供するものである。
本発明の他の目的は、集積回路化に適する低消費電力化、高速化並びに小型化が容易な乗算器を提供することにある。
【０００６】
【課題を解決するための手段】
本発明の目的を達成するため、本発明に係る乗算器は、
ｉ進法で符号化された被乗数Ｘと乗数Ｙの乗算結果Ｕ＝Ｘ×Ｙを求める乗算器であって、
最初にＵ＝Ｘとし、前記乗数ＹがｉＳで割り切れるか否かを判定し、
前記乗数ＹがｉＳで割り切れる場合には、前記Ｕをその最上位ビット側へＳビットシフトして、そのシフト結果を新たなＵとすると共に、Ｙ／ｉＳを新たなＹとする一方、
前記乗数ＹがｉＳで割り切れない場合には、当該乗数Ｙからｉより小さな数ｊを減算した（Ｙ−ｊ）または乗数Ｙに前記ｊを加算した（Ｙ＋ｊ）を新たにＹとした後、この新たな乗数ＹがｉＳで割り切れる場合には、前記Ｕをその最上位ビット側へＳビットシフトし、そのシフト結果にＸ×ｊを加算または減算したものを新たなＵとすると共に、Ｙ／ｉＳを新たなＹとし、
以下、前記乗数ＹがｉＳで割り切れる場合と、乗数ＹがｉＳで割り切れない場合との処理を、前記Ｓを順次減じながら繰り返してゆき、Ｙがｉより小さくなった時点におけるＵを被乗数Ｘと乗数Ｙの乗算結果として出力するよう構成されてなるものである。
【０００７】
かかる構成の乗算器は、例えば、被乗数Ｘと乗数Ｙが共に２進数で表されるものである場合において、乗数ＹがＹ＝（・・・（（（２Ｓ１±１）２Ｓ２±１）２Ｓ３±１）・・・）２Ｓｍ±１）の如くに展開できる場合に、Ｕ＝Ｘ×Ｙ＝（・・・（（（Ｘ２Ｓ１±Ｘ）２Ｓ２±Ｘ）２Ｓ３±Ｘ）・・・）２Ｓｍ±Ｘ）と表され、Ｘのシフトとそのシフト結果に対する加減算処理によって乗算結果を得ることができることに着目して、かかる処理が行われるように構成されたものであり、そのため構成の簡素化と、演算速度の向上が可能となるものである。
【０００８】
【発明の実施の形態】
以下、本発明の実施の形態について、図１乃至図３を参照しつつ説明する。
なお、以下に説明する部材、配置等は本発明を限定するものではなく、本発明の趣旨の範囲内で種々改変することができるものである。
最初に、第１の回路構成例について、図１を参照しつつ説明する。
第１の回路構成例における乗算器Ｍ１は、ｍ個の第１乃至第ｍのシフタ１〜ｍと、ｍ個の第１乃至第ｍの加減算回路１００〜（１００＋ｍ−１）とを有してなり、第１のシフタ１と第１の加減算回路１００とが１段目を、第２のシフタと第２の加減算回路１０１とが、２段目を構成するというようにして、以下、同様に第ｎ番目（ｎ＜ｍ）のシフタと第ｎ番目の加減算回路とがｎ段目を構成するようなものとなっている。
【０００９】
第１乃至第ｍのシフタ１〜ｍは、いずれも基本的に同一の回路構成を有してなるもので、入力されたデータが外部からのシフト信号によりシフトされるよう構成された公知・周知の回路構成を有してなるものである。この発明の実施の形態においては、被乗数Ｘがｎビットであるとすると、第１乃至第ｍのシフタ１〜ｍは、被乗数Ｘがパラレルで入力されると共に、シフト量Ｓ1，Ｓ2・・・Ｓm（詳細は後述）に対応するシフト信号ｓ1，ｓ2・・・ｓmが入力されるようになっている。そして、こらら第１乃至第ｍのシフタ１〜ｍは、シフト信号ｓ1，ｓ2・・・ｓmに応じて、ＭＳＢ(Most Significant Bit)側へ、ｎビットの入力データＸ1，Ｘ2，・・・，Ｘmがシフトされるようになっているものである。そして、そのシフト結果は、第１のシフタ１であれば、第１の加減算回路１００へ、第２のシフタ２であれば、第２の加減算回路１０１へというように、それぞれ対応する加減算回路へ入力されるようになっている。
【００１０】
第１乃至第ｍの加減算回路１００〜（１００＋ｍ−１）は、対応する第１乃至第ｍのシフタ１〜ｍから入力されたシフト結果と被乗数Ｘとの加算演算を行うもので、公知・周知の回路構成を有してなるものである。
そして、第１乃至第（ｍ−１）の加減算回路１００〜（１００＋ｍ−２）の演算結果は、それぞれ次段のシフタに入力されるような構成となっている。
【００１１】
次に、この乗算器Ｍ１による乗算の原理について説明する。
先ず、被乗数をＸとし、乗数をＹとして、共に２進数であるとする。
例えば、乗数ＹがＹ＝（・・・（（（２Ｓ１±１）２Ｓ２±１）２Ｓ３±１）・・・）２Ｓｍ±１）の如くに展開できるものとする（この式を式１とする）。
この場合、Ｕ＝Ｘ×Ｙは、Ｕ＝（・・・（（（Ｘ２Ｓ１±Ｘ）２Ｓ２±Ｘ）２Ｓ３±Ｘ）・・・）２Ｓｍ±Ｘ）と表現することができる（この式を式２とする）。
この式２において、最も内側の括弧に括られた項（Ｘ２Ｓ１±Ｘ）について見ると、これは、被乗数Ｘに２Ｓ１を乗じた結果に対してさらに被乗数Ｘを加減算するものとなっているが、ここで被乗数Ｘに２Ｓ１を乗ずる部分は、２進数の特性から、被乗数ＸをＳ１ビットだけ、ＭＳＢ(Most Significant Bit)側へシフトすることに他ならない。
（Ｘ２Ｓ１±Ｘ）の演算結果をＵ１とすれば、次の括弧で括られた項である（（Ｘ２Ｓ１±Ｘ）２Ｓ２±Ｘ）は、Ｕ1×２Ｓ２±Ｘとなり、これも、上述した最初の演算同様に処理することができる。すなわち、Ｕ１をＳ２ビットだけＭＳＢ側へシフトした結果に、被乗数Ｘを加算（または減算）すればよい。
結局、先の式２の場合、シフトと加減算処理をｍ回繰り返すことでＸ×Ｙの演算結果を得ることができる。換言すれば、シフタと加減算回路との組み合わせをｍ段縦列に組み合わせて乗算器を構成することで、上述したようなシフトと加減算をｍ回繰り返してＵ＝Ｘ×Ｙを得るようにすることができる。
図１に示された乗算器Ｍ１は、上述のような観点に基づき構成されたものである。
【００１２】
次に、乗数Ｙを式１の如くに表す際の２の指数部分の値、換言すればシフト量Ｓ１，Ｓ２，・・・，Ｓｍを求める手順について、図２を参照しつつ説明する。処理が開始されると、まず、演算パラメータｍ，Ｓ，Ｄの値が共に初期値ゼロに設定される（図２のステップ１００参照）。
次いで、Ｙが１か否かが判定され（図２のステップ１０２参照）、Ｙが「１」であると判定された場合（ＮＯの場合）には、処理の必要なしとして一連の処理が終了されることとなる一方、「１」であると判定された場合（ＹＥＳの場合）にはステップ１０４へ進み、Ｙが偶数か否かが判定されることとなる。
そして、Ｙが偶数であると判定された場合（ＹＥＳの場合）には、ステップ１０６へ進み、演算パラメータＳすなわちシフト量Ｓの値が、このステップ１０６を実行する直前のＳの値に「１」を加算した値へ更新されることとなる。また、このステップ１０６においては、Ｙの値がこのステップ１０６の実行直前のＹを２で除した値に更新され、その後、先のステップ１０２へ戻り一連の処理が繰り返されることとなる。
すなわち、Ｙが偶数である限りステップ１０２，１０４，１０６が繰り返されてシフト量Ｓ１，Ｓ２，・・・と求められてゆくこととなる。
【００１３】
一方、ステップ１０４において、Ｙが偶数ではないと判定された場合（ＮＯの場合）には、ステップ１０８へ進み、その時点における演算パラメータｍ，Ｄ，Ｓの各々の値が第１回目の結果として出力され、また、必要に応じて図示されない所定の記憶装置等に記憶されることとなる。
次いで、ステップ１１０へ進み、演算パラメータｍの値が、このステップ１１０の実行直前の値に「１」を加算した値に更新されると共に、Ｙの値がステップ１１０の実行直前の値に「１」を加算した値に更新されることとなる。
【００１４】
そして、Ｙの値が「４」の倍数か否かが判定され（図２のステップ１１２参照）、４の倍数である場合（ＹＥＳの場合）には、ステップ１１４へ進み、演算パラメータＤが「−１」に設定されると共に、演算パラメータＳが、このステップ１１４の実行直前の値に「２」を加算した値に更新される。さらに、Ｙの値が、このステップ１１４の実行直前の値を「４」で除した値に更新されて、その後、先のステップ１０２へ戻ることとなる。
【００１５】
一方、ステップ１１２において、Ｙの値が４の倍数ではないと判定された場合（ＮＯの場合）には、ステップ１１６へ進み、Ｙの値が、このステップ１１６の実行直前の値から「２」を減じた値に更新されることとなる。
次いで、ステップ１１８において、演算パラメータＤの値が「１」に設定されると共に、演算パラメータＳの値が、このステップ１１８の実行直前の値に「２」を加算した値に更新され、さらに、Ｙが、このステップ１１８の実行直前の値を「４」で除した値に更新されて、先のステップ１０２へ戻ることとなる。
【００１６】
ここで、ステップ１１０乃至１１８の処理の意味について説明する。まず、ステップ１１０以降の処理が行われる際のＹは、奇数である。そのため、２のｎ乗という形とするためには、奇数に「１」を加算し又は奇数から「１」を減算して偶数とする必要がある。
さらに、奇数の前後の値は、いずれかが２の倍数であり、他方が４の倍数であるという数の性質を利用し、奇数であるＹを４の倍数となるように「１」を加算するか又は「１」を減算するかして、４の倍数となったところで、ステップＳを「２」更新するようにしたのが、ステップ１１０乃至１１８の処理である。
例えば、理解を容易とするため、ステップ１１０の実行直前においてＹ＝５であったと仮定すると、ステップ１１０においては、Ｙ＝５＋１＝６とされる。
これは、４の倍数ではないため、ステップ１１６へ進むこととなり、Ｙ＝６−２＝４とＹが更新されることとなる。すなわち、このステップ１１６の処理は、ステップ１１０の実行直前のＹの値から「１」を減算することに相当する。
これで、Ｙは、４の倍数となるため、ステップ１１８において、シフト量の更新が行われ、また、Ｙが４で除されるようになっている。
ステップ１１０の実行直前において、Ｙ＝７の場合は、ステップ１１０の処理で４の倍数であるＹ＝８となるため、ステップ１１４へ進みシフト量の更新と、Ｙの除算が行われようになっている。
【００１７】
なお、演算パラメータＤは、ステップ１１０の実行直前のＹの値に「１」を加算して４の倍数となった場合と、ならない場合との識別のためのもので、この例では、「１」を加算して４の倍数となった場合にＤ＝−１、「１」を減算して４の倍数となった場合にＤ＝＋１としてある、
このようにして、Ｙの値が「１」となるまで、上述した処理が繰り返されてシフト量Ｓ１，Ｓ２，・・・，Ｓｍが求められることとなる。
なお、上述したような処理は、例えば、マイクロコンピュータにより図２に示された手順に従ったソフトウェアを実行させることにより実現でき、その場合には、得られたシフト量Ｓ１，Ｓ２，・・・，Ｓｍと共に、被乗数Ｘをそのマイクロコンピュータから図１に示された乗算器Ｍ１へ入力するようにすると好適である。
【００１８】
次に、図１を参照しつつ乗算器Ｍ１の動作について説明する。
まず、被乗数Ｘがｎビットであるとして、そのＭＳＢをＸ１として、以下、ＬＳＢ(Least Significant Bit)へ向かうに従いＸの添字の数値は昇順に表されるものとし、ＬＳＢは、Ｘｎと表すものとする。
そして、第１のシフタ１に、被乗数Ｘがパラレルに入力されると共に、先に図２を参照しつつ説明したように予め求められたシフト量Ｓ１が入力されると、被乗数Ｘがシフト量Ｓ１に対応してＭＳＢ側へシフトされ、そのシフト結果が第１の加減算回路１００へパラレル出力されることとなる。
第１の加減算回路１００においては、パラレル入力された被乗数Ｘと第１のシフタ１から入力されたデータとの加算演算が行われ、その演算結果は、第２のシフタ２にパラレル入力されることとなる。
【００１９】
第２のシフタ２においては、第１の加減算回路１００からデータが入力されると、シフト量Ｓ２が入力され、Ｓ２に相当するシフトが先の第１のシフタ１と同様にして第１の加減算回路１００から入力されたデータに対して施され、その結果が第２の加減算回路１０１へパラレル入力されることとなる。
そして、第２の加減算回路１０１においては、第２のシフタ２から入力されたデータと、この第２の加減算回路１０１へパラレル入力された被乗数Ｘとの加算演算が行われ、その演算結果は、第３のシフタ（図示せず）へパラレル入力されることとなる。
以下、同様にして、データのシフトと加算演算が行われ、その結果が次段へ入力されてゆくことが繰り返されてゆき、最終段のｍ段目において、第ｍの加減算回（１００＋ｍ−１）からＸ×Ｙの演算結果であるＵがパラレルデータとして得られることとなる。
【００２０】
次に、被乗数Ｘ＝１００（１０進数）で乗数Ｙ＝１５１（１０進数）の場合を例に採り、乗算器Ｍ１の構成及び動作についてより具体的に説明する。
まず、Ｙ＝１５１の場合、Ｙ＝（（（２３＋１）×２２＋１）×２＋１）２＋１と表すことができる。したがって、この場合、乗算器Ｍ１は４段構成とすればよいこととなる。
そして、１段目において、すなわち第１のシフタ１において、被乗数Ｘは、左に３ビット、すなわちＭＳＢ側に向かって３ビット分のシフトが施されることとなる。Ｘ＝１００は、２進数では、Ｘ＝（１１００１００）２と表されるので、３ビットのシフト後は、（１１００１０００００）２となる。したがって、被乗数Ｘとの加算は、（１１００１０００００）２＋（１１００１００）２＝（１１１００００１００）２となる。
【００２１】
次に、第２のシフタ２においては、（１１１００００１００）２が左に２ビットシフトされて、（１１１００００１００００）２となり、これに第２の加減算回路１０１において被乗数Ｘ＝（１１００１００）２が加算され、（１１１００００１００００）２＋（１１００１００）２＝（１１００１１１０１００）２となる。
次に、第３のシフタ（図示せず）においては、（１１００１１１０１００）２が左に１ビットシフトされて、（１１００１１１０１０００）２となり、第３の加減算回路（図示せず）において、これに被乗数Ｘが加算されて、（１１００１１１０１０００）２＋（１１００１００）２＝（１１１０１００００１１００）２となる。
最後に、この場合の第ｍのシフタ、すなわち第４のシフタ４においては、（１１１０１００００１１００）２が左に１ビットシフトされて（１１１０１００００１１０００）２となり、第ｍの加減算回路すなわち第４の加減算回路１０３において、これに被乗数Ｘが加算されて、（１１１０１００００１１０００）２＋（１１００１００）２＝（１１１０１０１１１１１１００）２となる。
（１１１０１０１１１１１１００）２は、１０進数へ戻せば１５１００であり、これは、Ｘ＝１００とＹ＝１５１との乗算結果に合致し、乗算器Ｍ１によって確かにＸ×Ｙが求められることが確認できる。
【００２２】
次に、第２の回路構成例における乗算器Ｍ２について、図３を参照しつつ説明する。
この乗算器Ｍ２は、先の乗算器Ｍ１がシフト処理の回数に対応してシフタと加減算回路の組がいわば縦列接続的に設けられた構成であるのに対して、一組のシフタと加減算回路を時系列的に繰り返し使用できるように構成されたものである。
すなわち、乗算器Ｍ２は、一組のシフタ１及び加減算回路１００に加えて、入力セレクタ２００と遅延素子２０２とを具備して構成されたものとなっている。シフタ１及び加減算回路１００は、それぞれ先に図１に示された第１乃至第ｍのシフタ１〜ｍ、第１乃至第ｍの加減算回路１００〜（１００＋ｍ−１）と基本的に同一のものであり、そのため、ここでの詳細な説明は省略することとする。
【００２３】
入力セレクタ２００には、被乗数Ｘと、遅延素子２０２を介した加減算回路１００の出力データとが、それぞれパラレルで入力できるようになっており、制御信号Ｓoに応じて（例えば論理値Ｈｉｇｈと論理値Ｌｏｗとの切り替えに応じて）、被乗数Ｘと、遅延素子２０２を介した加減算回路１００の出力データのいずれか一方が選択的にシフタ１へ出力されるようになっている。
【００２４】
シフタ１には、シフト量に対応するシフト信号Ｓ１乃至Ｓｍが順に入力されるようになっており、このシフト信号に応じて、入力セレクタ２００により入力されたデータがシフトされて加減算回路１００へ出力されるようになっている。
加減算回路１００は、シフタ１からの入力されたパラレルデータに、被乗数Ｘを加算して出力するようになっており、そのパラレル出力データは、遅延素子２０２を介して入力セレクタ２００へ戻されるようになっている。
ここで、遅延素子２０２には、シフタ１と加減算回路１００における演算時間に比して十分大きな遅延時間に設定されている。このような遅延素子２０２としては、例えば、ラッチやシフトレジスタなどのクロックの入力によってその駆動が行われる論理素子によって実現可能である。
したがって、入力セレクタ２００において、制御信号Ｓoの入力タイミングを適宜に設定することで、シフタ１と加減算回路１００における演算結果を、タイミングよくフィードバックして、そのフィードバック結果に対して再びシフトと加算処理を施すようにすることができ、あたかも先の図１に示されたように、シフタと加減算回路が複数段に構成されたと等価なものとすることができるようになっている。
【００２５】
次に、上記構成における乗算器Ｍ２の動作について説明する。
まず、入力セレクタ２００によって、被乗数Ｘが選択されて、シフタ１へ出力されると、シフタ１には、外部からシフト信号（シフト量）Ｓ１が入力されて、被乗数ＸはＳ１に対応するシフトが施された後、加減算回路１００へパラレル出力される。ここで、被乗数Ｘのシフトは、先の図１の回路例におけるのと同様に、ＭＳＢ側へ向かって行われるようになっている。
加減算回路１００においては、シフタ１からのパラレルデータに対して被乗数Ｘが加算されて出力され、その演算出力は、遅延素子２０２を介して入力セレクタ２００へ戻されることとなる。
【００２６】
入力セレクタ２００においては、制御信号Ｓoが適宜な信号レベルに切り替えられて、それによって、遅延素子２０２を介した加減算回路１００の出力が選択されて、シフタ１へ入力されることとなる。
シフタ１においては、シフト信号Ｓ２が入力され、入力セレクタ２００から入力されたパラレルデータに対してこのシフト信号に応じたシフトが施され、加減算回路１００へパラレル出力されることとなる。
加減算回路１００においては、シフタ１から入力されたパラレルデータと被乗数Ｘとの加算演算が行われ、その演算結果は、再び遅延素子２０２を介して入力セレクタ２００へ戻されて選択され、以下、上述したと同様な動作が繰り返されることとなる。そして、シフタ１へシフト信号Ｓｍが入力されて、そのシフト結果に対して加減算回路１００において被乗数Ｘが加算された結果が最終演算出力となる。
【００２７】
なお、上述した発明の実施の形態においては、被乗数Ｘ及び乗数Ｙが共に、２進数である場合について説明したが、被乗数Ｘ及び乗数Ｙが共に他の進法で表し得る場合にも適用されることは勿論である。例えば、被乗数Ｘ及び乗数Ｙが共にｉ進法で表されるものであるとすれば、先の式２に対応するＵについての式は、Ｕ＝（・・・（（（ＸｉＳ１±Ｘ・ｊ）ｉＳ２±Ｘ・ｊ）ｉＳ３±Ｘ・ｊ）・・・）ｉＳｍ±Ｘ）と表現されることとなり（なお、ｉ＞ｊである）。したがって、ＸについてのシフトのＸ・ｊを加算または減算する処理を繰り返すようにすることで、Ｕを得ることができるきこととなる。
【００２８】
上述した乗算器を例えば、ディジタルフィルタにおいて用いる場合、ディジタルフィルタの係数を乗数に対応させれば、各段のシフト量は固定されることとなるため、いわゆるバレルシフタ回路のようなものは不要となり、よりハードウェアの簡素化が図られたものとなる。
【００２９】
【発明の効果】
以上、述べたように、本発明によれば、乗算をシフトと加減算で処理できるようにしたので、例えば、乗数Ｙがｎビットの場合、最大でも（ｎ−１）の演算で乗算結果を得ることができることとなり、平均的には、大凡（ｎ−１）／２程度の演算量で済み、従来に比して回路の簡素化が図られると共に、演算処理の高速化実現できるという効果を奏するものである。
また、本発明によれば、ハードウェアの効率的、規則的な縮退による削減が可能となるため、特に、集積回路による実現に際して、低消費電力化、高速化を図ると共に、小型化が容易となるという効果を奏するものである。
【図面の簡単な説明】
【図１】本発明の実施の形態における乗算器の第１の回路構成例を示す構成図である。
【図２】本発明の実施の形態における乗算器による被乗数Ｘのシフト量を求めるための手順を示すフローチャートである。
【図３】本発明の実施の形態における乗算器の第２の回路構成例を示す構成図である。
【図４】従来の乗算器の一回路構成例を示す構成図である。
【図５】図４に示された回路における単位乗算回路の構成を示す構成図である。
【図６】従来の乗算器の他の回路構成例を示す構成図である。
【符号の説明】
１〜ｍ…シフタ
１００〜（１００＋ｍ−１）…加減算回路
２００…入力セレクタ
２０２…遅延素子
【図１】
0003851024.tif 000002
【図２】
0003851024.tif 000003
【図３】
0003851024.tif 000004
【図４】
0003851024.tif 000005
【図５】
0003851024.tif 000006
【図６】
0003851024.tif 000007