(57)【要約】      （修正有）【課題】キャッシュメモリを用いて極めて多数のデータについてリアルタイムで実数ＦＦＴ演算を行うＦＦＴ演算装置を提供する。【解決手段】キャッシュメモリ１３は、実数ＦＦＴ演算の対象となるデータの一部を格納する。ＦＦＴ演算部１０は、キャッシュメモリ１３の格納するデータについて、実数ＦＦＴ演算を行う。ＦＦＴ演算部１０が、複数ステージのバタフライ演算のいずれかのステージの後に前記データ転送を少なくとも１回行うことにより、複数ステージのバタフライ演算におけるその後のバタフライ演算と変換結果を得るためのバタフライ演算とにおいて必要なデータをキャッシュメモリ１３上に読み込み、その後のバタフライ演算を読み込まれたデータを用いて行い、その後にキャッシュメモリ１３の格納するデータをそのまま使用して変換結果を得るためのバタフライ演算を行う。【選択図】図１
2006331186.tif 000002
【特許請求の範囲】
【請求項１】
実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、
前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリと、
前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行うＦＦＴ演算部とを備え、
前記ＦＦＴ演算部が、前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う
ことを特徴とするＦＦＴ演算装置。
【請求項２】
前記ＦＦＴ演算部が、前記データ転送後のバタフライ演算を、前記実数ＦＦＴ演算の対象となるデータの昇順方向へのバタフライ演算及び前記実数ＦＦＴ演算の対象となるデータの降順方向へのバタフライ演算に分けて行う
ことを特徴とする請求項１記載のＦＦＴ演算装置。
【請求項３】
実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリとを用いて、前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行う実数ＦＦＴ演算方法であって、
前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、
前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、
前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う
ことを特徴とするＦＦＴ演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＦＦＴ演算装置及びＦＦＴ演算方法に関し、特に、キャッシュメモリを用いて極めて多数のデータについてリアルタイムでＦＦＴ演算を行うＦＦＴ演算装置及びＦＦＴ演算方法に関する。
【背景技術】
【０００２】
ＦＦＴ（高速フーリエ変換）演算の高速化は、多くの場合、高速で小さいサイズのキャッシュメモリと低速で大きいサイズの外部メモリとの間におけるデータ転送を、いかに効率良く行うかに依存している。
【０００３】
例えば、演算対象のデータを当該キャッシュメモリのサイズに応じた所定サイズのセグメントに区分すると共に、各セグメント内で演算の際に参照されるデータが連続して位置するように再配置し、当該再配置される各セグメントのデータをセグメント単位で演算することが提案されている（特許文献１参照）。
【０００４】
また、高速な内部メモリを有効に利用して高速で大きいサイズのデータを処理するＦＦＴ演算のために、被ＦＦＴデータを小さいサイズの高速メモリに見合った複数のブロックに分割し、高速メモリと外部メモリとの間でブロック毎にデータの転送をし、高速メモリに蓄積された被ＦＦＴデータをＦＦＴ演算することが提案されている（特許文献２参照）。
【特許文献１】特開２００２−０４９６１２号公報
【特許文献２】特開２００２−１６９７９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
宇宙探査において用いられる電波干渉計においては、複数の電波望遠鏡の出力を各々リアルタイムでＦＦＴ演算処理し、その後各アンテナ出力間でリアルタイムに相互相関演算を行う。観測精度を向上させるために、例えば、１６個のアンテナの各々からの左右の偏波を含む信号（ＧＨｚ帯）を適切な帯域毎に４分割し、各々の信号を８個の増幅器及びＡＤ変換器で処理して得た信号をＦＦＴ演算することが考えられる。この場合、１Ｍ（メガ）点にも及ぶＦＦＴ演算を、数ｍ（ミリ）秒で終える必要がある。
【０００６】
このような極めて大量のデータのリアルタイムでのＦＦＴ演算は、従来行なわれることが無かった。このような極めて大量のデータのＦＦＴ演算をリアルタイムで行うためには、演算速度が極めて速くキャッシュメモリのサイズに制限の無いスーパーコンピュータを用いることが考えられる。しかし、それでは開発コストや開発期間が膨大なものになり、現実的ではない。
【０００７】
そこで、本発明者は、市販の動作周波数が数ＧＨｚの演算装置（例えば、ＤＳＰ；Digital Signal Processor）を１個又は複数個用いて、１Ｍ点に及ぶＦＦＴ演算をリアルタイムで行うことについて検討した。そして、本発明者は、ＦＦＴ演算において、電波干渉計の出力が実数であることを利用すれば、１Ｍ点に及ぶＦＦＴ演算をリアルタイムで行い得ることを、初めて見出した。本発明はこのような新たな知見に基づくものである。
【０００８】
本発明は、キャッシュメモリを用いて極めて多数のデータについてリアルタイムで実数ＦＦＴ演算を行うＦＦＴ演算装置を提供することを目的とする。
【０００９】
また、本発明は、キャッシュメモリを用いて極めて多数のデータについてリアルタイムで実数ＦＦＴ演算を行うＦＦＴ演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明のＦＦＴ演算装置は、実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリと、前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行うＦＦＴ演算部とを備える。前記ＦＦＴ演算部が、前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う。
【００１１】
また、本発明のＦＦＴ演算装置において、好ましくは、前記ＦＦＴ演算部が、前記データ転送後のバタフライ演算を、前記実数ＦＦＴ演算の対象となるデータの昇順方向へのバタフライ演算及び前記実数ＦＦＴ演算の対象となるデータの降順方向へのバタフライ演算に分けて行う。
【００１２】
本発明のＦＦＴ演算方法は、実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリとを用いて、前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行う。この実数ＦＦＴ演算方法は、前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う。
【発明の効果】
【００１３】
本発明のＦＦＴ演算装置及び方法においては、演算対象のデータが実数値であることを利用することにより、ＦＦＴ演算それ自体の回数を削減している。これに加えて、本発明では、実数ＦＦＴ演算の特性を利用することによりキャッシュメモリと外部メモリ（主メモリ）との間におけるデータ転送の回数を削減している。
【００１４】
具体的には、本発明では、電波干渉計においては２乗検波により得られる実数部のみが意味を持つことに着目して、複素数値時間関数の虚数部を利用した実数値関数のＦＦＴ（以下、単に実数ＦＦＴと言う）演算を行う。これにより、実数ＦＦＴ演算の回数を複素数値時間関数によるＦＦＴ演算（通常のＦＦＴ演算）の回数の１／２とすることができる。更に、本発明では、通常のＦＦＴ演算ではなく実数ＦＦＴ演算を行うことに着目して、実数ＦＦＴ演算の特性を考慮したデータの並び替え（シャッフリング）を行う。これにより、同時ＦＦＴ演算の結果から変換結果を復元するための演算の直前におけるデータ転送を不要とすることができる。以上により、本発明によれば、ＦＦＴ演算の時間それ自体を短縮し、かつ、データ転送の時間を短縮して、１Ｍ点のように極めて大量のデータのＦＦＴ演算をリアルタイムで行うことができる。
【００１５】
また、本発明のＦＦＴ演算装置において、好ましくは、データ転送後のバタフライ演算を、実数ＦＦＴ演算の対象となるデータの昇順方向へのバタフライ演算及び降順方向へのバタフライ演算に分けて行う。これにより、大量のデータのＦＦＴ演算においても、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算との間におけるデータ転送を不要とすることができ、データ転送の時間を短縮して、リアルタイムでのＦＦＴ演算に寄与することができる。
【発明を実施するための最良の形態】
【００１６】
図１は、ＦＦＴ演算装置構成図であって、本発明のＦＦＴ演算装置の構成の一例を示す。このＦＦＴ演算装置は、演算装置であるＤＳＰ１と、外部メモリ２と、これらの間を接続するシステムバス３とからなる。ＤＳＰ１は、キャッシュメモリ１３と、ＦＦＴ演算部１０とからなる。この例では、ＦＦＴ演算部１０は、転送制御ユニット１１と、演算ユニット１２とからなり、実数ＦＦＴ演算を実行する。
【００１７】
外部メモリ２は、例えばＤＲＡＭ（Dynamic Random Access Memory）からなる主メモリであり、実数ＦＦＴ演算の対象となるデータを格納する。このデータは、図示はしないが、例えば電波干渉計の１６個のアンテナの各々からの左右の偏波を含む信号（ＧＨｚ帯）を適切な帯域毎に４分割し、各々の信号を８個の増幅器及びＡＤ（Analog to Digital）変換器で処理して得た信号である。このデータは、１Ｍ点のＦＦＴ演算に相当する信号であり、数ｍ秒での処理が必要とされる。
【００１８】
キャッシュメモリ１３は、外部メモリ２との間でシステムバス３を介してデータ転送を行うことにより、実数ＦＦＴ演算の対象となるデータの一部を格納する。キャッシュメモリ１３は、周知のように、例えばＤＳＰ１のチップ内に設けられたＳＲＡＭ（Static Random Access Memory）からなる高速メモリ（１次キャッシュ）であり、外部メモリ２よりも十分に高速である。キャッシュメモリ１３のサイズは、実数ＦＦＴ演算の対象となるデータより小さい。なお、キャッシュメモリ１３は、ＤＳＰ１と同一の実装ボード（基板）上に実装されたもの（２次キャッシュ）であっても良く、また、ＤＳＰ１と異なる実装ボード上に実装されていても外部メモリ２よりも十分に高速であれば良い。
【００１９】
この明細書において、「キャッシュメモリ１３のサイズ」とは、図１（Ｂ）に示すように、キャッシュメモリ１３の全ての記憶領域（容量）のうち、ＦＦＴ演算に用いられる記憶領域Ｄｃを言う。キャッシュメモリ１３は、通常、その全記憶領域がＦＦＴ演算に用いられることは無い。キャッシュメモリ１３には、変数格納領域及びその他の領域が設けられる。変数格納領域は、後述するように、ＦＦＴ演算及びその他の演算に必要な種々の変数及び補助的な変数を必要に応じて格納する。
【００２０】
ＦＦＴ演算部１０は、その転送制御ユニット１１においてキャッシュメモリ１３と外部メモリ２との間におけるデータ転送を制御し、その演算ユニット１２においてキャッシュメモリ１３の格納するデータについて実数ＦＦＴ演算を行う。転送制御ユニット１１は、例えば周知のＤＭＡ（Direct Memory Access controller）からなる。
【００２１】
ＦＦＴ演算部１０は、転送制御ユニット１１において、システムバス３を介して、外部メモリ２からキャッシュメモリ１３へ、演算対象のデータを読み込み、演算ユニット１２において、実数ＦＦＴ演算のための複数ステージのバタフライ演算を行う。ＦＦＴ演算部１０は、転送制御ユニット１１において、このバタフライ演算のいずれかのステージの後に、システムバス３を介して、キャッシュメモリ１３と外部メモリ２との間でキャッシュメモリ１３の格納するデータの退避又は書き込み（メモリライト；ＭＷ）及び読み出し（メモリリード；ＭＲ）を行う。これにより、当該データの順序を変更する。
【００２２】
その後、ＦＦＴ演算部１０は、演算ユニット１２において、残りのバタフライ演算を当該変更された順序のデータを用いてそのアドレスの正順方向及び逆順方向に分けて行い、更に、複数ステージのバタフライ演算の後に、キャッシュメモリ１３の格納するデータをそのまま使用して、実数ＦＦＴ演算の対となる実数部及び虚数部のデータを復元する演算を行う。この後、ＦＦＴ演算部１０は、転送制御ユニット１１において、この復元されたデータを、システムバス３を介して、キャッシュメモリ１３から外部メモリ２へ書き込む。
【００２３】
前述のように、外部メモリ２内の入力データ数（ＦＦＴ点数）は、キャッシュメモリ１３のサイズより大きい。従って、実際には、ＤＳＰ１（ＦＦＴ演算部１０）により当該データについて時分割でＦＦＴ演算を行う。即ち、周知のように、キャッシュメモリ１３のサイズを単位として演算対象のデータをブロックに分割して、各々のブロックについて前述の処理を行なう。又は、ＤＳＰ１（ＦＦＴ演算部１０）を複数個設けて、当該複数のブロックについて並列にＦＦＴ演算を行う。
【００２４】
次に、本発明の具体的な説明の前提として、ＦＦＴ演算部１０がその演算ユニット１２において実行するＦＦＴ演算であって、複素数値時間関数の虚数部を利用した２Ｎ個の標本で表されている実数値関数ｘ（ｋ）の離散フーリエ変換（ＦＦＴ）演算について、簡単に説明する。これは、周知のいわゆるＮ個の標本の変換による２Ｎ個の標本の変換（Ｎ点変換による２Ｎ点変換）によるＦＦＴ演算であるが、この明細書では、これを簡易に「実数ＦＦＴ演算」と呼ぶこととする。実数ＦＦＴ演算は、以下の演算過程ａ〜ｅからなる。
【００２５】
演算過程ａ：最初に、関数ｘ（ｋ）は実数値関数とする（ｋ＝０，１，．．．，２Ｎ−１）。
【００２６】
演算過程ｂ：次に、関数ｘ（ｋ）を２個の関数ｈ（ｋ）及びｇ（ｋ）に分ける。ここで、
ｈ（ｋ）＝ｘ（２ｋ）
ｇ（ｋ）＝ｘ（２ｋ＋１）
である（ｋ＝０，１，．．．，Ｎ−１）。これにより、関数ｘ（ｋ）は偶数番目の標本からなる関数ｈ（ｋ）と奇数番目の標本からなる関数ｇ（ｋ）とに分けられる。
【００２７】
演算過程ｃ：次に、次の複素数値関数ｙ（ｋ）を生成する（ｋ＝０，１，．．．，Ｎ−１）。
ｙ（ｋ）＝ｈ（ｋ）＋ｊｇ（ｋ）
ここで、ｈ（ｋ）及びｇ（ｋ）は、各々、ｙ（ｋ）の実数部と虚数部である。これにより、複素数値関数の虚数部を利用することができる。
【００２８】
演算過程ｄ：次に、次式（１）によりＹ（ｎ）＝Ｒ（ｎ）＋ｊＩ（ｎ）を計算する（ｎ＝０，１，．．．，Ｎ−１）。
【００２９】
【数１】
2006331186.tif 000003
【００３０】
ここで、Ｒ（ｎ）及びＩ（ｎ）は、各々、Ｙ（ｎ）の実数部と虚数部である。この明細書において、演算過程ｂ、ｃ及びｄを「複数ステージのバタフライ演算」と言うこととする。
【００３１】
演算過程ｅ：次に、次式（２）によりＸｒ（ｎ）及びＸｉ（ｎ）を計算する（ｎ＝０，１，．．．，Ｎ−１）。ＮはＦＦＴ演算の点の数（データの個数）であり、ｎは当該データの位置である。
【００３２】
【数２】
2006331186.tif 000004
【００３３】
ここで、Ｘｒ（ｎ）及びＸｉ（ｎ）は、各々、ｘ（ｋ）の２Ｎ点離散変換の実数部と虚数部である。これにより、複素数値関数の虚数部を利用した同時ＦＦＴ演算の結果から、変換結果を得ることができる。この明細書において、演算過程ｅを「変換結果を得るためのバタフライ演算」と言うこととする。
【００３４】
以上の演算過程ａ〜ｅを本発明に当てはめると、以下のようになる。この例では、電波干渉計で２乗検波により得たデータを演算対象としているので、関数ｘ（ｋ）は実数値関数からなると考えて良い。従って、この例では、演算過程ａは無視して良い（得られたデータを用いれば良い）。演算過程ｂ及びｃは、周知の処理によれば良い。
【００３５】
これに対して、演算過程ｄ及びｅは、周知の処理、即ち、バタフライ演算を用いる処理によれば良いが、本発明に従って、演算対象のデータのキャッシュメモリ１３内における位置が、少なくとも１回のキャッシュメモリ１３と外部メモリ２との間のデータ転送により変更されている。これにより、演算過程ｄと演算過程ｅとの間におけるキャッシュメモリ１３と外部メモリ２との間のデータ転送を不要とする。更に、実際には、１Ｍ点のＦＦＴ演算にもかかわらず、演算過程ｄにおけるキャッシュメモリ１３と外部メモリ２との間のデータ転送を必要最小限の回数としている。この回数は、後述するように、１回のみとされる。即ち、演算過程ｄとｅとの間におけるデータ転送を不要にするための１回のデータ転送のみとしている。
【００３６】
次に、本発明のＦＦＴ演算について、図２〜図５を参照して、具体的に説明する。本発明は、前述のように、１Ｍ（２の２０乗）点のＦＦＴ演算（１６ビット／個）を行うものであるが、説明の簡単のために、以下の説明においては１６（２の４乗）点のＦＦＴ演算を例とする。なお、１６点のＦＦＴ演算（（実数部１６ビット＋虚数部１６ビット）×１６個）は、実数ＦＦＴ演算における３２点のＦＦＴ演算（実数部１６ビット×３２個）に相当する。また、ＤＳＰ１が持つキャッシュメモリ１３のサイズ（演算領域Ｄｃの大きさ）が、一度に４個のデータ（３２ビット／個）を格納することが可能な大きさ（４データ分の大きさ）であるとする（図４参照）。
【００３７】
図２はＦＦＴ演算の基本方式を示し、図３は実数ＦＦＴ演算の基本方式を示し、図４は図３におけるデータのライト／リードを付加した実数ＦＦＴ演算を示す。図５は、図４の実数ＦＦＴ演算を本発明に従って変更した例を示す。図２〜図５において、各々、縦方向の数字は当該データのメモリアドレス、横方向の数字は演算ステージを表す。メモリアドレスは、周知のように、当該データの位置により又はこれに応じて定まる。
【００３８】
図２に示すように、複素数値時間関数の実数部及び虚数部を用いた（通常の）１６点のＦＦＴ演算は、第０ステージ〜第３ステージまでの４ステージのバタフライ演算により行われる。即ち、図２に示す上下の三角形の対は、その各々が、ＦＦＴ演算の信号の流れ（シグナルフロー）におけるバタフライ演算を簡易に表しているものとする（以下、同じ）。図２において、説明の簡単のために、外部メモリ２へのデータのライト／リードは考慮しておらず（図３において、同じ）、また、キャッシュメモリ１３のサイズも考慮していない。
【００３９】
一方、図３に示すように、実数ＦＦＴ演算は、第０ステージ〜第３ステージまでのバタフライ演算と、その後の同時にＦＦＴ演算した結果の各々から２個の変換結果を得るための演算（以下、実数ＬＡＳＴステージ）とを必要とする。即ち、実数ＦＦＴ演算のための複数ステージのバタフライ演算（演算過程ｂ〜ｄ）と、その後の変換結果を得るためのバタフライ演算（演算過程ｅ、即ち、実数ＬＡＳＴステージ）とを必要とする。図３から、周知のように、実数ＬＡＳＴステージは、第０ステージ〜第３ステージまでの４ステージとの比較において、演算の対となるデータがずれており、かつ、組み合わせが異なることが判る。これは、前述の式（２）からも明らかである。
【００４０】
次に、図３において外部メモリ２でのデータのライト／リードを考慮すると、図４のようになる。図４において、キャッシュメモリ１３から外部メモリ２へのデータ転送（退避）をメモリライト；ＭＷと表し、外部メモリ２からキャッシュメモリ１３へのデータ転送（読み込み）をメモリリード；ＭＲと表す（以下、同じ）。ＭＷとＭＲとを合わせて、キャッシュメモリ１３と外部メモリ２との間におけるデータ転送と言う。図４は、従来の実数ＦＦＴ演算の例に相当する。
【００４１】
ここで、キャッシュメモリ１３のサイズが４データ分であることを考慮すると、以下のような２種類のデータ転送を生じる。なお、図４に、ＦＦＴ演算のデータに合わせて、キャッシュメモリ１３のサイズ即ち演算領域Ｄｃの大きさを示す。
【００４２】
第１のデータ転送は、実数ＦＦＴ演算に特有のデータ転送である。即ち、前述のように、演算の対となるデータがずれており、かつ、組み合わせが異なるので、第３ステージと実数ＬＡＳＴステージとの間で、データの並び替え（シャッフリング）のために、ほぼ全てのデータについて、キャッシュメモリ１３と外部メモリ２との間におけるデータ転送が必要となる。従って、例えば１Ｍ点のＦＦＴ演算においては、このデータ転送の時間が演算時間に大きく影響する。全データの並び替えが必要となる理由は、従来、実数ＦＦＴ演算のための複数ステージのバタフライ演算（主として演算過程ｄ）におけるデータの組み合わせのみを意識しているためである。
【００４３】
第２のデータ転送は、実数ＦＦＴ演算に限らず、ＦＦＴ演算において通常生じるデータ転送である。即ち、ＤＳＰ１は、１回の外部メモリ２のリードにより、キャッシュメモリ１３上に第０〜第３データの４個のデータを展開する。この４個のデータについては、太線で囲んで示すように、第０ステージと第１ステージの２ステージにおいては、外部メモリ２へ退避することなく、バタフライ演算を行うことができる。
【００４４】
しかし、第２ステージ以降は、頻繁に（ほぼ各ステージ毎に）外部メモリ２との間でデータの退避と読み込みが必要となる。即ち、第２ステージにおける演算は、太線で囲んで示すように、第０、第１、第４及び第５データがバタフライ演算の対となる。第３ステージにおける演算は、太線で囲んで示すように、第０、第１、第８及び第９データがバタフライ演算の対となる。従って、第１ステージと第２ステージとの間、及び、第２ステージと第３ステージとの間において、各々、データ転送を利用したデータの並べ替えが必要となる。
【００４５】
キャッシュメモリ１３のサイズＤｃが、例えば８データ分である場合、第１ステージと第２ステージとの間におけるデータ転送は不要となるが、それ以降のステージにおけるデータ転送は、依然として必要である。データ転送の回数は、キャッシュメモリ１３のサイズＤｃに依存する。
【００４６】
更に、実際は、第３のデータ転送が生じる。ＦＦＴ演算すべきデータは１６個存在するので、ＦＦＴ演算は４回に分割して行う必要がある。即ち、第０〜第３データについての第０及び第１ステージの終了後、データ転送を行って、第４〜第７データについての第０及び第１ステージを実行する。この後、データ転送、第８〜第１１データについての第０及び第１ステージ、データ転送、第１２〜第１５データについての第０及び第１ステージを実行する。更に、データ転送を繰り返しながら、第２及び第３ステージも同様に実行する。第３のデータ転送は、その回数の多少はともかく、省略できない。
【００４７】
このように、図４においては（従来技術においては）、あるステージ以降、ステージ毎に外部メモリ２へのアクセスが発生し、大幅に処理時間が増大していた。また、外部メモリ２へのアクセスは、ＦＦＴ演算における特性のステージを意識したアドレスになり、アドレスが連続しないため、外部メモリ２がＤＲＡＭである場合、バースト転送が有効にならず、演算時間の増加要因になっていた。
【００４８】
本発明においては、前述の第１のデータ転送を省略する。このために、本発明では、変換結果を得るためのバタフライ演算（実数ＬＡＳＴステージ）におけるデータの組み合せを優先する。即ち、図５の場合、実数ＬＡＳＴステージにおいて、第０及び第８データは対とならず、第４データは第１２データとバタフライ演算を行い、第３ステージにおいて、第０データは第８データと第４データは第１２データと各々バタフライ演算を行うことに注目する。
【００４９】
そこで、少なくとも第３ステージの開始前に、第３ステージ及び実数ＬＡＳＴステージ（即ち、第３ステージ以降）において必要となる全てのデータがキャッシュメモリ１３上に存在するように、少なくとも１回のデータ転送を行う。このためには、図５（Ａ）から理解されるように、少なくとも第３ステージの開始前に、第０〜第３データがキャッシュメモリ１３から外部メモリ２にライト（ＭＷ）され、第０、第４、第８、第１２データが、外部メモリ２からリード（ＭＲ）されキャッシュメモリ１３に保持されれば良い。これにより、第３ステージと実数ＬＡＳＴステージとの間におけるデータ転送（第１のデータ転送）を不要とすることができる。
【００５０】
以上に加えて、本発明においては、前述の第２のデータ転送をできるだけ省略する。即ち、実数ＦＦＴ演算のための複数ステージのバタフライ演算（主として演算過程ｄ）におけるデータの組み合わせをも考慮する。即ち、図５の場合、第３ステージにおいて、第０データは第８データと第４データは第１２データと各々バタフライ演算を行い、第２ステージにおいて、第０データは第４データと第８データは第１２データと各々バタフライ演算を行うことに注目する。他についても同様である。
【００５１】
このような観点から、図５（Ａ）に示すように、（第１ステージの終了後かつ）第２ステージの開始前に、第２ステージ以降において必要となる全てのデータがキャッシュメモリ１３上に存在するように、少なくとも１回のデータ転送を行う。即ち、第２ステージの開始前に、第０〜第３データがキャッシュメモリ１３から外部メモリ２にライト（ＭＷ）され、第０、第４、第８、第１２データが、外部メモリ２からリード（ＭＲ）されキャッシュメモリ１３に保持される。他のデータ（例えば、第２、第６、第１０及び第１４データ）についても同様である。
【００５２】
これにより、第２ステージと第３ステージとの間におけるデータ転送（第２のデータ転送）を不要とすることができる。即ち、第２のデータ転送の回数を必要最小限にすることができる。これに加えて、前述のように、第３ステージと実数ＬＡＳＴステージとの間におけるデータ転送（第１のデータ転送）を不要とすることができる。
【００５３】
ここで、図５（Ａ）から判るように、キャッシュメモリ１３のサイズＤｃが４データ分である場合、第１、第５、・・・、第１１及び第１５データの８個のデータについては、第２ステージと第３ステージとの間におけるデータ転送を不要とすることができない。しかし、図５（Ｂ）から判るように、キャッシュメモリ１３のサイズＤｃが８データ分である場合、これらの８個のデータについても、第２ステージと第３ステージとの間におけるデータ転送を不要とすることができる。
【００５４】
このように、本発明によれば、キャッシュメモリ１３のサイズＤｃに対して、２を底とするべき乗個のステージ単位で、外部メモリ２へのアクセスを不要することができる。即ち、本発明によれば、キャッシュメモリ１３のサイズＤｃを所定の程度の大きさとすることにより、実数ＦＦＴ演算におけるデータ転送の回数を１回のみとすることができ、そのデータ転送のタイミングを定めることができる。
【００５５】
図６は、図５の例を拡張した例を示す。即ち、入力データ数が１２８点に対する（本発明による）実数ＦＦＴの例である。キャッシュメモリ１３のサイズＤｃは３２データ分である。
【００５６】
図６において、図示の便宜上、図５の第２、第３及び実数ＬＡＳＴステージに対応するステージのみを示す。即ち、第２ステージに対応するステージ（最終−１ステージ）の開始前において、本発明に従って、データ転送が行われる。この結果、図６に示すように、第０、第１、・・・、第１２６及び第１２７データがキャッシュメモリ１３上に存在するようにされる。これにより、最終−１ステージ、最終ステージ（第３ステージに対応するステージ）及び実数ＬＡＳＴステージを、データ転送を行うことなく、実行することができる。
【００５７】
図６において、３２個のデータが同時にキャッシュメモリ１３上に存在するようにされる。このキャッシュメモリ１３上に展開される３２個のデータは、４データ単位で、連続データ番号を持つようにされる。即ち、外部メモリ２において、その連続するアドレス上に存在するようにされる。外部メモリ２としては、例えばＤＲＡＭ２が使用される。ＤＲＡＭ２の高速転送モードであるバースト転送によれば、４アドレスのデータを連続して転送することができる。従って、この例においては、連続データ番号を持つ４データを、１回のバースト転送によりＤＲＡＭ２とキャッシュメモリ１３との間で転送することができる。これにより、個々のデータ転送に要する時間を短縮して、演算時間を短縮することができる。
【００５８】
即ち、本発明によれば、（Ｄｃ／Ｄｂ）に対して２を底とするべき乗個のステージ単位までであれば、バースト転送によるアクセス速度の改善を保ちつつ、前述のように、第２のデータ転送を必要最小限の回数とし、第１のデータ転送を省略することができる。但し、Ｄｂはバースト転送データ数である。
【００５９】
なお、図６において、「×」印で表されるデータは、その演算の対となるデータがキャッシュメモリ１３上に存在しない。即ち、当該データは、他の期間においてキャッシュメモリ１３上に存在する（読み込まれる）か、又は、他のキャッシュメモリ１３上に存在する。このため、当該データは、当該キャッシュメモリ１３又は他のキャッシュメモリ１３の変数格納領域（図１（Ｂ）参照）に、補助的変数として保存される。これにより、「×」印で表されるデータが存在しても、本発明の実数ＦＦＴへの影響は無くすことができる。
【００６０】
例えば、図６の例においては、入力データ数１２８点でキャッシュメモリ１３のサイズが３２データであるので、１個のＤＳＰ１により４回に時分割して演算する。時分割された１回目のＦＦＴ演算が終了した時点で、「×」印で表されるデータをキャッシュメモリ１３に保存し、時分割された２回目のＦＦＴ演算において、当該「×」印で表されるデータを用いる。
【００６１】
なお、例えば２個のＤＳＰ１で２回に時分割して並列演算するようにしても良い。又は、例えば４個のＤＳＰ１で並列演算するようにしても良い。いずれの場合においても、最初のＦＦＴ演算における「×」印で表されるデータは、キャッシュメモリ１３に保存され、続く他のＦＦＴ演算において使用される。
【００６２】
図７は、図５及び図６の例を更に拡張した例である。即ち、入力データ数が１Ｍ（２の２０乗点）点の（本発明による）実数ＦＦＴの例である。キャッシュメモリ１３のサイズＤｃは６４Ｋ（キロ）データ分（６５５３６データ分）である。バースト転送データ数は４Ｋデータ（４０９６データ）である。
【００６３】
図７において、第１ステージは、以下のように行われる。即ち、５１２Ｋ個（実数ＦＦＴ演算における１Ｍ個、演算過程ｂによる）のデータを、先頭から順に６４Ｋ個（１２８Ｋ個）づつ、８グループ（第０〜第７グループ）に分け、１個のＤＳＰ１で時分割により実数ＦＦＴ演算する。第０〜第７グループの各々は、この順に、グループ毎に実数ＦＦＴ演算される。各々のグループのデータは、６４Ｋデータであるので、キャッシュメモリ１３上に格納することができる。第１ステージの実行後、本発明に従って、データ転送が行われる。これにより、図７に示すように、第２〜第４ステージ及び実数ＬＡＳＴステージを、データ転送を行うことなく、実行することができる。
【００６４】
この例では、ＦＦＴ演算部１０は、データ転送の後のバタフライ演算を、当該データの昇順（データの位置又はデータのアドレスの昇順、以下同じ）方向へのバタフライ演算及びデータの降順（データの位置又はデータのアドレスの降順、以下同じ）方向へのバタフライ演算に２等分して行う。即ち、第２ステージが第２−１ステージと第２−２ステージとに２等分される。第２−１ステージは、データの昇順方向への（又は、データの先頭からの）バタフライ演算であり、３２Ｋデータの演算である。第２−２ステージは、データの降順方向への（又は、データの最後尾からの）バタフライ演算であり、３２Ｋデータの演算である。従って、第２−１ステージと第２−２ステージとは、キャッシュメモリ１３上のデータを用いて実行することができる。第３及び第４ステージも同様である。データの位置は、周知のように、予め定まる。
【００６５】
最初に、第２−１ステージ及び第２−２ステージにおける最初の３２Ｋデータ（合計で６４Ｋデータ）が、外部メモリ２からキャッシュメモリ１３上に読み込まれる。各々の３２Ｋデータは、４Ｋデータ毎にバースト転送される。
【００６６】
図７から判るように、第２−１ステージの最初の３２Ｋデータは、４Ｋデータづつ、アドレスの昇順方向へ飛び飛びに、８グループのデータからなる。第２−２ステージの最初の３２Ｋデータは、４Ｋデータづつ、アドレスの降順方向へ飛び飛びに、８グループのデータからなる。そして、第２−１ステージの最初の３２Ｋデータをそのまま用いて、第３−１ステージ及び第４−１ステージの最初の３２Ｋデータについての演算を行うことができる。換言すれば、本発明に従って、このように連続したバタフライ演算が可能なように、最初の３２Ｋデータが飛び飛びに読み込まれる。第２−２ステージ〜第４−２ステージについても同様である。従って、これらの期間におけるデータ転送は必要が無い。
【００６７】
更に、図７から判るように、第４−１ステージ及び第４−２ステージの双方の最初の３２Ｋデータ（合計で６４Ｋデータ）をそのまま用いて、実数ＬＡＳＴステージの最初の６４Ｋデータについての演算を行うことができる。これにより得られた合計で６４Ｋデータ（実数ＦＦＴ演算の１２８Ｋデータ）が、キャッシュメモリ１３から外部メモリ２にメモリライトされる。
【００６８】
この後、時分割処理のためのデータ転送（第３のデータ転送）が行われ、最初の３２Ｋデータに続く３２Ｋデータが、キャッシュメモリ１３上に読み込まれる。これについても、同様に、データ転送無しで、第２ステージから実数ＬＡＳＴステージまでの演算を行うことができる。
【００６９】
以上のように、この例においては、キャッシュメモリ１３と外部メモリ２との間におけるデータ転送は、キャッシュメモリ１３のサイズＤｃ当たり１回だけ行われる。即ち、前述のように、（Ｄｃ／Ｄｂ）に対して２を底とするべき乗個のステージ単位まで第２のデータ転送を必要最小限の回数とした結果、１回のみとしている。第１のデータ転送は、省略されている。
【００７０】
従って、この例において、ＦＦＴバタフライ演算途中での外部メモリアクセスは１度だけでよく、またその外部メモリアクセスはバースト転送による高速アクセスが可能なため、高速なＦＦＴ演算が行える。これにより、バタフライ演算の時間を約１／２とすると共に、シャッフリング後における演算において、バタフライ演算のほぼ全てのステージ及び実数ＬＡＳＴステージにおける外部メモリ２へのアクセスを省略している。この結果、この例の場合、シャッフリング前におけるバタフライ演算に要する時間が全体で約１．８ｍ秒、シャッフリングのためのメモリライト及びメモリリードに全体で約１ｍ秒×２、シャッフリング後における演算に要する時間が全体で約０．３４ｍ秒であった（全て第３のデータ転送時間を含む）。なお、ＤＳＰ１の動作クロックは１ＧＨｚである。このように、全体の演算時間に占めるメモリアクセスの時間の割合が大きいので、本発明によるシャッフリング後におけるメモリアクセスの省略の効果は大きい。
【００７１】
以上の説明から理解されるように、本発明によれば、以下のような実施の態様が把握される。
【００７２】
（付記１）実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、
前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリと、
前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行うＦＦＴ演算部とを備え、
前記ＦＦＴ演算部が、前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う
ことを特徴とするＦＦＴ演算装置。
【００７３】
（付記２）実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、
前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリと、
前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行うＦＦＴ演算部とを備え、
前記ＦＦＴ演算部が、前記複数ステージのバタフライ演算のいずれかのステージの後に、前記キャッシュメモリと外部メモリとの間におけるデータ転送を前記キャッシュメモリのサイズ当たり１回だけ行い、前記キャッシュメモリの格納するデータをそのまま使用して、前記複数ステージのバタフライ演算におけるその後のバタフライ演算及び前記変換結果を得るためのバタフライ演算を行う
ことを特徴とするＦＦＴ演算装置。
【００７４】
（付記３）前記ＦＦＴ演算部が、前記外部メモリの有する高速転送モードのみにより、前記キャッシュメモリと外部メモリとの間のデータ転送を行う
ことを特徴とする付記１又は付記２のいずれかに記載のＦＦＴ演算装置。
【００７５】
（付記４）前記ＦＦＴ演算部が、前記データ転送後のバタフライ演算を、前記実数ＦＦＴ演算の対象となるデータの昇順方向へのバタフライ演算及び前記実数ＦＦＴ演算の対象となるデータの降順方向へのバタフライ演算に分けて行う
ことを特徴とする付記１又は付記２のいずれかに記載のＦＦＴ演算装置。
【００７６】
（付記５）前記ＦＦＴ演算部が、前記実数ＦＦＴ演算の対象となるデータについて前記実数ＦＦＴ演算を時分割で行う
ことを特徴とする付記１又は付記２のいずれかに記載のＦＦＴ演算装置。
【００７７】
（付記６）前記ＦＦＴ演算部が複数個設けられ、複数個の前記ＦＦＴ演算部が、前記実数ＦＦＴ演算の対象となるデータについて並列して前記実数ＦＦＴ演算を行う
ことを特徴とする付記１又は付記２のいずれかに記載のＦＦＴ演算装置。
【００７８】
（付記７）実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリとを用いて、前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行う実数ＦＦＴ演算方法であって、
前記複数ステージのバタフライ演算のいずれかのステージの後に前記キャッシュメモリと外部メモリとの間におけるデータ転送を少なくとも１回行うことにより、前記複数ステージのバタフライ演算におけるその後のバタフライ演算と前記変換結果を得るためのバタフライ演算とにおいて必要なデータを前記キャッシュメモリ上に読み込み、
前記その後のバタフライ演算を当該読み込まれたデータを用いて行い、
前記複数ステージのバタフライ演算の後に前記キャッシュメモリの格納するデータをそのまま使用して前記変換結果を得るためのバタフライ演算を行う
ことを特徴とするＦＦＴ演算方法。
【００７９】
（付記８）実数ＦＦＴ演算の対象となるデータを格納する外部メモリと、前記実数ＦＦＴ演算の対象となるデータのサイズよりも小さいサイズのキャッシュメモリであって、前記外部メモリとの間でデータ転送を行うことにより前記実数ＦＦＴ演算の対象となるデータの一部を格納するキャッシュメモリとを用いて、前記キャッシュメモリの格納するデータについて、複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算とからなる実数ＦＦＴ演算を行う実数ＦＦＴ演算方法であって、
前記複数ステージのバタフライ演算と変換結果を得るためのバタフライ演算との間における前記キャッシュメモリと外部メモリとの間のデータ転送を不要にするように、前記キャッシュメモリ上のデータ順序を前記複数のバタフライ演算の途中で変化させる
ことを特徴とするＦＦＴ演算方法。
【産業上の利用可能性】
【００８０】
以上説明したように、本発明によれば、ＦＦＴ演算装置及び方法において、実数ＦＦＴ演算の回数を通常のＦＦＴ演算の回数の１／２とすることができ、かつ、実数ＦＦＴ演算の結果から変換結果を復元するための演算の直前におけるデータ転送を不要とすることができる。従って、本発明によれば、ＦＦＴ演算の時間それ自体を短縮し、かつ、データ転送の時間を短縮して、極めて大量のデータのＦＦＴ演算をリアルタイムで行うことができる。
【００８１】
これにより、大型の電波干渉計の出力する極めて大量のデータのＦＦＴ演算を、スーパーコンピュータ等を用いることなく、市販のＤＳＰを１個又は複数個用いて、リアルタイムで行うことができる。
【００８２】
更に、市販のＤＳＰによって膨大なＦＦＴ演算をリアルタイムで行うことができるので、電波干渉計に限らず、多くの信号処理を例えばパーソナルコンピュータにＤＳＰを搭載するのみで、簡易に行なうことができる。
【００８３】
また、ＦＦＴ演算は多くの科学技術計算の基礎であるので、ＦＦＴ演算を含む種々の科学技術計算を、スーパーコンピュータ等によらずに市販のＤＳＰにより、リアルタイムで行うことができる。
【図面の簡単な説明】
【００８４】
【図１】本発明のＦＦＴ演算装置の構成の一例を示す図である。
【図２】本発明のＦＦＴ演算の説明図である。
【図３】本発明のＦＦＴ演算の説明図である。
【図４】本発明のＦＦＴ演算の説明図である。
【図５】本発明のＦＦＴ演算の説明図である。
【図６】本発明のＦＦＴ演算の他の説明図である。
【図７】本発明のＦＦＴ演算の更に他の説明図である。
【符号の説明】
【００８５】
１  ＤＳＰ（演算装置）
２  外部メモリ
３  システムバス
１０  ＦＦＴ演算部
１１  転送制御ユニット
１２  演算ユニット
１３  キャッシュメモリ
【図１】
2006331186.tif 000005
【図２】
2006331186.tif 000006
【図３】
2006331186.tif 000007
【図４】
2006331186.tif 000008
【図５】
2006331186.tif 000009
【図６】
2006331186.tif 000010
【図７】
2006331186.tif 000011