(57)【特許請求の範囲】
【請求項１】
指定されたアドレスに複数のデータを上書きの形で同時に書き込み又は同時に読み出せる複数個のメモリバンクと、
前記複数個のメモリバンクから同時に読み出された複数の被演算データが供給されると、前記複数の被演算データを用いＲａｄｉｘ４のＦＦＴ処理としての演算処理を行って複数の演算結果を同時に出力し、前記演算処理を所定回数繰り返す演算回路と、
前記演算回路から同時に出力された前記複数の演算結果を複数段に亘って保持可能な複数個の保持回路を有し、前記演算回路の次回の演算処理時に必要な複数のデータを同時に前記演算回路に供給可能となるように、前記複数個の保持回路に前記複数段に亘って保持された演算結果の中から前記複数のデータを選択して前記複数のメモリバンクの各々に分配出力するメモリ制御回路と、
を備えたことを特徴とする演算装置。
【請求項２】
前記演算回路は、高速フーリエ変換処理又は逆高速フーリエ変換処理を行う回路であることを特徴とする請求項１記載の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、高速フーリエ変換（Fast  Fourier  Transformation、以下「ＦＦＴ」という。）や、このＦＦＴの１つである逆ＦＦＴ（InverseＦＦＴ、以下「ＩＦＦＴ」」という。）の処理をハード（回路）で実行する演算装置において、ＦＦＴ（又はＩＦＦＴ）の演算を行う演算手段と、この演算時に使用するデータを格納する複数のメモリバンクとの間に位置し、ＦＦＴ（又はＩＦＦＴ）処理を実現するために要求されるメモリ量を削減するために、データをどのメモリバンクに書き込むかを制御するメモリ制御手段と、を備えた演算装置に関するものである。
【背景技術】
【０００２】
近年、通信処理において直交波周波数分割多重（Orthogonal  Frequency  Division  Multiplexing、以下「ＯＦＤＭ」という。）が多用され、具体的には  地上波デジタル放送、ＩＥＥＥ８０２．１１ａ、ｇ等の無線ローカル・エリア・ネットワーク（ＬＡＮ）、電力線モデム等の伝送方式に採用されている。
【０００３】
ＯＦＤＭの処理の大部分はＦＦＴ（又はＩＦＦＴ）処理であり、ＯＦＤＭを実現するためには高速動作するＦＦＴ（又はＩＦＦＴ）回路を小さく実現する必要がある。高速処理を実現するためにＦＦＴ（又はＩＦＦＴ）処理は、ハードウェアで実現されるのが一般的である。このＦＦＴについての概略が、例えば、非特許文献１に記載されている。
【０００４】
この非特許文献１に記載されているように、Ｎ点の離散Fourier変換（以下「ＤＦＴ」という。）を計算するためにはＮ２  回の計算が必要であるが、ＦＦＴを用いるとＮlogＮに比例する計算で済む。このＦＦＴの基本原理は、簡単な添字の変換で大きなサイズのＤＦＴを計算が楽な小さなＤＦＴに分解するという考えに基づいている。
例えば、Ｎ点のＤＦＴの（１）式を計算する場合を考える。
【０００５】
【数１】
0005444287.tif 000002
【０００６】
この場合、Ａ０〜ＡＮ−１までの各項の計算にＮ回の乗算が入るため、全体でＮ２  回の乗算が必要となるが、仮にＮが２で割り切れるならば、添字ｋを偶数と奇数に分けることで、Ｎ点のＤＦＴを２つのＮ／２点のＤＦＴにおける（２）式と（３）式に分解出来る。
【０００７】
【数２】
0005444287.tif 000003
【０００８】
【数３】
0005444287.tif 000004
【０００９】
Ｎ／２点のＤＦＴの（２）式及び（３）式は、それぞれＮ２／４回の乗算で計算出来るので、この分解で計算量が約半分に減る。更に、この分解を２回、３回と繰り返せば計算量は約１／４、１／８と減少する。これがCooley-TukeyＦＦＴ（即ち、基数２、周波数間引きCooley-TukeyＦＦＴ）の基本的な考え方である。
【００１０】
図５は、非特許文献１の図１に記載された基数２周波数間引きＦＦＴのデータフローを示す図である。
【００１１】
（２）式、（３）式の分解をlog２Ｎ回行い、１点のＤＦＴになるまで行ったときの計算量を考える。この分解自体には各々の段でＷｊＮを乗ずるＮ／２回の複素数乗算とＮ回の複素数加算が必要で、複素数乗算回数は（Ｎ／２）log２Ｎに減少する。そのため、浮動小数点演算の量はＮlog２Ｎのオーダとなる。これは、Cooley-TukeyＦＦＴの典型的な演算量であり、様々なＦＦＴの演算量の削減アルゴリズムは、基本的にこのオーダの比例定数と、Ｎlog２Ｎより低い次数の項を小さくするものである。
【００１２】
次に、ＦＦＴの添字による一般的な分解方法について説明する。
例えば、ＮがＮ＝Ｎ１Ｎ２と因数分解出来ると仮定する。（１）式の添字ｊを次の２つの添字ｊ１（＝０，１，２，・・・，Ｎ１−１）とｊ２（＝０，１，２，・・・，Ｎ２−１）に置き換える。添字ｊ１，ｊ２をある自然数として、ｊ１，ｊ２からｊに変換する写像を（４）式のように定義する。
【００１３】
【数４】
0005444287.tif 000005
【００１４】
先ず第１に、（４）式の写像は、１対１とならなければならないが、このための必要十分条件は、ｐ，ｑをある自然数とするとき、次の（ａ）、（ｂ）の２つである。
（ａ）  Ｎ１とＮ２が互いに素の場合
Ｊ１＝ｐＮ２，Ｊ２＝ｑＮ１の少なくとも一方が満たされ、且つgcd（Ｊ１，Ｎ１）＝gcd（Ｊ２，Ｎ２）＝１
（ｂ）  Ｎ１とＮ２が互いに素ではない場合
【００１５】
【数５】
0005444287.tif 000006
【００１６】
（１）式に対してこれらの変換を適用すると、（６）式のようになる。
【００１７】
【数６】
0005444287.tif 000007
【００１８】
この（６）式中の２番目と３番目のＷの項が邪魔になるので、（６）式のままでは演算ブロックの順序を入れ換えることができず、小さなＤＦＴに分解することはできない。仮に、（７）式のような条件Ｊ１Ｋ２，Ｊ２Ｋ１の少なくとも一方が成り立つのならば、（６）式はＮ１とＮ２の２つの小さなＤＦＴに分解されることが分かる。
【００１９】
【数７】
0005444287.tif 000008
【００２０】
（７）式の条件を満たす例として、次の（ｉ）、（ｉｉ）の２種類の分解が考えられる。
（ｉ）  Ｎ１とＮ２が互いに素の場合
Ｊ１＝Ｎ２、且つＪ２＝Ｎ１、且つＫ１＝Ｎ２、且つＫ２＝Ｎ１
（ｉｉ）  Ｎ１とＮ２が任意の場合
Ｊ１＝Ｎ２、且つＪ２＝１、且つＫ１＝１、且つＫ２＝Ｎ１
又は
Ｊ１＝１、且つＪ２＝Ｎ１、且つＫ１＝Ｎ２、且つＫ２＝１
【００２１】
このような第１の場合は、N1とN2が互いに素の場合のみに用いられる分解であり、（６）式のWの項を２つ消去してN1とN2の２次元DFTに分解する。この分解は、N1，N2を互いに素になるように選ぶ必要があるが、分解に必要な演算量は零である。しかし、分解しきれずに残ったDFTは概ね素数の長さであり、ある程度の計算量は必要になる。この分解によるＦＦＴは素因数ＦＦＴ［５，２，７］やWinograd  ＤＦＴアルゴリズム［５，９］に用いられる。
【００２２】
一方、第２の分解は、Ｎ１とＮ２は任意でよい代わりに、（６）式のＷの項は１つしか消去されず、Ｎ１とＮ２のＤＦＴへの分解にＷを乗算する演算（回転因子の乗算）が必要になる。しかし、Ｎ１又はＮ２をＤＦＴが容易に計算出来る数に固定出来るため、分解以外に必要な計算量は少なくなる。この分解によるＦＦＴはCooley-TukeyＦＦＴ［３］であり、Ｎ１を固定して分解を再帰的に繰り返すのが基本アルゴリズムである。このときＮ１を基数といい、（６）式の２項目のＷ  を消し去るのが周波数間引き、３項目のＷを消し去るのが時間間引きアルゴリズムと呼ばれる。このCooley-TukeyＦＦＴには多くの種類があり、通常の基数２のＦＦＴ、任意基数ＦＦＴ、混合基数ＦＦＴ、演算量が少ないとされるSplit-Radix  ＦＦＴ［４，６，８］等が挙げられる。
以上が非特許文献１に記載されたＦＦＴの概略の説明である。
【００２３】
ＦＦＴ（又はＩＦＦＴ）処理は基数に依って、例えばRadix２（基数＝２）、Radix４（基数＝４）、Radix８（基数＝８）等が使用されるが、Radix４は同一量のデータを処理するために必要な演算量がRadix２の約７５％であるため、良く採用されている。
【００２４】
ＦＦＴ（又はＩＦＦＴ）処理を並列に行う場合、処理の基数に依って同時に必要なデータ数はRadix２の時２複素データ、Radix４の時４複素データである。又、同時にデータを供給するためにはメモリを複数のバンクに分割し、同時に使用されるデータは別のメモリバンクに格納しておく必要がある。
【００２５】
図６は、従来のRadix４ＦＦＴ演算装置を示す概略の構成図である。
このRadix４ＦＦＴ演算装置は、Radix４ＦＦＴ処理をハードで実行する装置であり、Radix４ＦＦＴ演算回路１と、この演算回路１に対して複素データを与えるランダム・アクセス・メモリ（以下「ＲＡＭ」という。）等のメモリ１０とを備えている。メモリ１０は、４個のメモリバンク１１−１〜１１−４に分割され、これらの各メモリバンク１１−１〜１１−４に対してアクセス用のアドレスを与えるための各アドレス発生回路（adr-gen）１２−１〜１２−４がそれぞれ接続されている。４個のメモリバンク１１−１〜１１−４は、ＦＦＴ演算回路１に対して４個の複素データを同時に供給可能となっており、又、複素データの格納も同時に４個可能な構成になっている。
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】大浦拓哉著“高速Fourier変換の概略メモ”、ｐ．１−３、［online］、京都大学数理解析研究所、［平成１７年６月３日検索］、インターネット〈URL:http://www.kurims.kyoto-u.ac.jp/~ooura/fftman/fft_note_s.pdf〉
【発明の概要】
【発明が解決しようとする課題】
【００２７】
図７は、従来のRadix２、Radix４のＦＦＴ（又はＩＦＦＴ）処理の演算フローを示す図である。この図７では、データ数が４２（＝ａ０−ａ１５）の場合の例が示されている。
なお、図７中の実線は加算パス、破線は減算パスを示している。
【００２８】
ここでＦＦＴ処理（又はＩＦＦＴ処理、このＩＦＦＴ処理はＦＦＴ処理と同様に行われるので、以下説明を簡略化するためにＦＦＴ処理について説明する。）に同時に使用されるデータに注目し、Radix２の場合のＦＦＴ処理（１）と、Radix４の場合のＦＦＴ処理（２）について説明する。
【００２９】
（１）  Radix２の場合のＦＦＴ処理
図７のフローで示される１回のＦＦＴ処理（Radix２ＦＦＴ基本演算処理）を左から１段目処理Ｔ１、２段目処理Ｔ２、３段目処理Ｔ３、４段目処理Ｔ４とする。図示しないクロックに同期して１段目処理Ｔ１から４段目処理Ｔ４へ実行されて行く。
【００３０】
１段目処理Ｔ１では、データ（ａ０，ａ８），（ａ１，ａ９），（ａ２，ａ１０），（ａ３，ａ１１），（ａ４，ａ１２），（ａ５，ａ１３），（ａ６，ａ１４），（ａ７，ａ１５）が同時に使用されている。つまり、１段目処理Ｔ１のためにはデータａ０，ａ１，ａ２，ａ３，ａ４，ａ５，ａ６，ａ７が同一メモリバンク（例えば、１１−１）に格納され、データａ８，ａ９，ａ１０，ａ１１，ａ１２，ａ１３，ａ１４，ａ１５が別のメモリバンク（例えば、１１−２）に格納されている必要がある。
【００３１】
２段目処理Ｔ２では、データ（ａ０，ａ４），（ａ１，ａ５），（ａ２，ａ６），（ａ３，ａ７），（ａ８，ａ１２），（ａ９，ａ１３），（ａ１０，ａ１４），（ａ１１，ａ１５）が同時に使用されている。つまり、２段目処理Ｔ２のためにはデータａ０，ａ１，ａ２，ａ３，ａ８，ａ９，ａ１０，ａ１１が同一メモリバンク（例えば、１１−３）に格納され、データａ４，ａ５，ａ６，ａ７，ａ１２，ａ１３，ａ１４，ａ１５が別のメモリバンク（例えば、１１−４）に格納されている必要がある。
【００３２】
ここで、１段目処理Ｔ１の結果としてデータａ０，ａ８は同時に得られるが、２段目処理Ｔ２で使用されることを考慮した場合、データａ０，ａ８は同一のメモリバンクに格納される必要がある。そのため、複数のクロックを用いて、データの格納先の変更処理が必要になり、高速処理を阻害していた。
【００３３】
（２）  Radix４の場合のＦＦＴ処理
ＦＦＴフローグラフで示される１回のＦＦＴ処理（Radix４ＦＦＴ基本演算処理）を左から１段目処理Ｔ１０、２段目処理Ｔ２０とする。
【００３４】
１段目処理Ｔ１０では、データ（ａ０，ａ４，ａ８，ａ１２），（ａ１，ａ５，ａ９，ａ１３），（ａ２，ａ６，ａ１０，ａ１４），（ａ３，ａ７，ａ１１，ａ１８）が同時に使用されている。つまり、１段目処理Ｔ１０のためにはデータａ０，ａ１，ａ２，ａ３がメモリバンク１１−１に格納され、データａ４，ａ５，ａ６，ａ７  がメモリバンク１１−２に格納され、データａ８，ａ９，ａ１０，ａ１１がメモリバンク１１−３に格納され、データａ１２，ａ１３，ａ１４，ａ１５がメモリバンク１１−４に格納されている必要がある。
【００３５】
２段目処理Ｔ２０では、データ（ａ０，ａ１，ａ２，ａ３），（ａ４，ａ５，ａ６，ａ７），（ａ８，ａ９，ａ１０，ａ１１），（ａ１２，ａ１３，ａ１４，ａ１５）が同時に使用されている。つまり、２段目処理Ｔ２０のためにはデータａ０，ａ４，ａ８，ａ１２がメモリバンク１１−１に格納され、データａ１，ａ５，ａ９，ａ１３がメモリバンク１１−２に格納され、データａ２，ａ６，ａ１０，ａ１４がメモリバンク１１−３に格納され、データａ３，ａ７，ａ１１，ａ１５がメモリバンク１１−４に格納されている必要がある。
【００３６】
ところが、１段目処理Ｔ１０の結果として、データａ０，ａ４，ａ８，ａ１２は同時に得られる。２段目処理Ｔ２０の処理で使用されることを考慮した場合、データａ０，ａ４，ａ８，ａ１２は同一のメモリバンクに格納される必要がある。そのため、複数のクロックを用いて、データの格納先の変更処理が必要になり、高速処理を阻害していた。
【００３７】
このような問題を図８を参照しつつ詳細に説明する。
図８は、従来のRadix４のＦＦＴ処理（データ数４５＝１０２４、データａ０〜ａ１０２３）の一例を示す図である。
【００３８】
Radix４の１０２４ポイント（point）のＦＦＴを４個のメモリバンク１１−１〜１１−４で実現する時、データａ０〜ａ１０２３をどのメモリバンク１１−１〜１１−４に入れるかを考える。
【００３９】
（１）  ＦＦＴ１段目処理Ｔ１０の入力
メモリバンク１１−１:  0,1,2,3,4,5,…,255
メモリバンク１１−２:  256,257,258,259,…,511
メモリバンク１１−３:  512,513,514,515,…,767
メモリバンク１１−４:  768,769,770,771,  …,1023
（２）  ＦＦＴ２段目処理Ｔ２０の入力
メモリバンク１１−１:  0,1,…,63,      256,257,…,319,  512,513,…,575,  768,769,…,831
メモリバンク１１−２:  64,65,…,127,    320,321,…,383,  576,577,…,639,  832,833,…,895
メモリバンク１１−３:  128,129,…,191,  384,385,…,447,  640,641,…,703,  896,897,…,959
メモリバンク１１−３:  192,193,…,255,  448,449,…,511,  704,705,…,767,  960,961,…,1023
（３）  ＦＦＴ３段目処理Ｔ３０の入力
メモリバンク１１−１:0,1,…,15,    64,65,…,79,    128,129,…,143,  …  960,961,…,975
メモリバンク１１−２:16,17,…,31,  80,81,…,95,    144,145,…,159,  …  976,977,…,991
メモリバンク１１−３:32,33,…,47,  96,97,…,111,    160,161,…,175,  …  992,993,…,1007
メモリバンク１１−３:48,49,…,63,  112,113,…,127,  176,177,…,191,  …  1008,1009,…,1023
（４）  ＦＦＴ４段目処理Ｔ４０の入力
メモリバンク１１−１:0,1,2,3,      16,17,18,19,  32,33,34,35,  …  1008,1009,1010,1011
メモリバンク１１−２:4,5,6,7,      20,21,22,23,  36,37,38,39,  …  1012,1013,1014,1015
メモリバンク１１−３:8,9,10,11,    24,25,26,27,  40,41,42,43,  …  1016,1017,1018,1019
メモリバンク１１−３:12,13,14,15,  28,29,30,31,  44,45,46,47,  …  1020,1021,1022,1023
（５）  ＦＦＴ５段目処理Ｔ５０の入力
メモリバンク１１−１:  0,  4,  8,  12,  …  1008,1012,1016,1020
メモリバンク１１−２:  1,  5,  9,  13,  …  1009,1013,1017,1021
メモリバンク１１−３:  2,  6,  10,  14,  …  1010,1014,1018,1022
メモリバンク１１−３:  3,  7,  11,  15,  …  1011,1015,1019,1023
【００４０】
これから分かるように、単純にデータａ０〜ａ１０２３順にＦＦＴを行うと、次段のＦＦＴ処理時にデータを提供できない。つまり、ＦＦＴの１段目処理Ｔ１０ではメモリバンク１１−１であるデータａ０〜ａ２５５は、ＦＦＴの２段目処理Ｔ２０では６４個づつの４メモリバンク１１−１〜１１−４となる。
【課題を解決するための手段】
【００４３】
本発明の演算装置は、指定されたアドレスに複数のデータを上書きの形で同時に書き込み又は同時に読み出せる複数個のメモリバンクと、前記複数個のメモリバンクから同時に読み出された複数の被演算データが供給されると、前記複数の被演算データを用いＲａｄｉｘ４のＦＦＴ処理としての演算処理を行って複数の演算結果を同時に出力し、前記演算処理を所定回数繰り返す演算回路と、前記演算回路から同時に出力された前記複数の演算結果を複数段に亘って保持可能な複数個の保持回路を有し、前記演算回路の次回の演算処理時に必要な複数のデータを同時に前記演算回路に供給可能となるように、前記複数個の保持回路に前記複数段に亘って保持された演算結果の中から前記複数のデータを選択して前記複数個のメモリバンクの各々に分配出力するメモリ制御回路と、を備えている。
【発明の効果】
【００４４】
本発明の演算装置によれば、メモリ制御回路により、演算回路から出力される演算結果のデータ順を入れ替えて複数個のメモリバンクに読み込むようにしているので、次の（１）、（２）のような効果がある。
【００４５】
（１）  演算回路の１回の演算結果データを次回の演算処理に最適なメモリバンクに格納することが可能となる。これより演算処理を中断することなく、効率よく実現出来る。
【００４６】
（２）  或る回の演算処理で使用されたデータと同じメモリバンクアドレスに次回の演算処理で使用されるデータを書き込むことが可能となるため、従来は２面それぞれ必要だった複数個のメモリバンクをそれぞれ１面にすることが出来、ハード規模を小さくすることが可能となる。
【図面の簡単な説明】
【００４７】
【図１】本発明の実施例１のRadix４ＦＦＴ演算装置を示す概略の構成図である。
【図２】図１（ｂ）のレジスタにおけるデータ格納状態を示す図である。
【図３】本発明の実施例２を示すRadix２＆Radix４兼用型のRadix２＆Radix４ＦＦＴ演算回路及びＦＦＴメモリ制御回路の構成図である。
【図４】図３のレジスタにおけるデータ格納状態を示す図である。
【図５】非特許文献１に記載された基数２周波数間引きＦＦＴのデータフローを示す図である。
【図６】従来のRadix４ＦＦＴ演算装置を示す概略の構成図である。
【図７】従来のRadix２、Radix４のＦＦＴ処理の演算フローを示す図である。
【図８】従来のRadix４のＦＦＴ処理の一例を示す図である。
【発明を実施するための形態】
【００４８】
本発明を実施するための形態は、以下の好ましい実施例の説明を添付図面と照らし合わせて読むと、明らかになるであろう。
【実施例１】
【００４９】
（実施例１の構成）
図１（ａ）、（ｂ）は、本発明の実施例１のRadix４ＦＦＴ演算装置を示す概略の構成図であり、同図（ａ）が全体図、及び同図（ｂ）がその中のＦＦＴメモリ制御回路の構成図である。
【００５０】
図１（ａ）に示すRadix４ＦＦＴ演算装置は、Radix４ＦＦＴ処理をハードで実行する装置であり、従来の図６と同様に、演算手段（例えば、Radix４ＦＦＴ演算回路）２０と、この演算回路２０に対して複素データを与えるＲＡＭ等のメモリ３０とを備えている。メモリ３０は、複数個（例えば、４個）のメモリバンク３１−１〜３１−４に分割され、これらの各メモリバンク３１−１〜３１−４に対してアクセス用のアドレスを指定するための各アドレス発生回路（adr-gen）３２−１〜３２−４がそれぞれ接続されている。４個のメモリバンク３１−１〜３１−４は、ＦＦＴ演算回路２０に対して４個の複素データを同時に供給可能となっており、又、複素データの格納も同時に４個可能な構成になっている。
【００５１】
本実施例１のRadix４ＦＦＴ処理装置では、Radix４ＦＦＴ演算回路２０とメモリ３０との間に、データ順を入れ替えるためのメモリ制御手段（例えば、ＦＦＴメモリ制御回路）４０が新たに設けられている点が、従来の装置と異なっている。ＦＦＴメモリ制御回路４０は、ＦＦＴ演算回路２０から４個の演算結果が入力され、同時に次段のＦＦＴ処理を考慮して（即ち、同時に必要なデータが同時に提供可能なようにバンク分けして）、データ順を入れ替えた演算結果をメモリ３０へ出力する回路である。
【００５２】
例えば、１段目のＦＦＴ処理を０，６４，１２８，１９２，１，６５，１２９，１９３，・・・の順番で行う。すると出力は、
1段目０：      0,256,512,768  ←  2段目ではメモリバンク３１−１
１段目64：  64,320,576,832←  2段目ではメモリバンク３１−２
１段目128：    128,384,640,896←  2段目ではメモリバンク３１−３
１段目192：    192,448,704,960←  2段目ではメモリバンク３１−４
となる。これにＦＦＴメモリ制御回路４０を使用することで、２段目のＦＦＴ処理時に同時出力可能なようにメモリバンク３１−１〜３１−４に書き込むことが出来る。
【００５３】
図１（ｂ）に示すＦＦＴメモリ制御回路４０は、ＦＦＴ演算回路２０から出力されたデータ等を保持するための複数個の初段データ保持回路及び複数個且つ複数段の後段データ保持回路（例えば、４×４個のレジスタ（Reg））４１−００〜４１−０３，・・・，４１−３０〜４１−３３と、各段のレジスタ間に設けられた複数個の段間セレクタ（例えば、６個の２入力１出力のセレクタ）４２−００〜４１−３３と、メモリバンク３１−１〜３１−４へデータを出力するために出力段に設けられた複数個の出力段セレクタ（例えば、４個の４入力１出力のセレクタ）４３−１〜４３−４とを有している。
【００５４】
各セレクタ４２−００〜４１−３３，４３−１〜４３−４の入出力は、図示しない制御信号等により切り替えられるようになっている。レジスタ間のセレクタ４２−００〜４１−３３の内、１段目セレクタ４２−００は、１段目レジスタ４１−００，４１−０１の出力のいずれか一方を選択して２段目レジスタ４１−１０へ与え、２段目セレクタ４２−１０は、２段目レジスタ４１−１０の出力又は１段目レジスタ４１−０２の出力のいずれか一方を選択して３段目レジスタ４１−２０へ与え、２段目セレクタ４２−１１は、２段目レジスタ４１−１１，４１−１２の出力のいずれか一方を選択して３段目レジスタ４１−２１へ与え、３段目セレクタ４２−２０は、３段目レジスタ４１−２０の出力又は１段目レジスタ４１−０３の出力のいずれか一方を選択して４段目レジスタ４１−３０へ与え、３段目セレクタ４２−２１は、３段目レジスタ４１−２１の出力又は２段目レジスタ４１−１３の出力のいずれか一方を選択して４段目レジスタ４１−３１へ与え、３段目セレクタ４２−２２は、３段目レジスタ４１−２２，４１−２３の出力のいずれか一方を選択して４段目レジスタ４１−３２へ与えるように接続されている。
【００５５】
出力段のセレクタ４３−１〜４３−４の内、セレクタ４３−１は、４段目レジスタ４１−３０〜４１−３３の出力のいずれか１つを選択してメモリバンク３１−１へ与え、セレクタ４３−２は、４段目レジスタ４１−３２又は３段目レジスタ４１−２０〜４１−２２の出力のいずれか１つを選択してメモリバンク３１−２へ与え、セレクタ４３−３は、４段目レジスタ４１−３０、３段目レジスタ４１−２１又は２段目レジスタ４１−１０，４１−１１の出力のいずれか１つを選択してメモリバンク３１−３へ与え、セレクタ４３−４は、４段目レジスタ４１−３０、３段目レジスタ４１−２０、２段目レジスタ４１−１０又は１段目レジスタ４１−００の出力のいずれか１つを選択してメモリバンク３１−４へ与えるように接続されている。
【００５６】
（実施例１のメモリ制御方法）
図２は、図１（ｂ）のレジスタ４１−００〜４１−３３の時刻（以下「Time」という。）０〜Time３におけるデータ格納状態を示す図である。
【００５７】
図２において、例えば、Time０では、１０２４ポイント（以下「point」という。）のRadix４ＦＦＴの１段目の４回目の処理結果がＦＦＴメモリ制御回路４０に入った時を示している。この時、レジスタ４１−００にpoint１９２の１段目ＦＦＴ処理結果が入り、レジスタ４１−１０にpoint１２８の１段目ＦＦＴ処理結果が入っていることを示している。又、括弧［  ］書きの数字がメモリ３０への出力データ、括弧（  ）書きの数字がＦＦＴ演算回路２０からの入力データを示している。図２の他のTime１〜Time３を示す図も同様である。
【００５８】
ＦＦＴメモリ制御回路４０では、図示しないクロックに同期して、以下の（１）〜（５）のようなTime０〜Time３の処理を繰り返す。
【００５９】
（１）  Time０の処理
Time０では同時に以下の処理を行う。
レジスタ４１−３０（point０の処理結果）をセレクタ４３−１からメモリバンク３１−１に出力し、レジスタ４１−０３（point９６０の処理結果）をセレクタ４２−２０を介してレジスタ４１−３０に入力する。
レジスタ４１−２０（point６４の処理結果）をセレクタ４３−２からメモリバンク３１−２に出力し、レジスタ４１−０２（point７０４の処理結果）をセレクタ４２−１０を介してレジスタ４１−２０に入力する。
レジスタ４１−１０（point１２８の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−０１（point４４８の処理結果）をセレクタ４２−００を介してレジスタ４２−１０に入力する。
レジスタ４１−００（point１９２の処理結果）をセレクタ４３−４からメモリバンク３１−４に出力し、ＦＦＴ演算回路２０からpoint１の処理結果をレジスタ４１−００に入力する。
レジスタ４１−０１にＦＦＴ演算回路２０からpoint２５７の処理結果を入力する。
レジスタ４１−０２にＦＦＴ演算回路２０からpoint５２３の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０からpoint７６９の処理結果を入力する。
【００６０】
（２）  Time１の処理
Time１では同時に以下の処理を行う。
レジスタ４１−３１（point２５６の処理結果）をセレクタ４３−１からメモリバンク３１−１に出力し、レジスタ４１−１３（point８９６の処理結果）をセレクタ４２−２１を介してレジスタ４１−３１に入力する。
レジスタ４１−２１（point３２０の処理結果）をセレクタ４３−２からメモリバンク３１−２に出力し、レジスタ４１−１２（point６４０の処理結果）をセレクタ４２−１１を介してレジスタ４１−２１に入力する。
レジスタ４１−１１（point３８４の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−０１（point２５７の処理結果）をレジスタ４１−１１に入力する。
レジスタ４１−１０（point４４８の処理結果）をセレクタ４３−４からメモリバンク３１−４に出力し、レジスタ４１−００（point１の処理結果）をセレクタ４２−００を介してレジスタ４１−１０に入力する。
レジスタ４１−１２にレジスタ４１−０２（point５２３の処理結果）を入力する。
レジスタ４１−１３にレジスタ４１−０３（point７６９の処理結果）を入力する。
レジスタ４１−００にＦＦＴ演算回路２０からpoint６５の処理結果を入力する。
レジスタ４１−０１にＦＦＴ演算回路２０からpoint３２１の処理結果を入力する。
レジスタ４１−０２にＦＦＴ演算回路２０からpoint５７７の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０からpoint８３３の処理結果を入力する。
【００６１】
（３）  Time２の処理
Time２では同時に以下の処理を行う。
レジスタ４１−３２（point５１２の処理結果）をセレクタ４３−１からメモリバンク３１−１に出力し、レジスタ４１−２３（point８３２の処理結果）をセレクタ４２−２２を介してレジスタ４１−３２に入力する。
レジスタ４１−２２（point５７６の処理結果）をセレクタ４３−２からメモリバンク３１−２に出力し、レジスタ４１−１２（point５２３の処理結果）をレジスタ４１−２２に入力する。
レジスタ４１−２１（point６４０の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−１１（point２５７の処理結果）をセレクタ４２−１１を介してレジスタ４１−２１に入力する。
レジスタ４１−２０（point７０４の処理結果）をセレクタ４３−４を介してメモリバンク３１−４に出力し、レジスタ４１−１０（point１の処理結果）をセレクタ４２−１０を介してレジスタ４１−２０に入力する。
レジスタ４１−２３にレジスタ４１−１３の値を入力する。
レジスタ４１−１０にセレクタ４２−００を介してレジスタ４１−００の値を入力する。
レジスタ４１−１１にレジスタ４１−０１の値を入力する。
レジスタ４１−１２にレジスタ４１−０２の値を入力する。
レジスタ４１−１３にレジスタ４１−０３の値を入力する。
レジスタ４１−０１にＦＦＴ演算回路２０からpoint１２９の処理結果を入力する。
レジスタ４１−０１にＦＦＴ演算回路２０からpoint３８５の処理結果を入力する。
レジスタ４１−０２にＦＦＴ演算回路２０からpoint６４１の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０からpoint８９７の処理結果を入力する。
【００６２】
（４）  Time３の処理
Time３では同時に以下の処理を行う。
レジスタ４１−３３（point７６８の処理結果）をセレクタ４３−１からメモリバンク３１−１に出力し、レジスタ４１−２３（point７６９の処理結果）をレジスタ４１−３３に入力する。
レジスタ４１−３２（point８３２の処理結果）をセレクタ４３−２からメモリバンク３１−２に出力し、レジスタ４１−２２（point５２３の処理結果）をセレクタ４２−２２を介してレジスタ４１−３２に入力する。
レジスタ４１−３１（point８９６の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−２１（point２５７の処理結果）をセレクタ４２−２１を介してレジスタ４１−３１に入力する。
レジスタ４１−３０（point９６０の処理結果）をセレクタ４３−４からメモリバンク３１−４に出力し、レジスタ４１−２０（point１の処理結果）をセレクタ４２−２０を介してレジスタ４１−３０に入力する。
レジスタ４１−２０にセレクタ４２−１０を介してレジスタ４１−１０の値を入力する。
レジスタ４１−２１にセレクタ４２−１１を介してレジスタ４１−１１の値を入力する。
レジスタ４１−２２にレジスタ４１−１２の値を入力する。
レジスタ４１−２３にレジスタ４１−１３の値を入力する。
レジスタ４１−１０にセレクタ４２−００を介してレジスタ４１−００の値を入力する。
レジスタ４１−１１にレジスタ４１−０１の値を入力する。
レジスタ４１−１２にレジスタ４１−０２の値を入力する。
レジスタ４１−１３にレジスタ４１−０３の値を入力する。
レジスタ４１−００にＦＦＴ演算回路２０からpoint１９３の処理結果を入力する。
レジスタ４１−０１にＦＦＴ演算回路２０からpoint４４９の処理結果を入力する。
レジスタ４１−０２にＦＦＴ演算回路２０からpoint７０５の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０からpoint９６１の処理結果を入力する。
【００６３】
（５）  Time３の処理終了後
Time３での処理終了後のＦＦＴメモリ制御回路４０の状態はTime０と同じ状態である。即ち、Time０の動作を繰り返す。
【００６４】
（メモリ制御方法の数式表現）
図１の演算装置を用いたメモリ制御方法を数式で表現すると、以下のようになる。
図１の演算装置を有効に使用するためには、メモリアクセスが重要になる。例えば、Radix４の場合では、メモリ３０が４分割されたメモリバンク３１−１〜３１−４の内容を次のように読み込んでいく必要がある。
０番目のアドレス（メモリバンク３１−１〜３１−４共に）のデータ
６４番目のアドレス（メモリバンク３１−１〜３１−４）のデータ
１２８番目のアドレス（メモリバンク３１−１〜３１−４）のデータ
【００６５】
即ち、メモリアドレッシングも必要な構成要素となる。アドレッシングとしては、ポイント数であるデータ数がＲｎ（但し、ＲはRadix数、ｎは処理の回数）で表現される場合、Radix４ならばＲｎ＝４である。処理の回数ｎは、例えば１０２４データのRadix４ＦＦＴならば、４５＝１０２４から、ｎ＝５となる。
【００６６】
ＦＦＴの処理の段数ｋとしては、ｎ回行われるので、次のようになる。
１回目はＲ（ｎ−２）毎のデータを読み込み  →Radix４の時は  ４３＝６４
２回目はＲ（ｎ−３）毎のデータを読み込み  →Radix４の時は  ４２＝１６
３回目はＲ（ｎ−４）毎のデータを読み込み  →Radix４の時は  ４１＝４
４回目はＲ（ｎ−５）毎のデータを読み込み  →Radix４の時は  ４０＝１
５回目はＲ（ｎ−５）毎のデータを読み込み  →Radix４の時は  ４０＝１
【００６７】
但し、最後の処理段数（ｋ＝５）のみ特別扱いとなる。こうすることによって図１の演算装置は有効に使用できる。因みにＲ＝２，８（Radix２，Radix８）の時も同様である。
以上のことを数式で表現すると、次のようになる。
【００６８】
図１の演算装置を用いたメモリの制御方法では、メモリ（３０）をＲ（Radix数）に分割したメモリバンク（３１−１〜３１−４）のｋ段目のFFT処理（又はIFFT処理）において、Ｒ（ｎ−ｋ−１）間隔のデータを読み込むこと（但し、ＦＦＴ最後の段の処理は間隔は１）を特徴としている。
【００６９】
（実施例１の効果）
本実施例１によれば、ＦＦＴ演算回路２０とメモリ３０との間にＦＦＴメモリ制御回路４０を設け、このＦＦＴメモリ制御回路４０を、次段のＦＦＴ処理で同時に必要なデータを別々のメモリバンク３１−１〜３１−４に格納可能とし、且つ使用したメモリ番地に上書きの形でのＦＦＴ処理を実現可能としたので、次の（ａ）〜（ｃ）のような効果がある。
【００７０】
（ａ）  ＦＦＴの１段の演算結果データを次段の演算処理に最適なブロック分けされる形でメモリ３０に格納することが可能となる。これよりＦＦＴ処理を中断することなく効率よく実現出来る。
【００７１】
（ｂ）  ある段のＦＦＴ処理で使用されたデータ、同じアドレスに次段のＦＦＴ処理で使用されるデータを書き込むことが可能となるため、従来の図６では２面必要だったメモリ１０，１０を１面（３０）にすることが出来、ハード規模を小さくすることが可能となる。
【００７２】
（ｃ）  本実施例１によるＦＦＴメモリ制御回路４０では、データの並べ替えを行うとき必要なレジスタ４１−００〜４１−３３を最小限に出来るため、ハードコストを最小にすることが出来る。しかも、レジスタ間に設けられるセレクタ４２−００〜４２−２２が２入力１出力型のセレクタのみであり、小さい回路で実現することが可能である。
【実施例２】
【００７３】
（実施例２の構成）
図３は、本発明の実施例２を示すRadix２＆Radix４兼用型のRadix２＆Radix４ＦＦＴ演算回路及びＦＦＴメモリ制御回路の構成図であり、実施例１を示す図１中の要素と共通の要素には共通の符号が付されている。
【００７４】
本実施例２は、Radix２＆Radix４兼用型のＦＦＴ演算装置において、演算手段（例えば、Radix２＆Radix４ＦＦＴ演算回路）２０Ａとメモリ３０との間に、メモリ制御手段（例えば、ＦＦＴメモリ制御回路）４０Ａが設けられている。Radix２＆Radix４ＦＦＴ演算回路２０Ａは、第１のＦＦＴ処理（例えば、Radix２ＦＦＴ演算）機能と第２のＦＦＴ処理（例えば、Radix４ＦＦＴ演算）機能とを有し、これらが切り替えられるようになっている。ＦＦＴメモリ制御回路４０Ａは、図１のＦＦＴメモリ制御回路４０に対して、レジスタ間において２入力１出力のセレクタ（Reg）４２−０２，４２−１２，４２−１３が追加され、図１の出力段の４入力１出力のセレクタ４３−２，４３−１に代えて、５入力１出力のセレクタ４３−２Ａ，４３−１Ａが設けられている点が異なっている。
【００７５】
追加されたレジスタ間のセレクタ４２−０２，４２−１２，４２−１３は、これらの入出力が図示しない制御信号により切り替えられるものであり、この内、セレクタ４２−０２は、１段目レジスタ４１−０２，４１−０３の出力のいずれか一方を選択して２段目レジスタ４１−１２へ与え、セレクタ４２−１２は、１段目レジスタ４１−０２又は２段目レジスタ４１−１２の出力のいずれか一方を選択して出力段レジスタ４３−２Ａへ与え、セレクタ４２−１３は、２段目レジスタ４１−１２，４１−１３の出力のいずれか一方を選択して出力段レジスタ４３−１Ａへ与えるように接続されている。
【００７６】
本実施例２のRadix２＆Radix４兼用型のＦＦＴ処理装置は、Radix４とRadix２ＦＦＴの両方に対応し、これはＦＦＴのpoint数を任意に定めた場合に有効である。この理由は、以下の通りである。
【００７７】
Radix４ＦＦＴはRadix２ＦＦＴに比べて同じpoint数のＦＦＴを実行する場合、演算回数を約２５％少なく出来るが、ＦＦＴのpoint数が４のべきで表現される必要がある。このため、４のべきで表現出来ないpoint数のＦＦＴを実行する場合、Radix４ＦＦＴとRadix２ＦＦＴと混在して使用する。本回路はそれに対応している。
【００７８】
（実施例２のメモリ制御方法）
ＦＦＴメモリ制御回路４０Ａは、Radix４ＦＦＴの処理の時は、図１のＦＦＴメモリ制御回路４０と同様の処理を行う。例えば、１０２４point  Radix２ＦＦＴ処理の時は、レジスタ４１−２０，４１−２１，４１−２２，４１−２３，４１−３０，４１−３１，４１−３２，４１−３３を使用しない。
【００７９】
図４は、図３のレジスタ４１−００〜４１−３３のTime０〜Time１におけるデータ格納状態を示す図である。この図の意味は図２と同様である。
【００８０】
例えば、１０２４point  Radix２ＦＦＴ処理の場合、ＦＦＴメモリ制御回路４０Ａは、図示しないクロックに同期して、以下の（１）〜（３）のようなTime０〜Time１の処理を繰り返す。
【００８１】
（１）  Time０の処理
Time０では同時に以下の処理を行う。
レジスタ４１−００（point６４の処理結果）をセレクタ４３−４からメモリバンク３１−４に出力し、ＦＦＴ演算回路２０Ａからpoint１２８の処理結果をレジスタ４１−００に入力する。
レジスタ４１−１０（point０の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−０１（point３２０の処理結果）をセレクタ４２−００を介してレジスタ４１−１０に入力する。
レジスタ４１−０２（point５７６の処理結果）をセレクタ４２−１２，４３−２Ａからメモリバンク３１−２に出力し、ＦＦＴ演算回路２０Ａからpoint６４０の処理結果をレジスタ４１−０２に入力する。
レジスタ４１−１２（point５１２の処理結果）をセレクタ４２−１３，４３−１Ａからメモリバンク３１−１に出力し、レジスタ４１−０３（point３２０の処理結果）をセレクタ４２−０２を介してレジスタ４１−１２に入力する。
レジスタ４１−０１にＦＦＴ演算回路２０Ａからpoint３８４の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０Ａからpoint８９６の処理結果を入力する。
【００８２】
（２）  Time１の処理
Time１では同時に以下の処理を行う。
レジスタ４１−１０（point３２０の処理結果）をセレクタ４３−４からメモリバンク３１−４に出力し、レジスタ４１−００（point１２８の処理結果）をセレクタ４２−００を介してレジスタ４１−１０に入力する。
レジスタ４１−１１（point２５６の処理結果）をセレクタ４３−３からメモリバンク３１−３に出力し、レジスタ４１−０１（point３８４の処理結果）をレジスタ４１−１１に入力する。
レジスタ４１−１２（point８３２の処理結果）をセレクタ４２−１２，４３−２Ａからメモリバンク３１−２に出力し、レジスタ４１−０２（point６４０の処理結果）をセレクタ４２−０２を介してレジスタ４１−１２に入力する。
レジスタ４１−１３（point７６８の処理結果）をセレクタ４２−１３，４３−１Ａからメモリバンク３１−１に出力し、レジスタ４１−０３（point８９６の処理結果）をレジスタ４１−１３に入力する。
レジスタ４１−００にＦＦＴ演算回路２０Ａからpoint１９２の処理結果を入力する。
レジスタ４１−０１にＦＦＴ演算回路２０Ａからpoint４４８の処理結果を入力する。
レジスタ４１−０２にＦＦＴ演算回路２０Ａからpoint７０４の処理結果を入力する。
レジスタ４１−０３にＦＦＴ演算回路２０Ａからpoint９６０の処理結果を入力する。
【００８３】
（３）  Time１終了後
Time１での処理終了後のＦＦＴメモリ制御回路４０Ａの状態は、Time０と同じ状態である。即ち、Time０の動作を繰り返すこととなる。
【００８４】
（実施例２の効果）
本実施例２のＦＦＴメモリ制御回路４０Ａによれば、次段のＦＦＴ処理で同時に必要なデータを別々のメモリバンク３１−１〜３１−４に格納可能とし、使用したメモリ番地に上書きの形でのＦＦＴ処理を実現可能とし、且つRadix２ＦＦＴとRadix４ＦＦＴの両者に対応可能な構成にしたので、実施例１とほぼ同様の効果がある上に、ＦＦＴのpoint数を任意に定めた場合に有効である。
【実施例３】
【００８５】
本発明は上記実施例１、２に限定されず、種々の変形が可能である。この変形例である実施例３としては、例えば、次の（Ａ）〜（Ｃ）のようなものがある。
【００８６】
（Ａ）  実施例１、２では、メモリ３０を４分割したメモリバンク３１−１〜３１−４を使用する例について説明したが、これに代えて、メモリ３０中の４つの指定場所を使用しても良い。例えば、メモリ３０において、ｍ（但し、ｍは任意の正整数）行目且つｎ（但し、ｎは任意の正整数）列目の指定場所（メモリバンク３１−１に対応）、ｍ行目且つ（ｎ＋１）列目の指定場所（メモリバンク３１−２に対応）、（ｍ＋１）行目且つｎ列目の指定場所（メモリバンク３１−３に対応）、及び、（ｍ＋１）行目且つ（ｎ＋１）列目の指定場所（メモリバンク３１−４に対応）を使用して、データの読み出しと書き込みを行うようにしても、実施例１、２とほぼ同様の作用効果を奏することが出来る。
【００８７】
（Ｂ）  実施例１、２では、ＦＦＴ処理について説明したが、ＩＦＦＴ処理に適用しても、ほぼ同様の作用効果が得られる。
【００８８】
（Ｃ）  図１のＦＦＴ演算回路２０，２０Ａは、Radix２ＦＦＴ、Radix４ＦＦＴ以外の構成に変更したり、メモリバンク３１−１〜３１−４の個数（或いはメモリ３０の指定場所の数）を４個以外の数に変更したり、図１、図３のＦＦＴメモリ制御回路４０，４０Ａの構成要素を図示以外の段数や個数等に変更しても良い。
【符号の説明】
【００８９】
２０，２０Ａ      ＦＦＴ演算回路
３０      メモリ
３１−１〜３１−４      メモリバンク
４０，４０Ａ      ＦＦＴメモリ制御回路
４１−００〜４１−３３      レジスタ
４２−００〜４２−２２，４３−１〜４３−４，４３−１Ａ，４３−２Ａ  セレクタ
【図１】
0005444287.tif 000009
【図２】
0005444287.tif 000010
【図３】
0005444287.tif 000011
【図４】
0005444287.tif 000012
【図５】
0005444287.tif 000013
【図６】
0005444287.tif 000014
【図７】
0005444287.tif 000015
【図８】
0005444287.tif 000016