JP6995629B2 - 演算回路 - Google Patents

Description

本発明は、ディジタル信号処理における演算回路に係り、特に積和演算を行う演算回路に関するものである。

ディジタル信号処理における主な演算は、ディジタル信号のデータに係数を乗じて合算する積和演算であるが、積和演算を効率的に行うための手法として分散演算（distributed arithmetic）が知られている（非特許文献１参照）。図１０に、分散演算を採用した積和演算回路の構成例を示し、図１１に、図１０の積和演算回路の動作のタイミングチャートを示す。

図１０の積和演算回路は、Ｎ個（Ｎは２以上の整数）のデータｘ［ｎ］（ｎ＝１，・・・，Ｎ）が入力されたとき、各データｘ［ｎ］に係数ｃ［ｎ］を乗じて合算する積和演算を行う、すなわちΣ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］）を計算する演算回路である。この積和演算回路にｘ［ｎ］（ｎ＝１，・・・，Ｎ）を入力した時点から、ｘ［ｎ］のビット幅に相当する個数のクロックパルスを入力することによって、積和演算の結果が出力される。

上記の分散演算を用いた演算回路は、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）が定数であることを前提として、上記の積和演算を開始する前に、ＲＯＭ（Read Only Memory）などのメモリ回路によって構成されたルックアップテーブル（Look-Up Table、以下ＬＵＴ）１００１の各アドレスのメモリ領域に、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）と前記アドレスとに基づいて計算された値を記憶しておく。データｘ［ｎ］（ｎ＝１，・・・，Ｎ）が入力されたとき、データｘ［ｎ］（ｎ＝１，・・・，Ｎ）に基づいてＬＵＴ１００１に記憶された値を検索し、ＬＵＴ１００１からの読出値を合算することによって、積和演算と同じ結果を得ることができる。このように、分散演算を採用した積和演算回路は、回路構成が複雑な乗算回路を用いる必要がない。

図１０のＬＵＴ１００１は、図１２に示されるように、２^N個のアドレスのメモリ領域を備えている。各アドレスのメモリ領域には、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）に基づいて計算された値が予め記憶される。具体的には、アドレスａに記憶される値ＬＵＴ［ａ］は、アドレスａを２進数表記したときの各ビットをａ［ｎ］（ｎ＝１，・・・，Ｎ、ａ＝Σ_{n=1,・・・,N}（２^n-1×ａ［ｎ］））としたときの、Σ_{n=1,・・・,N}（ｃ［ｎ］×ａ［ｎ］）の値である。

図１０のシフトレジスタ１０００－ＸＲ［ｎ］（ｎ＝１，・・・，Ｎ）は、２進数で表現されたデータｘ［ｎ］（ｎ＝１，・・・，Ｎ）の各ビットｘ［ｎ］［ｌ］（ｌ＝１，・・・，Ｌ、Ｌはｘ［ｎ］のビット幅、ｘ［ｎ］＝Σ_{l=1,・・・,L}（ｘ［ｎ］［ｌ］×２^l-1）が入力され、かつデータ有効信号が有効を示すとき、データｘ［ｎ］の各ビットｘ［ｎ］［ｌ］を取り込んで、その後のクロックパルスの入力毎に、各ビットをＭＳＢ（Most Significant Bit）から順にＬＳＢ（Least Significant Bit）まで出力する。

図１３を用いて、シフトレジスタ１０００－ＸＲ［ｎ］の動作を説明する。まず、データｘ［ｎ］が入力されたときの有効を表すデータ有効信号に応じて、各セレクタｓ［ｎ，２］～ｓ［ｎ，Ｌ］は、データｘ［ｎ］の各ビットｘ［ｎ］［２］～ｘ［ｎ］［Ｌ］の値を選択する。そして、その直後のクロックパルス（１個目のクロックパルス）の入力を契機として、フリップフロップｘｒ［ｎ，１］はビットｘ［ｎ］［１］の値を取り込み、フリップフロップｘｒ［ｎ，２］～ｘｒ［ｎ，Ｌ］はそれぞれセレクタｓ［ｎ，２］～ｓ［ｎ，Ｌ］から出力されるビットｘ［ｎ］［２］～ｘ［ｎ］［Ｌ］の値を取り込む。したがって、フリップフロップｘｒ［ｎ，１］はデータｘ［ｎ］のＬＳＢであるｘ［ｎ］［１］を取り込み、フリップフロップｘｒ［ｎ，Ｌ］はデータｘ［ｎ］のＭＳＢであるｘ［ｎ］［Ｌ］を取り込む。

その後は、データ有効信号が無効を表す値になることにより、各セレクタｓ［ｎ，２］～ｓ［ｎ，Ｌ］は、前段のフリップフロップｘｒ［ｎ，１］～ｘｒ［ｎ，Ｌ－１］から出力された値を選択する。したがって、クロックパルスの入力毎に、フリップフロップｘｒ［ｎ，２］～ｘｒ［ｎ，Ｌ］は、前段のフリップフロップｘｒ［ｎ，１］～ｘｒ［ｎ，Ｌ－１］が保持していた値を取り込む動作となる。

すなわち、クロックパルスの入力毎に、シフトレジスタ１０００－ＸＲ［ｎ］の最終段のフリップフロップｘｒ［ｎ，Ｌ］（ｎ＝１，・・・，Ｎ）の出力値は変化する。フリップフロップｘｒ［ｎ，Ｌ］の出力値は、最初のクロックパルスの入力時にはｘ［ｎ］［Ｌ］となるが、次のクロックパルスの入力時にはｘ［ｎ］［Ｌ－１］となる。すなわち、データ有効信号が有効になった時点からｔ個目（ｔ＝１，・・・，Ｌ）のクロックパルスの入力時には、フリップフロップｘｒ［ｎ，Ｌ］の出力値は、ｘ［ｎ］［Ｌ－ｔ＋１］となる。

図１０の積和演算回路において、ＬＵＴ１００１から値を読み出すときの読出アドレスａの各ビットをａ［ｎ］（ｎ＝１，・・・，Ｎ）とすると、ａ［ｎ］の値は、フリップフロップｘｒ［ｎ，Ｌ］が保持している値である。したがって、データ有効信号が有効になった時点からｔ個目（ｔ＝１，・・・，Ｌ）のクロックパルスの入力直後には、ａ［ｎ］の値はｘ［ｎ］［Ｌ－ｔ＋１］となる。

ＬＵＴ１００１は、上記の読出アドレスａが入力されると、読出アドレスａのメモリ領域に記憶されている値ＬＵＴ［ａ］を出力する。ＬＵＴ［ａ］の値は、図１２に示されているように、Σ_{n=1,・・・,N}（ｃ［ｎ］×ａ［ｎ］）であり、データ有効信号が有効になった時点からｔ個目（ｔ＝１，・・・，Ｌ）のクロックパルスの入力直後のａ［ｎ］の値はｘ［ｎ］［Ｌ－ｔ＋１］の値と一致するため、ｔ個目（ｔ＝１，・・・，Ｌ）のクロックパルスの入力直後のＬＵＴ１００１の出力は、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ－ｔ＋１］）となる。

図１０の積和演算回路において、上記のＬＵＴ１００１の出力値と、累積値レジスタ１００２が保持する累積値を２倍にする２倍回路１００３の出力値とは、加算回路１００４に入力される。加算回路１００４は、ＬＵＴ１００１の出力値と２倍回路１００３の出力値とを加算し、その結果を加算値ｙとして出力する。

累積値レジスタ１００２は、クロックパルスの入力毎に、加算値ｙを、更新された累積値として保持する。なお、累積値レジスタ１００２が保持する値は、データ有効信号が有効になったときに０にリセットされるので、その初期値（最初のクロックパルスが入力された時点での値）は０である。

累積値レジスタ１００２が保持する累積値を２倍にする２倍回路１００３は、２進数で表現された累積値を１ビット左にシフトする配線で実現できるため、累積値を２倍にする処理に論理ゲートを必要としない。したがって、図１０の積和演算回路に乗算回路は用いられていない。

図１０の積和演算回路が、積和演算結果を出力するまでの過程を説明する。まず、データ有効信号が有効になった直後に入力される１個目のクロックパルスの入力により、加算回路１００４は、累積値レジスタ１００２に保持されている累計値が０であるため、ＬＵＴ１００１の出力値を加算値ｙとして出力する。すなわち、１個目のクロックパルス入力直後の加算値ｙは、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ］）となる。

次に、データ有効信号が有効になった時点から２個目のクロックパルスの入力により、加算回路１００４は、ＬＵＴ１００１の出力値と２倍回路１００３の出力値とを加算した値を加算値ｙとして出力する。ＬＵＴ１００１の出力値はΣ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ－１］）であり、累積値レジスタ１００２に保持されている累積値は１個目のクロックパルス入力直後の加算値であるため、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ］）である。したがって、２個目のクロックパルス入力直後の加算値ｙは、２×Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ］）＋Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ－１］）となる。

このように、クロックパルスの入力毎に、ＬＵＴ１００１の出力値が合算されるため、Ｌ個のクロックパルス入力直後の加算値ｙは、式（１）のようになる。
ｙ＝Σ_{t=1,・・・,L}（２^L-t×Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］［Ｌ－ｔ＋１］））
・・・（１）

ここで、Ｌ個のクロックパルス入力直後の加算値ｙを表す上記の式（１）に対して、クロックパルスの番号を表すｔを Ｌ－ｌ＋１（ｌ＝Ｌ，・・・，１）と置き換えて変形することにより、Ｌ個のクロックパルス入力直後の加算値ｙは、式（２）のようになる。
ｙ＝Σ_{n=1,・・・,N}（ｃ［ｎ］×（Σ_{l=L,・・・,1}（ｘ［ｎ］［ｌ］×２^l-1））
・・・（２）

さらに、ｘ［ｎ］［ｌ］は、データｘ［ｎ］を２進数で表現したときの各ビットの値であり、式（２）中のΣ_{l=L,・・・,1}（ｘ［ｎ］［ｌ］×２^l-1）はｘ［ｎ］に一致するため、Ｌ個のクロックパルス入力直後の加算値ｙは、積和演算の結果であるΣ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｎ］）となる。すなわち、積和演算回路の加算値ｙは、データｘ［ｎ］（ｎ＝１，・・・，Ｎ）が入力された時点から、ｘ［ｎ］のビット幅Ｌと同じ個数のクロックパルスが入力された時点で、求めるべき積和演算結果となる。

