(57)【要約】高速フーリエ変換アーキテクチャは、並列データ処理経路を有する。入力データを、繰り返し連続するシーケンスの並列データ処理経路に供給し、それらの経路において処理を行う。データ処理経路からの出力を結合して必要とされるシーケンスとするために、データシーケンサを使用する。
2008538434.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換演算を実行する装置において、該装置が、
入力データを受信するための入力部と、
複数の第１データ処理経路であって、前記高速フーリエ変換演算を実行するように各前記処理経路を構成し、かつ、入力データを前記データ処理経路の１つに供給するように、前記入力部に接続した第１データ処理経路と、
前記複数の第１データ処理経路の各々からの出力を受信するように接続した第１データ・スケジューラと、
複数の第２データ処理経路を有する少なくとも一つの他の高速フーリエ変換プロセッサ段とを備え、
前記第１データ・スケジューラを、前記複数の第１データ処理経路の各々の前記出力から、前記他の高速フーリエ変換プロセッサ段における前記複数の第２データ処理経路の各々に入力を供給するように構成したことを特徴とする装置。
【請求項２】
請求項１に記載の装置において、
前記第１データ処理経路の各々は、複数のバタフライ回路と、前記バタフライ回路からの前記出力を受信するための対応する複数のマルチプレクサとを備え、
さらに、前記装置は、
複数のデータ・スケジューラであって、このデータ・スケジューラの数が前記第１データ処理経路のバタフライ回路とマルチプレクサとの数に対応するデータ・スケジューラと、
各々を前記複数のデータ・スケジューラのそれぞれ１つから入力信号を受信するように接続した、前記複数の更なる高速フーリエ変換プロセッサ段と
を備えたことを特徴とする装置。
【請求項３】
請求項２に記載の装置において、
前記第１データ処理経路は各々が、基数２２の単一経路遅延フィードバック高速フーリエ変換プロセッサを備え、
前記複数のバタフライ回路の少なくとも１つは、
１対の第１および第２バタフライ手段であって、それぞれの前記バタフライ手段の出力部からその入力部へのフィードバック経路を有する、第１および第２バタフライ手段と、
前記第２バタフライ手段からの出力を受信するように接続したマルチプレクサと
を備えたことを特徴とする装置。
【請求項４】
請求項２または３に記載の装置において、前記マルチプレクサは各々が、ＣＳＤマルチプレクサを含むことを特徴とする装置。
【請求項５】
請求項４に記載の装置において、前記マルチプレクサは各々が、パイプライン化したＣＳＤマルチプレクサであることを特徴とする装置。
【請求項６】
請求項１または２に記載の装置において、
前記データ・スケジューラは、
入力データを並列に受信し、かつ、第１マルチプレクサ出力データを供給する、第１マルチプレクサと、
前記第１マルチプレクサ出力データを受信し、かつ、受信した前記第１マルチプレクサ出力データを第１制御信号に従って複数のレジスタに供給する、第１デマルチプレクサと、
出力データを並列に供給する第２デマルチプレクサと、
前記複数のレジスタからのデータを受信し、かつ、前記複数のレジスタから受信したデータを、第２制御信号に従って前記第２デマルチプレクサに供給する、第２マルチプレクサと、
前記第１制御信号を前記第１マルチプレクサに供給し、かつ、前記第２制御信号を前記第２デマルチプレクサに供給して、出力データ形式が前記入力データ形式と既知の関係を有するようにしたアドレス発生器と
を備えたことを特徴とする装置。
【請求項７】
請求項１−６のいずれか一項に記載の装置において、入力シリアルデータを受信して、このシリアルデータを前記複数の第１データ処理経路に並列に供給する、シリアル−パラレル変換器を備えたことを特徴とする装置。
【請求項８】
請求項１−７のいずれか一項に記載の装置において、
前記入力データの受信データワードを、反復するシーケンス内の前記複数の第１データ処理経路に供給することを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速フーリエ変換を実行する方法および装置に関する。この方法と装置は、例えば逆フーリエ変換のような、関連する操作を実行することにも適している。
【背景技術】
【０００２】
高速フーリエ変換、および、逆フーリエ変換操作は、例えば、ＩＥＥＥ  ８０２．１１ファミリの通信システムや、ＯＦＤＭ超広帯域無線（ＵＷＢ）通信システムなどのデジタル通信システムなどの信号処理アプリケーションで広く使用されている。
【０００３】
特許文献１は、基数２２の単一経路遅延フィードバック（Ｒ２２ＳＤＦ）アーキテクチャに基づく、高速フーリエ変換プロセッサのアーキテクチャを開示する。入力データに、一連のバタフライ手段のペアを供給し、その個々のペアには第１型のバタフライと第２型のバタフライとを含み、かつ、各バタフライのペアは、その出力からその入力へのフィードバック経路を有する。その連続するバタフライ手段が終了するまで、各ペアの第２バタフライの出力は、マルチプレクサに供給され、その後、そのマルチプレクサの出力は、次のペアの第１バタフライに供給される。
【特許文献１】米国特許第６，０９８，０８８号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＯＦＭＤ超広帯域無線（ＵＷＢ）通信システムのようなデータ通信システムにおいて、高速フーリエ変換プロセッサ・アーキテクチャを使用できるようにするために、プロセッサは高データレートを扱えなければならない。さらに、プロセッサのハードウェア・コストは、重要な要素である。
【課題を解決するための手段】
【０００５】
本発明の第１の態様によれば、高速フーリエ変換動作を実行する装置が設けられ、この装置は、
入力データを受信するための入力部と、
複数の第１データ処理経路であって、前記高速フーリエ変換演算を実行するように各前記処理経路を構成し、かつ、入力データを前記データ処理経路の１つに供給するように、前記入力部に接続した第１データ処理経路と、
前記複数の第１データ処理経路の各々からの出力を受信するように接続した第１データ・スケジューラと、
複数の第２データ処理経路を有する少なくとも一つの他の高速フーリエ変換プロセッサ段とを備え、
前記第１データ・スケジューラを、前記複数の第１データ処理経路の各々の前記出力から、前記他の高速フーリエ変換プロセッサ段における前記複数の第２データ処理経路の各々に入力を供給することを特徴とする。
【発明の効果】
【０００６】
この並列構造は、高いデータ処理速度を達成しつつ、プロセッサのハードウェア・コストが対応して高くならないという効果がある。
【発明を実施するための最良の形態】
【０００７】
本発明の第１の態様によれば、高速フーリエ変換動作を実行する装置が設けられ、この装置は、
データを入力するための入力部と、
前記高速フーリエ変換動作を実行し、かつ、入力データを前記データ処理経路に供給するように、前記入力部と接続した、データ処理経路とを備え、
前記データ処理経路は、複数のバタフライ回路と、このバタフライ回路からの出力を受信するための対応する複数のマルチプレクサとを備え、各前記マルチプレクサはパイプライン化したＣＳＤマルチプレクサを備える。
【０００８】
このことは、高いデータ処理速度を達成することを可能にし、対応したプロセッサのハードウェア・コストの増加も必要としない。
【実施例１】
【０００９】
本発明の理解のために、あくまで例として添付した以下の図面を参照する。
【００１０】
図１は、高速フーリエ変換プロセッサ１０を示す。入力データであるＤａｔａＩｎは、クロック信号Ｃｌｋの周波数に対応したデータ速度で、入力ライン１２に受信される。入力データは、４つのデータ処理経路１４１，１４２，１４２，１４４に分かれる。この４つのデータ処理経路１４１，１４２，１４３，１４４は、基本的に同じものであり、したがって、第１データ処理経路１４１だけを以下に詳細に記述する。第１データ処理経路１４１の対応する特徴と同じ、第２，第３，第４のデータ処理経路の特徴は、図１において、データ処理経路の番号を示す下付き添字を有する同一の参照番号によって識別される。
【００１１】
本発明の本実施例は、４つの並列データ処理用経路を有しているが、必要に応じて、他の並列の形式が使用できることは明らかである。
【００１２】
本発明のこの例示の実施例は、Ｎ＝１２８のプロセッサを示すが、同じ原理が他のサイズのプロセッサに適用できることは明らかである。
【００１３】
受信した入力データのデータワードは、後で詳しく述べるように４つののデータ処理経路１４１，１４２，１４３，１４４に分けられる。４つのデータ処理経路１４１，１４２，１４３，１４４は、それぞれ、４つの異なるクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４をそれぞれのクロックとする。
【００１４】
第１データ処理経路１４１において受信されるデータは、第１型の第１バタフライ１６１に供給され、この第１バタフライ１６１は、その入力と出力との間に接続した１６ワードのフィードバック・レジスタ１８１を有する。４つのデータ処理経路があるので、第１バタフライとフィードバック・レジスタの必要な大きさは、並列データ処理経路を有しないアーキテクチャのように半分の大きさではなく、ＦＦＴプロセッサの大きさの８分の１である。このように、Ｎ＝１２８の８分の１は、バタフライと１６ワードのフィードバック・レジスタを必要とする。
【００１５】
第１型の第１バタフライ１６１からの出力は、第２型の第１バタフライ２０１に供給され、この第２型の第１バタフライ２０１は、その出力と入力との間に結合した、８ワードのフィードバック・レジスタ２２１を有する。
【００１６】
第１型および第２型のバタフライの構造および動作は、当業者にとって周知であるから、さらに詳細に記載はしない。第１データ処理経路１４１が、基数２２の単一経路遅延フィードバック（Ｒ２２ＳＤＦ）高速フーリエ変換プロセッサ・アーキテクチャを形成する点に注意されたい。
【００１７】
第２型の第１バタフライ２０１からの出力データは、クロック信号Ｃｌｋ１に基づいて作動する第１正準サインデジット（ＣＳＤ）マルチプレクサ２４１に供給される。その他３つのデータ処理経路１４２，１４３，１４４内の正準サインデジット（ＣＳＤ）マルチプレクサ２４２，２４３，２４４は、それぞれクロック信号Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて作動する。
【００１８】
図２は、さまざまなクロック信号Ｃｌｋ，Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４の間の関係を図示する。具体的には、クロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４は、それぞれ、クロック信号Ｃｌｋの４分の１の周波数を有するパルスを含む。より詳しくは、クロック信号Ｃｌｋ１は、クロック信号Ｃｌｋのパルス４回ごとに、対応するパルスを含み、クロック信号Ｃｌｋ２は、クロック信号Ｃｌｋのパルス４回ごとに、対応するパルスを含むが、Ｃｌｋ１と比較すると１パルス分遅延し、クロック信号Ｃｌｋ３は、クロック信号Ｃｌｋのパルス４回ごとに、対応するパルスを含むが、Ｃｌｋ２と比較すると１パルス分遅延し、クロック信号Ｃｌｋ４は、クロック信号Ｃｌｋのパルス４回ごとに、対応するパルスを含むが、Ｃｌｋ３と比較すると１パルス分遅延する。
【００１９】
ＣＳＤマルチプレクサの構造を、図３に図式的に示す。具体的には、関連するバタフライからの入力データを、データ準備ブロック７０に供給し、続いて、第１段加減算器７２に供給する。当業者には周知なように、ＣＳＤマルチプレクサは、適切な加／減およびシフト演算によって所望の乗算を行う。ＣＳＤマルチプレクサの段数は、データワードの大きさに依存する。図３は、Ｋ個の段を有するＣＳＤマルチプレクサを示し、最終的にデータを第Ｋ段の加減算器７４に渡して出力することを示す。ＣＳＤマルチプレクサの構造および動作は、当業者にとって周知であるから、より詳細に記載には記載しない。
【００２０】
第１ＣＳＤマルチプレクサ２４１からの出力は、第１型の第２バタフライ２６１に供給され、このバタフライ２６１は、その出力と入力との間に接続した４ワードのフィードバック・レジスタ２８１を有する。第１型の第２バタフライ２６１からの出力データは第２型の第２バタフライ３０１に供給され、そして、それはその出力および入力の間に連結した２ワードのフィードバック・レジスタ３２１を有する。
【００２１】
第２型の第２バタフライ３０１からの出力データは、第２ＣＳＤマルチプレクサ３４１に供給され、クロック信号Ｃｌｋ１に基づいて作動する。その他３本のデータ処理経路１４１，１４２，１４３のＣＳＤマルチプレクサ３４２，３４３，３４４は、それぞれのクロック信号Ｃｌｋ２、Ｃｌｋ３，Ｃｌｋ４に基づいて作動する。ＣＳＤマルチプレクサの構造は、図３に概略的に示した通りである。
【００２２】
第２ＣＳＤマルチプレクサ３４１からの出力は第２型の第３バタフライ３６１に供給され、このバタフライ３６１には、その出力と入力との間に１ワードのフィードバック・レジスタ３８１が接続される。この場合、プロセッサの大きさのために、第２型の第３バタフライの前に、第１型のバタフライの必要が無いことに注意すべきである。
【００２３】
第２型の第３バタフライ３６１からの出力データは、第３ＣＳＤマルチプレクサ４０１に供給され、これは、クロック信号Ｃｌｋ１に基づいて作動する。その他３つのデータ処理経路１４１，１４２，１４３内のＣＳＤマルチプレクサ４０２，４０３，４０４は、それぞれのクロック信号Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて作動する。ＣＳＤマルチプレクサの構造を、図３にて概略的に示す。
【００２４】
４つのデータ処理経路１４１，１４２，１４３，１４４内の第３ＣＳＤマルチプレクサ４０１，４０２，４０３，４０４からの出力データは、クロック信号Ｃｌｋに基づいて作動する第１データ・スケジューラ４２に供給される。第１データ・スケジューラ４２は、データが正しいシーケンスで第１の他の高速フーリエ変換プロセッサ段４４に供給されることを確実にするために作動する。
【００２５】
４つのデータ処理経路１４１，１４２，１４３，１４４から成る初期段のように、第１の他の高速フーリエ変換プロセッサ段４４は、４つのデータ処理経路を有し、各々が第１型のそれぞれのバタフライ４６１，４６２，４６３，４６４を含み、それぞれその出力と入力との間に接続した１ワードのフィードバック・レジスタ４８１，４８２，４８３，４８４を有し、それらはそれぞれのクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて作動する。
【００２６】
第１の他の高速フーリエ変換プロセッサ段４４からの出力データは、クロック信号Ｃｌｋに基づいて作動する第２データ・スケジューラ５０に供給される。第２データ・スケジューラ５０は、データが第２の他の高速フーリエ変換プロセッサ段５２に正しいシーケンスで供給されることを確実にするために作動する。
【００２７】
第２の他の高速フーリエ変換プロセッサ段５２は４つのデータ処理経路を有し、各々が第１型のそれぞれのバタフライ５４１，５４２，５４３，５４４を含み、その出力と入力との間を接続したそれぞれの1ワード・フィードバック・レジスタ５６１，５６２，５６３，５６４を有し、それぞれクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて作動する。
【００２８】
第２の他の高速フーリエ変換プロセッサ段５２からの出力データは、第３のデータ・スケジューラ５８に供給され、それは、クロック信号Ｃｌｋに基づいて作動する。第３のデータ・スケジューラ５８は、データが出力ライン６０に正しいシーケンスで供給されることを確実にするために作動する。ただし、本発明のこの実施例において、出力データはビット逆順バッファ（Bit Reverse Buffer）６２を経て供給される。
【００２９】
上述したように、入力データの受信データ・サンプルは、４つのデータ処理経路１４１，１４２，１４３，１４４に分けられる。
【００３０】
より詳しくは、入力データの受信データワードは、反復するシーケンスの４つのデータ処理経路１４１，１４２，１４３，１４４で分けられる。例えば、入力データの各ブロックの第１番目、第５番目、第９番目、第１３の番目等のワードを、第１データ処理経路１４１に供給し、第２番目、第６番目、第１０番目等のワードを、第２データ処理経路１４２に供給し、第３番目、第７番目、第１１番目等のワードを、第３データ処理経路１４３に供給し、第４番目、第８番目、第１２番目等のワードを、第２データ処理経路１４４に供給するようにすることができる。これらのワードのグループをデータ処理経路に分配する方法は、以下に明らかとするように、第１データ・スケジューラ４２の動作に影響を及ぼす。
【００３１】
図４は、Ｎ＝８のＦＦＴの場合におけるフローグラフを示す。第１段には4つのバタフライ演算（ｂｕｔ１ｓ１，ｂｕｔ２ｓ１，ｂｕｔ３ｓ１およびｂｕｔ４ｓ１）があり、第２段には４つ（ｂｕｔ１ｓ２，ｂｕｔ２ｓ２，ｂｕｔ３ｓ２およびｂｕｔ４ｓ２）の、第３の段にも４つのバタフライ演算（ｂｕｔ１ｓ３，ｂｕｔ２ｓ３，ｂｕｔ３ｓ３およびｂｕｔ４ｓ３）がある。このプロセッサが、２本の並列データ処理経路を有し、本発明に従って実装されたならば、１つの可能性は、各段の第１および第３演算（ｂｕｔ１ｓ１，ｂｕｔ３ｓ１；ｂｕｔ１ｓ２，ｂｕｔ３ｓ２；ｂｕｔ１ｓ３，ｂｕｔ３ｓ３）を第１経路に、第２および第４演算（ｂｕｔ２ｓ１，ｂｕｔ４ｓ１；ｂｕｔ２ｓ２，ｂｕｔ４ｓ２；ｂｕｔ２ｓ３，ｂｕｔ４ｓ３）を第２経路にスケジュールすることである。
【００３２】
図５は、各データ・スケジューラ４２，５０，５８のより詳細な構造を示す概略ブロック図である。前の段からのデータ出力が次のバタフライ段（最初２つのデータ・スケジューラ４２，５０の場合）に正しいシーケンスで提示されるように、あるいは、ビット逆順バッファ（第３データ・スケジューラ５８の場合）に提示されるように、これらは機能する。
【００３３】
前段の４つの並列データ処理経路からの入力データは、第１マルチプレクサ９０に供給される。２ビット・カウンタ９２からの入力に基づいて、４つの入力ワードのうち１つが、第１デマルチプレクサ９４に供給される。アドレス発生器９６からの入力に基づいて、第１デマルチプレクサ９４に供給されるワードは、４台のレジスタ、（Ｄ０）９８，（Ｄ１）１００，（Ｄ２）１０２，（Ｄ３）１０４のうちの1つに渡される。
【００３４】
４台のレジスタ９８，１００，１０２，１０４に保存された値は、第２マルチプレクサ１０６に供給される。アドレス発生器９６からの入力に基づいて、４つの入力ワードのうち１つは、第２デマルチプレクサ１０８に供給される。２ビット・カウンタ９２からの入力に基づいて、第２デマルチプレクサ１０８に供給されるワードは、４本の出力ライン１１０，１１２，１１４，１１６のうち１つに渡され、次のデータ処理段への入力となる。
【００３５】
しかしながら、出力をビット逆順バッファ６２へ渡す第３のデータ・スケジューラ５８の場合、データ処理経路およびビット逆順バッファ６２間で取り決めたインターフェイスによって、第２デマルチプレクサ１０８は、必要としないこともできる。
【００３６】
２ビット・カウンタ９２は、次々に前段の４つのデータ処理経路からデータワードを取出し、次々に後段の４つのデータ処理経路にデータワードを送り出すように動作する。レジスタ９８，１００，１０２，１０４は、第１マルチプレクサ９０を通して取り込まれたデータワードを保存する。
【００３７】
データワードが正しい所望のシーケンスでデータ・スケジューラから送り出されるように、アドレス発生器９６は作動し、それはたとえその所望のシーケンスがデータワードを受信したシーケンスとは異なっていても良い。
【００３８】
アドレス発生器９６によって発生するアドレスのシーケンスは、これを達成するような方法で、データワードをレジスタ９８，１００，１０２，１０４に保存するものである。この図の例において、アドレス発生器９６によって発生する各アドレスは、第１デマルチプレクサ９４および第２マルチプレクサ１０６を制御するために用いる。すなわち、データの１つのワードが第１デマルチプレクサ９４からレジスタのうちの１つに格納されると、第２マルチプレクサ１０６は、出力のために、そのレジスタから前に格納されたこのワードを選択する。
【００３９】
アドレス発生器９６が、第１デマルチプレクサ９４および第２マルチプレクサ１０６を制御するために、異なるシーケンスのアドレスを生成する本発明の別の実施例もまた可能である。これらは、データワードを格納するために、より多くのレジスタを使用することが必要とされる。
【００４０】
必要とされるアドレスのシーケンスは周期的であり、初期化期間の後、（４つの並列のデータ処理経路があるこの図示される実施例において）周期の長さが４クロックサイクルの倍数になることがわかった。図６は、周期の長さが１６のクロックサイクルである実施例を図示する。このように、アドレス発生器９６からの出力である必要なアドレスのシーケンスは、初期化１３０の４つのサイクルを含み、これに、さらに各４サイクルの４つのブロック１３２，１３４，１３６，１３８が続く。更なる第４ブロック１３８の後、シーケンスは第１の更なるブロック１３２に戻る。
【００４１】
図１において例示される本発明の実施例で、図７は、データ・スケジューラ４２の動作および特にそのアドレス発生器９６の動作を図示する。具体的には、データ・スケジューラ４２の場合、４つのデータ処理経路から、ｘ０ｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７の順序のデータワードを受信し、ｘ０ｘ１ｘ４ｘ５ｘ２ｘ３ｘ６ｘ７の順序でバタフライ４６１，４６２，４６３，４６４に出力を供給することを必要とする。図７（ａ）−（ｆ）は、各２０クロックサイクル後の、４つのレジスタ９８，１００，１０２，１０４に格納されたデータワードを示す。
【００４２】
このように、第１サイクルにおいて、アドレス発生器９６は、レジスタ（Ｄ０）９８を示すアドレス”０”を生成し、受信したシーケンスの最初のデータワードｘ０を、図７（ａ）に示すように、Ｄ０に格納する。第２サイクルにおいて、アドレス発生器９６は、レジスタ（Ｄ１）１００を示すアドレス”１”を生成し、受信シーケンスの２番目のデータワードｘ１を、図７（ｂ）に示すように、Ｄ１に格納する。このように初期化の４サイクルの後、図7（ｄ）に示すように、最初の４つの受信データワードｘ０ｘ１ｘ２ｘ３は、それぞれ４つのレジスタに保存される。
【００４３】
第５番目のサイクルにおいて、図7（ｅ）に示すように、出力シーケンスの第１データワードであるため、データワードｘ０を出力することが要求される。したがって、アドレス発生器９６は、アドレス”０”を生成し、レジスタ（Ｄ０）９８を示すが、これは、そのデータワードを格納している場所だからである。この時点で、次の受信データワードは、受信シーケンスの第５のデータワードｘ４であり、したがって、これは、レジスタ（Ｄ０）９８に格納される。
【００４４】
同様に、第６のサイクルで、図7（ｆ）に示すように、データワードｘ１を出力することが要求され、これは、出力シーケンスの第２データワードだからである。したがって、アドレス発生器９６は、アドレス”１”を生成し、レジスタ（Ｄ１）１００を示す。これは、そのデータワードの格納されている場所だからである。この時点で、次の受信データワードは、受信シーケンスの第６のデータワードｘ５であるから、これはレジスタ（Ｄ１）１００に格納される。
【００４５】
このように処理が続き、図７の各図はアドレス発生器９６により生成されるアドレスと、そのアドレスによって示されるレジスタからの出力であるデータワード、およびその結果生じるレジスタＤ０−Ｄ３の内容を示す。合計２０サイクルの後、すなわち、初期化の４サイクルとさらに１６サイクルの後、レジスタＤ０−Ｄ３の内容は初期化の４サイクル後のそれらの値に戻ったことになる。
【００４６】
このことは、アドレスのシーケンスは周期的であることが必要とされ、その周期は１６サイクルであることを示す。すなわち、初期化の４サイクルにおいて必要なアドレスが０１２３であり、そして、その後の１６サイクルで、それらは０１０１−２３０１−２３２３−０１２３であることが、図７から解る。これら１６の更なるサイクルからのアドレスのシーケンスは、１６のサイクルに続くそれぞれのブロックでさらに繰り返される。
【００４７】
第２データ・スケジューラ５０の場合、シーケンスｘ０ｘ１ｘ４ｘ５ｘ２ｘ３ｘ６ｘ７の４つのデータ処理経路からのデータワードを受信し、バタフライ５４１，５４２，５４３，５４４にシーケンスｘ０ｘ２ｘ４ｘ６ｘ１ｘ３ｘ５ｘ７の出力を供給することが必要である。コンピューターシミュレーションによって、または、手動の演算によって、アドレスが０１２３を有する初期化の４サイクルの後、アドレス発生器９６から必要とされるアドレスのシーケンスは、００２２−１０３２−１１３３−０１２３であることがわかる。したがって、また、必要とされるアドレスのシーケンスは周期的であって、１６サイクルの期間を有する。
【００４８】
第３のデータ・スケジューラ５８の場合、シーケンスｘ０ｘ２ｘ４ｘ６ｘ１ｘ３ｘ５ｘ７の４つのデータ処理経路からデータワードを受信し、出力をビット逆順バッファ５８にシーケンスｘ０ｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７で出力を供給することが必要である。ここでも、必要なアドレスのシーケンスは、コンピューターシミュレーションまたは手動の演算によって決定され、この場合は、２４サイクルの周期を有する周期性を有することがわかる。より詳しくは、アドレス発生器９６からの必要とされるアドレスのシーケンスが、アドレス０１２３を有する初期化の４サイクルの後、００１０-２１３０-２２１２−３１０２−３３１３−０１２３であることを決定できる。
【００４９】
必要なアドレスのシーケンスは、この実施例のために用いられたものである。しかしながら、高速フーリエ変換プロセッサの大きさは、図示されたものと異なり、４つより多いまたは少ない並列データ処理経路がある場合は、必要となるアドレスのシーケンスは異なる。しかしながら、あらゆるケースにおいて、必要なアドレスのシーケンスは、特定の順序で出力データワードを供給する必要から推論することができる。
【００５０】
このことは、大量の付加的ハードウェア資源を必要とせず、高いデータ・スループットを有するＦＦＴプロセッサであることを示す。
【００５１】
当業者が理解できるように、入力サンプルおよび出力サンプルを活用するためのモジュールを加えることによって、本発明の高速フーリエ変換プロセッサ・アーキテクチャは、逆フーリエ変換（ＩＦＦＴ）プロセッサにおいても使用することができる。
【実施例２】
【００５２】
さらにより高いデータ・スループットを達成するために、図１に示したＣＳＤマルチプレクサはパイプライン化したＣＳＤマルチプレクサに置き換えることができる。したがって、図８は、本発明の別の実施例を示す。図１のＦＦＴプロセッサの要素と同一の、図８のＦＦＴプロセッサ２１０の要素は、同一の参照番号によって示す。
【００５３】
第２型の第1のバタフライ２０１，２０２，２０３，２０４からの出力は、それぞれのクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて作動する、それぞれの第１のパイプライン化したＣＳＤマルチプレクサ１５２１，１５２２，１５２３，１５２４に供給される。第２型の第２バタフライ３０１，３０２，３０３，３０４からの出力データは、それぞれのクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４を基礎とする、それぞれのパイプライン化したＣＳＤマルチプレクサ１５４１，１５４２，１５４３，１５４４に供給される。第２型の第３のバタフライ３６１，３６２，３６３，３６４からの出力データは、再び、それぞれのクロック信号Ｃｌｋ１，Ｃｌｋ２，Ｃｌｋ３，Ｃｌｋ４に基づいて動作する、それぞれのパイプライン化したＣＳＤマルチプレクサ１５６１，１５６２，１５６３，１５６４に供給される。
【００５４】
各々のパイプライン化したＣＳＤマルチプレクサの構造は、当業者にとって明らかな形式である。既に知られているように、マルチプレクサは、ビットレベルで、またはワードレベルでパイプライン化することができる。マルチプレクサをワードレベルでパイプライン化するべきものである場合、データは各段の出力部で記録され、その結果、クリティカルパスを１つの加算器の範囲内に固定することができる。
【００５５】
本発明の本実施例において、データ・スケジューラ４２，５０，５８は高クロック・スピードで動作しているので、必要であるか望ましい場合、それらをパイプライン化することができる。
【実施例３】
【００５６】
図９は、本発明の他の実施例を示す概略ブロック図である。図１のＦＦＴプロセッサの要素と同一の、図９のＦＦＴプロセッサの要素を、同じ参照番号で示す。
【００５７】
本発明の本実施例において、クロック信号の周波数Ｃｌｋで、入力データであるＤａｔａＩｎは、１：４シリアル−パラレル変換器２２２に供給される。シリアル−パラレル変換器２２２は、受信シリアルデータ列を、４つの並列のデータ列に変換し、これを４つの並列のデータ処理経路１４１，１４２，１４３，１４４に供給する。各ＣＳＤマルチプレクサ２４１，２４２，２４３，２４４が同じクロック信号、すなわち、クロック信号Ｃｌｋの４分の１の周波数（１／４Ｃｌｋ）のクロック信号に基づいて動作することを除き、図１に図示した実施例におけるのと同様に、このデータは、その後、これら４つの並列データ処理経路において処理される。同様に、他のＣＳＤマルチプレクサ３４１，３４２，３４３，３４４;  ４０１，４０２，４０３，４０４もまた、同じクロック信号１／４Ｃｌｋに基づいて動作する。
【００５８】
４つのの並列データ処理用経路１４１，１４２，１４３，１４４からの出力は、その後、第１データ・スケジューラ２２６に供給され、これは、図１の第１データスケジューラ４２と比較して単純化される。全て同じクロックドメインで動作する４つの経路からの入力を受信しているからである。データ・スケジューラ２２６は４つのレジスタを含み、入力データをレジスタに格納することを可能にし、かつ、入力データと格納されたデータとを出力データとして供給することを可能とする。
【００５９】
例えば、第１データ・スケジューラ２２６を例にとると、初期化の間、４つのデータワードｘ０ｘ１ｘ２ｘ３を４つの並列データ処理経路から並列に受信し、４つのレジスタに格納する。
【００６０】
次のクロックサイクルの間、次の４つのデータワードｘ４ｘ５ｘ６ｘ７を受信する。必要な出力データシーケンスを達成するために、新しく受信したデータワードｘ６ｘ７の２つを、現在のデータワードｘ０ｘ１が格納されている２つのレジスタに格納し、一方、他の新たに受信した２つのデータワードｘ４ｘ５を、データワードｘ０ｘ１とともに出力する。次のクロックサイクルの間に、次の４つデータワードｘ０ｘ１ｘ２ｘ３を受信し、それらを４つのレジスタに格納し、一方、現在格納しているデータワードｘ６ｘ７ｘ２ｘ３を出力する。このシーケンスをその後繰り返し行い、入力データシーケンスｘ０ｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７が所望出力データシーケンスｘ０ｘ１ｘ４ｘ５ｘ２ｘ３ｘ６ｘ７に変換されることがわかる。同様の動作を第２データ・スケジューラ２２８において、そして、ブロック２２４のデータ・スケジューラ・セクションにおいても行う。そして、このブロック２２４は、４：１パラレル−シリアル変換器としても動作し、このデータは必要とされる形式のビット逆順バッファ６２に供給できる。
【００６１】
したがって、システム２２０の動作は、５つではなく２つのクロックドメインがあることを除き、基本的に、図１に示されるシステム１０の動作と同様である。
【００６２】
この同じ変更は、また、図８に示されるアーキテクチャに対しても行うことができる。すなわち、入力データを並列の構成に変換することにより、そして、図９を参照して説明したデータ・スケジューラに変更を加えることによって、パイプライン化したＣＳＤマルチプレクサ１５２１，１５２２，１５２３，１５２４；１５４１，１５４２，１５４３，１５４４；１５６１，１５６２，１５６３，１５６４を共通のクロック信号、つまり、クロック信号Ｃｌｋの４分の１の周波数（１／４Ｃｌｋ）に基づいて、動作させることができる。
【００６３】
したがって、大きなハードウェア・コスト増大を必要とせずに、高いデータ速度で入力データの処理をすることができるＦＦＴアーキテクチャについて説明した。
【図面の簡単な説明】
【００６４】
【図１】本発明の第１の態様による高速フーリエ変換プロセッサの構造を示す概略ブロック図である。
【図２】図１に示すプロセッサにおいて使用するクロック信号を示す図である。
【図３】図１に示すプロセッサ内のマルチプレクサの概略図である。
【図４】図１に示すプロセッサに、データを入力するための方法を示す図である。
【図５】図１に示すプロセッサ内のデータ・スケジューラの構造を示す概略ブロック図である。
【図６】図５に示すデータ・スケジューラ内のアドレス発生器の動作を示す概略図である。
【図７】図５に示すデータ・スケジューラの動作を示す図である。
【図８】本発明の第１態様による第２高速フーリエ変換プロセッサの構造を示す概略ブロック図である。
【図９】本発明による他の高速フーリエ変換プロセッサの構造を示す概略ブロック図である。
【図１−１】
2008538434.tif 000003
【図１−２】
2008538434.tif 000004
【図２】
2008538434.tif 000005
【図３】
2008538434.tif 000006
【図４】
2008538434.tif 000007
【図５】
2008538434.tif 000008
【図６】
2008538434.tif 000009
【図７】
2008538434.tif 000010
【図８−１】
2008538434.tif 000011
【図８−２】
2008538434.tif 000012
【図９−１】
2008538434.tif 000013
【図９−２】
2008538434.tif 000014