(57)【要約】【課題】  処理速度を向上させる高速フーリエ変換装置およびその方法を提供する。【解決手段】  本発明の高速フーリエ変換装置は、Ｎ個のデータを書き込むためのＮ個のメモリアドレスを有し、メモリアドレスに対して偶数アドレスと奇数アドレスとに分離された構造を有するメモリと、メモリアドレスに対して最下位ビットを除外した残りのビットから構成されるアドレスを生成するアドレス生成部と、アドレス生成部で生成されたアドレスに基づく偶数アドレスおよび奇数アドレスからデータをそれぞれ呼び出してＲａｄｉｘ−２構造のバタフライ演算を行う演算部と、を備え、新しいディジット反転方式で絡まったメモリアドレスを再配列する。【選択図】      図３
2005196787.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個（Ｎは整数）のデータを処理する高速フーリエ変換装置において、
前記Ｎ個のデータを書き込むためのＮ個のメモリアドレスを有し、前記メモリアドレスに対して偶数アドレスと奇数アドレスとに分離された構造を有するメモリと、
前記メモリアドレスに対して最下位ビットを除外した残りのビットから構成されるアドレスを生成するアドレス生成部と、
前記アドレス生成部で生成されたアドレスに基づいて前記偶数アドレスおよび前記奇数アドレスからそれぞれデータを呼び出してＲａｄｉｘ−２構造のバタフライ演算を行う演算部と、
を備えることを特徴とする高速フーリエ変換装置。
【請求項２】
前記メモリは、
前記メモリアドレスの最下位ビッドが「０」である前記偶数アドレスから構成される第１のバンクと、
前記メモリアドレスの最下位ビットが「１」である前記奇数アドレスから構成される第２のバンクと、
を含むことを特徴とする請求項１に記載の高速フーリエ変換装置。
【請求項３】
前記アドレス生成部は、
ｌｏｇ2Ｎ個のステージ別にＮ／２個のアドレスを生成することを特徴とする請求項１に記載の高速フーリエ変換装置。
【請求項４】
前記演算部は、
前記生成されたアドレスに基づく前記偶数アドレスから呼び出されたデータを用いてＲａｄｉｘ−２構造のバタフライ演算を行う第１の演算部と、
前記生成されたアドレスに基づく前記奇数アドレスから呼び出されたデータを用いてＲａｄｉｘ−２構造のバタフライ演算を行う第２の演算部と、
前記Ｒａｄｉｘ−２構造のバタフライ演算のための回転因子が既に格納されたＲＯＭと、
を含むことを特徴とする請求項１に記載の高速フーリエ変換装置。
【請求項５】
前記第１の演算部は、上位偶数アドレスおよび下位偶数アドレスからそれぞれ呼び出されたデータを用いて演算を行い、前記第２の演算部は、上位奇数アドレスおよび下位奇数アドレスからそれぞれ呼び出されたデータを用いて演算を行い、
前記第１の演算部は、上位偶数アドレスから呼び出されて演算されたデータを、前記上位偶数アドレスに、前記下位偶数アドレスから呼び出されて演算されたデータを、前記上位奇数アドレスにて、それぞれ書き換え、前記第２の演算部は、上位奇数アドレスから呼び出されて演算されたデータを、前記下位偶数アドレスに、前記下位奇数アドレスから呼び出されて演算されたデータを、前記下位奇数アドレスにて、それぞれ書き換えることを特徴とする請求項４に記載の高速フーリエ変換装置。
【請求項６】
前記Ｎ個のデータに対応してカウント値を出力するカウンタと、
前記カウント値に基づいてディジット反転アドレスを生成するディジット反転アドレス生成部と、
をさらに含むことを特徴とする請求項１に記載の高速フーリエ変換装置。
【請求項７】
前記ディジット反転アドレスは、
前記カウント値に対応する呼び出しアドレスの最上位二番目のビットが最上位一番目のビットに位置し、前記呼び出しアドレスの残りのビットがビット反転方式でそれぞれのビットに位置することを特徴とする請求項６に記載の高速フーリエ変換装置。
【請求項８】
Ｎ個（Ｎは整数）のデータに対して高速フーリエ変換を行う高速フーリエ変換処理方法において、
（ａ）入力される前記Ｎ個のデータをＮ個のメモリアドレスを有するメモリに書き込むステップと、
（ｂ）ｌｏｇ2Ｎ個のステージ別にＮ／２個のアドレスを生成するステップと、
（ｃ）前記生成されたアドレスに基づく前記メモリの偶数アドレスおよび奇数アドレスからデータを呼び出して前記ステージ別にＲａｄｉｘ−２構造のバタフライ演算を行ってから前記メモリにて書き換えるステップと、
（ｄ）前記ｌｏｇ2Ｎ番目ステージのＲａｄｉｘ−２構造のバタフライ演算が完了すると、ディジット反転アドレスを生成するステップと、
（ｅ）前記ディジット反転アドレスによって前記メモリにて書き換えられたデータを呼び出すステップと、
を含むことを特徴とする高速フーリエ変換処理方法。
【請求項９】
前記ステップ（ｃ）は、
（ｃ−１）前記生成されたアドレスに基づく上位偶数アドレスおよび下位偶数アドレスから呼び出されたデータを用いて演算を行うステップと、
（ｃ−２）前記生成されたアドレスに基づく上位奇数アドレスおよび下位奇数アドレスから呼び出されたデータを用いて演算を行うステップと、
（ｃ−３）前記上位偶数アドレスから呼び出されて演算されたデータを、前記上位偶数アドレスに、前記下位偶数アドレスから呼び出されて演算されたデータを、前記上位奇数アドレスにて、それぞれ書き換え、前記上位奇数アドレスから呼び出されて演算されたデータを、前記下位偶数アドレスに、前記下位奇数アドレスから呼び出されて演算されたデータを、前記下位奇数アドレスにてそれぞれ書き換えるステップと、
を含むことを特徴とする請求項８に記載の高速フーリエ変換処理方法。
【請求項１０】
前記ステップ（ｄ）は、
（ｄ−１）前記ｌｏｇ2Ｎ番目ステージのＲａｄｉｘ−２構造のバタフライ演算が完了すると、前記Ｎ個のデータに対応してカウント値を出力するステップと、
（ｄ−２）前記カウント値に基づいてディジット反転アドレスを生成するステップと、
を含むことを特徴とする請求項９に記載の高速フーリエ変換処理方法。
【請求項１１】
前記ディジット反転アドレスは、前記カウント値に対応する呼び出しアドレスの最上位二番目のビットは、最上位一番目のビットに配置し、前記呼び出しアドレスの残りのビットは、ビット反転方式でそれぞれのビットに位置することを特徴とする請求項１０に記載の高速フーリエ変換処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ヨーロッパ向けのデジタル放送受信機に関し、より詳しくは、処理速度を向上させる高速フーリエ変換（FFT：Fast Fourier Transform）装置およびその方法に関する。
【背景技術】
【０００２】
一般に、ＦＦＴの最も簡単な実装方法としては、Ｒａｄｉｘ−２構造を採用する方法が挙げられる。図１Ａは、Ｒａｉｄｘ−２構造のバタフライ演算構造を示すものであり、図１Ｂは、１６個のデータをＲａｄｉｘ−２構造でＦＦＴ処理する１６−ｐｏｉｎｔ  ＦＦＴの処理過程を示すものである。図示するように、入力の際に、１６個のデータが書き込まれたアドレスと、バタフライ演算処理が行われてから書き換えられた１６個のアドレスとは、入力時のアドレスに対して絡まった状態となる。従って、一般に、Ｒａｄｉｘ−２構造では、呼び出しアドレスに対してビット反転（bit-reverse）を行ってデータを呼び出す。例えば、呼び出しアドレスが‘０００１’の場合、ビット反転された‘１０００’アドレスのデータを呼び出すようになる。
【０００３】
図１Ｃは、Ｒａｄｉｘ−２構造のＦＦＴをパイプライン方式で実現する場合におけるデータ処理の時間フローを示すものである。図１ＡのＲａｄｉｘ−２構造のバタフライ演算構造を参照すると、メモリから処理すべきデータ（ｎ）を読み出してバタフライ演算（Ａ’［ｎ］）を行った後、再びメモリに格納するのに要するクロック数は、３クロックである。例えば、１０２４−ｐｏｉｎｔ  ＦＦＴをＲａｄｉｘ−２構造のバタフライ演算構造で行う場合において必要な全クロック数は、（３＋（１０２４−１））×ｌｏｇ2１０２４＝１０２６０クロックとなる。ここで、ｌｏｇ2１０２４は、ステージ数である。
【０００４】
しかし、Ｒａｄｉｘ−２構造は、実装化が簡単であるが、他の構造に比べて比較的処理速度が遅いという短所があり、これを補うため、Ｒａｄｉｘ−４、Ｒａｉｄｘ−８など他の構造を採用することがある。しかし一般に、Ｒａｉｄｘ−８構造は、非常に複雑であるため、殆ど使用されていない。
【０００５】
図２Ａは、Ｒａｉｄｘ−４構造のバタフライ演算構造を示すものであり、図２Ｃは、Ｒａｉｄｘ−４構造でＦＦＴ処理する１６−ｐｏｉｎｔ  ＦＦＴの処理過程を示すものである。図示するように、入力の際に、１６個のデータが書き込まれたアドレスとバタフライ演算処理が行われてからメモリにて書き換えられる１６個のアドレスとは、入力時のアドレスに対して絡まった状態となる。従って、一般に、Ｒａｄｉｘ−４構造では、呼び出しアドレスに対してディジット反転(digit-reverse)を行ってデータを呼び出す。例えば、呼び出しアドレスが‘０００１’の場合、ディジット反転された‘０１００’アドレスのデータを呼び出すようになる。
【０００６】
図１Ｂに示したＲａｉｄｘ−２構造と、図２Ｃに示したＲａｄｉｘ−４構造とにおけるステージ数を比較すると、Ｒａｄｉｘ−４構造において必要なステージ個数は１／２であり、これによって、演算処理にかかる時間も減少する。
【０００７】
一般に、バタフライ演算では、図２Ｂに示した、２−ｉｎｐｕｔ方式が使用されている。図２Ｄは、２−ｉｎｐｕｔ方式の１６−ｐｏｉｎｔ  ＦＦＴをパイプライン方式で実装する場合におけるデータ処理の時間フローを示す。図示するように、メモリから処理すべきデータ（ｎ）を読み出してバタフライ演算（Ａ’［ｎ］）を行った後、再びメモリに格納するのに要するクロック数は、７クロックである。例えば、１０２４−ｐｏｉｎｔ  ＦＦＴをＲａｄｉｘ−４で行う場合において必要な全クロック数は、（７＋（１０２４−１））×ｌｏｇ4１０２４＝５１５０クロックとなる。ここで、ｌｏｇ4１０２４は、ステージ数である。
【０００８】
Ｒａｄｉｘ−４構造の演算においては、バタフライ演算構造の実装が複雑であるため、１つの演算構造から結果を得るためにはＲａｄｉｘ−２構造の場合に比べてより多くのクロック数が必要となるが、パイプライン方式の採用およびステージ数の減少により、全クロック数は、半分に減少する。しかし、２０４８−ｐｏｉｎｔ  ＦＦＴ、５１２−ｐｏｉｎｔ  ＦＦＴのように、処理すべきデータの数が４n形態となっていない場合は、Ｒａｄｉｘ−４構造で実装できない。
【０００９】
即ち、Ｒａｄｉｘ−４構造は、Ｒａｄｉｘ−２構造が有する処理速度を向上させることはできるが、処理すべきデータの数に制限があり、その特性を生かすことが難しい。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、前述のような問題点を解決するためになされたものであって、本発明の目的は、Ｒａｄｉｘ−２構造のバタフライ演算構造を有する高速フーリエ変換装置の処理速度を改善する高速フーリエ変換装置およびその方法を提供することにある。
【課題を解決するための手段】
【００１１】
前記の目的を達成するための本発明によれば、Ｎ個のデータを処理する高速フーリエ変換装置において、前記Ｎ個のデータを書き込むためのＮ個のメモリアドレスを有し、前記メモリアドレスに対して偶数アドレスと奇数アドレスとに分離された構造を有するメモリと、前記メモリアドレスに対して最下位ビットを除外した残りのビットから構成されるアドレスを生成するアドレス生成部と、前記アドレス生成部で生成されたアドレスに基づいて前記偶数アドレスおよび前記奇数アドレスからそれぞれデータを呼び出してＲａｄｉｘ−２構造のバタフライ演算を行う演算部と、を備えることを特徴とする。
【００１２】
前記メモリは、前記メモリアドレスの最下位ビッドが「０」である前記偶数アドレスから構成される第１のバンクと、前記メモリアドレスの最下位ビットが「１」である前記奇数アドレスから構成される第２のバンクと、を含み、また、前記アドレス生成部は、ｌｏｇ2Ｎ個のステージ別にＮ／２個のアドレスを生成する。
【００１３】
前記演算部は、前記生成されたアドレスに基づく前記偶数アドレスから呼び出されたデータを用いてＲａｄｉｘ−２構造のバタフライ演算を行う第１の演算部と、前記生成されたアドレスに基づく前記奇数アドレスから呼び出されたデータを用いてＲａｄｉｘ−２構造のバタフライ演算を行う第２の演算部と、前記Ｒａｄｉｘ−２構造のバタフライ演算のための回転因子が既に格納されたＲＯＭと、を含むことを特徴とする。
【００１４】
より好ましくは、前記第１の演算部は、上位偶数アドレスおよび下位偶数アドレスからそれぞれ呼び出されたデータを用いて演算を行い、前記第２の演算部は、上位奇数アドレスおよび下位奇数アドレスからそれぞれ呼び出されたデータを用いて演算を行い、また、前記第１の演算部は、上位偶数アドレスから呼び出されて演算されたデータを、前記上位偶数アドレスにて、前記下位偶数アドレスから呼び出されて演算されたデータを、前記上位奇数アドレスにて、それぞれ書き換え、前記第２の演算部をは、上位奇数アドレスから呼び出されて演算されたデータを、前記下位偶数アドレスにて、前記下位奇数アドレスから呼び出されて演算されたデータを、前記下位奇数アドレスに、それぞれ書き換える。
【００１５】
また、高速フーリエ変換装置は、前記Ｎ個のデータに対応してカウント値を出力するカウンタと、前記カウント値に基づいてディジット反転アドレスを生成するディジット反転アドレス生成部と、をさらに含む。また、好ましくは、前記ディジット反転アドレスは、前記カウント値に対応する呼び出しアドレスの最上位二番目のビットが最上位一番目のビットに位置し、前記呼び出しアドレスの残りのビットがビット反転方式でそれぞれのビットに位置することを特徴とする。
【００１６】
さらに、本発明に係るＮ個のデータに対して高速フーリエ変換を行う高速フーリエ変換処理方法は、（ａ）入力される前記Ｎ個のデータをＮ個のメモリアドレスを有するメモリに書き込むステップと、（ｂ）ｌｏｇ2Ｎ個のステージ別にＮ／２個のアドレスを生成するステップと、（ｃ）前記生成されたアドレスに基づく前記メモリの偶数アドレスおよび奇数アドレスからデータをそれぞれ呼び出して前記ステージ別にＲａｄｉｘ−２構造のバタフライ演算を行ってから前記メモリにて書き換えるステップと、（ｄ）前記ｌｏｇ2Ｎ番目ステージのＲａｄｉｘ−２構造のバタフライ演算が完了すると、ディジット反転アドレスを生成するステップと、（ｅ）前記ディジット反転アドレスによって前記メモリにて書き換えられたデータを呼び出すステップと、を含む。
【００１７】
ここで、前記ステップ（ｃ）は、（ｃ−１）前記生成されたアドレスに基づく上位偶数アドレスおよび下位偶数アドレスから呼び出されたデータを用いて演算を行うステップと、（ｃ−２）前記生成されたアドレスに基づく上位奇数アドレスおよび下位奇数アドレスから呼び出されたデータを用いて演算を行うステップと、（ｃ−３）前記上位偶数アドレスから呼び出されて演算されたデータを、前記上位偶数アドレスにて、前記下位偶数アドレスから呼び出されて演算されたデータを、前記上位奇数アドレスにて、それぞれ書き換え、前記上位奇数アドレスから呼び出されて演算されたデータを、前記下位偶数アドレスにて、前記下位奇数アドレスから呼び出されて演算されたデータを、前記下位奇数アドレスにて、それぞれ書き換えるステップと、を含む。
【００１８】
また、前記ステップ（ｄ）は、（ｄ−１）前記ｌｏｇ2Ｎ番目ステージのＲａｄｉｘ−２構造のバタフライ演算が完了すると、前記Ｎ個のデータに対応してカウント値を出力するステップと、（ｄ−２）前記カウント値に基づいてディジット反転アドレスを生成するステップと、を含む。
【発明の効果】
【００１９】
本発明の高速フーリエ変換装置によれば、２つのバタフライ演算構造を同時に動作させることで処理速度を二倍にすることができ、また、その実装が簡単になる。２つのバタフライ演算構造を同時に使用するため、処理すべきデータが格納されたメモリのアドレスを偶数アドレスと奇数アドレスとに分離し、メモリを第１のバンクおよび第２のバンクに分離して処理する。従って、２つのバンクから同時にそれぞれ２つのデータを呼び出して２つのバタフライ演算を独立して動作させる。
また、本発明に係るバタフライ演算構造に対応する新しいディジット反転方式を適用する。
【発明を実施するための最良の形態】
【００２０】
以下、添付の図面を参照して本発明の好適な実施例を詳述する。
図３は、本発明に係る高速フーリエ変換装置を示す概略的なブロック図である。
高速フーリエ変換装置は、カウンタ３１０、Ｎ／２−ｐｏｉｎｔアドレス生成部３２０、メモリ３３０、演算部３５０、およびディジット反転アドレス生成部３７０を備えて構成されている。
【００２１】
カウンタ３１０は、Ｎ個のデータに対するメモリ３３０の書き込みアドレスおよび呼び出しアドレスを生成するためのカウント値を出力する。
【００２２】
Ｎ／２−ｐｏｉｎｔアドレス生成部３２０は、Ｎ個のデータに対してＲａｉｄｘ−２構造のバタフライ演算を処理するためのＮ／２−ｐｏｉｎｔ呼び出しアドレスを生成する。
【００２３】
メモリ３３０には、入力されるＮ個のデータが下記の表１のように分離されて書き込まれる。即ち、カウンタ３１０から出力されるカウント値に基づいて表１に示されたようにメモリ３３０に書き込む。
【００２４】
【表１】
2005196787.tif 000003
【００２５】
例えば、１６−ｐｏｉｎｔ  ＦＦＴを処理するために入力される１６個のデータをメモリ３３０に書き込む場合、偶数番目の入力データは、偶数アドレスに、奇数番目の入力データは、奇数アドレスに、それぞれ書き込む。
【００２６】
従って、本発明に係るメモリ３３０は、下記の表２に示されたように、偶数アドレス（ｅｖｅｎ：ｅ）と奇数アドレス（ｏｄｄ：ｏ）とに分離された第１および第２のバンク（ＢＡＮＫｅ、ＢＡＮＫｏ）を有する。
【００２７】
【表２】
2005196787.tif 000004
【００２８】
表２に示すように、メモリ３３０は、最下位ビットが‘０’である偶数アドレスから構成される第１のバンク３３１と、最下位ビットが‘１’である奇数アドレスから構成される第２のバンク３３３とに分けられる。従って、第１のバンク３３１のアドレスは、上位３ｂｉｔと‘ｅ’との組み合わせで示すことができ、第２のバンク３３３のアドレスは、上位３ｂｉｔと‘ｏ’との組み合わせで示すことができる。
【００２９】
演算部３５０は、Ｒａｄｉｘ−２構造のバタフライ演算器である第１および第２の演算部３５１、３５３と、バタフライ演算を行うための回転因子(twiddle factor:W)が既に格納されているＲＯＭ３５５を有している。第１および第２の演算部３５１、３５３によるバタフライ演算は、数式（１）に示す通りである。
【００３０】
【数１】
2005196787.tif 000005
【００３１】
式中、ｘ（ｎ）は、入力データ、Ｘ（ｍ）は、ｘ（ｎ）に対するバタフライ演算が行われたデータであり、Ｗは、回転因子である。
【００３２】
Ｎ／２−ｐｏｉｎｔアドレス生成部３２０では、Ｒａｄｉｘ−２構造のバタフライ演算を行うため、２つのＮ／２−ｐｏｉｎｔ  ＦＦＴに対する呼び出しアドレスを生成し、生成された２つのＮ／２−ｐｏｉｎｔ  ＦＦＴに対する呼び出しアドレスは、第１の演算部３５１および第２の演算部３５３にそれぞれ送信される。
【００３３】
従って、第１の演算部３５１は、２つの呼び出しアドレスに対応する第１のバンク３３１の偶数アドレスのデータを呼び出してＲａｄｉｘ−２構造のバタフライ演算を行い、第２の演算部３５３は、第２のバンク３３３から２つの呼び出しアドレスに対応する第２のバンク３３３の奇数アドレスのデータを呼び出してＲａｄｉｘ−２構造のバタフライ演算を行うこととなる。
【００３４】
このように、第１の演算部３５１および第２の演算部３５３でバタフライ演算が行われた各２つのデータを、本発明によって、第１のバンク３３１および第２のバンク３３３にて書き換える。前記のようなＲａｄｉｘ−２構造のバタフライ演算は、ステージ数ｌｏｇ2Ｎ分だけ繰り返されるが、演算されたデータを第１のバンク３３１および第２のバンク３３３にて書き換える方式については、後記する。
【００３５】
ディジット反転アドレス生成部３７０は、ステージ数ｌｏｇ2Ｎ分だけバタフライ演算が完了した後、カウンタ３１０のカウント値に基づいて絡まったメモリアドレスに対してディジット反転アドレスを生成する。従って、ディジット反転アドレスを用いて高速フーリエ変換装置に入力されたデータの順にバタフライ演算されたデータを呼び出すようになる。本発明に係るディジット反転方式については、後述する。
【００３６】
図４は、本発明に係るＲａｄｉｘ−２構造のバタフライ演算を用いてＲａｄｉｘ−４構造のバタフライ演算速度を有する高速フーリエ変換装置を示す詳細ブロック図であり、図５は、図４に示した高速フーリエ変換装置で処理される一例であって、１６−ｐｏｉｎｔ  ＦＦＴ処理過程を示すものである。以下、図４および図５を参照して本発明をより詳しく説明する。
【００３７】
１６個の入力データは、表１に示すように、偶数番目に入力されたデータについては、第１のバンク４３１に順次書き込まれ、奇数番目に入力されたデータについては、第２のバンク４３３に順次書き込まれる。次いで、Ｎ／２−ｐｏｉｎｔアドレス生成部（図３の符号３２０）では、Ｎ／２−ｐｏｉｎｔ、即ち、８−ｐｏｉｎｔ  ＦＦＴの呼び出しアドレスを生成する。
【００３８】
図４に示すように、Ｎ／２−ｐｏｉｎｔアドレス生成部（図３の符号３２０）は、呼び出しアドレス（０００），（１００）を生成して第１の演算部４５１及び第２の演算部４５３に送られる。
【００３９】
第１の演算部４５１は、送られた呼び出しアドレスに対応する第１のバンク４３１の偶数アドレス（０００ｅ），（１００ｅ）に書き込まれたデータ（Ａｅ，Ｂｅ）を呼び出してバタフライ演算を行い、第２の演算部４５３は、提供された呼び出しアドレスに対応する第２のバンク４３３の奇数アドレス（０００ｏ），（１００ｏ）に書き込まれたデータ（Ａｏ，Ｂｏ）を呼び出してバタフライ演算を行う。このとき、第１の演算部４５１および第２の演算部４５３は、ＲＯＭ４５５の回転因子（Ｗ）を用いてＲａｄｉｘ−２構造のバタフライ演算をそれぞれ行う。
【００４０】
第１の演算部４５１では、入力データ（Ａｅ，Ｂｅ）に対してバタフライ演算が行われたデータ（Ａｅ’，Ｂｅ’）を出力し、第２の演算部４５３では、入力データ（Ａｏ，Ｂｏ）に対してバタフライ演算が行われたデータ（Ａｏ’，Ｂｏ’）を出力する。
【００４１】
このように演算が完了した第１の演算部４５１および第２の演算部４５３からの出力データは、メモリである、第１のバンク４３１および第２のバンク４３３で書き換えられる。
【００４２】
第１の演算部４５１および第２の演算部４５３は、演算されたデータ（Ａｅ’，Ｂｅ’）、 （Ａｏ’，Ｂｏ’）を図４に示すような方式で第１のバンク４３１および第２のバンク４３３で、それぞれ書き換える。
【００４３】
即ち、第１の演算部４５１は、第１のバンク４３１の上位アドレス（０００ｅ）から呼び出されて演算されたデータ（Ａｅ’）は、第１のバンク４３１の上位アドレス（０００ｅ）に、下位アドレス（１００ｅ）から呼び出されて演算されたデータ（Ｂｅ’）は、第２のバンク４３３の上位アドレス（０００ｏ）にて書き換える。第２の演算部４５３は、第２のバンク４３３の上位アドレス（０００ｏ）から呼び出されて演算されたデータ（Ａｏ’）は、第１のバンク４３１の下位アドレス（１００ｅ）に、下位アドレス（１００ｏ）から呼び出されて演算されたデータ（Ｂｏ’）は、第２のバンク４３３の下位アドレス（１００ｏ）にて書き換える。
【００４４】
このようにステージ１（Ｓｔａｇｅ  １）に対するＲａｄｉｘ−２構造のバタフライ演算が行われる。
【００４５】
ステージ２（Ｓｔａｇｅ  ２）に対する第１のバンク４３１および第２のバンク４３３の呼び出しおよび書き込みアドレスについては、図５を参照することができる。図示するように、例えば、アドレス生成部（図３の符号３２０）では、呼び出しアドレス（０００），（０１０）を生成して第１のバンク４３１および第２のバンク４３３にそれぞれ送る。また、第１のバンク４３１では、偶数アドレス（０００ｅ），（１００ｅ）で書き込まれたデータを呼び出して第１の演算部４５１に送り、第２のバンク４３３では、奇数アドレス（０００ｏ），（１００ｏ）で書き込まれたデータを呼び出して第２の演算部４５３に送る。第１の演算部４５１および第２の演算部４５３では、回転因子（Ｗ）を用いてバタフライ演算を行う。
【００４６】
次に、第１の演算部４５１は、第１のバンク４３１の上位アドレス（０００ｅ）から呼び出されて演算されたデータを、第１のバンク４３１の上位アドレス（０００ｅ）で、また、下位アドレス（１００ｅ）から呼び出されて演算されたデータを、第２のバンク４３３の上位アドレス（０００ｏ）で書き換える。同様な方式で、第２の演算部４５３は、第２のバンク４３３の上位アドレス（０００ｏ）から呼び出されて演算されたデータを、第１のバンク４３１の下位アドレスにて、また、第２のバンク４３３の下位アドレス（１００ｏ）から呼び出されて演算されたデータを、第２のバンク４３３の下位アドレス（１００ｏ）にて書き換える。
【００４７】
このような方式でステージ３（Ｓｔａｇｅ  ３）およびステージ４（Ｓｔａｇｅ  ４）に対してバタフライ演算を繰り返して行う。
従って、図５に示すように、本発明に係るＲａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴは、前述の図１Bに示した従来のＲａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴに比べて、１つのメモリのアドレスを偶数アドレスと奇数アドレスとに分離して２つのバタフライ演算を同時に動作させることで、処理速度を二倍にできる。
【００４８】
図６は、本発明に係るメモリ構造に対応してＮ／２−ｐｏｉｎｔアドレス生成部（図３の符号３２０）で各ステージ別に生成される呼び出しアドレスを示すものであって、１６−ｐｏｉｎｔ  ＦＦＴを例にしている。図示するように、各ステージ別に生成される呼び出しアドレスは、Ｎ／２−ｐｏｉｎｔ、即ち、Ｒａｄｉｘ−２構造の８−ｐｏｉｎｔ  ＦＦＴに対する呼び出しアドレス生成方式とビット反転方式で示すことができる。ステージ１乃至ステージ３の呼び出しアドレスは、８−ｐｏｉｎｔ  ＦＦＴの呼び出しアドレスと同様な形態を有しており、ステージ４の８−ｐｏｉｎｔ  ＦＦＴの結果に対するビット反転アドレスと同様な形態を有している。
【００４９】
このように本発明に係る高速フーリエ変換装置で処理されたデータは、新しいディジット反転方式を有する。
【００５０】
図７は、本発明に係るディジット反転方式を示す図であって、図５に示したＲａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴ処理過程を参照して本発明に係るディジット反転方式を説明するものである。
【００５１】
前記のような方式でＲａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴが完了した後、メモリで書き換えられたデータのメモリアドレスは、入力時のデータが書き込まれたメモリアドレスに対して絡まった状態となる。従って、入力時のデータ順に演算されたデータを呼び出すため、ディジット反転アドレスを生成するようになる。
【００５２】
ディジット反転アドレス生成部３７０は、カウンタ（図３の符号３１０）から順次出力されるカウント値（０〜Ｎ−１）に基づいて図７に示すような方式でディジット反転アドレスを生成する。図示するように、カウント値に対応する呼び出しアドレスが（ａ［ｎ］ａ［ｎ−１］ａ［ｎ−２］・・・１  ０）である場合、上位２ｂｉｔ、‘ａ［ｎ−１］’をディジット反転アドレスの最上位ビットとし、上位２ｂｉｔを除外した残りのビットに対してはビット反転方式でディジット反転アドレスを生成する。従って、ディジット反転アドレスは、（ａ［ｎ−１］１  ０・・・ａ［ｎ−２］ａ［ｎ］）となる。
【００５３】
このように、図７に示す本発明に係るディジット反転方式は、次のような原理に従う。例えば、図５のステージ４（Ｓｔａｇｅ  ４）の書き込みアドレス（Ｗ＿ＡＤＤ）、‘０００ｏ’（以下、‘０００ｏ’の代わりに‘０００１’を使用）に対するディジット反転アドレスは、次の通りである。先ず、‘０００１’に対してＲａｄｉｘ−２構造のビット反転アドレス‘１０００’となり、‘１０００’に位置するステージ４（Ｓｔａｇｅ  ４）の書き込みアドレス（Ｗ＿ＡＤＤ）は、‘０１０ｅ（０１００）’となる。従って、カウンタの呼び出しアドレス‘０００１’に対するディジット反転アドレスは、‘０１００’となる。
【００５４】
図８は、本発明に係るＲａｄｉｘ−２構造の２つのバタフライ演算構造を有する高速フーリエ変換装置による高速フーリエ変換処理過程を示すフローチャートである。以下、図３乃至図５を参照して本発明に係る高速フーリエ変換処理過程を詳細に説明する。
【００５５】
高速フーリエ変換装置で処理すべきＮ個のデータが入力されると、カウンタ３１０は、入力されるデータに対応してカウント値を出力し、Ｎ／２−ｐｏｉｎｔアドレス生成部３２０は、カウント値に基づいてメモリアドレスを生成する。
【００５６】
メモリ３３０は、メモリアドレスに対して偶数アドレスと奇数アドレスとに分離された第１のバンク３３１と第２のバンク３３３とを有し、このようなメモリ３３０の分離によって、偶数番目に入力されたデータは、第１のバンク３３１に書き込まれ、奇数番目に入力されたデータは、第２のバンク３３３に書き込まれる（Ｓ８１１）。
【００５７】
Ｎ／２−ｐｏｉｎｔアドレス生成部３２０は、Ｒａｄｉｘ−２構造のバタフライ演算構造に対応して２つの呼び出しアドレスを生成し、生成された２つの呼び出しアドレスは、第１の演算部３５１および第２の演算部３５３にそれぞれ提供される（Ｓ８１３）。
【００５８】
次に、第１の演算部３５１は、２つの呼び出しアドレスに対応して第１のバンク３３１から呼び出された２つのデータを用いてバタフライ演算を行い、第２の演算部３５３は、２つの呼び出しアドレスに対応して第２のバンク３３３から呼び出された２つのデータを用いてバタフライ演算を行う（Ｓ８１５）。
【００５９】
次いで、第１の演算部３５１は、第１のバンク３３１の上位アドレスから呼び出されて演算されたデータは、第１のバンク３３１の上位アドレスに、下位アドレスから呼び出されて演算されたデータを、第２のバンク３３３の上位アドレスにて書き換える。また、第２の演算部３５３は、第２のバンク３３３の上位アドレスから呼び出されて演算されたデータは、第１のバンク３３１の下位アドレスに、第２のバンク３３３の下位アドレスから呼び出されて演算されたデータを、第２のバンク３３３の下位アドレスにて書き換える（Ｓ８１７）。
【００６０】
このような方式で、Ｎ個のデータに対してステージ数ｌｏｇ2Ｎ分のバタフライ演算を繰り返して行って第１のバンク３３１および第２のバンク３３３にて書き換える（Ｓ８１９）。
【００６１】
ステージ数ｌｏｇ2Ｎ分に対するバタフライ演算が完了すると、ディジット反転アドレス生成部３７０は、カウンタ３１０のカウント値（０〜Ｎ−１）に基づいて図７に示すような方式でディジット反転アドレスを生成してメモリ３３０に書き込まれたバタフライ演算が行われたデータを順次呼び出す（Ｓ８２１）。
【００６２】
前記のように、高速フーリエ変換を行うにあたって、２つのバタフライ演算構造を同時に動作させる。これによって、処理速度が２倍速くなる。１０２４−ｐｏｉｎｔ  ＦＦＴ処理を行う場合、（３＋１０２４／２−１））×ｌｏｇ2１０２４＝５１４０クロックが必要になる。これは、４n形態のデータをＲａｄｉｘ−４構造のＦＦＴを行う場合と同様な結果であるものの、本発明では、Ｒａｄｉｘ−２構造を基に構成されているため、Ｒａｄｉｘ−４構造で処理できない２n形態のデータも処理できる。また、既存の技術では、演算速度を節減する方式として、主にバタフライ演算構造の簡略化に重点を置いているため、ＦＦＴの全体実行時間には大きな影響を与えなていないが、これに対し、本発明では、バタフライ演算構造の実現が可能であると共にＦＦＴの全体実行時間を半分にすることができる。
【００６３】
ＯＦＤＭ(Orthogonal Frequency Division Multiplex)技術を使用する応用分野であるＤＡＢ(digital audio broadcast)、ＤＭＢ(digital multimedia broadcast)、ワイアレスＬＡＮ(local area network)などにおいてＦＦＴを使用する場合、処理すべきデータの容量より少なくとも２倍のメモリ領域を有する。その理由としては、一定の周期で一定大きさのデータが転送されるため、１周期の間にデータを転送されてから次の周期にＦＦＴを行うようになり、ＦＦＴを行う間に次のデータが転送されるため、他のメモリ空間が必要となるためである。なお、ＯＦＤＭの信号は、データが転送される区間があり、また、同期のためにデータが転送されないＮＵＬＬ区間がある。
【００６４】
本発明により処理速度が向上することによって、ＦＦＴ処理が前記のＮＵＬＬ区間内で行われる場合、既存の二倍のメモリ領域を有する必要がなくなり、１周期におけるデータに対するメモリ領域のみが必要となる。即ち、本発明によって、メモリの使用量をも半分にすることができる効果が得られる。
【００６５】
また、１つのメモリを、偶数アドレスと奇数アドレスとに分離して２つのバタフライ演算構造を同時に動作させるために使用するが、本発明におけるアドレス呼び出し方式は、分離されたメモリに同様に適用されて処理すべきデータ数の半数のＦＦＴに対するアドレス呼び出し方式とビット反転アドレス呼び出し方式とを使用しているため、非常に簡単に実現することができる。また、新しいディジット反転方式を用いてＦＦＴ演算で絡まったメモリアドレスを正しく配列することができる。
【００６６】
以上、本発明の好適な実施の形態を挙げて図示および説明してきたが、本発明は、その趣旨または主要な特徴から逸脱することなく、他の種々の形態で実施することができる。そのため、上述の実施の形態は、あらゆる点で単なる例示にすぎず、限定的に解釈してはならない。本発明の範囲は特許請求の範囲によって示すものであって、明細書本文には、何ら限定されるものではない。さらに、特許請求の範囲の均等範囲に属する変形や変更は、全て本発明の範囲内のものである。
【産業上の利用可能性】
【００６７】
本発明は、処理速度を向上させるための高速フーリエ変換装置およびその方法に適用される。
【図面の簡単な説明】
【００６８】
【図１Ａ】Ｒａｄｉｘ−２構造のバタフライ演算構造を説明するための図である。
【図１Ｂ】Ｒａｄｉｘ−２構造のバタフライ演算構造を説明するための図である。
【図１Ｃ】Ｒａｄｉｘ−２構造のバタフライ演算構造を説明するための図である。
【図２Ａ】Ｒａｄｉｘ−４構造のバタフライ演算構造を説明するための図である。
【図２Ｂ】Ｒａｄｉｘ−４構造のバタフライ演算構造を説明するための図である。
【図２Ｃ】Ｒａｄｉｘ−４構造のバタフライ演算構造を説明するための図である。
【図２Ｄ】Ｒａｄｉｘ−４構造のバタフライ演算構造を説明するための図である。
【図３】本発明に係るＲａｄｉｘ−２構造のバタフライ演算構造を有する高速フーリエ変換装置を示す概略的なブロック図である。
【図４】本発明に係る高速フーリエ変換装置のメモリ３３０および演算部３５０を示す詳細ブロック図である。
【図５】本発明に係る一実施例であって、Ｒａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴ処理過程とその各ステージ別に呼び出し／書き込みアドレスを示す図である。
【図６】本発明に係る一実施例であって、Ｒａｄｉｘ−２構造の１６−ｐｏｉｎｔ  ＦＦＴの各ステージ別に呼び出しアドレスを示す図である。
【図７】本発明に係るディジット反転アドレス生成方式を示す図である。
【図８】本発明に係るＲａｄｉｘ−２構造を有する高速フーリエ変換装置の処理過程を示すフローチャートである。
【符号の説明】
【００６９】
３１０    カウンタ
３２０    Ｎ／２−ｐｏｉｎｔアドレス生成部
３３０    メモリ
３３１    第１のバンク
３３３    第２のバンク
３５０    演算部
３５１    第１の演算部
３５３    第２の演算部
３５５    ＲＯＭ
【図１Ａ】
2005196787.tif 000006
【図１Ｂ】
2005196787.tif 000007
【図１Ｃ】
2005196787.tif 000008
【図２Ａ】
2005196787.tif 000009
【図２Ｂ】
2005196787.tif 000010
【図２Ｃ】
2005196787.tif 000011
【図２Ｄ】
2005196787.tif 000012
【図３】
2005196787.tif 000013
【図４】
2005196787.tif 000014
【図５】
2005196787.tif 000015
【図６】
2005196787.tif 000016
【図７】
2005196787.tif 000017
【図８】
2005196787.tif 000018