なお、入力されるデータｘ［ｎ］（ｎ＝１，・・・，Ｎ）が、負の値も取り得る符号付き数値である場合は、データｘ［ｎ］を２の補数とする。すなわち、ｘ［ｎ］≧０の場合は、ｘ［ｎ］［Ｌ］＝０、ｘ［ｎ］＝Σ_{l=1,・・・,L-1}（ｘ［ｎ］［ｌ］×２^l-1）とする。また、Σｘ［ｎ］＜０の場合は、ｘ［ｎ］［Ｌ］＝１、かつｘ［ｎ］＝－２^L＋Σ_{l=1,・・・,L-1}（ｘ［ｎ］［ｌ］×２^l-1）とする。さらに、図１０の加算回路１００４を、１個目のクロックパルスの入力直後の動作のみ加算ではなく減算するように、すなわち、ＬＵＴ１００１の出力値に対して符号を反転するように、変更する。ただし、２個目のクロックパルス入力以後は、累積値を２倍した値との加算であり変更はない。

このように、分散演算を採用した積和演算回路は、入力値を１ビットづつシフトさせる（Ｌ×Ｎ）個のフリップフロップと、入力値をフリップフロップに取り込むかシフトさせるかを選択するセレクタと、ＬＵＴを構成するメモリ回路と、クロックパルスを契機に累積値を取り込んで保持する累積値レジスタ（累積値のビット幅と同じ個数のフリップフロップ）と、１個の加算回路（符号付き入力データを扱う場合は加算／符号反転回路）とによって実現できるため、複雑な乗算回路は不要となり、比較的単純な回路で実現できるという特徴を備える。

上記の分散演算を採用した従来の積和演算回路には、乗算回路が不要となる一方で、データｘ［ｎ］の入力後、データｘ［ｎ］のビット位置毎にＬＵＴに記憶された値を検索する、すなわちデータｘ［ｎ］のビット幅Ｌと同じ回数だけＬＵＴに記憶された値の検索を繰り返す必要があるため、スループットが低い（データ入力から次のデータ入力が可能となるまでの時間が長い）という課題があった。

また、係数ｃ［ｎ］の値が固定値ではなく時間の経過に伴って変動する積和演算に、ＬＵＴとしてメモリ回路を用いる図１０の積和演算回路を適用する場合、係数ｃ［ｎ］の値が変化した時点で、ＬＵＴに保持する値の再計算と、再計算した結果のＬＵＴへの書込（全アドレスに１個づつアクセスして計算結果を書き込む処理）とを行う必要が生じる。ＬＵＴの更新中は積和演算を中断する必要があるため、係数ｃ［ｎ］の変動によって生じる頻繁なＬＵＴの更新によって、スループットが低下するという課題があった。

また、データｘ［ｎ］のビット幅Ｌと同じ個数のコピーされたＬＵＴを用いるＬＵＴ検索の並列化によって、分散演算を用いた積和演算を高速化しようとする場合や、分散演算を用いた積和演算回路の並列化によって、スループットを高くしようとする場合、ＬＵＴが保持する値が同じであっても、各ＬＵＴに対してそれぞれ異なる検索を行うので、積和演算回路毎にＬＵＴ用のメモリ回路を備える必要があるため、同じ値を記憶するメモリ素子が多数存在する冗長な回路となって、無駄に回路規模が増大するという課題があった。

また、ディジタル信号処理において頻繁に行われる複素数間の乗算についても、実部や虚部の乗算とこの乗算の結果の加減算を積和演算として扱うことで、複素数間の乗算に分散演算を採用した積和演算回路を使用することが可能である。しかしながら、実部を計算するためのＬＵＴと虚部を計算するためのＬＵＴという、一部の記憶値が同じ２個のＬＵＴを必要とするので、同じ値を記憶しているメモリ素子が２個存在する冗長な回路となって、無駄に回路規模が増大するという課題があった。

易 茹，立岩武徳，浅見幸司，小林春夫，「遅延デジタルフィルタの分散型積和演算回路を用いたＦＰＧＡ実装の検討」，第２回 電気学会 東京支部 栃木支所・群馬支所 合同研究発表会，２０１２年

本発明は、上記課題を解決するためになされたもので、回路規模および消費電力を削減し、演算のスループットを向上させることができる演算回路を提供することを目的とする。

本発明は、Ｎ個（Ｎは２以上の整数）のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の組をＭ組（Ｍは２以上の整数）含むデータセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）と、Ｎ個の係数ｃ［ｎ］とを入力とし、Ｍ個の積和演算の値ｙ［ｍ］を計算して出力する演算回路において、前記係数ｃ［ｎ］を２個ずつに組み分けしたときの組毎に計算した値を出力するＬＵＴ生成回路と、前記データセットＸ［ｍ］のうちＮ個のデータｘ［ｍ，ｎ］の各々に係数ｃ［ｎ］を乗じて合算した結果である前記積和演算の値ｙ［ｍ］を、前記Ｍ組の各組毎に並列に計算して出力するＭ個の分散演算回路とを備え、各分散演算回路は、自回路に対応するＮ個のデータｘ［ｍ，ｎ］を２個ずつに組み分けした各値と前記係数ｃ［ｎ］を２個ずつに組み分けした各値と前記ＬＵＴ生成回路によって計算された値とに基づいて、前記Ｎ個のデータｘ［ｍ，ｎ］の各々に前記係数ｃ［ｎ］の各々を乗じて合算した２項積和演算の値を、前記２個ずつに組み分けした各組毎に並列に計算して出力する複数の２項分散演算回路と、前記複数の２項分散演算回路によって計算された値を合算した結果を前記積和演算の値ｙ［ｍ］として出力する２項分散演算結果合算回路とから構成され、前記ＬＵＴ生成回路は、前記係数ｃ［ｎ］を２個ずつに組み分けした値ｃ［２×ｎ’－１］とｃ［２×ｎ’］（ｎ’＝１，・・・，Ｎ’）の和ｃ［２×ｎ’－１］＋ｃ［２×ｎ’］を値ｄ［ｎ’］としてＮ’個（Ｎ’はＮ／２以下で最大の整数）の組毎に計算し、各分散演算回路は、前記データセットＸ［ｍ］と前記ＬＵＴ生成回路から出力された係数ｃ［ｎ］および前記ＬＵＴ生成回路によって計算された値ｄ［ｎ’］とを入力とし、データセットＸ［ｍ］のうち自回路に対応するＮ個のデータｘ［ｍ，ｎ］の各々に係数ｃ［ｎ］を乗じて合算した結果である前記積和演算の値ｙ［ｍ］を出力することを特徴とするものである。

また、本発明の演算回路の１構成例は、前記ＬＵＴ生成回路と前記Ｍ個の分散演算回路との間に設けられ、前記係数ｃ［ｎ］と前記ＬＵＴ生成回路によって計算された値とをクロックに同期して保持し、保持した値を前記Ｍ個の分散演算回路に出力するＬＵＴラッチ回路をさらに備えることを特徴とするものである。

また、本発明の演算回路の１構成例において、各分散演算回路は、前記Ｎが奇数の場合にｃ［Ｎ］×ｘ［ｍ，Ｎ］を計算した結果を出力する補助乗算回路をさらに備え、前記２項分散演算結果合算回路は、前記Ｎが奇数の場合に、前記複数の２項分散演算回路によって計算された値と前記補助乗算回路によって計算された値とを合算した結果を前記積和演算の値ｙ［ｍ］として出力することを特徴とするものである。
また、本発明の演算回路の１構成例において、前記２項分散演算回路は、前記Ｎ個のデータｘ［ｍ，ｎ］のうち同一組の２個の値のビット位置毎に設けられ、値０と、前記係数ｃ［ｎ］のうち同一組の２個の値と、この係数ｃ［ｎ］の２個の値から前記ＬＵＴ生成回路によって計算された値とからなる要素値の中から、前記Ｎ個のデータｘ［ｍ，ｎ］のうち同一組の２個の値を構成する同一ビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の索引回路と、前記複数の索引回路によって取得された要素値を、それぞれ２ ^(l-1) 倍（ｌはビット位置の番号）することをビット位置毎に行う複数の倍数演算回路と、前記複数の倍数演算回路によって計算された値を合算した結果を前記２項積和演算の値として出力する合算回路とから構成されることを特徴とするものである。

また、本発明は、Ｍ個（Ｍは２以上の整数）の各々が実部値ｘ＿ｒｅａｌ［ｍ］と虚部値ｘ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個の複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとに分かれる複素数係数Ｃとを入力とし、実部の積和演算の結果と虚部の積和演算の結果とからなるＭ個の複素数値Ｙ［ｍ］を計算して出力する演算回路において、前記複素数係数Ｃの実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの差の値ｄ＿ｓｕｂと、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの和の値ｄ＿ａｄｄとを計算するＬＵＴ生成回路と、前記複素数Ｘ［ｍ］のうち自回路に対応するデータの各々に前記複素数係数Ｃを乗じて合算した結果である前記複素数値Ｙ［ｍ］を、前記Ｍ個の各々について並列に計算して出力するＭ個の分散演算回路とを備え、各分散演算回路は、前記複素数Ｘ［ｍ］と前記複素数係数Ｃの実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと前記ＬＵＴ生成回路によって計算された値ｄ＿ｓｕｂおよびｄ＿ａｄｄとを入力とし、前記実部の積和演算ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］の結果であるｙ＿ｒｅａｌ［ｍ］と、前記虚部の積和演算ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］の結果であるｙ＿ｉｍａｇ［ｍ］とを、前記Ｍ個の各々について並列に計算して出力することを特徴とするものである。

また、本発明の演算回路の１構成例は、前記ＬＵＴ生成回路と前記Ｍ個の分散演算回路との間に設けられ、前記複素数係数Ｃの実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと前記ＬＵＴ生成回路によって計算された値ｄ＿ｓｕｂおよびｄ＿ａｄｄとをクロックに同期して保持し、保持した値を前記Ｍ個の分散演算回路に出力するＬＵＴラッチ回路をさらに備えることを特徴とするものである。
また、本発明の演算回路の１構成例において、前記分散演算回路は、前記複素数Ｘ［ｍ］の実部値ｘ＿ｒｅａｌ［ｍ］および虚部値ｘ＿ｉｍａｇ［ｍ］のビット位置毎に設けられ、値０、ｃ＿ｒｅａｌ、－ｃ＿ｉｍａｇ、ｄ＿ｓｕｂからなる要素値の中から、前記実部値ｘ＿ｒｅａｌ［ｍ］および前記虚部値ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の第１の索引回路と、前記複数の第１の索引回路によって取得された要素値を、それぞれ２ ^(l-1) 倍（ｌはビット位置の番号）することをビット位置毎に行う複数の第１の倍数演算回路と、前記複数の第１の倍数演算回路によって計算された値を合算した結果を前記実部の積和演算の値ｙ＿ｒｅａｌ［ｍ］として出力する第１の合算回路と、前記複素数Ｘ［ｍ］の実部値ｘ＿ｒｅａｌ［ｍ］および虚部値ｘ＿ｉｍａｇ［ｍ］のビット位置毎に設けられ、値０、ｃ＿ｉｍａｇ、ｃ＿ｒｅａｌ、ｄ＿ａｄｄからなる要素値の中から、前記実部値ｘ＿ｒｅａｌ［ｍ］および前記虚部値ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の第２の索引回路と、前記複数の第２の索引回路によって取得された要素値を、それぞれ２ ^(l-1) 倍することをビット位置毎に行う複数の第２の倍数演算回路と、前記複数の第２の倍数演算回路によって計算された値を合算した結果を前記虚部の積和演算の値ｙ＿ｉｍａｇ［ｍ］として出力する第２の合算回路とから構成されることを特徴とするものである。

