前の文書 次の文書 閉じる 登録PDF 公開PDF ブックマークに登録 集合登録 ログイン
出願番号特願平9-1639151997/06/20
国際出願番号
公開番号特開平10-1242981998/05/15
公表/再公表番号
国際公開番号
公告番号
請求公告番号
登録番号
評価スコア係数
AECIL
引用           
引用文献
被引用特願2000-315049, 特願2006-155862
被引用文献
関係図の参照
発明の名称定数乗算器並びに定数乗算器自動生成方法および装置並びに定数乗算器自動生成プログラムを格納した記憶媒体
出願人・権利者富士通株式会社
発明者・考案者小杉一之
代理人真田有
要約
【要約】
【課題】 定数と信号との2値を掛け合わせるものであって、その定数に基づく部分積の数(加算段数)を削減し、回路面積および演算遅延時間を減少させる。
【解決手段】 定数を分解して得られた最少項数の2のべき乗の加減算項の各項に、信号を乗算して得られた部分積を全て加減算する加減算回路(加算器1,2およびインバータ3,4)から構成する。
請求の範囲
【特許請求の範囲】
【請求項1】 定数と任意の値である信号とを掛け合わせる定数乗算器であって、
該定数を分解して得られた最少項数の2のべき乗の加減算項の各項に、該信号を乗算して得られた部分積を全て加減算する加減算回路から構成されたことを特徴とする、定数乗算器。
【請求項2】 該加減算回路が、
前記加減算項のうちの減算項に該信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、
該第1加算回路により加算された値を反転する反転回路と、
該反転回路により反転された値と前記加減算項のうちの加算項に該信号を乗算して得られた部分積とを加算する第2加算回路とから構成されていることを特徴とする、請求項1記載の定数乗算器。
【請求項3】 定数Iと任意の値である信号とを掛け合わせる定数乗算器を自動的に生成するための定数乗算器自動生成方法であって、
該定数Iを最少項数の2のべき乗の加減算項に分解する定数分解ステップと、
該定数分解ステップで得られた前記加減算項の各項に該信号を乗算して部分積を生成する部分積生成ステップと、
該部分積生成ステップで得られた該部分積を全て加減算する加減算回路を該定数乗算器として生成する回路生成ステップとを有することを特徴とする、定数乗算器自動生成方法。
【請求項4】 該定数分解ステップが、
該定数Iについて、2n-1 <I<2n を満たす自然数nを求める第1ステップと、
該第1ステップで得られた自然数nに基づき、I=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを求める第2ステップと、
該第2ステップで得られた自然数aとbとの大小関係を判定する第3ステップと、
該第3ステップでa<bと判定された場合には前記(式1)を選択し、該第1ステップにおける該定数Iとして自然数aを設定する第4ステップと、
該第3ステップでa>bと判定された場合には前記(式2)を選択し、該第1ステップにおける該定数Iとして自然数bを設定する第5ステップとを有し、
該第1ステップにおける該定数Iが2のべき乗になるまで、前記の第1〜第5ステップを繰り返し実行することを特徴とする、請求項3記載の定数乗算器自動生成方法。
【請求項5】 該回路生成ステップにおいて、該加減算回路として、前記加減算項のうちの減算項に該信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、該第1加算回路により加算された値を反転する反転回路と、該反転回路により反転された値と前記加減算項のうちの加算項に該信号を乗算して得られた部分積とを加算する第2加算回路とが生成されることを特徴とする、請求項3または請求項4に記載の定数乗算器自動生成方法。
【請求項6】 定数Iと任意の値である信号とを掛け合わせる定数乗算器を自動的に生成するための定数乗算器自動生成装置であって、
該定数Iを最少項数の2のべき乗の加減算項に分解する定数分解部と、
該定数分解部で得られた前記加減算項を格納するレジスタと、
該レジスタに格納された前記加減算項の各項に該信号を乗算して部分積を生成する部分積生成部と、
該部分積生成部で得られた該部分積を全て加減算する加減算回路を該定数乗算器として生成する回路生成部とをそなえたことを特徴とする、定数乗算器自動生成装置。
【請求項7】 該定数分解部が、
該定数Iについて、2n-1 <I<2n を満たす自然数nを算出する第1演算部と、
該第1演算部にて算出された自然数nに基づき、I=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを算出する第2演算部と、
該第2演算部にて算出された自然数aとbとの大小関係を判定する判定部と、
該判定部でa<bと判定された場合には前記(式1)を選択し、2n-1 を該レジスタに設定するとともに、前項の加減算情報に応じた今回の項2n-1 の加減算情報を該レジスタに設定し、該第1演算部における該定数Iとして自然数aを設定する第1加減算項設定部と、
該判定部でa>bと判定された場合には前記(式2)を選択し、2n を該レジスタに設定するとともに、前項の加減算情報に応じた今回の項2n の加減算情報を該レジスタに設定し、該第1演算部における該定数Iとして自然数bを設定する第2加減算項設定部とから構成され、
該第1演算部における該定数Iが2のべき乗になるまで、前記の第1演算部,第2演算部,判定部,第1加減算項設定部および第2加減算項設定部による処理を繰り返し実行することを特徴とする、請求項6記載の定数乗算器自動生成装置。
【請求項8】 該回路生成部が、該加減算回路として、前記加減算項のうちの減算項に該信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、該第1加算回路により加算された値を反転する反転回路と、該反転回路により反転された値と前記加減算項のうちの加算項に該信号を乗算して得られた部分積とを加算する第2加算回路とを生成することを特徴とする、請求項6または請求項7に記載の定数乗算器自動生成装置。
【請求項9】 定数Iと任意の値である信号とを掛け合わせる定数乗算器をコンピュータにより自動的に生成するための定数乗算器自動生成プログラムを格納した記憶媒体であって、
該定数乗算器自動生成プログラムが、
該定数Iを最少項数の2のべき乗の加減算項に分解しその加減算項をレジスタに格納する定数分解手段、
該レジスタに格納された前記加減算項の各項に該信号を乗算して部分積を生成する部分積生成手段、および、
該部分積生成手段で得られた該部分積を全て加減算する加減算回路を該定数乗算器として生成する回路生成手段として、該コンピュータを機能させることを特徴とする、定数乗算器自動生成プログラムを格納した記憶媒体。
【請求項10】 該定数乗算器自動生成プログラムが、
該コンピュータを該定数分解部として機能させるべく、
該定数Iについて、2n-1 <I<2n を満たす自然数nを算出する第1演算手段、
該第1演算手段にて算出された自然数nに基づき、I=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを算出する第2演算手段、
該第2演算手段にて算出された自然数aとbとの大小関係を判定する判定手段、
該判定手段でa<bと判定された場合には前記(式1)を選択し、2n-1 を該レジスタに設定するとともに、前項の加減算情報に応じた今回の項2n-1 の加減算情報を該レジスタに設定し、該第1演算手段における該定数Iとして自然数aを設定する第1加減算項設定手段、および、
該判定手段でa>bと判定された場合には前記(式2)を選択し、2n を該レジスタに設定するとともに、前項の加減算情報に応じた今回の項2n の加減算情報を該レジスタに設定し、該第1演算手段における該定数Iとして自然数bを設定する第2加減算項設定手段として、該コンピュータを機能させ、
該第1演算手段における該定数Iが2のべき乗になるまで、前記の第1演算手段,第2演算手段,判定手段,第1加減算項設定手段および第2加減算項設定手段として、該コンピュータを繰り返し機能させることを特徴とする、請求項9記載の定数乗算器自動生成プログラムを格納した記憶媒体。
【請求項11】 該回路生成手段が、該加減算回路として、前記加減算項のうちの減算項に該信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、該第1加算回路により加算された値を反転する反転回路と、該反転回路により反転された値と前記加減算項のうちの加算項に該信号を乗算して得られた部分積とを加算する第2加算回路とを生成することを特徴とする、請求項9または請求項10に記載の定数乗算器自動生成プログラムを格納した記憶媒体。
利用分野
【0002】
【発明の属する技術分野】本発明は、定数と任意の値である信号とを掛け合わせる定数乗算器,その定数乗算器を自動的に生成するための方法および装置,並びにその定数乗算器を自動的に生成するためのプログラムを格納した記憶媒体に関する。
従来の技術
【0003】
【従来の技術】一般に、MPEG(Moving Picture Expert Group)等の機能を有する大規模集積回路では、画像処理等を行なうための演算回路として多数の乗算器を必要としている。これらの乗算器のうち大半のものは定数(既知の一定値)と未知の任意値をもつ信号との乗算を行なうものである。
【0004】例えば、離散コサイン・カラースペース変換で多用される。より具体的な例としては、下記のようなRGBコード/YUVコードの変換式において、UやVが未知の任意値をもつ信号であり、これらの信号U,Vに乗算されるパラメータ(係数)は定数である。
R=Y+1.367 ×V
G=Y−0.703125×U−0.34375 ×V
B=Y+1.7345×U
【0005】従来、上述のような定数と信号との乗算を行なう乗算器は、その定数に応じた専用のものとして設計されることはなく、その定数に関係なく、全ての乗算器が、未知の任意値どうしの乗算を行なう乗算器として設計されている。つまり、定数と信号との乗算も、信号と信号との乗算を行なう乗算器と同じアルゴリズムにより動作する乗算器によって実行されている。
課題
【0006】
【発明が解決しようとする課題】このように、従来、大規模集積回路を設計する際、掛け合わせる信号のうち一方の値が常に一定で予め分かっているものであっても、その信号(定数)を、未知の値をもつ信号として扱い、乗算器を成す回路の最適化を行なっていない。このため、無駄な回路部分が多く生じ、定数と信号との乗算を行なう乗算器を多く有する大規模集積回路(例えばMPEG用のLSI)上において、上述のような乗算器を作成すると、回路面積が増大するだけでなく、動作遅延も生じてしまう。
【0007】例えばシフトマルチプライヤ(Shift Multiplier)法を用いて設計される乗算器は、定数である乗数Bを信号として扱い、それぞれの桁(ビット)毎に被乗数Aとの積により部分積を生成し、これらの部分積を1ビットずつシフトして加算する手法を用いている。より具体的に説明すると、A=「1101」,B=「1011」の場合、下記のような演算が行なわれる。
【0008】
1101 被乗数(A:信号)
× 1011 乗 数(B:定数)
1101 部分積(A)
1101 部分積(2A)
0000 部分積(0)
+ 1101 部分積(8A)
10001111 乗算結果
上述の例では、部分積は0なので、実際に加算する必要はないが、信号どうしの乗算を行なう乗算器を用いた場合、部分積も加算するため、その分、不必要な回路(加算器)が生成されることになる。
【0009】次に、シフトマルチプライヤ法で部分積を生成して設計された乗算器の回路例について、図11や図12を参照しながら説明する。図11に示すように、乗数として例えば定数“59〔=(111011)2 ;6ビット〕”が与えられ、被乗数が信号Aであるとする。この場合、前述したシフトマルチプライヤ法を用いて部分積を生成すると、6個の部分積32A,16A,8A,0A,2A,Aが得られ、これらを加算して信号Aとの乗算結果“59A”を算出して出力する、部分積の加算回路、即ち乗算器100を生成する。
【0010】図11に示す乗算器100は、5個のCSA(Carry Save Adder;桁上げ保存加算器)101〜105を連結するとともに、CSA105の次段に、最終段として、桁上げ伝播加算器〔以下、CPA(Carry Propagate Adder 〕と略記する)の代表的な高速タイプである桁上げ先見加算器〔以下、CLA(Carry Look-ahead Adder)と略記する〕106を連結して構成されている。なお、最終段の加算器は、CPAに属するものであればよく、CLAのほか、桁上げ選択加算器(Carry Select Adder)や順次桁上げ伝播加算器(Ripple Carry Adder)などを用いることができる。
【0011】上述の構成により、部分積,,,,,が5個のCSA101〜105で規則正しく順次加算され、最終段のCLA106において、キャリーが高速に伝搬されて加算され、乗算結果“59A”が出力される。図11に示す乗算器100において、最終段を除く加算段数は“5”である。
【0012】しかし、部分積が“0”であるか否かの判断を行なわずに乗算器100が設計されているので、“0”の部分積を加算するためのCSA103がそなえられることになり、回路面積が増大し動作遅延が発生する要因となっている。
【0013】また、図12に示す乗算器200では、図11と同様のシフトマルチプライヤ法を用いて6個の部分積〜を生成し、これらの6つの部分積,,,,,を加算して、乗算結果“59A”を算出するものであるが、この乗算器200は、加算段数を削減するために木状に連結した4個のCSA201〜204と、CSA204の次段に最終段として連結されたCPA205とから構成されている。つまり、4個のCSA201〜204によって加算段数“3”の定数乗算器200が生成/設計される。この木状の加算器構成を“Wallace tree”という。なお、CPA205としては、CLAや桁上げ選択加算器(Carry SelectAdder)などを用いることができる。
【0014】上述のごとく生成/設計された乗算器200では、図11に示した乗算器100に比べて加算段数を少なくでき、使用されるCSAの数も削減されるので、回路面積の増大や動作遅延の発生は若干解消されているが、加算段数や使用加算器の数をより多く削減することが望まれている。
【0015】さらに、図13に示す乗算器300では、ブース・デコーダ(Booth decoder)301とブース・セレクタ(Booth selector)302とから成る部分積生成回路がそなえられている。この部分積生成回路を用いることにより、部分積数を2分の1に削減することができる。従って、前述したように定数“59”と信号Aとを乗算する場合、部分積は6個から3個に削減され、その3つの部分積〜が、加算回路(“Wallace tree”もしくはCSAによる)303と、最終段のCLA304とによって加算され、乗算結果“59A”が算出される。しかし、このような乗算器300では、ブース・デコーダ301およびブース・セレクタ302を作るために、余分なハードウェアが必要となり、回路面積の増大や動作遅延の発生を解消することができない。
【0016】本発明は、このような課題に鑑み創案されたもので、定数と信号との2値を掛け合わせるものであって、その定数に基づく部分積の数(加算段数)を削減し、回路面積および演算遅延時間を減少させた定数乗算器を提供するとともに、このような定数乗算器を自動的に生成/設計できるようにした、定数乗算器自動生成方法および装置並びに定数乗算器自動生成プログラムを格納した記憶媒体を提供することを目的とする。
手段
【0017】
【課題を解決するための手段】上記目的を達成するために、本発明の定数乗算器(請求項1)は、定数と任意の値である信号とを掛け合わせるものであって、その定数を分解して得られた最少項数の2のべき乗の加減算項の各項に、信号を乗算して得られた部分積を全て加減算する加減算回路から構成されている。
【0018】上述のごとく構成された本発明の定数乗算器では、乗数である定数を、項数が最も少ない2のべき乗の加減算項に分解し、その加減算項の各項に被乗数である信号を乗算して得られた全ての部分積を加減算回路にて加減算することにより、定数と信号との乗算結果が得られる。従って、定数乗算器における加算段数や使用加算器の数を最少にすることができる。
【0019】このとき、加減算回路を、前記加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、この第1加算回路により加算された値を反転する反転回路と、この反転回路により反転された値と前記加減算項のうちの加算項に信号を乗算して得られた部分積とを加算する第2加算回路とから構成してもよい(請求項2)。
【0020】これにより、まず、全ての減算項についての部分積の絶対値が第1加算回路により加算されてから、その加算結果を反転回路により反転した結果と加算項についての部分積とが第2加算回路により加算されて、定数と信号との乗算結果が得られる。つまり、定数の減算項を括弧で括り出した状態にして、その括弧内の部分積(絶対値)を第1加算回路により加算してから、反転回路および第2加算回路を用いて減算を行なうため、減算項毎に減算機能(反転回路)をそなえる必要がなくなる。
【0021】一方、本発明の定数乗算器自動生成方法(請求項3)は、定数Iと任意の値である信号とを掛け合わせる定数乗算器を自動的に生成するためのものであって、定数Iを最少項数の2のべき乗の加減算項に分解する定数分解ステップと、この定数分解ステップで得られた前記加減算項の各項に信号を乗算して部分積を生成する部分積生成ステップと、この部分積生成ステップで得られた部分積を全て加減算する加減算回路を定数乗算器として生成する回路生成ステップとを有している。
【0022】このとき、定数分解ステップが、定数Iについて、2n-1 <I<2n を満たす自然数nを求める第1ステップと、この第1ステップで得られた自然数nに基づきI=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを求める第2ステップと、この第2ステップで得られた自然数aとbとの大小関係を判定する第3ステップと、この第3ステップでa<bと判定された場合には前記(式1)を選択し第1ステップにおける定数Iとして自然数aを設定する第4ステップと、第3ステップでa>bと判定された場合には前記(式2)を選択し第1ステップにおける定数Iとして自然数bを設定する第5ステップとを有し、第1ステップにおける定数Iが2のべき乗になるまで、第1〜第5ステップを繰り返し実行する(請求項4)。
【0023】なお、回路生成ステップにおいて、加減算回路として、前記加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、この第1加算回路により加算された値を反転する反転回路と、この反転回路により反転された値と前記加減算項のうちの加算項に信号を乗算して得られた部分積とを加算する第2加算回路とを生成してもよい(請求項5)。
【0024】また、本発明の定数乗算器自動生成装置(請求項6)は、定数Iと任意の値である信号とを掛け合わせる定数乗算器を自動的に生成するためのものであって、定数Iを最少項数の2のべき乗の加減算項に分解する定数分解部と、この定数分解部で得られた前記加減算項を格納するレジスタと、このレジスタに格納された前記加減算項の各項に信号を乗算して部分積を生成する部分積生成部と、この部分積生成部で得られた部分積を全て加減算する加減算回路を定数乗算器として生成する回路生成部とをそなえたことを特徴としている。
【0025】このとき、定数分解部が、定数Iについて、2n-1 <I<2n を満たす自然数nを算出する第1演算部と、この第1演算部にて算出された自然数nに基づきI=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを算出する第2演算部と、この第2演算部にて算出された自然数aとbとの大小関係を判定する判定部と、この判定部でa<bと判定された場合には前記(式1)を選択し2n-1 をレジスタに設定するとともに前項の加減算情報に応じた今回の項2n-1 の加減算情報をレジスタに設定し第1演算部における定数Iとして自然数aを設定する第1加減算項設定部と、判定部でa>bと判定された場合には前記(式2)を選択し2n をレジスタに設定するとともに前項の加減算情報に応じた今回の項2n の加減算情報をレジスタに設定し第1演算部における定数Iとして自然数bを設定する第2加減算項設定部とから構成され、第1演算部における定数Iが2のべき乗になるまで、第1演算部,第2演算部,判定部,第1加減算項設定部および第2加減算項設定部による処理を繰り返し実行する(請求項7)。
【0026】なお、回路生成部が、加減算回路として、前記加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、この第1加算回路により加算された値を反転する反転回路と、この反転回路により反転された値と前記加減算項のうちの加算項に信号を乗算して得られた部分積とを加算する第2加算回路とを生成してもよい(請求項8)。
【0027】さらに、本発明の定数乗算器自動生成プログラムを格納した記憶媒体(請求項9)は、定数Iと任意の値である信号とを掛け合わせる定数乗算器をコンピュータにより自動的に生成するためのものであって、その定数乗算器自動生成プログラムが、定数Iを最少項数の2のべき乗の加減算項に分解しその加減算項をレジスタに格納する定数分解手段、レジスタに格納された前記加減算項の各項に信号を乗算して部分積を生成する部分積生成手段、および、この部分積生成手段で得られた部分積を全て加減算する加減算回路を定数乗算器として生成する回路生成手段として、コンピュータを機能させることを特徴としている。
【0028】このとき、定数乗算器自動生成プログラムが、コンピュータを定数分解部として機能させるべく、定数Iについて、2n-1 <I<2n を満たす自然数nを算出する第1演算手段、この第1演算手段にて算出された自然数nに基づきI=2n-1 +a(式1)およびI=2n −b(式2)を満たす自然数a,bを算出する第2演算手段、この第2演算手段にて算出された自然数aとbとの大小関係を判定する判定手段、この判定手段でa<bと判定された場合には前記(式1)を選択し、2n-1 をレジスタに設定するとともに前項の加減算情報に応じた今回の項2n-1 の加減算情報をレジスタに設定し第1演算手段における定数Iとして自然数aを設定する第1加減算項設定手段、および、判定手段でa>bと判定された場合には前記(式2)を選択し2n をレジスタに設定するとともに前項の加減算情報に応じた今回の項2n の加減算情報をレジスタに設定し第1演算手段における定数Iとして自然数bを設定する第2加減算項設定手段として、コンピュータを機能させ、第1演算手段における定数Iが2のべき乗になるまで、第1演算手段,第2演算手段,判定手段,第1加減算項設定手段および第2加減算項設定手段として、コンピュータを繰り返し機能させ(請求項10)。
【0029】なお、回路生成手段が、加減算回路として、前記加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路と、この第1加算回路により加算された値を反転する反転回路と、この反転回路により反転された値と前記加減算項のうちの加算項に信号を乗算して得られた部分積とを加算する第2加算回路とを生成してもよい。
【0030】上述のごとく構成された本発明の定数乗算器自動生成方法(請求項3〜5),定数乗算器自動生成装置(請求項6〜8)および定数乗算器自動生成プログラムを格納した記憶媒体(請求項9〜11)では、定数を分解した最少項数の2のべき乗の加減算項の各項に信号を乗算して得られた部分積を全て加減算する加減算回路により定数と信号とを掛け合わせる定数乗算器を、自動的に生成することができる。
効果
【0110】
【発明の効果】以上詳述したように、本発明の定数乗算器(請求項1)によれば、乗数である定数を、項数が最も少ない2のべき乗の加減算項に分解し、その加減算項の各項に被乗数である信号を乗算して得られた全ての部分積を加減算回路にて加減算することにより、定数と信号との乗算結果が得られるので、定数乗算器における加算段数や使用加算器の数を最少にすることができる。
【0111】従って、定数乗算器の小型化かつ処理の高速化を実現でき、多数の定数乗算器を有する大規模集積回路を設計する際に、各定数乗算器として定数に応じた最少構成のものを用いることができるので、大規模集積回路上における乗算器の専有面積を大幅に削減できるほか、大規模集積回路における動作遅延を抑制でき処理速度を高速化できる効果もある。
【0112】このとき、定数の減算項を括弧で括り出した状態にして、その括弧内の部分積(絶対値)を第1加算回路により加算してから、反転回路および第2加算回路を用いて減算を行なうため、減算項毎に減算機能をそなえる必要がなくなり、さらなる小型化・高速化を実現することができる。
【0113】一方、本発明の定数乗算器自動生成方法(請求項3〜5),定数乗算器自動生成装置(請求項6〜8)および定数乗算器自動生成プログラムを格納した記憶媒体(請求項9〜11)によれば、定数を分解した最少項数の2のべき乗の加減算項の各項に信号を乗算して得られた部分積を全て加減算する加減算回路により定数と信号とを掛け合わせる定数乗算器が自動的に生成/設計されるので、多数の定数乗算器を有する大規模集積回路を設計する際に、各定数乗算器として定数に応じた最少構成のものを自動的に生成でき、大規模集積回路上における乗算器の専有面積削減や大規模集積回路における処理速度の高速化に大きく寄与する。
実施例
【0031】
【発明の実施の形態】以下、図面を参照して本発明の実施の形態を説明する。図1は本発明の一実施形態としての定数乗算器の構成を示す図である。本実施形態の定数乗算器は、定数Iと任意の値である信号Aとを掛け合わせるものである。そして、本発明では、乗数である定数Iを項数が最も少ない2のべき乗の加減算項に分解し、その分解結果に応じて定数乗算器を生成/設計している。
【0032】例えば定数Iを“59”した場合、その定数Iは、次式(1),(2)のような、2のべき乗の項に分解される。
59=32+16+8+2+1=25 +24 +23 +21 +20 (1)
59=64−4−1=26 −22 −20 (2)
(1)式の項数は5、(2)式の項数は3であり、(2)式の方が少なく、後述するように、定数59を2のべき乗の加減算項に分解した場合、項数3が最少項数である。
【0033】従って、定数59と信号Aとを乗算する本実施形態の定数乗算器10は、図1に示すように、(2)式のごとく分解して得られた加減算項の各項26 ,−22,−20 に信号Aを乗算して得られる部分積A×26 ,−A×22 ,−A×20を全て加減算する加減算回路から構成されている。つまり、本実施形態の定数乗算器10は、2つの多入力加算器(CSA:Carry Save Adder)1,2と2つのインバータ(反転回路)3,4とから構成されている。なお、多入力加算器は、以下、単に加算器という場合がある。
【0034】ここで、加算器1は、入力端子から入力されるA×26 と、入力端子から入力されるA×22 をインバータ3により反転したもの(A×22 の補数)と、図示省略のキャリーイン回路からのキャリーインCin“1”とを加算して、“A×26 −A×22 ”を算出して出力するものである。
【0035】また、加算器2は、加算器1による算出結果“A×26 −A×22 ”と、入力端子から入力されるA×20 をインバータ4により反転したもの(A×20 の補数)と、図示省略のキャリーイン回路からのキャリーインCin“1”とを加算して、“A×26 −A×22 −A×20 =A×59”を算出して出力するものである。
【0036】上述のごとく構成された本実施形態の定数乗算器10では、乗数である定数I=59を、項数が最も少ない2のべき乗の加減算項“26 −22 −20 ”に分解し、その加減算項の各項に被乗数である信号Aを乗算して得られた全ての部分積を加算器1,2および反転回路3,4にて加減算することにより、定数59と信号Aとの乗算結果が得られる。
【0037】従って、定数乗算器10における加算段数や使用加算器の数を最少にすることができる。定数が59である場合、図11に示す例では、部分積の数が6、加算段数が5、使用加算器の数が5になり、図12に示す例では、部分積の数が5、加算段数が3、使用加算器の数が4になるのに対し、図1に示す本実施形態の定数乗算器10では、部分積の数が3、加算段数が2、使用加算器の数が2となり、その加算段数や使用加算器の数を大幅に少なくすることができる。
【0038】これにより、定数乗算器10の小型化かつ処理の高速化を実現できる。なお、図13に示すような2次ブース法を用いた場合、部分積の数を3として乗算器を構成することができる。しかし、この2次ブース法では、部分積数を最高で2分の1までしか減らすことはできない。しかも、2次ブース法に基づいて構成される乗算器300では、部分積生成のためにデコーダ301やセレクタ302を必要とするため、余分なハードウェアが必要で、段数を減らすのに比例して動作遅延は減少するが、本実施形態の定数乗算器10よりもどうしても大きな面積を専有することになる。
【0039】多数の定数乗算器を有する大規模集積回路を設計する際に、各定数乗算器を、図1に示した定数乗算器10のごとく、乗算すべき定数Iに応じた最少構成のものとすることにより、大規模集積回路上における乗算器の専有面積を大幅に削減できるほか、大規模集積回路における動作遅延を抑制でき処理速度を高速化することができる。
【0040】ところで、前記(2)式は、下式(3)のごとく書き換えることができる。
59=64−(4+1)=26 −(22 +20 ) (3)
この(3)式に基づいて、図2に示すように、定数59と信号Aとを乗算する定数乗算器10′を構成することもできる。
【0041】図2は本発明の一実施形態としての定数乗算器の変形例の構成を示す図であり、この図2に示すように、定数乗算器10′は、加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値A×22 ,A×20 を全て加算する多入力加算器(CSA,第1加算回路)5と、この加算器5により加算された値を反転するインバータ(反転回路)6と、このインバータ6により反転された値と加減算項のうちの加算項に信号を乗算して得られた部分積A×26 とを加算する多入力加算器(CSA,第2加算回路)7とから構成されている。
【0042】つまり、加算器5は、入力端子からのA×22 と入力端子からのA×20とを加算して出力するものであり、加算器7は、入力端子からのA×26 と、加算器5による算出結果“A×22 +A×20 ”をインバータ6により反転したもの(A×22 +A×20 の補数)と、図示省略のキャリーイン回路からのキャリーインCin“1”とを加算して、“A×26 −(A×22 +A×20 )=A×59”を算出して出力するものである。
【0043】これにより、定数乗算器10′の回路構成は、図1に示した定数乗算器10よりもインバータを一つ少なくすることができ、また、キャリーイン回路となる“1”クリップ素子も省略できるので、定数乗算器10′は、定数乗算器10よりも小型化なものになる。
【0044】即ち、前記(3)式のごとく、定数Iの減算項を括弧で括り出した状態にして、その括弧内の部分積(絶対値)を加算器5により加算してから、インバータ6および加算器7を用いて減算を行なうため、減算項毎に減算機能(インバータやキャリーイン回路となる“1”クリップ素子」)をそなえる必要がなくなり、さらなる小型化・高速化を実現することができる。
【0045】次に、図3〜図10を参照しながら、図1や図2に示すような定数乗算器10,10′を自動的に生成するための装置について説明する。図3は本発明の一実施形態としての定数乗算器自動生成装置の構成を示すブロック図であり、この図3に示すように、本実施形態の定数乗算器自動生成装置20は、定数Iと任意の値である信号とを掛け合わせる定数乗算器を自動的に生成するためのものであって、実際には、キーボード,マウス,ディスプレイ,CPU,ROM,RAM等から構成されるコンピュータにおいて、ハードディスク,磁気テープ,フロッピディスク,光ディスク,光磁気ディスク,CD−ROM等の記憶媒体に格納された定数乗算器自動生成プログラムを読み出し、そのプログラムを実行することにより実現される。この定数乗算器自動生成プログラムは、コンピュータを、図3において符号21,23〜25を付して示す各構成要素として機能させるものである。
【0046】そして、本実施形態の定数乗算器自動生成装置20は、定数分解部21,演算結果レジスタ22,部分積生成部23,第1回路生成部24,第2回路生成部25,ポインタ26おより定数保持レジスタ27から構成されており、図4に示すフローチャート(後述)に従って動作するものである。
【0047】定数分解部(定数分解手段)21は、図5に示すフローチャート(後述)に従い、演算結果レジスタ22の書込位置を指示するポインタ26と定数Iを保持する定数保持レジスタ27とを参照しながら、定数Iを最少項数の2のべき乗の加減算項に分解し、その分解結果(加減算項)を演算結果レジスタ22に設定するするもので、第1演算部31,第2演算部32,判定部33,第1加減算項設定部34および第2加減算項設定部35から構成されている。
【0048】第1演算部(第1演算手段)31は、定数保持レジスタ27に保持される定数Iについて、2n-1 <I<2n を満たす自然数nを算出するものである。第2演算部(第2演算手段)32は、第1演算部31にて算出された自然数nに基づき、下記の(4)式および(5)式を満たす自然数a,bを算出するものである。なお、a+b=2n-1 である。
I=2n-1 +a (4)
I=2n −b (5)
判定部(判定手段)33は、第2演算部32にて算出された自然数aとbとの大小関係を判定するものである。
【0049】第1加減算項設定部(第1加減算項設定手段)34は、判定部33でa<bであると判定された場合に、上記(4)式を選択し、ポインタ26の指示する演算結果レジスタ22の所定位置に2n-1 を設定するとともに前項の加減算情報(+/−;正負情報)に応じた今回の項2n-1 の加減算情報(+/−;正負情報)を演算結果レジスタ22の所定位置に設定してから、第1演算部31における定数Iとして自然数aを設定、つまり、定数保持レジスタ27に定数Iとして自然数aを設定するものである。
【0050】第2加減算項設定部(第2加減算項設定手段)35は、判定部33でa>bであると判定された場合に、上記(5)式を選択し、ポインタ26の指示する演算結果レジスタ22の所定位置に2n を設定するとともに前項の加減算情報(+/−;正負情報)に応じた今回の項2n の加減算情報(+/−;正負情報)を演算結果レジスタ22の所定位置に設定してから、第1演算部31における定数Iとして自然数bを設定、つまり、定数保持レジスタ27に定数Iとして自然数bを設定するものである。
【0051】そして、定数分解部21は、図5に示すフローチャートにて後述するごとく、第1演算部31における定数I(つまり定数保持レジスタ27に保持される定数I)が2のべき乗になるまで、第1演算部31,第2演算部32,判定部33,第1加減算項設定部34および第2加減算項設定部35による処理を繰り返し実行する。
【0052】なお、演算結果レジスタ22は、ポインタ26によりk=0,1,2,…として指示される複数の区分S[k]で構成されている。そして、ポインタ26は、前述したように、定数分解部21における第1加減算項設定部34および第2加減算項設定部35に対し、演算結果を記入すべき演算結果レジスタ22の位置(区分)を指示するものである。これにより、図7にて後述するごとく、演算結果レジスタ22の各区分S[k]には、定数分解部21により算出された加減算項(絶対値)およびその加減算情報(+/−;正負情報)が保持されるようになっている。
【0053】一方、部分積生成部(部分積生成手段)23は、演算結果レジスタ22に格納された加減算項の各項に信号を乗算して部分積を生成するものである。第1回路生成部24(回路生成部,回路生成手段)は、部分積生成部23で得られた部分積を全て加減算する加減算回路(部分積加算回路)を生成するものである。
【0054】この第1回路生成部24は、加減算項内に複数の減算項が存在する場合、加減算回路(部分積加算回路)として、加減算項のうちの減算項に信号を乗算して得られた部分積の絶対値を全て加算する第1加算回路(図2の加算器5参照)と、この第1加算回路により加算された値を反転する反転回路(図2のインバータ6参照)と、この反転回路により反転された値と前記加減算項のうちの加算項に信号を乗算して得られた部分積とを加算する第2加算回路(図2の加算器7参照)とを生成するように構成されている。
【0055】第2回路生成部(回路生成部,回路生成手段)25は、CLA(Carry Look-ahead Adder)等の最終段回路を生成し、その最終段回路と第1回路生成部24により生成された加減算回路(部分積加算回路)とを連結し、最終的な定数乗算器を生成・出力するものである。
【0056】次に、図3に示すごとく構成された本実施形態の定数乗算器自動生成装置20の動作(定数乗算器自動生成手順)について、図4に示すフローチャート(ステップS1〜S4)に従って説明する。まず、乗数である定数Iを入力されると、定数分解部21では、図5に示すフローチャート(後述)に従って、その定数Iが最少項数の2のべき乗の加減算項に分解され、その分解結果が演算結果レジスタ22に格納される(定数分解ステップS1)。
【0057】そして、部分積生成部23では、演算結果レジスタ22を参照し、定数分解ステップS1で得られた加減算項の各項に信号Aを乗算して部分積が生成される(部分積生成ステップS2)。この後、第1回路生成部24において、部分積生成ステップS2で得られた部分積を全て加減算する加減算回路(部分積加算回路)が生成され(回路生成ステップS3)、第2回路生成部25において、CLA等の最終段回路が生成され、その最終段回路と回路生成部24により生成された加減算回路(部分積加算回路)とが連結され、最終的な定数乗算器が生成・出力される(回路生成ステップS4)。
【0058】なお、回路生成ステップS3では、部分積生成部23からの部分積を単純に加算するようにして加減算回路を生成してもよいし、前述した“Wallace tree”やCSAなどを用い部分積の加算段数を減らすようにして加減算回路を生成してもよい。このとき、本実施形態では、前述したように、加減算項内に複数の減算項が存在する場合、加減算回路を、定数Iの減算項を括弧で括り出した状態にして生成する。
【0059】さて、次に、本実施形態の定数分解部21による定数分解手順について、図5に示すフローチャート(ステップS11〜S29)に従って説明する。まず、乗算すべき定数Iを、定数保持レジスタ27に記入し、ポインタ13の指示する区分kとして1を記入し、S[0]つまり演算結果レジスタ22の区分k=0に、定数Iの符号情報(加減算情報)である“+”を記入する(ステップS11)。
【0060】ついで、第1演算部31において、nとして0を設定し(ステップS12)、2n を演算し、その2n (n=0)が、定数保持レジスタ27に記入済みの定数Iよりも大きいか否かを判定する(ステップS13)。2n <Iである場合(ステップS13からYESルート)には、nに1を加算して(ステップS14)、21 ,22 ,23 ,…を順次演算し、その値をステップS13で定数Iと比較する。2n ≦Iとなった場合(ステップS13からNOルート)には、次のステップS15へ進む。
【0061】ステップS15では、定数Iが2n に等しいか否かを判定し、等しい場合(YESルート)には、S[k]に2n を記入してから、Sつまり演算結果レジスタ22に記入された演算結果(分解結果)をディスプレイ上に表示して(ステップS16)、処理を終了する。なお、本実施形態では、ステップS12〜S15が、定数Iについて、2n-1<I<2n を満たす自然数nを求める第1ステップ(第1演算部31)としての機能を果たしている。
【0062】一方、ステップS15で定数Iが2n に等しくないと判定された場合(NOルート)には、第2演算部32において、前記の(4)式および(5)式を満たす自然数a,bを算出する(ステップS17,第2ステップ)。つまり、自然数aとしては“I−2n-1 が、自然数bとしては“2n −I”が算出される。そして、判定部33において、自然数a,bの大小関係が判定される(ステップS18,第3ステップ)。
【0063】ステップS18でa<bと判定された場合(NOルート)には、2n-1 を、S[k]つまり演算結果レジスタ22の区分kに記入するとともに、ポインタ26の値kに1を加算してから(ステップS19)、演算結果レジスタ22の区分k−2(S[k−2])における符号が“−”か否かを判定する(ステップS20)。
【0064】“−”である場合(YESルート)には、演算結果レジスタ22の区分k(S[k])に符号“−”を記入する一方(ステップS21)、“+”である場合(NOルート)には、演算結果レジスタ22の区分k(S[k])に符号“+”を記入し(ステップS22)、定数保持レジスタ27に自然数aを記入してから(ステップS23)、ポインタ26の値kに1を加算してから(ステップS29)、ステップS2へ戻る。
【0065】なお、本実施形態では、ステップS19〜S23が、a<bと判定された場合に前記(4)式を選択し定数Iとして自然数aを設定する第4ステップ(第1加減算項設定部34)としての機能を果たしている。
【0066】これに対し、ステップS18でa>bと判定された場合(YESルート)には、2n を、演算結果レジスタ22の区分k(S[k])に記入するとともに、ポインタ26の値kに1を加算してから(ステップS24)、演算結果レジスタ22の区分k−2(S[k−2])における符号が“+”か否かを判定する(ステップS25)。
【0067】“+”である場合(YESルート)には、演算結果レジスタ22の区分k(S[k])に符号“−”を記入する一方(ステップS26)、“−”である場合(NOルート)には、演算結果レジスタ22の区分k(S[k])に符号“+”を記入し(ステップS27)、定数保持レジスタ27に自然数bを記入してから(ステップS28)、ポインタ26の値kに1を加算してから(ステップS29)、ステップS2へ戻る。
【0068】なお、本実施形態では、ステップS24〜S28が、a>bと判定された場合に前記(5)式を選択し定数Iとして自然数bを設定する第5ステップ(第2加減算項設定部35)としての機能を果たしている。また、本実施形態では、ステップS18でa=bと判定される場合についての説明が省略されているが、a=bの場合には、ステップS19とステップS25とのうちのいずれに進んでもよいが、出来る限り、符号が“+”になるように(つまり分解された項が加算項となるように)、ステップS19とステップS25とのいずれか一方に進むことが望ましい。何故ならば、その項が減算項になると、インバータやキャリーイン回路を必要とすることになるからである。
【0069】次に、より具体的に、定数Iが例えば59〔=(111011)2 〕である場合における、本実施形態の定数乗算器自動生成装置20の動作について、図5〜図7を参照しながら説明する。まず、図5および図6を参照しながら、定数59を、最少項数の2のべき乗の加減算項に分解する手順について説明する。なお、図6においては、符号情報もしくは項情報が記入される図5のステップ番号が各区分に付されている。
【0070】ステップS11で、定数Iとして59を定数保持レジスタ27に記入し、ポインタ26の指示としてk=1を記入し、図6に示すように、演算結果レジスタ22の区分k=0(S[0])に符号情報“+”を記入する。そして、ステップS12でn=0とし、ステップS13で、2n を演算し、2n (n=0)が、定数保持レジスタ27に記入済みの定数I=59よりも大きいか比較し、小さい時は、ステップS14でnに1を加算して、2n と定数I=59との比較を行なう。この処理は、n=6つまり26 =64となって、26 <59が不成立(ステップS13でNO判定)となるまで、繰り返し行なわれる。
【0071】ステップS13において、26 により、26 <I(=59)が不成立となった時、ステップS15で26 が定数I=59と等しいか否かを判別するが、今、I=59のため、当然、26 ≠59となり、ステップS17で、自然数a(=I−2n-1 )と自然数b(=2n −I)とが算出される。ここでは、I=59,n=6であるので、a=27,b=5が算出される。
【0072】この後、ステップS18で、a>bであるか否かを判定するが、a=27,b=5であるので、YES判定となり、ステップS24へ進む。つまり、ステップS24では、図6に示すように、2n つまり26 が、演算結果レジスタ22の区分k=1(S[1])に記入され、ポインタ26の指示値k=1に1を加算してk=2とする。
【0073】ついで、ステップS25で演算結果レジスタ22のk−2の区分つまりS[0]が“+”か否かをチェックする。今、区分0には“+”が記入されているので、ステップS26で、図6に示すように、“−”が、演算結果レジスタ22の区分k=2(S[2])に記入される。この後、b=5を、定数Iとして定数保持レジスタ27に記入し、ポインタ26の指示値k=2にさらに1を加算してk=3としてから、ステップS12に戻る。
【0074】このとき、定数保持レジスタ27には、ステップS28で定数I=5が記入されている。従って、ステップS13で、n=3のとき、2n <I(23 <5)が不成立となり、且つ、23 ≠5であるので、ステップS17において、a=1←5−22 とb=3←23 −5とが演算される。a=1,b=3でありa>bが不成立であるので、ステップS18からステップS19へ進む。
【0075】ステップS19では、図6に示すように、2n-1 つまり22 が、演算結果レジスタ22の区分k=3(S[3])に記入され、ポインタ26の指示値k=3に1を加算してk=4とする。
【0076】ついで、ステップS20で演算結果レジスタ22のk−2の区分つまりS[2]が“−”か否かをチェックする。今、区分2には“−”が記入されているので、ステップS21で、図6に示すように、“−”が、演算結果レジスタ22の区分k=4(S[4])に記入される。この後、a=1を、定数Iとして定数保持レジスタ27に記入し、ポインタ26の指示値k=4にさらに1を加算してk=5としてから、ステップS12に戻る。
【0077】このときには、定数保持レジスタ27に保持されるIが1となっているため、ステップS13で、n=0のとき、2n <I(20 <1)が不成立となり、ステップS15へ進み、このステップS15で、I=2n (20 =1)と判定されるので、ステップS12へ進み、図6に示すように、2n つまり20 が、演算結果レジスタ22の区分k=5(S[5])に記入される。
【0078】以上のようにして、定数I=59が、項数が最も少ない2のべき乗の加減算項で表現されることになり、定数分解部21での分解処理を終了する。そして、定数分解部21は、図示省略のディスプレイ(表示装置)に、図6に示した演算結果レジスタ22の内容を表示し、オペレータに通知する。このようにして、定数を最適化して項数が最も少ない2のべき乗の加減算項に分解することができる。さらに、分解された加減算項の減算項を減らすように、減算項を括弧で括り出し、加算項に変える処理を施す。このようにして分解した値に対応した信号との部分積により回路を生成/設計する。
【0079】上述のごとく、ディスプレイに演算結果レジスタ22の内容を表示することにより、オペレータは、59=64−4−1を認識し、これに基づいて、図1に示すような定数乗算器10を設計することができる。また、減算項を括弧で括り出した式59=64−(4+1)を表示することにより、オペレータは、図2に示すような定数乗算器10′を設計することができる。
【0080】ただし、本実施形態においては、定数分解部21により定数I(=59)の分解を行なった後、その分解結果から図2(もしくは図1)に示す定数乗算器10′(もしくは10)を生成する処理は、部分積生成部23,第1回路生成部24および第2回路生成部25により自動的に行なわれる。つまり、部分積生成部23において、演算結果レジスタ22を参照し、定数分解部21で得られた加減算項の各項に信号Aを乗算して3つの部分積64A,−4A,−Aが生成される。
【0081】この後、第1回路生成部24において、部分積生成部23で得られた部分積を、64A−(4A+A)として全て加減算する加減算回路(部分積加算回路)が生成され、第2回路生成部25において、CLA,桁上げ選択加算器(Carry Select Adder),順次桁上げ伝播加算器(Ripple Carry Adder)等のCPAが最終段回路として生成され、その最終段回路と回路生成部24により生成された加減算回路(部分積加算回路)とが連結されて、最終的な定数乗算器10′(図2参照)が生成・出力される。
【0082】なお、図1や図2では、定数乗算器10,10′のうちの部分積加算回路の部分のみが図示されているが、実際には、加算器2,7の後段には、最終段回路として、CLA,桁上げ選択加算器(Carry Select Adder),順次桁上げ伝播加算器(Ripple Carry Adder)等のCPAが連結されている。
【0083】図7(A)〜(C)を参照しながら、本実施形態により得られた定数乗算器(定数I=59として得られた定数乗算器10′)を具体的に実現した回路例について説明する。定数I=59のとき、前述した図5に示すアルゴリズムを適用すると、32<59<64であるから、定数59は、32+27=25 +aと、64−5=26 −bとの2通りに分解することができる。
【0084】そして、27>5であるから、分解方式として59=64−5=26 −bを採用し、定数Iとして5を設定する。同様に、4<5<8であるから、定数5は、4+1=22 +aと、8−3=23 −bとの2通りに分解することができる。そして、1<3であるから、分解方式として5=4+1=22 +aを採用する。このとき、a=1=20 であるので、この時点で分解処理を終了し、演算結果レジスタ22に格納された分解結果Sを表示するとともに、部分積生成部23による処理へ移行する。
【0085】この結果、S=64−4−1となる。これは、59を項数が最も少ない2のべき乗の加減算項で表現した形式である。さらに、減算項を減らすように括弧で減算項を括り出すと、S=64−(4+1)となる。一般に、減算を実現する回路は、加算器に比較して、インバータ(反転回路)とキャリーインCinを“1”クリップする素子が必要になるため、回路規模や動作遅延が増大してしまう。そこで、本実施形態では、減算項を括弧で括り減算項を減らすことにより、出来るだけ減算処理を加算処理に変換し、素子数および動作遅延を減少させている。
【0086】これにより、図7(A)に示すように、信号Aが6ビットの“aaaaaa”である場合、この信号Aと定数59=(111011)2 との乗算値は、3段の部分積を加算することにより算出することが可能になり、さらに、図7(B)に示すように、減算処理を加算処理に変換することにより、図7(C)に示すように、64A−(4A+A)を算出する加減算回路としての定数乗算器10′(図2と同一)を自動的に生成することができる。
【0087】定数59を、2進数で表現すると、前記の通り、(111011)2 の6ビットで表現することができる。また、被乗数の信号Aを6ビット“aaaaaa”とすると、従来方式では、信号(幅6ビット)×信号(幅6ビット)として、乗算器を構成している。即ち、定数59と信号Aとの乗算を、図14(A)に示すごとく行なうため、部分積の段数が6段になる。
【0088】この乗算を図14(B)に示すように〜の部分積で表現し、これにより、図14(C)に示すように、6個の部分積を加算する5個の加算器51〜55により乗算器が構成され、図14(D)に示すような数式の演算が行なわれる。このように、従来方式では、部分積の数が6であり、加算段数が5で使用加算器の数も5となる。
【0089】これに対して、本実施形態では、定数59を信号に乗算する定数乗算器10′を、図2や図7(C)に示すように、部分積の数が3、加算段数が2、使用加算器の数が2となり、その加算段数や使用加算器の数を大幅に少なくすることができる。
【0090】従って、本実施形態の定数乗算器自動生成装置20を用いることにより、小型化かつ処理を高速化した定数乗算器10′を自動的に生成することができる。このため、多数の定数乗算器を有する大規模集積回路を設計する際に、各定数乗算器を、図2や図7(C)に示した定数乗算器10′のごとく、乗算すべき定数Iに応じた最少構成のものとして自動的に生成することができ、前述した通り、大規模集積回路上における乗算器の専有面積を大幅に削減できるほか、大規模集積回路における動作遅延を抑制でき処理速度を高速化することができる。
【0091】さらに、図8(A)〜図8(C)および図9を参照しながら、本実施形態により得られた定数乗算器(定数I=59)を具体的に実現した他の回路例について説明する。ここでは、図8(A)に示すように、部分積64A,−4A,−Aを2の補数として表現して加算するようにして生成される定数乗算器(図9参照)について説明する。
【0092】定数分解処理により得られた部分積が全て正の値であれば、通常、単純に全ての部分積をそのまま足し合わせることにより積を求めることができる。これに対して、負の部分積がある場合には、その値を反転してLSB(最下位ビット)に“1”を加算し2の補数として表現する。
【0093】つまり、図8(A)に示すごとく、絶対値が小さい順に部分積を足し合わせ〔(−A)+(−4A)+64A〕、負数である−A,−4Aについては反転して符号ビットsを拡張するとともに、64Aについては1ビットだけ符号ビットsを拡張し、反転した部分積のLSBに“1”を加算するビットを追加する。なお、図8(A)〜図8(C)および図9において、信号Aの各ビット(6ビット)の値“a”や符号ビット“s”を反転した値には“a”や“s”の上部にそれぞれバーを付して表示している。
【0094】しかし、このような符号拡張はハードウェアの増加を招くため、符号拡張を不要にする、公知の技術である符号不拡張補正演算手法を適用し、図8(B)に示すごとく、符号ビット“s”に対応する位置(7ビット分)で“1”を加算するとともに、符号のLSBにも“1”を加算する。これらの加算により、全体としては“0”を加算しているだけで、問題は生じない。
【0095】図8(B)に示す処理により、符号ビットの大部分が削除され、最終的な部分積の総和(−A)+(−4A)+64A=59Aは、図8(C)に示すような式で表現される。この図8(C)に示すごとく表現された式に基づいて、例えば図9に示すような定数乗算器を生成することができる。この図9において、符号11は半加算器(HA;Half Adder)、符号12は全加算器(FA;Full Adder)、符号13は最終段回路(CLA等)である。
【0096】なお、以下に、図5のステップS18でa>bと判定された場合に、何故、前記の(4)式と(5)式とのうち(5)式の表現形式を採用して、定数Iを分解するかについて説明する。何故ならば、定数Iを前記の(4)式および(5)式の2通りで表現する場合、a>bの場合、(5)式の表現形式に分離した方が、表現コストが小さくなるからである。次に(5)式の方が表現コストが小さくなる理由について説明する。
【0097】ここでいう表現コストとは、ある数を2進数で表現した場合に、その2進数に含まれる“1”の数に比例したオーダとする。例えば、3は21 +20 =(11)2 となるので、“1”の数は2となり、8は23 =(100)2 となるので、“1”の数は1となる。
【0098】前記の(4)式および(5)式を用いて定数Iを消去すると、次式(6)が成立する。
a+b=2n-1 (6)
次に、m=n−1とすると(6)式はa+b=2m となり、a>bとすると、次式(7)が成立する。
2m-1 <a<2m (7)
【0099】そこで、自然数aを表現する最も簡単な表現形式は、(4),(5)式から、それぞれ下式(8),(9)の2通りとなる。ただし、a′,a″は自然数である。
a=2m-1 +a′ (8)
a=2m −a″ (9)
【0100】上記の(8)式および(9)式から、自然数aの表現コストは、それぞれ、下式(10),(11)として表現される。
〔a′の表現コスト〕+〔2m-1 の表現コスト〕 (10)
〔a″の表現コスト〕+〔2m の表現コスト〕 (11)
故に、自然数aの表現コストは、a′,a″の表現コストよりも必ず1(2m-1 ,2m )だけ多くなる。
【0101】(8)式を選択する時、b=2m −a=2m −(2m-1 +a′)=(2m −2m-1 )−a′=2m-1 −a′であるので、自然数bの表現コストは下式(12)のように表現される。
〔bの表現コスト〕=〔2m-1 の表現コスト〕+〔a′の表現コスト〕
=1+〔a′の表現コスト〕
=〔aの表現コスト〕 (12)
【0102】一方、(9)式を選択する時、b=2m −a=2m −(2m −a″)=a″となる。自然数a′およびa″を表現するためのコストは、必ず自然数aを表現するコストよりも1少ないので、自然数bを表現するコストは、自然数aの表現コストと等しいかそれ以下になる。よって、〔aの表現コスト〕>〔bの表現コスト〕となり、a>bの時は、(5)式の表現形式を選ぶ。a<bの場合は、同様の理由により、(4)式の表現形式を選択する。なお、a=bの時は、aおよびbの表現コストは等しくなる。
【0103】以上のような理由から、a>bの条件を満たす時は、(5)式の分解方式を採用し、定数Iとして自然数bを設定し、それ以外の時は、(4)式の分解方式を採用し、定数Iとして自然数aを設定している。従って、定数Iが2n に等しくなるまで図5に示す処理を繰り返すことにより、定数Iを項数が最も少ない2のべき乗の加減算項に分解することができる。
【0104】なお、上述した実施形態では、定数Iが59である場合についてのみ説明したが、本発明は、これに限定されるものではなく、定数Iが他の値である場合にも上述した実施形態と同様に適用され、上述した実施形態と同様の作用効果を得ることができる。
【0105】また、図1および図2に示した本実施形態の定数乗算器10および10′を、2段のCSA1,2;5,7の次段に、CLA等のCPAを最終段回路として連結して構成しているが、ビット数が小さい場合には、2段の加算器ともCPAとして構成し最終段回路を省略することができるほか、1段目をCSA、2段目をCLAとして構成することもできる。
【0106】さらに、例えば、部分積生成部23により、加算項としてA,B,Cが得られるとともに、減算項として−D,−E,−F,−Gが得られた場合には、回路生成部24,25により、例えば図10に示すように、多入力加算器41,42,44とインバータ(反転回路)43とからなる定数乗算器40を生成することもできる。
【0107】ここで、多入力加算器41は、加算項A,B,Cの総和を算出するものであり、多入力加算器(第1加算回路)42は、減算項の絶対値D,E,F,Gの総和を算出するものであり、インバータ43は、多入力加算器42からの値を反転するものである。
【0108】そして、多入力加算器(第2加算回路)44は、多入力加算器41からの値と、インバータ43により反転された値と、図示省略のキャリーイン回路からのキャリーインCin“1”とを加算することにより、部分積の総和、即ち、定数と信号との乗算結果を算出して出力するものである。
【0109】またさらに、上述した実施形態では、図5に示す手順により定数Iを分解する場合について説明しているが、本発明は、これに限定されるものではなく、定数Iを分解する手法は、定数Iを最少項数の2のべき乗の加減算項に分解できるものであれば、他の種々の手法を用いてもよい。そして、本発明は上述した実施形態に限定されるものではなく、本発明とその趣旨を逸脱しない範囲で種々変形して実施することができる。
図の説明
【図1】本発明の一実施形態としての定数乗算器の構成を示す図である。
【図2】本発明の一実施形態としての定数乗算器の変形例の構成を示す図である。
【図3】本発明の一実施形態としての定数乗算器自動生成装置の構成を示すブロック図である。
【図4】本実施形態の動作(定数乗算器自動生成手順)を説明するためのフローチャートである。
【図5】本実施形態の定数分解手順を説明するためのフローチャートである。
【図6】本実施形態の演算結果レジスタに格納される情報の具体例を示す図である。
【図7】(A)〜(C)はいずれも本実施形態の動作を具体的な例に基づいて説明するための図である。
【図8】(A)〜(C)はいずれも本実施形態の動作を具体的な例に基づいて説明するための図である。
【図9】図8(A)〜図8(C)に示す動作に基づいて生成された本実施形態の定数乗算器の具体例を示す回路図である。
【図10】本実施形態により生成される定数乗算器の他例を示す図である。
【図11】信号どうしの乗算が可能な乗算器により定数と信号との乗算を行なう場合の、乗算処理手順および乗算器の構成例を示す図である。
【図12】“Wallace tree”を用いた定数乗算器の、設計手順および構成例を示す図である。
【図13】ブース・デコーダとブース・セレクタとから成る部分積生成回路を有する乗算器の構成例を示すブロック図である。
【図14】(A)〜(D)はいずれも従来の乗算手順および乗算器構成を具体的な例に基づいて説明するための図である。
【符号の説明】
1,2 多入力加算器(CSA,加減算回路)
3,4 インバータ(反転回路,加減算回路)
5 多入力加算器(CSA,第1加算回路,加減算回路)
6 インバータ(反転回路,加減算回路)
7 多入力加算器(CSA,第2加算回路,加減算回路)
10,10′ 定数乗算器
11 半加算器
12 全加算器
13 最終段回路(CLA)
20 定数乗算器自動生成装置(コンピュータ,CPU)
21 定数分解部(定数分解手段)
22 演算結果レジスタ(レジスタ)
23 部分積生成部(部分積生成手段)
24 第1回路生成部(回路生成部,回路生成手段)
25 第2回路生成部(回路生成部,回路生成手段)
26 ポインタ
27 定数保持レジスタ
31 第1演算部(第1演算手段)
32 第2演算部(第2演算手段)
33 判定部(判定手段)
34 第1加減算項設定部(第1加減算項設定手段)
35 第2加減算項設定部(第2加減算項設定手段)
40 定数乗算器
41 多入力加算器
42 多入力加算器(第1加算回路)
43 インバータ(反転回路)
44 多入力加算器(第2加算回路)
その他
状態の移り変わり
1998/05/15  公開