(57)【要約】【課題】高速フーリエ変換装置及び高速フーリエ変換処理方法に関し、演算データの並び替えを行うことなくバタフライ演算を行い、より高速にフーリエ変換を行う。【解決手段】高速フーリエ変換におけるバタフライ演算の演算対象のデータを、入力ＲＡＭ１−１の４つのＲＡＭの各アドレスに、アドレス値の各ビットの排他的論理和の値に従って、４つのメモリの番号のインクリメント順又はデクリメント順に、順番に振り分けて格納し、データ選択部１−３で、基数２バタフライ演算の実行対象とするデータを読み出し、各ステージの基数２のバタフライ演算を、２つのバタフライ演算部１−４１，１−４２で実行し、各ステージの演算結果を演算ＲＡＭ１−５に書き込む。そのとき、バタフライ演算の対象となったデータを読み出したメモリと同一番号のメモリの同一のアドレスに書き込む。演算対象のデータのアドレス等は簡易なロジックで生成することができる。【選択図】図１
2008217359.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換におけるバタフライ演算の演算対象のデータを格納する４つのメモリと、
前記４つのメモリに格納されたデータの中から、基数２のバタフライ演算の実行対象とするデータのアドレスを生成するアドレス生成部と、
前記アドレス生成部で生成されたアドレスのデータを前記メモリから読み出して出力するデータ選択部と、
前記データ選択部から入力されるデータに対して、各ステージの基数２のバタフライ演算を実行するバタフライ演算部と、を備え、
前記アドレス生成部は、演算対象の入力データを、４つのメモリの各アドレスに、該アドレス値の各ビットの排他的論理和の値に従って、該４つのメモリの番号のインクリメント順又はデクリメント順に振り分けて格納するよう、該４つのメモリの書き込みアドレスを生成し、かつ、前記バタフライ演算部で実行された各ステージのバタフライ演算の結果を、該バタフライ演算の対象となったデータを読み出したメモリの番号と同一のメモリの同一アドレスに書き込むよう、４つのメモリの書き込みアドレスを生成する構成を有することを特徴とする高速フーリエ変換装置。
【請求項２】
前記バタフライ演算部を２個備え、該２個のバタフライ演算部により、それぞれ異なるデータの組に対して、基数２のバタフライ演算を並列して実行する構成を有することを特徴とする請求項１に記載の高速フーリエ変換装置。
【請求項３】
前記演算対象のデータを格納する４つのメモリとして、入力データを取り込むメモリと、前記バタフライ演算の各ステージの演算結果を格納するメモリとを、別々に設けたことを特徴とする請求項１又は２に記載の高速フーリエ変換装置。
【請求項４】
高速フーリエ変換におけるバタフライ演算の演算対象のデータを、４つのメモリの各アドレスに、該アドレス値の各ビットの排他的論理和の値に従って、該４つのメモリの番号のインクリメント順又はデクリメント順に振り分けて格納し、
前記４つのメモリに格納されたデータの中から、基数２のバタフライ演算の実行対象とするデータを読み出し、各ステージの基数２のバタフライ演算を実行し、
前記バタフライ演算の各ステージの演算結果を、該バタフライ演算の対象となったデータを読み出したメモリと同一番号のメモリの同一のアドレスに書き込むことを特徴とする高速フーリエ変換処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速フーリエ変換装置及び高速フーリエ変換処理方法に関し、特に、高速フーリエ変換（ＦＦＴ：Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）における代表的な演算の一つであるバタフライ演算の改良を図った高速フーリエ変換装置及び高速フーリエ変換処理方法に関する。
【背景技術】
【０００２】
高速フーリエ変換処理は、時間領域信号のサンプルポイントの離散値の複素数データを入力し、サンプルポイント数の入力データに対して、基数４（Ｒａｄｉｘ−４）又は基数２（Ｒａｄｉｘ−２）のバタフライ演算を実行し、演算回数を大幅に減らして周波数領域信号に高速に変換する。
【０００３】
上記演算を行うために、演算データを保存するメモリ（ＲＡＭ：Random Access Memory）、回転子（ＷＮ＝ｅｘｐ（−２πｉ／Ｎ）の係数を格納したメモリ（ＲＯＭ：Read Only Memory）及び複数の演算器を用いて演算を行う構成となっており、サンプルポイント数をＮとしたとき、基数２（Ｒａｄｉｘ−２）の場合ｌｏｇ２Ｎ、基数４（Ｒａｄｉｘ−４の場合ｌｏｇ４Ｎのステージ数のバタフライ演算を行う。
【０００４】
バタフライ演算については下記の特許文献等に記載されている。下記の特許文献１に記載のバタフライ演算は、メモリ（ＲＡＭ）に保存した演算データの並び替えを演算のステージ毎に行って演算処理を行うものである。該演算データの並び替えは、ポイント数が増えるほど、またステージ数が増えるほど、多くの処理時間が掛かり、また、並び替えを行うためのメモリ（ＲＡＭ）を別途用意する必要があり、回路規模が増大してしまう。
【０００５】
また、下記の特許文献２や特許文献３では、演算データを複数のメモリ（ＲＡＭ）に分けて格納し、２つの演算部で同時にバタフライ演算を行う、或いは複数のメモリ（ＲＡＭ）に同時に独立してアクセス可能とすることにより、処理速度の向上を図った高速フーリエ変換装置が提案されている。
【０００６】
下記の特許文献４では、基数４（Ｒａｄｉｘ−４）のバタフライ演算と基数２（Ｒａｄｉｘ−２）のバタフライ演算との混合方式を用いることで、処理時間の短縮を図った高速フーリエ変換処理が提案されている。但し、２の奇数のべき乗のポイント数の場合に基数２（Ｒａｄｉｘ−２）のバタフライ演算を行うときに、データの並べ替えを行っているため、その処理時間を必要とする。
【特許文献１】特開平１１−２０３２７２号公報
【特許文献２】特開２００５−１９６７８７号公報
【特許文献３】特開２００１−５６８０６号公報
【特許文献４】特表２００５−５３１２５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
バタフライ演算において、演算データの並び替えの処理は、メモリ（ＲＡＭ）へのアクセス時間のために、ポイント数の増加とともに処理時間が増えてしまい、上記特許文献１に記載のバタフライ演算のように、ステージ毎に演算データの並び替えを行うと、並び替え処理の時間だけで、例えばポイント数２５６の場合は、ポイント数１６の場合の３２倍に処理時間が増えてしまう。
【０００８】
これは、ポイント数２５６の場合のステージ数は８（＝ｌｏｇ２２５６）で、ポイント数１６の場合のステージ数は４（＝ｌｏｇ２１６）であり、並び替えのためのメモリ（ＲＡＭ）へのアクセス時間は、ポイント数２５６の場合、
（８段×２５６アドレス）／（４段×１６アドレス）＝３２倍
となるからである。
【０００９】
演算時間を短縮するためにはデータの並び替えの処理時間の無駄をなくし、効率的に演算を行うことが必要である。また、バタフライ演算として、基数４（Ｒａｄｉｘ−４）と基数２（Ｒａｄｉｘ−２）とがあるが、基数２（Ｒａｄｉｘ−２）のバタフライ演算は、基数４（Ｒａｄｉｘ−４）のバタフライ演算より、ステージ数が２倍となるため、演算時間が２倍掛かる。一方、基数４（Ｒａｄｉｘ−４）のバタフライ演算は、２の奇数のべき乗のポイント数の場合の高速フーリエ変換処理を実施することができない。
【００１０】
基数２（Ｒａｄｉｘ−２）のバタフライ演算部を２個設け、基数２（Ｒａｄｉｘ−２）のバタフライ演算を並列して同時に行うことにより、基数４（Ｒａｄｉｘ−４）のバタフライ演算と同等の処理速度が得られる高速フーリエ変換装置を構成することができるが、従来のものは、演算データの並び替えなしに演算を行うことができず、基数２（Ｒａｄｉｘ−２）バタフライ演算自体は高速化されても、演算データの並び替えの処理時間が掛かり、メモリ（ＲＡＭ）の個数も増え、回路規模が増大するという問題があった。
【００１１】
本発明は、基数２（Ｒａｄｉｘ−２）のバタフライ演算部を２個設けて並列に演算を実行させても、演算データの並び替えの必要がないように、バタフライ演算を行い、これにより、２の奇数のべき乗のバタフライ演算も実施することができ、基数４（Ｒａｄｉｘ−４）のバタフライ演算と同等の処理時間で高速に演算を行うことができる高速フーリエ変換装置及び高速フーリエ変換処理方法を提供する。
【課題を解決するための手段】
【００１２】
本発明の高速フーリエ変換装置は、高速フーリエ変換におけるバタフライ演算の演算対象のデータを格納する４つのメモリと、前記４つのメモリに格納されたデータの中から、基数２のバタフライ演算の実行対象とするデータのアドレスを生成するアドレス生成部と、前記アドレス生成部で生成されたアドレスのデータを前記メモリから読み出して基数２バタフライ演算部に出力するデータ選択部と、前記データ選択部から入力されるデータに対して、各ステージの基数２のバタフライ演算を実行するバタフライ演算部と、を備え、前記アドレス生成部は、演算対象の入力データを、４つのメモリの各アドレスに、該アドレス値の各ビットの排他的論理和の値に従って、該４つのメモリの番号のインクリメント順又はデクリメント順に、順番に振り分けて格納するよう、該４つのメモリの書き込みアドレスを生成し、かつ、前記バタフライ演算部で実行された各ステージのバタフライ演算の結果を、該バタフライ演算の対象となったデータを読み出したメモリの番号と同一のメモリの同一アドレスに書き込むよう、４つのメモリの書き込みアドレスを生成する構成を有することを特徴とする。
【００１３】
この構成により、演算データの並び替えを行うことなく、各ステージの基数２のバタフライ演算を行うことができる。
【００１４】
また、前記バタフライ演算部を２個備え、該２個のバタフライ演算部により、それぞれ異なるデータの組に対して、基数２のバタフライ演算を同時に並列して実行する構成を有することを特徴とする。この構成により、基数２のバタフライ演算を基数４のバタフライ演算と同等の処理時間で実行することができる。
【００１５】
また、前記演算対象のデータを格納する４つのメモリとして、入力データを取り込むメモリと、前記バタフライ演算の各ステージの演算結果を格納するメモリとを、別々に設けたことを特徴とする。この構成により、１周期分のサンプルポイントの入力データのバタフライ演算の最中に、次の周期の入力データをメモリに取り込んで保持しておき、実行中のバタフライ演算の終了後に、次周期の入力データのバタフライ演算を連続的に行うことができる。
【発明の効果】
【００１６】
本発明によれば、各ステージのバタフライ演算において、演算対象のデータを読み出したメモリの同一アドレスに演算結果を書き込むことにより、演算データの並び替えを行う必要が無く、その分の処理時間を短縮し、並び替え用のメモリを削減することができる。また、基数２のバタフライ演算のみを行い、基数４のバタフライ演算を行わないため、２の奇数のべき乗のポイント数のデータの演算も行うことができる。
【００１７】
また、演算対象のデータを４つのメモリの各アドレスに、該アドレス値の各ビットの排他的論理和の値に従って、該４つのメモリの番号のインクリメント順又はデクリメント順に順番に振り分けて格納することにより、ポイント数によって振り分け方を変えることなく格納することができ、また、演算対象のデータを読み出すメモリのアドレスを、ポイント数に拘わりなく、ビットシフト、デクリメント若しくはインクリメント、排他的論理和等の簡単な論理回路又は論理演算で生成することができ、また、データの出力順のメモリの番号及びアドレスも、同様の簡単な論理回路又は論理演算で生成することができる。
【００１８】
また、基数２のバタフライ演算部を２個設けて並列に動作させることにより、基数４のバタフライ演算と同等の処理時間で演算を行うことができ、２の奇数のべき乗のポイント数のデータの演算も高速に行うことができる。また、データ入力用のメモリと演算用のメモリとを分けて設けたことにより、バタフライ演算を連続的に行うことができ、フーリエ変換処理を高速に行うことができる。
【発明を実施するための最良の形態】
【００１９】
図１に本発明の高速フーリエ変換装置の構成を示す。本発明の高速フーリエ変換装置は、入力データｘ（０），・・・，ｘ（Ｎ）を格納する入力メモリ（ＲＡＭ）１−１と、回転子（Ｗ）の係数を格納した回転子メモリ（ＲＯＭ）１−２と、データ選択部１−３と、基数２（Ｒａｄｉｘ−２）の１ステージ分のバタフライ演算を行う第１及び第２のＲａｄｉｘ−２バタフライ演算部１−４１，１−４２と、バタフライ演算の演算データを格納する演算メモリ（ＲＡＭ）１−５と、アドレス生成部１−６とを備える。
【００２０】
入力メモリ（ＲＡＭ）１−１は、４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）から成り、また、演算メモリ（ＲＡＭ）１−５も、４つのメモリＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ）から成る。入力メモリ（ＲＡＭ）１−１及び演算メモリ（ＲＡＭ）１−５は、共に演算対象のデータを格納するメモリであり、共用することも可能であるが、入力メモリ（ＲＡＭ）１−１と演算メモリ（ＲＡＭ）１−５とに分けて設けたのは、１周期分のサンプルポイントの入力データを、演算メモリ（ＲＡＭ）１−５を使用してバタフライ演算を行っている最中に、次の周期の入力データを入力メモリ（ＲＡＭ）１−１に取り込んで保持しておき、実行中のバタフライ演算の終了後に、次周期の入力データのバタフライ演算を連続的に行い、バタフライ演算処理の高効率化、高速化を図るためである。
【００２１】
図２に連続的なバタフライ演算処理のタイムチャートを示す。同図に示すように、期間Ｔ１で入力データＤ１を入力メモリ（ＲＡＭ）１−１に書き込み、次の期間Ｔ２で演算メモリ（ＲＡＭ）１−５を用いて入力データＤ１のバタフライ演算を実行中に、次の入力データＤ２を入力メモリ（ＲＡＭ）１−１に書き込んでおくことにより、入力データＤ１のバタフライ演算処理が終了した直後に、次の期間Ｔ３で次の入力データＤ２のバタフライ演算処理を連続して実行することが可能となる。
【００２２】
図１に示した本発明の高速フーリエ変換装置におけるバタフライ演算処理のフローは、まず、入力データｘ（０），・・・，ｘ（Ｎ）を、以下に述べる振り分け法によって、入力メモリ（ＲＡＭ）１−１の４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に振り分けて格納する。
【００２３】
データ選択部１−３は、アドレス生成部１−６から生成されるアドレスに従って、入力メモリ（ＲＡＭ）１−１の４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）から同時に４つ入力データ読み出し、また、回転子メモリ（ＲＯＭ）１−２から回転子（Ｗ）の係数を読み出して、第１及び第２のＲａｄｉｘ−２バタフライ演算部１−４１，１−４２に出力する。
【００２４】
第１及び第２のＲａｄｉｘ−２バタフライ演算部１−４１，１−４２は、データ選択部１−３から入力されたデータに対して第１ステージのＲａｄｉｘ−２バタフライ演算を行い、その演算結果を、アドレス生成部１−６によって生成されるアドレスに従って、演算メモリ（ＲＡＭ）１−５の４つのメモリＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ）に書き込むが、書き込む場所は、演算対象の入力データを読み出したメモリ入力メモリ（ＲＡＭ）１−１と同一の記憶位置（ＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）のＲＡＭ番号及びアドレスが同一の位置）に書き込む。
【００２５】
第２ステージのバタフライ演算は、演算メモリ（ＲＡＭ）１−５の４つのメモリＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ）から読み出した演算データを、データ選択部１−３で選択して、第１及び第２のＲａｄｉｘ−２バタフライ演算部１−４１，１−４２に入力し、第１及び第２のＲａｄｉｘ−２バタフライ演算部１−４１，１−４２は、第２ステージ以降のＲａｄｉｘ−２バタフライ演算を行い、該演算結果を、演算データを読み出した演算メモリ（ＲＡＭ）１−５（ＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ））の同一記憶位置に書き込み、第３ステージ以降も同様の動作を繰り返す。そして、最終ステージのバタフライ演算が終了したときに、出力順に演算メモリ（ＲＡＭ）１−５の４つのメモリＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ）から演算結果を読み出し、出力データＦ（０），・・・Ｆ（Ｎ）として出力する。
【００２６】
上述したように、本発明によるバタフライ演算自体は、演算メモリ（ＲＡＭ）１−５のＲＡＭ１（ｏｐ）〜ＲＡＭ４（ｏｐ）の４個のメモリのみの使用で実行可能である。ここで、前述の入力データｘ（０），・・・，ｘ（Ｎ）を、入力メモリ（ＲＡＭ）１−１の４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に振り分ける振り分け法について説明する。
【００２７】
該入力データの振り分け法を図３の表１に示す。表１は、４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）がそれぞれ０番〜３１番の３２個のアドレスを有し、該４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に、ｘ０〜ｘ１２７の１２８個の入力データを振り分けて格納する例を示している。
【００２８】
図３の表１に示すように、４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）の共通のアドレスに関して、アドレス生成部１−６は、該アドレス値の各ビットの排他的論理和（ＸＯＲ）を算出し、該排他的論理和（ＸＯＲ）が０のときは、各メモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）のＲＡＭ番号のインクリメント順に入力データを各メモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に振り分けて当該アドレスに格納し、該アドレス値の各ビットの排他的論理和（ＸＯＲ）が１のときは、各メモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）のＲＡＭ番号のデクリメント順に入力データを振り分けて当該アドレスに格納するよう、入力メモリ（ＲＡＭ）に対して、書き込みアドレスを送出する。
【００２９】
即ち、アドレス０（＝“０００００”）については、その各ビットの排他的論理和（ＸＯＲ）が０なので、入力データの最初の４つの入力データｘ０〜ｘ３をＲＡＭ番号のインクリメント順に、ＲＡＭ１（ｉｎ）にｘ０，ＲＡＭ２（ｉｎ）にｘ１，ＲＡＭ３（ｉｎ）にｘ２，ＲＡＭ４（ｉｎ）にｘ３を格納する。
【００３０】
アドレス１（＝“００００１”）については、その各ビットの排他的論理和（ＸＯＲ）が１なので、入力データの次の４つの入力データｘ４〜ｘ７をＲＡＭ番号のデクリメント順に、ＲＡＭ４（ｉｎ）にｘ４，ＲＡＭ３（ｉｎ）にｘ５，ＲＡＭ２（ｉｎ）にｘ６，ＲＡＭ１（ｉｎ）にｘ７を格納する。
【００３１】
以下同様に、アドレス値の排他的論理和（ＸＯＲ）が０か１かによってインクリメント順又はデクリメント順に、入力データを４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に振り振り分けて格納する。このように格納しておくことにより、演算データの並び替えを行うことなく、バタフライ演算を行うことが可能となる。
【００３２】
図３の表では、入力データｘ１２７までの場合について記載しているが、ｘ１２８以降の入力データに対しても同様の振り分け法で４つのメモリＲＡＭ１（ｉｎ）〜ＲＡＭ４（ｉｎ）に格納することにより、演算データの並び替えを行うことなく、バタフライ演算を行うことが可能であり、ポイント数（Ｎ）によって、振り分け方が変わることはない。
【００３３】
図４にポイント数１６の場合のバタフライ演算の処理フローを示す。同図に示すように、第１ステージの演算として、入力メモリ（ＲＡＭ）のＲＡＭ１（ｉｎ）のアドレス０のデータｘ０とＲＡＭ４（ｉｎ）のアドレス２のデータｘ８とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０及びＲＡＭ４（ｏｐ）のアドレス２に書き込む。
【００３４】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ１（ｉｎ）のアドレス１のデータｘ７とＲＡＭ４（ｉｎ）のアドレス３のデータｘ１５とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１及びＲＡＭ４（ｏｐ）のアドレス３に書き込む。
【００３５】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ１（ｉｎ）のアドレス２のデータｘ１１とＲＡＭ４（ｉｎ）のアドレス０のデータｘ３とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２及びＲＡＭ４（ｏｐ）のアドレス０に書き込む。
【００３６】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ１（ｉｎ）のアドレス３のデータｘ１２とＲＡＭ４（ｉｎ）のアドレス１のデータｘ４とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３及びＲＡＭ４（ｏｐ）のアドレス１に書き込む。
【００３７】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ２（ｉｎ）のアドレス０のデータｘ１とＲＡＭ３（ｉｎ）のアドレス２のデータｘ９とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス０及びＲＡＭ３（ｏｐ）のアドレス２に書き込む。
【００３８】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ２（ｉｎ）のアドレス１のデータｘ６とＲＡＭ３（ｉｎ）のアドレス３のデータｘ１４とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス１及びＲＡＭ３（ｏｐ）のアドレス３に書き込む。
【００３９】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ２（ｉｎ）のアドレス２のデータｘ１０とＲＡＭ３（ｉｎ）のアドレス０のデータｘ２とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス２及びＲＡＭ３（ｏｐ）のアドレス０に書き込む。
【００４０】
同様に、入力メモリ（ＲＡＭ）のＲＡＭ２（ｉｎ）のアドレス３のデータｘ１３とＲＡＭ３（ｉｎ）のアドレス１のデータｘ５とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス３及びＲＡＭ３（ｏｐ）のアドレス１に書き込む。
【００４１】
第２ステージでは、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０のデータｘ０とＲＡＭ４（ｏｐ）のアドレス１のデータｘ４とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０及びＲＡＭ４（ｏｐ）のアドレス１に書き戻す。
【００４２】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１のデータｘ７とＲＡＭ４（ｏｐ）のアドレス０のデータｘ３とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１及びＲＡＭ４（ｏｐ）のアドレス０に書き戻す。
【００４３】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２のデータｘ１１とＲＡＭ４（ｏｐ）のアドレス３のデータｘ１５とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２及びＲＡＭ４（ｏｐ）のアドレス３に書き戻す。
【００４４】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３のデータｘ１２とＲＡＭ４（ｏｐ）のアドレス２のデータｘ８とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３及びＲＡＭ４（ｏｐ）のアドレス２に書き戻す。
【００４５】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス０のデータｘ１とＲＡＭ３（ｏｐ）のアドレス１のデータｘ５とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス０及びＲＡＭ３（ｏｐ）のアドレス１に書き戻す。
【００４６】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス１のデータｘ６とＲＡＭ３（ｏｐ）のアドレス０のデータｘ２とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス１及びＲＡＭ３（ｏｐ）のアドレス０に書き戻す。
【００４７】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス２のデータｘ１０とＲＡＭ３（ｏｐ）のアドレス３のデータｘ１４とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス２及びＲＡＭ３（ｏｐ）のアドレス３に書き戻す。
【００４８】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス３のデータｘ１３とＲＡＭ３（ｏｐ）のアドレス２のデータｘ９とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス３及びＲＡＭ３（ｏｐ）のアドレス２に書き戻す。
【００４９】
第３ステージでは、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０のデータｘ０とＲＡＭ３（ｏｐ）のアドレス０のデータｘ２とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０及びＲＡＭ３（ｏｐ）のアドレス０に書き戻す。
【００５０】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１のデータｘ７とＲＡＭ３（ｏｐ）のアドレス１のデータｘ５とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１及びＲＡＭ３（ｏｐ）のアドレス１に書き戻す。
【００５１】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２のデータｘ１１とＲＡＭ３（ｏｐ）のアドレス２のデータｘ９とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２及びＲＡＭ３（ｏｐ）のアドレス２に書き戻す。
【００５２】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３のデータｘ１２とＲＡＭ３（ｏｐ）のアドレス３のデータｘ１４とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３及びＲＡＭ３（ｏｐ）のアドレス３に書き戻す。
【００５３】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス０のデータｘ１とＲＡＭ４（ｏｐ）のアドレス０のデータｘ３とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス０及びＲＡＭ４（ｏｐ）のアドレス０に書き戻す。
【００５４】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス１のデータｘ６とＲＡＭ４（ｏｐ）のアドレス１のデータｘ４とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス１及びＲＡＭ４（ｏｐ）のアドレス１に書き戻す。
【００５５】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス２のデータｘ１０とＲＡＭ４（ｏｐ）のアドレス２のデータｘ８とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス２及びＲＡＭ４（ｏｐ）のアドレス２に書き戻す。
【００５６】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス３のデータｘ１３とＲＡＭ４（ｏｐ）のアドレス３のデータｘ１５とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ２（ｏｐ）のアドレス３及びＲＡＭ４（ｏｐ）のアドレス３に書き戻す。
【００５７】
第４ステージでは、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０のデータｘ０とＲＡＭ２（ｏｐ）のアドレス０のデータｘ１とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス０及びＲＡＭ２（ｏｐ）のアドレス０に書き戻す。
【００５８】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１のデータｘ７とＲＡＭ２（ｏｐ）のアドレス１のデータｘ６とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス１及びＲＡＭ２（ｏｐ）のアドレス１に書き戻す。
【００５９】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２のデータｘ１１とＲＡＭ２（ｏｐ）のアドレス２のデータｘ１０とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス２及びＲＡＭ２（ｏｐ）のアドレス２に書き戻す。
【００６０】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３のデータｘ１２とＲＡＭ２（ｏｐ）のアドレス３のデータｘ１３とのＲａｄｉｘ−２バタフライ演算を、第１のＲａｄｉｘ−２バタフライ演算部１−４１で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ１（ｏｐ）のアドレス３及びＲＡＭ２（ｏｐ）のアドレス３に書き戻す。
【００６１】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス０のデータｘ２とＲＡＭ４（ｏｐ）のアドレス０のデータｘ３とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス０及びＲＡＭ４（ｏｐ）のアドレス０に書き戻す。
【００６２】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス１のデータｘ５とＲＡＭ４（ｏｐ）のアドレス１のデータｘ４とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス１及びＲＡＭ４（ｏｐ）のアドレス１に書き戻す。
【００６３】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス２のデータｘ９とＲＡＭ４（ｏｐ）のアドレス２のデータｘ８とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス２及びＲＡＭ４（ｏｐ）のアドレス２に書き戻す。
【００６４】
同様に、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス３のデータｘ１４とＲＡＭ４（ｏｐ）のアドレス３のデータｘ１５とのＲａｄｉｘ−２バタフライ演算を、第２のＲａｄｉｘ−２バタフライ演算部１−４２で行い、その演算結果を、それぞれ、演算メモリ（ＲＡＭ）のＲＡＭ３（ｏｐ）のアドレス３及びＲＡＭ４（ｏｐ）のアドレス３に書き戻す。
【００６５】
上述のポイント数１６の場合のバタフライ演算における入力データの組み合わせを図５及び図６の表２に示す。図５は第１ステージ及び第２ステージにおけるＲａｄｉｘ−２バタフライ演算の入力データの組み合わせを示している。また、図６は第３ステージ及び第４ステージにおけるＲａｄｉｘ−２バタフライ演算の入力データの組み合わせを示している。
【００６６】
上述の表２は、例えば、第１ステージのＲａｄｉｘ−２演算（第１の演算部１−４１）の入力１の欄のＲＡＭ番号ＲＡＭ１のアドレス０のデータｘ０と、入力２の欄のＲＡＭ番号ＲＡＭ４のアドレス２のデータｘ８とが、第１のＲａｄｉｘ−２バタフライ演算部１−４１でＲａｄｉｘ−２バタフライ演算されることを示している。他の欄についても同様である。
【００６７】
また、第１ステージのＲａｄｉｘ−２演算（第２の演算部１−４２）の入力１の欄のＲＡＭ番号ＲＡＭ２のアドレス０のデータｘ１と、入力２の欄のＲＡＭ番号ＲＡＭ３のアドレス２のデータｘ９とが、第２のＲａｄｉｘ−２バタフライ演算部１−４２でＲａｄｉｘ−２バタフライ演算されることを示している。他の欄についても同様である。
【００６８】
本発明において、Ｒａｄｉｘ−２バタフライ演算部を２つ備えているため、２組の入力データに対するＲａｄｉｘ−２バタフライ演算を同時に行うことが可能である。例えば、第１ステージの場合では、ＲＡＭ１のアドレス０のデータｘ０とＲＡＭ４のアドレス２のデータｘ８との演算と、ＲＡＭ２のアドレス０のデータｘ１とＲＡＭ３のアドレス２のデータｘ９との演算とを同時に行うことができる。
【００６９】
ポイント数が変わっても演算データの組み合わせは変わらない。これは、表１に示したように、ポイント数が増加しても、前述の振り分け法に従って、増加した入力データを、順番に４つの各入力メモリのＲＡＭ番号の順番に従って、インクリメント順又はデクリメント順に格納し、その演算結果を、該入力データを格納した記憶位置と同一の記憶位置の演算メモリ（ＲＡＭ）に格納するからである。
【００７０】
但し、ポイント数の増加によって、演算のステージ数及びデータ数が増加するが、増加分を除いたデータ部分は、増加前のデータのバタフライ演算と同一である。例えば、ポイント数１６とポイント数３２の場合、ポイント数１６の第１ステージはポイント数３２の第２ステージに当たり、ポイント数１６に対して、ポイント数３２は第１ステージを新たに追加したような形になる。図７〜図９の表３に、ポイント数３２の場合のバタフライ演算における入力データの組み合わせを示す。
【００７１】
次に、Ｒａｄｉｘ−２バタフライ演算の演算対象（入力１及び入力２）の組み合わせのアドレス生成について説明する。演算対象（入力１及び入力２）の組み合わせのアドレスは、以下のようにして生成することができる。該演算対象の一方（入力１）のアドレスは、アドレス値の昇順に生成すればよく、もう一方（入力２）のアドレス生成は、ポイント数の値から導き出すことができる。
【００７２】
上記入力２のアドレス生成について図１０及び図１１を参照して説明する。図１０及び図１１は、ポイント数３２の場合の第１ステージ及び第２ステージにおける入力２のアドレス生成の手順を示しているが、ポイント数が１６や６４等の場合でも同様であり、また、第３ステージ以降についても同様である。
【００７３】
第１ステージの入力２の最初のアドレスは、ポイント数÷８によって算出される。ポイント数が１６の場合は２（＝１６÷８）、ポイント数が３２の場合は４（＝３２÷８）となる。ポイント数が３２の場合、第１ステージの入力２のアドレス（４，５，６，７，０，１，２，３）は、図１０に示すように、最初のアドレス４を２進数で表した“１００”を、その下位２ビットを順にインクリメントし、第２ビット目が“１”から“０”に変化するときに、最上位ビットを“１”から“０”にデクリメントすることによって生成される。
【００７４】
第２ステージの入力２のアドレス（２，３，０，１，６，７，４，５）は、図１０に示すように、第１ステージの最初のアドレス“１００”を１ビット分右シフトすることにより、最初のアドレス“０１０”が生成され、この最初のアドレス“０１０”を、最下位ビットを順にインクリメントし、第２ビット目は、最下位ビットが“１”から“０”に変化するときに、“１”から“０”にデクリメントし、第２ビット目が“０”から“１”に変化するときに、最上位ビットを“０”から“１”にインクリメントすることによって生成される。
【００７５】
第３ステージの入力２のアドレス（１，０，３，２，５，４，７，６）は、図１１に示すように、第２ステージの最初のアドレス“０１０”を１ビット分右シフトすることにより最初のアドレス“００１”が生成され、この最初のアドレス“００１”を、最下位ビットを順にデクリメントし、第２ビット目は、最下位ビットが“０”から“１”に変化するときに、“０”から“１”にインクリメントし、第２ビット目が“１”から“０”に変化するときに、最上位ビットを“０”から“１”にインクリメントすることによって生成される。
【００７６】
第４ステージの入力２のアドレス（０，１，２，３，４，５，６，７）は、第３ステージの最初のアドレス“００１”を１ビット分右シフトすることにより最初のアドレス“０００”が生成され、この最初のアドレス“０００”から順にインクリメントすることによって生成することができる。第５ステージの入力２のアドレス（０，１，２，３，４，５，６，７）についても同様である。
【００７７】
次にデータの出力順について説明する。データの出力順は、入力データの順序の値を２進数で表示したビットの並び順を、上位側と下位側とで互いに入れ替えて逆向きにした値として得られる。図１２の表４にポイント数１６の場合の出力順、図１３の表５にポイント数３２の場合の出力順を示す。表４及び表５には、入力データの順序並びに出力データの順序順及び該出力データが格納されているＲＡＭ番号及びアドレスを示している。
【００７８】
ポイント数３２の場合のデータ出力順のＲＡＭ番号及びアドレスの生成を図１４に示す。データ出力順のアドレスは、同図（ａ）に示すように、データ出力順（入力データの順序の値を２進数で表示したビットの並び順を上位側と下位側とで互いに入れ替えて逆向きにした値）の上位３ビットの値によって与えられる。
【００７９】
また、データ出力順のＲＡＭ番号は、同図（ｂ）に示すように、データの出力順（入力データの順序の値を２進数で表示したビットの並び順を上位側と下位側とで互いに入れ替えて逆向きにした値）の上位４ビットの排他的論理和（ＸＯＲ）の値を第２ビット目に配置し、データの出力順の下位２ビットの排他的論理和（ＸＯＲ）の値を第１ビット目に配置して合成した値に、１を加えることによって与えられる。
【００８０】
ポイント数１６の場合のデータ出力順のＲＡＭ番号及びアドレスの生成も、類似の手法で生成することができる。データ出力順のアドレスは、同様に、データ出力順（入力データの順序の値を２進数で表示したビットの並び順を上位側と下位側とで互いに入れ替えて逆向きにした値）の上位２ビットの値によって与えられる。
【００８１】
また、ポイント数１６の場合のデータ出力順のＲＡＭ番号は、データ出力順の上位３ビットの排他的論理和（ＸＯＲ）の値を第２ビット目に配置し、データ出力順の下位１ビットと上位２ビットとの排他的論理和（ＸＯＲ）の値を第１ビット目に配置して合成した値に、１を加えることによって与えられる。
【図面の簡単な説明】
【００８２】
【図１】本発明の高速フーリエ変換装置の構成を示す図である。
【図２】連続的なバタフライ演算処理のタイムチャートを示す図である。
【図３】表１（入力データの各メモリへの振り分け）を示す図である。
【図４】ポイント数１６の場合のバタフライ演算の処理フローを示す図である。
【図５】表２（ポイント数１６のバタフライ演算の入力データの組み合わせ）を示す図である。
【図６】表２（ポイント数１６のバタフライ演算の入力データの組み合わせ）を示す図である。
【図７】表３（ポイント数３２のバタフライ演算の入力データの組み合わせ）を示す図である。
【図８】表３（ポイント数３２のバタフライ演算の入力データの組み合わせ）を示す図である。
【図９】表３（ポイント数３２のバタフライ演算の入力データの組み合わせ）を示す図である。
【図１０】ポイント数３２の場合のアドレス生成の手順を示す図である。
【図１１】ポイント数３２の場合のアドレス生成の手順を示す図である。
【図１２】表４（ポイント数１６の場合のデータの入力順及び出力順）を示す図である。
【図１３】表５（ポイント数３２の場合のデータの入力順及び出力順）を示す図である。
【図１４】ポイント数３２の場合のデータ出力順のＲＡＭ番号及びアドレスの生成手順を示す図である。
【符号の説明】
【００８３】
１−１  入力メモリ（ＲＡＭ）
１−２  回転子メモリ（ＲＯＭ）
１−３  データ選択部
１−４１，１−４２  Ｒａｄｉｘ−２バタフライ演算部
１−５  演算メモリ（ＲＡＭ）
１−６  アドレス生成部
【図１】
2008217359.tif 000003
【図２】
2008217359.tif 000004
【図３】
2008217359.tif 000005
【図４】
2008217359.tif 000006
【図５】
2008217359.tif 000007
【図６】
2008217359.tif 000008
【図７】
2008217359.tif 000009
【図８】
2008217359.tif 000010
【図９】
2008217359.tif 000011
【図１０】
2008217359.tif 000012
【図１１】
2008217359.tif 000013
【図１２】
2008217359.tif 000014
【図１３】
2008217359.tif 000015
【図１４】
2008217359.tif 000016