本発明の演算回路は、データのビット位置毎にＬＵＴを検索する分散演算において、対象となるビット位置をずらしながらＬＵＴの検索を繰り返すのではなく、全ビット位置について並列処理することにより、演算のスループットを向上させることができる。
また、本発明の演算回路は、ＬＵＴにメモリ回路を用いていないため、係数ｃ［ｎ］または複素数係数Ｃが時間の経過に伴って変動する積和演算に本発明を適用した場合にも、ＬＵＴのアドレス１個ずつ更新するのではなく、全アドレスに対して同時に更新することができるので、係数ｃ［ｎ］または複素数係数Ｃの変動によって生じる頻繁なＬＵＴの更新が生じても、スループットが低下しない。
また、本発明の演算回路は、１個のＬＵＴを複数個のメモリ回路にコピーすることで高速化するのではなく、ＬＵＴの要素値を生成する回路をＬＵＴ生成回路として共通化し、ＬＵＴを検索する回路である分散演算回路のみを並列化することによって、冗長回路（同じ値を保持する回路のコピー）を無くすことができ、回路規模が増大しない。
このように、本発明では、従来の分散演算を採用した積和演算回路が持っていた乗算回路を用いた積和演算回路と比較したときにスループットが低いという課題と、同じ値を保持する回路が並列化され回路規模が増大するという課題を解決することができる。さらに、本発明では、分散演算によって乗算回路が不要となるため、乗算中のスイッチング電力を抑制できるので、回路規模および消費電力を大幅に削減できる効果がある。

図１は、本発明の第１の実施例に係る演算回路の構成を示すブロック図である。 図２は、本発明の第１の実施例に係る分散演算回路の構成を示すブロック図である。 図３は、本発明の第１の実施例に係る２項分散演算回路の構成を示すブロック図である。 図４は、本発明の第１の実施例におけるＬＵＴ索引回路の動作を説明する図である。 図５は、本発明の第２の実施例に係る演算回路の構成を示すブロック図である。 図６は、本発明の第３の実施例に係る演算回路の構成を示すブロック図である。 図７は、本発明の第３の実施例に係る分散演算回路の構成を示すブロック図である。 図８は、本発明の第３の実施例における実部演算用ＬＵＴ索引回路および虚部演算用ＬＵＴ索引回路の動作を説明する図である。 図９は、本発明の第４の実施例に係る演算回路の構成を示すブロック図である。 図１０は、従来の積和演算回路の構成例を示すブロック図である。 図１１は、従来の積和演算回路の動作を説明するタイミングチャートである。 図１２は、従来の積和演算回路のルックアップテーブルを説明する図である。 図１３は、従来の積和演算回路のシフトレジスタの構成例を示すブロック図である。

［第１の実施例］
以下、本発明の実施例について図面を参照して説明する。図１は本発明の第１の実施例に係る演算回路の構成を示すブロック図である。本実施例の演算回路は、Ｍ組（Ｍは２以上の整数）のデータセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）と、Ｎ個（Ｎは２以上の整数）の係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）とを入力とする。各データセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）は、Ｎ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の組からなる。なお、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）は、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）である。

図１の演算回路は、上記入力に対して、Ｍ個の積和演算の値ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を計算して出力する。演算回路が出力する積和演算の値ｙ［ｍ］（ｍ＝１，・・・，Ｍ）の各々は、データセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）を構成するＮ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の各々に係数ｃ［ｎ］を乗じて合算した結果、すなわち、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）に相当する値である。

図１の演算回路は、１個のＬＵＴ生成回路１と、Ｍ個（Ｍは２以上の整数）の分散演算回路２－１～２－Ｍとから構成される。
ＬＵＴ生成回路１は、積和演算の係数であるＮ個の係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）を入力とし、これらを２個ずつの組に分けたときの各組の値から、分散演算用ＬＵＴの要素として使用する値を計算する。そして、ＬＵＴ生成回路１は、計算した値を係数ｃ［ｎ］と併せて各分散演算回路２－１～２－Ｍに分配する。

係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）を２個ずつに組み分けする方法は、後述する各分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）において行われる、分散演算に基づいた２項の積和演算の計算ｃ［ｐ］×ｘ［ｍ，ｐ］＋ｃ［ｑ］×ｘ［ｍ，ｑ］（ｐとｑはそれぞれ１からＮまでの範囲内の整数で、ｐ≠ｑ）でのｃ［ｐ］とｃ［ｑ］の組み分けと同じにする必要がある。

本実施例では、係数ｃ［ｎ］を、番号順が連続する奇数番目の値と直後の偶数番目の値の２個の組に組み分けする方法を説明する。したがって、本実施例では、２個ずつの組み分けにより、ｃ［１］とｃ［２］、ｃ［３］とｃ［４］、・・・というように、ｃ［２×ｎ’－１］とｃ［２×ｎ’］（ｎ’＝１，・・・，Ｎ’、Ｎ’はＮ／２以下で最大の整数）が同じ組に属する。前記のＮ’の値は、Ｎが偶数の場合にＮ／２であり、Ｎが奇数の場合に（Ｎ－１）／２である。

なお、本発明はこの組み分け方法に限定されず、係数ｃ［ｎ］の組み分け方法は、各分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）において行われる分散演算に基づいた２項の積和演算での組み分け方法と同じであればよい。

ＬＵＴ生成回路１は、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）を２個ずつに組み分けした値ｃ［２×ｎ’－１］とｃ［２×ｎ’］（ｎ’＝１，・・・，Ｎ’）の和、すなわちｃ［２×ｎ’－１］＋ｃ［２×ｎ’］をｄ［ｎ’］として計算し、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）と計算した値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とを、各分散演算回路２－１～２－Ｍに出力する。

なお、本発明は、以上の計算に限定されず、各分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）において用いられる分散演算用ＬＵＴの要素を生成するための計算であればよい。

分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）の各々は、Ｎ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）から構成されるデータセットＸ［ｍ］と、ＬＵＴ生成回路１から分配された係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）およびＬＵＴ生成回路１で計算された数値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とを入力とし、データセットＸ［ｍ］のうち自回路に対応するＮ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の各々に係数ｃ［ｎ］を乗じて合算した結果、すなわち、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）に相当する値ｙ［ｍ］を出力する。

図２に分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）の構成を示す。各分散演算回路２－ｍは、Ｎ’個の２項分散演算回路２０ｍ－ｎ’（ｎ’＝１，・・・，Ｎ’）と、２項分散演算結果合算回路２１ｍとから構成される。
図２の分散演算回路２－ｍは、入力されたデータセットＸ［ｍ］のうち自回路に対応するＮ個のデータｘ［ｍ，ｎ］に対して、ＬＵＴ生成回路１が係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）に対して行った２個ずつの組み分けと同様に、２個ずつの組み分けを行う。

本実施例のＬＵＴ生成回路１は、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）のうち番号が連続する奇数番目の値と直後の偶数番目の値の２個を同じ組みとして組み分けしている。このため、各分散演算回路２－ｍが行うＮ個のデータｘ［ｍ，ｎ］の組み分けについても同じく、ｘ［ｍ，２×ｎ’－１］とｘ［ｍ，２×ｎ’］（ｎ’＝１，・・・，Ｎ’、Ｎ’はＮ／２以下で最大の整数）を１つの組とする。

２項分散演算回路２０ｍ－ｎ’（ｎ’＝１，・・・，Ｎ’）の各々は、自回路に対応する１組みのデータｘ［ｍ，２×ｎ’－１］，ｘ［ｍ，２×ｎ’］と、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）のうち自回路に対応する１組みの係数ｃ［２×ｎ’－１］，ｃ［２×ｎ’］と、ＬＵＴ生成回路１により計算された値ｄ［ｎ’］とを入力とする。

２項分散演算回路２０ｍ－ｎ’は、値０、ｃ［２×ｎ’－１］、ｃ［２×ｎ’］、ｄ［ｎ’］を各要素の数値とするＬＵＴを構成し、このＬＵＴを用いた分散演算によって、積和演算ｃ［２×ｎ’－１］×ｘ［ｍ，２×ｎ’－１］＋ｃ［２ｎ’］×ｘ［ｍ，２×ｎ’］の結果を取得してｙ’［ｍ，ｎ’］として出力する。

２項分散演算結果合算回路２１ｍは、各２項分散演算回路２０ｍ－ｎ’（ｎ’＝１，・・・，Ｎ’）が出力した値ｙ’［ｍ，ｎ’］を合算、すなわち、Σ_{n'=1,・・・,N'}（ｙ’［ｍ，ｎ’］）を計算し、その結果をｙ［ｍ］として出力する。

なお、以上の分散演算回路２－ｍの説明はＮが偶数の場合であり、Ｎが奇数の場合は、図２に示すように、ｃ［Ｎ］×ｘ［ｍ，Ｎ］を計算して結果をｙ’［ｍ，Ｎ’＋１］として出力する補助乗算回路２２ｍを追加する。
さらに、Ｎが奇数の場合、２項分散演算結果合算回路２１ｍは、各２項分散演算回路２０ｍ－ｎ’（ｎ’＝１，・・・，Ｎ’）が出力した値ｙ’［ｍ，ｎ’］（ｎ’＝１，・・・，Ｎ’）と補助乗算回路２２ｍが出力した値ｙ’［ｍ，Ｎ’＋１］とを合算して、結果をｙ［ｍ］として出力する。

図３に、２項分散演算回路２０ｍ－ｎ’（ｍ＝１，・・・，Ｍ、ｎ’＝１，・・・，Ｎ’）の構成を示す。ここで、２進数で表現された任意のデータｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）の１個分のビット幅をＬとし、２項分散演算回路２０ｍ－ｎ’が入力とするデータｘ［ｍ，２×ｎ’－１］の各ビットをｘ［ｍ，２×ｎ’－１］［ｌ］（ｌ＝１，・・・，Ｌ）、ｘ［ｍ，２×ｎ’］の各ビットをｘ［ｍ，２×ｎ’］［ｌ］（ｌ＝１，・・・，Ｌ）とする。

図３に示した２項分散演算回路２０ｍ－ｎ’は、Ｌ個のＬＵＴ索引回路２００ｍ－ｎ’－ｌ（選択回路）と、符号反転回路２０２と、Ｌ個の倍数演算回路２０３ｍ－ｎ’－ｌと、合算回路２０４とから構成される。

２項分散演算回路２０ｍ－ｎ’は、データｘ［ｍ，２×ｎ’－１］，ｘ［ｍ，２×ｎ’］のビット位置ｌ（ｌ＝１，・・・，Ｌ）毎に設けられたＬＵＴ索引回路２００ｍ－ｎ’－ｌを有する。ＬＵＴ索引回路２００ｍ－ｎ’－ｌは、データｘ［ｍ，２×ｎ’－１］とｘ［ｍ，２×ｎ’］のうち自回路に対応するビット位置ｌにあるビットｘ［ｍ， ２×ｎ’－１］［ｌ］とｘ［ｍ， ２×ｎ’］［ｌ］とに基づいて、ＬＵＴの要素４個から１個を選択し、この選択した要素値をＬＵＴ＃ｍ－ｎ’－ｌとして取得する。

図４に、ビットｘ［ｍ，２×ｎ’－１］［ｌ］およびｘ［ｍ，２×ｎ’］［ｌ］の各値と、そのとき選択されるＬＵＴの要素値ＬＵＴ＃ｍ－ｎ’－ｌとの関係を示す。ビットｘ［ｍ，２×ｎ’－１］［ｌ］およびｘ［ｍ，２×ｎ’］［ｌ］の各値と要素値ＬＵＴ＃ｍ－ｎ’－ｌとの関係は、Ｎ＝２（２項の積和演算）の場合の図１２に示した、アドレスと、各アドレスに対応する記憶値の関係と同じである。

すなわち、図１２のアドレスａ［０］は図４のビットｘ［ｍ， ２×ｎ’－１］［ｌ］に対応し、図１２のアドレスａ［１］は図４のビットｘ［ｍ， ２×ｎ’］［ｌ］に対応し、図１２のｃ［０］は図４のｃ［２×ｎ’－１］に対応し、図１２のｃ［１］は図４のｃ［２×ｎ’］に対応する。

図３に示した２項分散演算回路２０ｍ－ｎ’において、ＬＵＴ索引回路２００ｍ－ｎ’－ｌによってビット位置ｌ（ｌ＝１，・・・，Ｌ）毎に選択された、ＬＵＴの要素値ＬＵＴ＃ｍ－ｎ’－ｌは、それぞれ倍数演算回路２０３ｍ－ｎ’－ｌによって２ ^(l-1) 倍される。
合算回路２０４は、Ｌ個の倍数演算回路２０３ｍ－ｎ’－ｌによって計算された値を合算した結果を、積和演算ｃ［２×ｎ’－１］×ｘ［ｍ，２×ｎ’－１］＋ｃ［２ｎ’］×ｘ［ｍ，２×ｎ’］の結果であるｙ’［ｍ，ｎ’］として出力する。

ただし、ｌ＝Ｌのビット位置（データのＭＳＢ位置）については、選択された要素値ＬＵＴ＃ｍ－ｎ’－Ｌに対して符号反転回路２０２によって符号反転が行われた後に、倍数演算回路２０３ｍ－ｎ’－Ｌによって２ ^(L-1) 倍される。

図１０に示した従来の積和演算回路では、ｌ番目のクロックパルスの入力により、ビット位置ｌについてＬＵＴ出力値を、累積値を２倍した値と合算する処理を行い、Ｌ個のクロックパルス入力によって積和演算の結果を得ることができた。

一方、図３に示した２項分散演算回路２０ｍ－ｎ’では、図１０のＬＵＴ１００１と累積値レジスタ１００２と２倍回路１００３と加算回路１００４に相当する処理を、全てのビット位置ｌ（ｌ＝１，・・・，Ｌ）に関して同時に行うことによって、Ｌ個のクロックパルス入力を必要とせずに、即座に積和演算の結果を得ることができる。

なお本実施例では、ＭＳＢのビット位置Ｌについては、選択された要素値ＬＵＴ＃ｍ－ｎ’－Ｌの符号反転を行っている。符号反転を行う理由は、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）を、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）としているためである。データｘ［ｍ，ｎ］が、０以上のみに限定される符号なし数値の場合は、ＭＳＢのビット位置Ｌについても、他のビット位置と同様に、要素値ＬＵＴ＃ｍ－ｎ’－Ｌをそのまま倍数演算回路２０３ｍ－ｎ’－Ｌによって２ ^(L-1) 倍すればよい。

また、上記のビット位置ｌについて、選択された要素値ＬＵＴ＃ｍ－ｎ’－ｌを２ ^(l-1) 倍する処理は、２進数で表現された要素値ＬＵＴ＃ｍ－ｎ’－ｌを、（ｌ－１）ビット左にシフトすることによって実現できる。したがって、Ｌ個の倍数演算回路２０３ｍ－ｎ’－ｌに乗算回路を用いる必要はなく、簡易な回路で実現できる。

本実施例の演算回路が出力するＭ個の数値ｙ［ｍ］（ｍ＝１，・・・，Ｍ）は、各データセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）を構成するＮ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の各々にＮ個の係数ｃ［ｎ］を乗じて合算した積和演算の結果Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）と同じ値となる。

図１０の積和演算回路は、Ｎ個のデータの数値とＮ個の係数との乗算とその合算であるＮ項の積和演算を分散演算により実現している。
一方、本実施例の演算回路は、Ｎ項の積和演算を、Ｎ’個の２項の積和演算に分割して、各２項の積和演算をそれぞれ並列演算により実現し、これらの結果を合算することによって、Ｎ項の積和演算と同じ結果を得ている。前記の構成の差による効果について、以下に説明する。

図１０の積和演算回路は、Ｎ項の積和演算を分散演算により実現するために、２^N個の要素を備えた１個のＬＵＴ１００１を必要としている。ＬＵＴ１００１には、２^N個のアドレスをもつメモリ回路が使用される。メモリ回路により実現されたＬＵＴ１００１は、フリップフロップおよび論理ゲートにより実現されたＬＵＴ回路と比較して、一般的に、１ビットあたりの記憶素子の面積が小さく、かつ、多数のアドレスの各々に記憶された値から指定された１個のアドレスに記憶された値の読み出しを行う処理を効率的に（高速かつ低消費電力かつ小さい面積の回路で）実現できる。この特徴によって、要素数が多い図１０のＬＵＴ１００１を、フリップフロップや論理ゲートによって実現する場合よりも、メモリ回路で実現する方が、高速かつ低消費電力かつ小面積となる。

しかしながら、図１０の積和演算回路では、データのビット位置毎にＬＵＴ１００１のメモリ回路を読み出す必要があるので、データのビット幅分の回数のメモリアクセスによってスループットが制限される。スループットの制限を緩和する対策としては、データのビット幅分の個数のメモリ回路を備えておき、１個のＬＵＴ１００１をこれらのメモリ回路にコピーすることにより、全ビット位置について同時にＬＵＴを検索可能とする方法がある。しかし、この方法では、多数のメモリ回路を備える必要があるので、回路の面積が増大するという課題が生じる。

本実施例の演算回路は、Ｎ項積和演算をＮ’（＝Ｎ／２）個の２項積和演算へと分割することによって、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）に保持すべき数値の個数を大幅に削減し、ＬＵＴをメモリ回路ではなくフリップフロップや論理ゲートにより構成した場合にも回路規模が問題とならないような構成としている。

すなわち、Ｎ項積和演算を１個のＬＵＴ１００１を用いて分散演算を行う場合は、ＬＵＴ１００１に２^N-1個の数値を保持する必要がある（アドレス数は２^Nだが、そのうち１個のアドレスには値０が入るため数値として保持する必要はないので、保持すべき数値の個数は２^N-1個）。

一方、本実施例では、Ｎ’（＝Ｎ／２）個の２項積和演算に分割することにより、３（＝２²－１）個の数値を保持するＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）がＮ’（＝Ｎ／２）個使用されるので、（Ｎ×１．５）個の数値を保持すれば済む。

例えばＮ＝８の場合、保持すべき数値の個数を２５５個から１２個に削減できるので、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）にメモリ回路を使用しなくとも回路規模が問題とならないような構成とすることができる。なお、Ｎ項積和演算を２項積和演算に分割することによって、Ｎ’（＝Ｎ／２）個の２項積和演算結果を合算する２項分散演算結果合算回路２１ｍを追加する必要があるが、ＬＵＴ１００１を構成するメモリ回路と比較すると、２項分散演算結果合算回路２１ｍの回路規模は十分に小さく、問題とはならない。

本実施例の演算回路では、上記のように、Ｎ項積和演算を２項積和演算に分割することにより、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）に保持される要素値の個数を大幅に削減することができるが、さらにＬＵＴ索引回路２００ｍ－ｎ’－ｌの合計規模についても、大幅に削減できることを、３項積和演算に分割する場合と比較することにより示す。

Ｎ項積和演算を２項積和演算に分割する場合は、４：１セレクタであるＬＵＴ索引回路２００ｍ－ｎ’－ｌがＮ／２個必要となるが、３項積和演算に分割する場合は、８：１セレクタであるＬＵＴ索引回路がＮ／３個必要となる。４：１セレクタは３個の２：１セレクタから構成可能であり、８：１セレクタは７個の２：１セレクタから構成可能である。したがって、Ｎ項積和演算を２項積和演算に分割する場合は、（Ｎ×１．５）個の２：１セレクタが必要となるのに対して、３項積和演算に分割する場合は、（Ｎ×７／３）個の２：１セレクタが必要となる。

また、Ｎ項積和演算を２項積和演算に分割する場合は、ＬＵＴの要素値に２個の係数ｃ［２×ｎ’－１］とｃ［２×ｎ’］の合計値ｄ［ｎ’］が含まれるため、ＬＵＴの要素値のビット幅は、係数ｃ［２×ｎ’－１］，ｃ［２×ｎ’］のビット幅＋１ビットとなる。

これに対して、Ｎ項積和演算を３項積和演算に分割する場合は、ＬＵＴの要素値に３個の係数の合計値が含まれるため、そのＬＵＴの要素値のビット幅は、係数のビット幅＋２ビットとなる。このため、ＬＵＴ索引回路に使用される２：１セレクタの個数、および２：１セレクタのビット幅が、Ｎ項積和演算を２項積和演算に分割する場合よりも３項積和演算に分割する場合の方が大きくなる。このように、本実施例の演算回路は、Ｎ項積和演算を２項積和演算に分割することにより、ＬＵＴ索引回路２００ｍ－ｎ’－ｌの合計規模を削減する効果がある。

本実施例の演算回路では、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）を、メモリ回路ではなく、予め要素値を生成する回路と要素値をセレクタ等の論理ゲートを用いて選択する回路としている。従来のようにＬＵＴがメモリ回路の場合、データの全ビット位置について同時にＬＵＴを検索する並列化や、積和演算回路自体の並列化によって、スループットを高くしようとしたときに、データのビット位置毎や積和演算回路毎に、ＬＵＴをコピーした複数個のメモリ回路を備える必要がある。

本実施例の演算回路では、ＬＵＴにメモリ回路を用いていないため、ＬＵＴの各要素値を事前に生成・保持する回路（ＬＵＴ生成回路１）と、要素値を選択する回路（ＬＵＴ索引回路２００ｍ－ｎ’－ｌ）に分けることが可能であり、ＬＵＴ生成回路１を並列化せずにＬＵＴ索引回路２００ｍ－ｎ’－ｌのみを並列化する。これにより、冗長な回路の構成、すなわちＬＵＴの各要素値を保持する回路の並列化（コピー）を防止することができ、並列化に伴う回路規模の増大を抑制することができる。

また、本実施例で説明した演算回路は、乗算回路と加算回路によりΣ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）を計算する一般的な積和演算回路と同様に、データの入力時点から結果が出力されるまでに要する時間を、入力データのビット幅の平方根に比例した時間とすることができる。

一方、図１０に示した積和演算回路では、入力データのビット幅と同じ個数のクロックパルス入力を完了するまで計算結果を得ることができない。したがって、データの入力時点から結果が出力されるまでに要する時間は、入力データのビット幅と比例した時間となる。このように、本実施例の演算回路は入力データのビット幅の平方根に比例した計算時間で済むため、前記ビット幅に比例した計算時間を要する図１０の積和演算回路と比較して、スループットを向上させることができる。

また、本実施例の演算回路は、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）にメモリ回路を用いずに、ＬＵＴ生成回路１からＬＵＴの各要素値を分配し、これらが分配された２項分散演算回路２０ｍ－ｎ’において要素値の中から１個を選択する。このため、係数ｃ［ｎ］が時間の経過に伴って変動する積和演算に本実施例を適用した場合に、係数ｃ［ｎ］の変化を即時にＬＵＴに反映させることができる。

一方、図１０の積和演算回路のようにＬＵＴ１００１にメモリ回路を用いる場合は、そのアドレスを１個ずつアクセスして記憶値を書き換える処理が必要となるため、全てのアドレスに対して書き換え処理が完了するまで積和演算が中断される。このように、本実施例の演算回路は、係数ｃ［ｎ］の変動によって生じる頻繁なＬＵＴの更新が生じても、スループットが低下しない。

［第２の実施例］
次に、本発明の第２の実施例について説明する。図５は本発明の第２の実施例に係る演算回路の構成を示すブロック図であり、図１と同一の構成には同一の符号を付してある。本実施例は、第１の実施例に示した演算回路に対して、回路規模や消費電力の増大なく、スループットを改善する構成を示す。

図５の演算回路は、図１に示した演算回路と同じく、Ｍ組（Ｍは２以上の整数）のデータセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）と、Ｎ個（Ｎは２以上の整数）の係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）とを入力とする。各データセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）は、Ｎ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の組からなる。なお、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）は、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）である。

図５の演算回路は、図１に示した演算回路と同じく、上記入力に対して、Ｍ個の積和演算の値ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を計算して出力する。演算回路が出力する積和演算の値ｙ［ｍ］（ｍ＝１，・・・，Ｍ）の各々は、データセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）を構成するＮ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の各々に係数ｃ［ｎ］を乗じて合算した結果、すなわち、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）に相当する値である。

図５の演算回路は、１個のＬＵＴ生成回路１と、１個のＬＵＴラッチ回路３と、Ｍ個（Ｍは２以上の整数）の分散演算回路２－１～２－Ｍから構成される。
ＬＵＴ生成回路１は、積和演算の係数であるＮ個の係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）を入力とし、これらを２個ずつの組に分けたときの各組の値から、分散演算用ＬＵＴの要素として使用する値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’、Ｎ’はＮ／２以下で最大の整数）を計算し、計算した値ｄ［ｎ’］を係数ｃ［ｎ］と併せてＬＵＴラッチ回路３に出力する。ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）の計算方法は、第１の実施例において説明した方法と同じである。

ＬＵＴラッチ回路３は、ＬＵＴ生成回路１から出力された係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）とＮ’個（Ｎ’はＮ／２以下で最大の整数）の値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とを入力とし、クロックパルスの入力毎に、係数ｃ［ｎ］と値ｄ［ｎ’］とをラッチして、次のクロックパルスの入力まで保持する回路である。ＬＵＴラッチ回路３は、係数ｃ［ｎ］と値ｄ［ｎ’］の各ビットの値をクロックに同期して保持するフリップフロップによって実現できる。そして、ＬＵＴラッチ回路３は、保持した係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）と値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とを、各分散演算回路２－１～２－Ｍに出力する。

分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）の各々は、Ｎ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）から構成されるデータセットＸ［ｍ］と、ＬＵＴラッチ回路３から分配された係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）および値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とを入力とし、データセットＸ［ｍ］のうち自回路に対応するＮ個のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の各々に係数ｃ［ｎ］を乗じて合算した結果、すなわち、Σ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）に相当する値ｙ［ｍ］を出力する。値ｙ［ｍ］の計算方法は、第１の実施例において説明した方法と同じである。

図５の演算回路は、図１の演算回路と比較して、ＬＵＴラッチ回路３がＬＵＴ生成回路１と分散演算回路２－１～２－Ｍの間に挿入されている点が異なる。すなわち、ＬＵＴ生成回路１とＭ並列の分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）とがパイプライン構成となっている。

図１の演算回路では、ＬＵＴ生成回路１内で、ｃ［ｎ］（ｎ＝１，・・・，Ｎ）からｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）を計算する処理時間である生成時間Ｔｄ＿ＬＵＴと、分散演算回路２－ｍ内でデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）と係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）および値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とに基づいてΣ_{n=1,・・・,N}（ｃ［ｎ］×ｘ［ｍ，ｎ］）に相当する数値ｙ［ｍ］を生成する処理時間である分散演算時間Ｔｄとの合計時間、すなわち（Ｔｄ＿ＬＵＴ＋Ｔｄ）によって、演算回路を含むシステムのクロック周波数の上限が制約される。
一方、図５の演算回路では、生成時間Ｔｄ＿ＬＵＴと分散演算時間Ｔｄのそれぞれによって、演算回路を含むシステムのクロック周波数の上限が制約される。

すなわち、図１の演算回路を採用したシステムのクロック周波数の上限値は １／（Ｔｄ＿ＬＵＴ＋Ｔｄ）であるのに対して、図５の演算回路を採用したシステムのクロック周波数の上限値は、１／Ｔｄ＿ＬＵＴと１／Ｔｄのうち値が小さい方になる。つまり、図１の演算回路よりも、図５の演算回路の方が、高速に動作する。

通常、処理の流れが一方向の回路は、パイプライン構成の採用によって、高速化（スループット向上）が可能となるが、フリップフロップが多数使用されるため、回路規模や消費電力が増大するという課題が存在する。
本実施例において、パイプライン構成での課題となるフリップフロップは、ＬＵＴラッチ回路３内で、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）と値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）とをクロックに同期して保持する回路に使用されるフリップフロップである。

パイプライン構成の回路規模や消費電力は、ＬＵＴの要素数、すなわち、係数ｃ［ｎ］（ｎ＝１，・・・，Ｎ）および値ｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）の個数（Ｎ＋Ｎ’）に、ほぼ比例する。なお、正確にはｃ［２×ｎ’－１］とｃ［２×ｎ’］の加算値であるｄ［ｎ’］（ｎ’＝１，・・・，Ｎ’）の方が少なくとも１ビット分ビット幅が大きくなるため、追加されるフリップフロップの個数は、完全に（Ｎ＋Ｎ’）に比例はしないが、通常ｃ［ｎ］のビット幅は１ビットと比較すると十分に大きいため、ほぼ比例すると考えてよい。

しかし、第１の実施例の説明にあるように、第１の実施例および本実施例では、メモリ回路でＬＵＴを構成しなくとも済むようＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）の要素数を削減している。

図１０の積和演算回路では、Ｎ項積和演算を１個のＬＵＴ１００１を用いて分散演算を行うため、ＬＵＴ１００１の要素数は２^N－１であったが、本実施例や第１の実施例の演算回路では、Ｎ項積和演算をＮ／２個の２項積和演算に分割することによってその要素数を（Ｎ×１．５）個にまで削減している。例えばＮ＝８の場合、要素数を２５５個から１２個にまで削減できる。このように、本実施例では、図１０の積和演算回路を基にパイプライン構成化した場合と比較すると、パイプライン構成化に伴って追加されるフリップフロップの個数を大幅に削減できるため、回路規模や消費電力を増大させることなく、スループットを改善できる。

また、分散演算を用いない、乗算回路と加算回路を組み合わせて構成された一般的な積和演算回路に対してパイプライン構成化する場合、乗算回路と加算回路の間にフリップフロップを挿入する構成を採ることが可能である。乗算回路と加算回路の間に挿入すべきフリップフロップ数は、積和演算の並列数Ｍに比例するので、演算回路全体に対するフリップフロップの規模の割合が大きく、パイプライン構成の採用によって生じる回路規模や消費電力の増加が問題となる。しかし、本実施例に示した演算回路では、パイプライン構成化により挿入されるフリップフロップ数は、演算の並列数Ｍに比例して増加することはなく、少ないＬＵＴの要素数に比例した個数で済む。

このように、従来の積和演算回路では、パイプライン構成化に伴って回路規模・消費電力が大幅に増大するが、本実施例に示したようにＬＵＴ生成回路１とＭ並列の分散演算回路２－ｍ（ｍ＝１，・・・，Ｍ）とを分けたパイプライン構造とすることで、本実施例の演算回路は、回路規模や消費電力を増大させることなく、スループットを改善できるという、特徴を備える。

［第３の実施例］
次に、本発明の第３の実施例について説明する。図６は本発明の第３の実施例に係る演算回路の構成を示すブロック図である。図６の演算回路は、各々が実部値ｘ＿ｒｅａｌ［ｍ］と虚部値ｘ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個（Ｍは２以上の整数）の複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとに分かれる複素数係数Ｃとを入力とする。なお、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）は、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）である。

図６の演算回路は、上記入力に対して、実部値ｙ＿ｒｅａｌ［ｍ］と虚部値ｙ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個の複素数値Ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を、分散演算（distributed arithmetic）により取得し出力する。Ｍ個の複素数値Ｙ［ｍ］は、各々が（Ｃ×Ｘ［ｍ］）に相当する。すなわち、実部値ｙ＿ｒｅａｌ［ｍ］は、ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］に相当する。虚部値ｙ＿ｉｍａｇ［ｍ］は、ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］に相当する。

図６の演算回路は、１個のＬＵＴ生成回路１ａと、Ｍ個（Ｍは２以上の整数）の分散演算回路２ａ－１～２ａ－Ｍとから構成される。

ＬＵＴ生成回路１ａは、複素数係数Ｃの実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとを入力とし、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの差ｃ＿ｒｅａｌ－ｃ＿ｉｍａｇに相当する値ｄ＿ｓｕｂと、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの和ｃ＿ｒｅａｌ＋ｃ＿ｉｍａｇに相当する値ｄ＿ａｄｄとをそれぞれ計算し、実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと共に値ｄ＿ｓｕｂおよびｄ＿ａｄｄを各分散演算回路２ａ－１～２ａ－Ｍに出力する。

分散演算回路２ａ－ｍ（ｍ＝１，・・・，Ｍ）の各々は、複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、ＬＵＴ生成回路１ａから分配された実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと値ｄ＿ｓｕｂおよびｄ＿ａｄｄとを入力とし、複数数Ｘ［ｍ］のうち自回路に対応するデータの各々に複素数係数Ｃを乗じて合算した結果である複素数値Ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を、Ｍ個の各々について並列に計算して出力する。

分散演算回路２ａ－ｍは、値０、ｃ＿ｒｅａｌ、－ｃ＿ｉｍａｇ、ｄ＿ｓｕｂを各要素の数値とする実部演算用ＬＵＴと、値０、ｃ＿ｉｍａｇ、ｃ＿ｒｅａｌ、ｄ＿ａｄｄを各要素の数値とする虚部演算用ＬＵＴとを構成し、実部演算用ＬＵＴを用いた分散演算によって実部の積和演算ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］の結果を取得してｙ＿ｒｅａｌ［ｍ］として出力すると共に、虚部演算用ＬＵＴを用いた分散演算によって虚部の積和演算ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］の結果を取得してｙ＿ｉｍａｇ［ｍ］として出力する。

図７に、分散演算回路２ａ－ｍ（ｍ＝１，・・・，Ｍ）の構成を示す。ここで、２進数で表現された任意のデータｘ＿ｒｅａｌ［ｍ］（ｍ＝１，・・・，Ｍ）およびｘ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）の１個分のビット幅をＬとし、分散演算回路２ａ－ｍが入力とするデータｘ＿ｒｅａｌ［ｍ］の各ビットをｘ＿ｒｅａｌ［ｍ］［ｌ］（ｌ＝１，・・・，Ｌ）、ｘ＿ｉｍａｇ［ｍ］の各ビットをｘ＿ｉｍａｇ［ｍ］［ｌ］（ｌ＝１，・・・，Ｌ）とする。

図７に示した分散演算回路２ａ－ｍは、Ｌ個の実部演算用ＬＵＴ索引回路２０５ｍ－ｌ（実部演算用選択回路）と、符号反転回路２０６，２０７と、Ｌ個の倍数演算回路２０８ｍ－ｌと、合算回路２０９と、Ｌ個の虚部演算用ＬＵＴ索引回路２１０ｍ－ｌ（虚部演算用選択回路）と、符号反転回路２１１と、Ｌ個の倍数演算回路２１２ｍ－ｌと、合算回路２１３とから構成される。

分散演算回路２ａ－ｍは、データｘ＿ｒｅａｌ［ｍ］，ｘ＿ｉｍａｇ［ｍ］のビット位置ｌ（ｌ＝１，・・・，Ｌ）毎に設けられた実部演算用ＬＵＴ索引回路２０５ｍ－ｌと虚部演算用ＬＵＴ索引回路２１０ｍ－ｌとを有する。
実部演算用ＬＵＴ索引回路２０５ｍ－ｌは、データｘ＿ｒｅａｌ［ｍ］，ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置ｌにあるビットｘ＿ｒｅａｌ［ｍ］［ｌ］，ｘ＿ｉｍａｇ［ｍ］［ｌ］に基づいて、実部演算用ＬＵＴの４要素値、すなわち値０、ｃ＿ｒｅａｌ、－ｃ＿ｉｍａｇ、ｄ＿ｓｕｂの中から１個を取得する。

虚部演算用ＬＵＴ索引回路２１０ｍ－ｌは、データｘ＿ｒｅａｌ［ｍ］，ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置ｌにあるビットｘ＿ｒｅａｌ［ｍ］［ｌ］，ｘ＿ｉｍａｇ［ｍ］［ｌ］に基づいて、虚部演算用ＬＵＴの４要素値、すなわち値０、ｃ＿ｉｍａｇ、ｃ＿ｒｅａｌ、ｄ＿ａｄｄの中から１個を取得する。

図８に、ビットｘ＿ｒｅａｌ［ｍ］［ｌ］およびｘ＿ｉｍａｇ［ｍ］［ｌ］の各値と、そのとき選択される実部演算用ＬＵＴの要素値および虚部演算用ＬＵＴの要素値との関係を示す。ビットｘ＿ｒｅａｌ［ｍ］［ｌ］およびｘ＿ｉｍａｇ［ｍ］［ｌ］の各値と実部演算用ＬＵＴの要素値および虚部演算用ＬＵＴの要素値との関係は、Ｎ＝２（２項の積和演算）の場合の図１２に示した、アドレスと、各アドレスに対応する記憶値の関係と同じである。

すなわち、図１２のアドレスａ［０］は本実施例のビットｘ＿ｒｅａｌ［ｍ］［ｌ］に対応し、図１２のアドレスａ［１］は本実施例のビットｘ＿ｉｍａｇ［ｍ］［ｌ］に対応する。また、ｙ＿ｒｅａｌ［ｍ］を求める実部の積和演算については、図１２の係数ｃ［０］は本実施例のｃ＿ｒｅａｌに対応し、図１２の係数ｃ［１］は本実施例の－ｃ＿ｉｍａｇに対応する。また、ｙ＿ｉｍａｇ［ｍ］を求める虚部の積和演算については、図１２の係数ｃ［０］は本実施例のｃ＿ｉｍａｇに対応し、図１２の係数ｃ［１］は本実施例のｃ＿ｒｅａｌに対応する。

図７に示した分散演算回路２ａ－ｍにおいて、実部演算用ＬＵＴ索引回路２０５ｍ－ｌによってビット位置ｌ（ｌ＝１，・・・，Ｌ）毎に選択された実部演算用ＬＵＴの要素値は、それぞれ倍数演算回路２０８ｍ－ｌによって２ ^(l-1) 倍される。
同様に、虚部演算用ＬＵＴ索引回路２１０ｍ－ｌによってビット位置ｌ（ｌ＝１，・・・，Ｌ）毎に選択された虚部演算用ＬＵＴの要素値は、それぞれ倍数演算回路２１２ｍ－ｌによって２ ^(l-1) 倍される。

合算回路２０９は、Ｌ個の倍数演算回路２０８ｍ－ｌによって計算された値を合算し、合算回路２１３は、Ｌ個の倍数演算回路２１２ｍ－ｌによって計算された値を合算する。

ただし、実部値のｌ＝Ｌのビット位置（データのＭＳＢ位置）については、実部演算用ＬＵＴ索引回路２０５ｍ－Ｌによって選択された要素値に対して符号反転回路２０７によって符号反転が行われた後に、倍数演算回路２０８ｍ－Ｌによって２ ^(L-1) 倍される。同様に、虚部値のｌ＝Ｌのビット位置については、虚部演算用ＬＵＴ索引回路２１０ｍ－Ｌによって選択された要素値に対して符号反転回路２１１によって符号反転が行われた後に、倍数演算回路２１２ｍ－Ｌによって２ ^(L-1) 倍される。

このように、全てのビット位置について合算回路２０９による合算が行われた結果は、本実施例の演算回路が出力すべき複素数値Ｙ［ｍ］の実部値であるｙ＿ｒｅａｌ［ｍ］として出力される。また、合算回路２１３による合算が行われた結果は、複素数値Ｙ［ｍ］の虚部値であるｙ＿ｉｍａｇ［ｍ］として出力される。

図７に示した分散演算回路２ａ－ｍでは、図３に示した第１の実施例の回路と同じく、図１０のＬＵＴ１００１と累積値レジスタ１００２と２倍回路１００３と加算回路１００４に相当する処理を、全てのビット位置ｌ（ｌ＝１，・・・，Ｌ）に関して同時に行うことによって、Ｌ個のクロックパルス入力を必要とせずに、即座に積和演算の結果を得ることができる。

なお本実施例では、ＭＳＢのビット位置Ｌについては、実部演算用ＬＵＴ索引回路２０５ｍ－Ｌによって選択された要素値の符号反転、および虚部演算用ＬＵＴ索引回路２１０ｍ－Ｌによって選択された要素値の符号反転を行っている。符号反転を行う理由は、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）を、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）としているためである。

ｘ＿ｒｅａｌ［ｍ］やｘ＿ｉｍａｇ［ｍ］が、０以上のみに限定される符号なし数値の場合は、ＭＳＢのビット位置Ｌについても、他のビット位置と同様に、実部演算用ＬＵＴ索引回路２０５ｍ－Ｌによって選択された要素値をそのまま倍数演算回路２０８ｍ－Ｌによって２ ^(L-1) 倍し、虚部演算用ＬＵＴ索引回路２１０ｍ－Ｌによって選択された要素値をそのまま倍数演算回路２１２ｍ－Ｌによって２ ^(L-1) 倍すればよい。

また、上記のビット位置ｌについて、実部演算用ＬＵＴ索引回路２０５ｍ－ｌ、虚部演算用ＬＵＴ索引回路２１０ｍ－ｌによって選択された要素値を２ ^(l-1) 倍する処理は、２進数で表現された要素値を（ｌ－１）ビット左にシフトすることによって実現できる。したがって、Ｌ個の倍数演算回路２０８ｍ－ｌおよびＬ個の倍数演算回路２１２ｍ－ｌに乗算回路を用いる必要はなく、簡易な回路で実現できる。

本実施例の演算回路が出力するＭ個の複素数値Ｙ［ｍ］（ｍ＝１，・・・，Ｍ）は、複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）に複素数係数Ｃを乗じて合算した積和演算の結果（Ｃ×Ｘ［ｍ］）と同じ値となる。

第１の実施例では、Ｎ項積和演算をＮ’（＝Ｎ／２）個の２項積和演算へと分割することによって、ＬＵＴ（ＬＵＴ生成回路１とＬＵＴ索引回路２００ｍ－ｎ’－ｌ）に保持すべき数値の個数を大幅に削減している。
一方、本実施例では、複素数間の乗算が２項積和演算の形式であるため、Ｎ項積和演算から２項積和演算に分割しなくとも、わずか４個の要素値のＬＵＴ（ＬＵＴ生成回路１ａと実部演算用ＬＵＴ索引回路２０５ｍ－ｌと虚部演算用ＬＵＴ索引回路２１０ｍ－ｌ）を用いて分散演算が可能となる。

本実施例は、複素数間の乗算に関する上記の特徴を利用しており、複素数のデータに係数を乗じた結果の実部および虚部の各数値を得るための各ＬＵＴを、メモリ回路ではなく、予めＬＵＴの要素値を生成する回路と要素値をセレクタ等の論理ゲートを用いて選択する回路としている。このような構成により、第１の実施例と同様の効果を得ることができる。

すなわち、従来のように各ＬＵＴがメモリ回路であった場合、データの全ビット位置について同時にＬＵＴを検索する並列化や、複素数係数ＣをＭ個の複素数のデータＸ［ｍ］（ｍ＝１，・・・，Ｍ）の各々に乗じるための複素数乗算回路の並列化によって、スループットを高くしようとしたときに、データのビット位置毎や積和演算回路毎に、ＬＵＴをコピーした複数個のメモリ回路を備える必要がある。

本実施例の演算回路では、ＬＵＴにメモリ回路を用いていないため、ＬＵＴの各要素値を事前に生成・保持する回路（ＬＵＴ生成回路１ａ）と、ＬＵＴの各要素値を選択する回路（実部演算用ＬＵＴ索引回路２０５ｍ－ｌおよび虚部演算用ＬＵＴ索引回路２１０ｍ－ｌ）に分けることが可能であり、ＬＵＴ生成回路１ａを並列化せずに実部演算用ＬＵＴ索引回路２０５ｍ－ｌおよび虚部演算用ＬＵＴ索引回路２１０ｍ－ｌのみを並列化する。これにより、冗長な回路の構成、すなわちＬＵＴの各要素値を保持する回路の並列化（コピー）を防止することができ、並列化に伴う回路規模の増大を抑制することができる。

なお、本実施例の演算回路は、複素数の乗算に適用した場合に、実部計算用と虚部計算用のＬＵＴに分けて、各ＬＵＴの要素値を生成・分配するのではなく、実部計算用ＬＵＴと虚部計算用ＬＵＴの要素値のうち、共通する要素であるｃ＿ｒｅａｌについては生成・分配を共通化している。さらに、虚部計算用ＬＵＴの要素値であるｃ＿ｉｍａｇについては、実部計算用ＬＵＴの要素に－ｃ＿ｉｍａｇがあるため、ｃ＿ｉｍａｇのみを実部演算用ＬＵＴ索引回路２０５ｍ－ｌ側の符号反転回路２０６によって符号反転することにより、分配に用いられる回路内の配線数を削減している。このような共通化と符号反転により、実部計算用ＬＵＴと虚部計算用ＬＵＴを完全に独立して生成・分配する構成よりも回路規模および消費電力を削減することができる。

［第４の実施例］
次に、本発明の第４の実施例について説明する。図９は本発明の第４の実施例に係る演算回路の構成を示すブロック図であり、図６と同一の構成には同一の符号を付してある。本実施例は、第３の実施例に示した演算回路に対して、回路規模や消費電力の増大なく、スループットを改善する構成を示す。

図９の演算回路は、図６に示した演算回路と同じく、各々が実部値ｘ＿ｒｅａｌ［ｍ］と虚部値ｘ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個（Ｍは２以上の整数）の複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとに分かれる複素数係数Ｃとを入力とする。なお、データｘ［ｍ，ｎ］（ｍ＝１，・・・，Ｍ、ｎ＝１，・・・，Ｎ）は、負の値も取り得る符号付き数値（２の補数による２進数で表現された数値）である。

図９の演算回路は、図６に示した演算回路と同じく、上記入力に対して、実部値ｙ＿ｒｅａｌ［ｍ］と虚部値ｙ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個の複素数値Ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を、分散演算により取得し出力する。Ｍ個の複素数値Ｙ［ｍ］は、各々が（Ｃ×Ｘ［ｍ］）に相当する。すなわち、実部値ｙ＿ｒｅａｌ［ｍ］は、ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］に相当する。虚部値ｙ＿ｉｍａｇ［ｍ］は、ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］に相当する。

図９の演算回路は、１個のＬＵＴ生成回路１ａと、１個のＬＵＴラッチ回路３ａと、Ｍ個（Ｍは２以上の整数）の分散演算回路２ａ－１～２ａ－Ｍから構成される。

ＬＵＴ生成回路１ａは、複素数係数Ｃの実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとを入力とし、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの差ｃ＿ｒｅａｌ－ｃ＿ｉｍａｇに相当する値ｄ＿ｓｕｂと、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの和ｃ＿ｒｅａｌ＋ｃ＿ｉｍａｇに相当する値ｄ＿ａｄｄとをそれぞれ計算し、実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと共に値ｄ＿ｓｕｂおよびｄ＿ａｄｄをＬＵＴラッチ回路３ａに出力する。

ＬＵＴラッチ回路３ａは、ＬＵＴ生成回路１ａから出力されたｃ＿ｒｅａｌ、ｃ＿ｉｍａｇ、ｄ＿ｓｕｂ、ｄ＿ａｄｄを入力とし、クロックパルスの入力毎に、ｃ＿ｒｅａｌ、ｃ＿ｉｍａｇ、ｄ＿ｓｕｂ、ｄ＿ａｄｄの各値をラッチして、次のクロックパルスの入力まで保持する回路である。ＬＵＴラッチ回路３ａは、ｃ＿ｒｅａｌ、ｃ＿ｉｍａｇ、ｄ＿ｓｕｂ、ｄ＿ａｄｄの各値の各ビットの値をクロックに同期して保持するフリップフロップによって実現できる。そして、ＬＵＴラッチ回路３ａは、保持したｃ＿ｒｅａｌ、ｃ＿ｉｍａｇ、ｄ＿ｓｕｂ、ｄ＿ａｄｄを、各分散演算回路２ａ－１～２ａ－Ｍに出力する。

分散演算回路２ａ－ｍ（ｍは１～Ｍの整数）の各々は、第３の実施例と同様に、複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、ＬＵＴラッチ回路３から分配された実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと値ｄ＿ｓｕｂおよびｄ＿ａｄｄとを入力とし、複数数Ｘ［ｍ］のうち自回路に対応するデータの各々に複素数係数Ｃを乗じて合算した結果である複素数値Ｙ［ｍ］（ｍ＝１，・・・，Ｍ）を、Ｍ個の各々について並列に計算して出力する。

分散演算回路２ａ－ｍは、値０、ｃ＿ｒｅａｌ、－ｃ＿ｉｍａｇ、ｄ＿ｓｕｂを各要素の数値とする実部演算用ＬＵＴと、値０、ｃ＿ｉｍａｇ、ｃ＿ｒｅａｌ、ｄ＿ａｄｄを各要素の数値とする虚部演算用ＬＵＴとを構成し、実部演算用ＬＵＴを用いた分散演算によって実部の積和演算ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］の結果を取得してｙ＿ｒｅａｌ［ｍ］として出力すると共に、虚部演算用ＬＵＴを用いた分散演算によって虚部の積和演算ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］の結果を取得してｙ＿ｉｍａｇ［ｍ］として出力する。分散演算回路２ａ－ｍの構成は第３の実施例で説明したとおりである。

図９の演算回路は、図６の演算回路と比較して、ＬＵＴラッチ回路３ａがＬＵＴ生成回路１ａと分散演算回路２ａ－１～２ａ－Ｍの間に挿入されている点が異なる。すなわち、ＬＵＴ生成回路１ａとＭ並列の分散演算回路２ａ－ｍ（ｍ＝１，・・・，Ｍ）とがパイプライン構成となっている。

図６の演算回路では、ＬＵＴ生成回路１ａ内で、複素数係数Ｃからｄ＿ｓｕｂおよびｄ＿ａｄｄを計算する処理時間である生成時間Ｔｄ＿ＬＵＴと、分散演算回路２ａ－ｍ内でｙ＿ｒｅａｌ［ｍ］およびｙ＿ｉｍａｇ［ｍ］を生成する処理時間である分散演算時間Ｔｄとの合計時間、すなわち（Ｔｄ＿ＬＵＴ＋Ｔｄ）によって、演算回路を含むシステムのクロック周波数の上限が制約される。
一方、図９の演算回路では、生成時間Ｔｄ＿ＬＵＴと分散演算時間Ｔｄのそれぞれによって、演算回路を含むシステムのクロック周波数の上限が制約される。

すなわち、図６の演算回路を採用したシステムのクロック周波数の上限値は １／（Ｔｄ＿ＬＵＴ＋Ｔｄ）であるのに対して、図９の演算回路を採用したシステムのクロック周波数の上限値は、１／Ｔｄ＿ＬＵＴと１／Ｔｄのうち値が小さい方になる。つまり、図６の演算回路よりも、図９の演算回路の方が、高速に動作する。

通常、処理の流れが一方向の回路は、パイプライン構成の採用によって、高速化（スループット向上）が可能となるが、フリップフロップが多数使用されるため、回路規模や消費電力が増大するという課題が存在する。
本実施例において、パイプライン構成での課題となるフリップフロップは、ＬＵＴラッチ回路３ａ内で、ｃ＿ｒｅａｌ、ｃ＿ｉｍａｇ、ｄ＿ｓｕｂ、ｄ＿ａｄｄをクロックに同期して保持する回路に使用されるフリップフロップのみである。分散演算回路２ａ－１～２ａ－Ｍの並列数Ｍが大きい場合、演算回路全体に対するフリップフロップの規模の割合はわずかであり、本実施例に示したパイプライン構成の採用によって生じる回路規模や消費電力の増加は問題とならない。

また、分散演算を用いない、乗算回路と加算回路を組み合わせて構成された一般的な複素数乗算回路に対してパイプライン構成化する場合、乗算回路と加算回路の間にフリップフロップを挿入する構成を採ることが可能である。乗算回路と加算回路の間に挿入すべきフリップフロップ数は、複素数乗算の並列数Ｍに比例するので、演算回路全体に対するフリップフロップの規模の割合が大きく、パイプライン構成の採用によって生じる回路規模や消費電力の増加が問題となる。しかし、本実施例に示した演算回路では、パイプライン構成化により挿入されるフリップフロップ数は、演算の並列数Ｍに比例して増加することはなく、少ないＬＵＴの要素数に比例した個数で済む。

このように、従来の複素数乗算回路ではパイプライン構成化に伴って回路規模・消費電力が大幅に増大するが、本実施例に示したようにＬＵＴ生成回路１ａとＭ並列の分散演算回路２ａ－ｍ（ｍ＝１，・・・，Ｍ）とを分けたパイプライン構造とすることにより、本実施例の演算回路は、回路規模や消費電力を増大させることなく、スループットを改善できるという、特徴を備える。

なお、第１～第４の実施例で説明した演算回路は例えばＦＰＧＡによって実現することができる。

本発明は、演算回路に適用することができる。

１，２ａ…ＬＵＴ生成回路、２－１～２－Ｍ，２ａ－１～２ａ－Ｍ…分散演算回路、３，３ａ…ＬＵＴラッチ回路、２０ｍ…２項分散演算回路、２１ｍ…２項分散演算結果合算回路、２２ｍ…補助乗算回路２２、２００ｍ…ＬＵＴ索引回路、２０２，２０６，２０７，２１１…符号反転回路、２０３ｍ，２０８ｍ，２１２ｍ…倍数演算回路、２０４，２０９，２１３…合算回路、２０５ｍ…実部演算用ＬＵＴ索引回路、２１０ｍ…虚部演算用ＬＵＴ索引回路。

Claims (7)

1. Ｎ個（Ｎは２以上の整数）のデータｘ［ｍ，ｎ］（ｎ＝１，・・・，Ｎ）の組をＭ組（Ｍは２以上の整数）含むデータセットＸ［ｍ］（ｍ＝１，・・・，Ｍ）と、Ｎ個の係数ｃ［ｎ］とを入力とし、Ｍ個の積和演算の値ｙ［ｍ］を計算して出力する演算回路において、
   前記係数ｃ［ｎ］を２個ずつに組み分けしたときの組毎に計算した値を出力するＬＵＴ生成回路と、
   前記データセットＸ［ｍ］のうちＮ個のデータｘ［ｍ，ｎ］の各々に係数ｃ［ｎ］を乗じて合算した結果である前記積和演算の値ｙ［ｍ］を、前記Ｍ組の各組毎に並列に計算して出力するＭ個の分散演算回路とを備え、
   各分散演算回路は、
   自回路に対応するＮ個のデータｘ［ｍ，ｎ］を２個ずつに組み分けした各値と前記係数ｃ［ｎ］を２個ずつに組み分けした各値と前記ＬＵＴ生成回路によって計算された値とに基づいて、前記Ｎ個のデータｘ［ｍ，ｎ］の各々に前記係数ｃ［ｎ］の各々を乗じて合算した２項積和演算の値を、前記２個ずつに組み分けした各組毎に並列に計算して出力する複数の２項分散演算回路と、
   前記複数の２項分散演算回路によって計算された値を合算した結果を前記積和演算の値ｙ［ｍ］として出力する２項分散演算結果合算回路とから構成され、
   前記ＬＵＴ生成回路は、前記係数ｃ［ｎ］を２個ずつに組み分けした値ｃ［２×ｎ’－１］とｃ［２×ｎ’］（ｎ’＝１，・・・，Ｎ’）の和ｃ［２×ｎ’－１］＋ｃ［２×ｎ’］を値ｄ［ｎ’］としてＮ’個（Ｎ’はＮ／２以下で最大の整数）の組毎に計算し、
   各分散演算回路は、前記データセットＸ［ｍ］と前記ＬＵＴ生成回路から出力された係数ｃ［ｎ］および前記ＬＵＴ生成回路によって計算された値ｄ［ｎ’］とを入力とし、データセットＸ［ｍ］のうち自回路に対応するＮ個のデータｘ［ｍ，ｎ］の各々に係数ｃ［ｎ］を乗じて合算した結果である前記積和演算の値ｙ［ｍ］を出力することを特徴とする演算回路。
2. 請求項１の演算回路において、
   前記ＬＵＴ生成回路と前記Ｍ個の分散演算回路との間に設けられ、前記係数ｃ［ｎ］と前記ＬＵＴ生成回路によって計算された値とをクロックに同期して保持し、保持した値を前記Ｍ個の分散演算回路に出力するＬＵＴラッチ回路をさらに備えることを特徴とする演算回路。
3. 請求項１または２記載の演算回路において、
   各分散演算回路は、
   前記Ｎが奇数の場合にｃ［Ｎ］×ｘ［ｍ，Ｎ］を計算した結果を出力する補助乗算回路をさらに備え、
   前記２項分散演算結果合算回路は、前記Ｎが奇数の場合に、前記複数の２項分散演算回路によって計算された値と前記補助乗算回路によって計算された値とを合算した結果を前記積和演算の値ｙ［ｍ］として出力することを特徴とする演算回路。
4. 請求項１乃至３のいずれか１項に記載の演算回路において、
   前記２項分散演算回路は、
   前記Ｎ個のデータｘ［ｍ，ｎ］のうち同一組の２個の値のビット位置毎に設けられ、値０と、前記係数ｃ［ｎ］のうち同一組の２個の値と、この係数ｃ［ｎ］の２個の値から前記ＬＵＴ生成回路によって計算された値とからなる要素値の中から、前記Ｎ個のデータｘ［ｍ，ｎ］のうち同一組の２個の値を構成する同一ビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の索引回路と、
   前記複数の索引回路によって取得された要素値を、それぞれ２^{（ｌ－１）}倍（ｌはビット位置の番号）することをビット位置毎に行う複数の倍数演算回路と、
   前記複数の倍数演算回路によって計算された値を合算した結果を前記２項積和演算の値として出力する合算回路とから構成されることを特徴とする演算回路。
5. Ｍ個（Ｍは２以上の整数）の各々が実部値ｘ＿ｒｅａｌ［ｍ］と虚部値ｘ＿ｉｍａｇ［ｍ］（ｍ＝１，・・・，Ｍ）とに分かれる、Ｍ個の複素数Ｘ［ｍ］（ｍ＝１，・・・，Ｍ）と、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇとに分かれる複素数係数Ｃとを入力とし、実部の積和演算の結果と虚部の積和演算の結果とからなるＭ個の複素数値Ｙ［ｍ］を計算して出力する演算回路において、
   前記複素数係数Ｃの実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの差の値ｄ＿ｓｕｂと、実部値ｃ＿ｒｅａｌと虚部値ｃ＿ｉｍａｇの和の値ｄ＿ａｄｄとを計算するＬＵＴ生成回路と、
   前記複素数Ｘ［ｍ］のうち自回路に対応するデータの各々に前記複素数係数Ｃを乗じて合算した結果である前記複素数値Ｙ［ｍ］を、前記Ｍ個の各々について並列に計算して出力するＭ個の分散演算回路とを備え、
   各分散演算回路は、前記複素数Ｘ［ｍ］と前記複素数係数Ｃの実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと前記ＬＵＴ生成回路によって計算された値ｄ＿ｓｕｂおよびｄ＿ａｄｄとを入力とし、前記実部の積和演算ｃ＿ｒｅａｌ×ｘ＿ｒｅａｌ［ｍ］－ｃ＿ｉｍａｇ×ｘ＿ｉｍａｇ［ｍ］の結果であるｙ＿ｒｅａｌ［ｍ］と、前記虚部の積和演算ｃ＿ｉｍａｇ×ｘ＿ｒｅａｌ［ｍ］＋ｃ＿ｒｅａｌ×ｘ＿ｉｍａｇ［ｍ］の結果であるｙ＿ｉｍａｇ［ｍ］とを、前記Ｍ個の各々について並列に計算して出力することを特徴とする演算回路。
6. 請求項５の演算回路において、
   前記ＬＵＴ生成回路と前記Ｍ個の分散演算回路との間に設けられ、前記複素数係数Ｃの実部値ｃ＿ｒｅａｌおよび虚部値ｃ＿ｉｍａｇと前記ＬＵＴ生成回路によって計算された値ｄ＿ｓｕｂおよびｄ＿ａｄｄとをクロックに同期して保持し、保持した値を前記Ｍ個の分散演算回路に出力するＬＵＴラッチ回路をさらに備えることを特徴とする演算回路。
7. 請求項５または６記載の演算回路において、
   前記分散演算回路は、
   前記複素数Ｘ［ｍ］の実部値ｘ＿ｒｅａｌ［ｍ］および虚部値ｘ＿ｉｍａｇ［ｍ］のビット位置毎に設けられ、値０、ｃ＿ｒｅａｌ、－ｃ＿ｉｍａｇ、ｄ＿ｓｕｂからなる要素値の中から、前記実部値ｘ＿ｒｅａｌ［ｍ］および前記虚部値ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の第１の索引回路と、
   前記複数の第１の索引回路によって取得された要素値を、それぞれ２^{（ｌ－１）}倍（ｌはビット位置の番号）することをビット位置毎に行う複数の第１の倍数演算回路と、
   前記複数の第１の倍数演算回路によって計算された値を合算した結果を前記実部の積和演算の値ｙ＿ｒｅａｌ［ｍ］として出力する第１の合算回路と、
   前記複素数Ｘ［ｍ］の実部値ｘ＿ｒｅａｌ［ｍ］および虚部値ｘ＿ｉｍａｇ［ｍ］のビット位置毎に設けられ、値０、ｃ＿ｉｍａｇ、ｃ＿ｒｅａｌ、ｄ＿ａｄｄからなる要素値の中から、前記実部値ｘ＿ｒｅａｌ［ｍ］および前記虚部値ｘ＿ｉｍａｇ［ｍ］のうち自回路に対応するビット位置の２個の値に対応する１個の要素値をビット位置毎に取得する複数の第２の索引回路と、
   前記複数の第２の索引回路によって取得された要素値を、それぞれ２^{（ｌ－１）}倍することをビット位置毎に行う複数の第２の倍数演算回路と、
   前記複数の第２の倍数演算回路によって計算された値を合算した結果を前記虚部の積和演算の値ｙ＿ｉｍａｇ［ｍ］として出力する第２の合算回路とから構成されることを特徴とする演算回路。

Images