(57)【要約】高速フーリエ変換（ＦＦＴ）ハードウェア実施および方法は、集積回路（ＩＣ）に必要なダイ領域を最小化しながら効率的なＦＦＴ処理を提供する。ＦＦＴハードウェアはＮポイントＦＦＴを実施することができる。但し、Ｎ＝ｒｎは基数（ｒ）の関数である。ハードウェア実装は、各々がサンプルを記憶するＮ／ｒ行を有するサンプルメモリを含む。回転因子メモリは、１行あたりｋの回転因子を記憶することができる。但し、０＜ｋ＜ｒは利用可能な複雑な回転乗算器(complex twiddle multiplier)の数を表す。ＦＦＴモジュールはメモリから行を読み、サンプルにｒポイント複素ＦＦＴを実行し、次に回転乗算(twiddle multiplication)を行い、その結果をｒ×ｒのレジスターバンクに書き込む。レジスターバンクの内容は転置された順番でサンプルメモリに書き戻される。この動作は各ステージに対してＮ／ｒ2回反復され、次にｎステージに対して反復され、ＮポイントＦＦＴを生成する。
2007513431.tif 000002
【特許請求の範囲】
【請求項１】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定するための方法において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書き込むことと、
前記メモリからｒ行を読むことと、
ｒ基数ｒ部分ＦＦｔｓを決定し、ｒ2部分ＦＦＴ値を発生することと、
回転因子をｒ2部分ＦＦＴ値に印加してｒ2の重み付けされた部分ＦＦＴ値を発生することと、
前記ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書くことと、
前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生することと、
前記転置された値を前記メモリに書くことと、
前記メモリの内容からＦＦＴ値を決定することとを備えた方法。
【請求項２】
前記メモリにサンプルを書くことは、列方向に転置されたサンプルをｒn-1行とｒ列を有するメモリに書くことを備えた、請求項１の方法。
【請求項３】
前記メモリにサンプルを書くことは、変換される複素サンプルを前記メモリに書くことを備えた、請求項１の方法。
【請求項４】
前記メモリからｒ行を読むことは、
ｒの行インデックスを決定することと、
前記ｒの行インデックスに対応する前記メモリから行を読むこととを備えた、請求項１の方法。
【請求項５】
ｒの行インデックスを計算することは、式ａi＝ｉ×ｒn-k-1に対応する行インデックスを備える、但し、kは前記ＦＦＴのステージを表し、ｉ＝０乃至（ｒ−１）である、請求項４の方法。
【請求項６】
回転因子を前記ｒ2部分ＦＦＴ値に印加することは、
少なくとも１つの複素回転因子を検索することと、
前記少なくとも１つの回転因子と前記ｒ2部分ＦＦＴ値の対応する値との複素乗算を計算することとを備えた、請求項１の方法。
【請求項７】
前記ｒ2の重み付けされた部分ＦＦＴ値を前記レジスターブロックに書くことは、ｒ2の重み付けされた部分ＦＦＴ値を、ｒ行およびｒ列として構成されたレジスターブロックに書くことを備えた、請求項１の方法。
【請求項８】
前記ｒ2の重み付けされた部分ＦＦＴ値を転置することは、
前記レジスターバンクの行および列に対応する重み付けされた部分ＦＦＴ値を検索することと、
前記行および列のインデックスを転置することと、
前記転置されたインデックスに対応する前記行および列に前記重み付けされたＦＦＴを書くこととを備えた、請求項７の方法。
【請求項９】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定するための方法において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書くことと、
ステージ値をイニシャライズすることと、
ブロック値をイニシャライズすることと、
ＦＦＴステージを処理することであって、前記処理は、
ａ）前記ステージ値に基づいてブロックの数を決定することと、
ｂ）前記メモリからｒ行を検索することと、
ｃ）ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生することと、
ｄ）回転因子を前記レジスターブロック内の前記ｒ2部分ＦＦＴ値に印加し、ｒ2の重み付けされたＦＦＴ値を発生することと、
ｅ）前記レジスターブロック内の、前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生することと、
ｆ）前記転置された値を前記メモリに書くことと、
ｇ）前記ブロック値およびステージ値に基づいてステップｂ）乃至ｆ）を反復することと、
ｈ）前記ステージ値をインクリメントすることを含むことと、
前記ＦＦＴステージをｎ回反復することと、
前記メモリの内容からＦＦＴ値を決定することとを備えた方法。
【請求項１０】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定する方法において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書くことと、
ａ）ステージカウンターをイニシャライズすることと、
ｂ）ブロックカウンターおよび部分ＦＦＴカウンターをイニシャライズすることと、
ｃ）前記ステージ、ブロック、および部分ＦＦＴカウンター値に基づいて前記メモリからｒ行を検索することと、
ｄ）ｒ基数ｒ部分ＦＦＴを決定し、ｒ2部分ＦＦＴ値を発生することと、
ｅ）回転因子を前記ｒ2部分ＦＦＴ値に印加しｒ2の重み付けされた部分ＦＦＴ値を発生することと、
ｇ）  前記レジスターブロック内で前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生することと、
ｉ）前記転置された値を前記メモリに書くことと、
ｊ）  前記部分カウンターとブロックカウンターを更新することと、
ｋ）前記ブロックカウンターの値と前記部分ＦＦＴのカウンターの値に基づいてステップｃ）乃至ｊ）を反復することと、
ｌ）前記ステージカウンタの値を更新することと、
ｍ）前記ステージカウンターの値に基づいてステップｂ）乃至ｋ）を反復することと、
前記メモリの内容からＦＦＴ値を決定することとを備えた方法。
【請求項１１】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）装置において、
メモリ行あたりｒサンプルを有するｒnサンプルを記憶するように構成されたメモリと、
前記メモリのｒ行からのサンプルに対してｒのｒ−ポイントＦＦＴ部分ＦＦＴを実行するように構成されたＦＦＴエンジンと、
ｒ列のｒ行として構成され、前記ＦＦＴエンジンから出力値を受信するように構成されたレジスターバンクと、
前記レジスターバンク内の前記値を転置し、転置された値を、前記ＦＦＴエンジンにより動作されるメモリのｒ行に書くように構成された転置モジュールとを備えた装置。
【請求項１２】
少なくとも１つのＦＦＴ回転因子を記憶するように構成された回転因子メモリと、
前記レジスターバンク内のレジスターからの値を、前記回転因子メモリからのＦＦＴ回転因子と乗算するように構成され、出力値を前記レジスターに書くように構成された少なくとも１つの乗算器とをさらに備えた、請求項１１の装置。
【請求項１３】
前記少なくとも１つの乗算器は少なくとも１つの複雑な乗算器を備えた、請求項１２の装置。
【請求項１４】
前記少なくとも１つの乗算器は、ｒ−１複雑な乗算器を備えた、請求項１２の装置。
【請求項１５】
前記回転因子メモリは、ＲＯＭ、ＲＡＭ、ＮＶ−ＲＡＭ、およびフラッシュメモリを備えたグループから選択された少なくとも１つのメモリを備える、請求項１２の装置。
【請求項１６】
前記ｒnサンプルはｒn複素サンプルを備える、請求項１１の装置。
【請求項１７】
前記メモリはＲＡＭを備える、請求項１１の装置。
【請求項１８】
前記ＦＦＴエンジンは、パイプラインＦＦＴエンジンを備える、請求項１１の装置。
【請求項１９】
前記転置モジュールは、列方向に値を読み、値を行方向にメモリに書くことにより前記レジスターバンク内の値を転置する、請求項１１の装置。
【請求項２０】
前記レジスターバンクの行値および列値に相当するレジスター値を読み、前記行値および列値を転置し、前記レジスター値を前記転置された行値および列値に相当する前記レジスターに書くことにより前記レジスター内の値を書く、請求項１１の装置。
【請求項２１】
１つ以上のプロセッサーにより実行されるとき、下記を備えた方法を実行する１つ以上のプロセッサー使用可能な命令群を記憶するように構成された１つ以上の記憶装置において、前記方法は、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書くことと、
前記メモリからｒの行を読むことと、
ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生することと、
回転因子を前記ｒ2部分ＦＦＴ値に印加し、ｒ2の重み付けされた部分ＦＦＴ値を発生することと、
ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書くことと、
前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴ値を転置し、転置された値を発生することと、
前記転置された値を前記メモリに書くことと、
前記メモリの内容からＦＦＴ値を決定することとを備えた、記憶装置。
【請求項２２】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定する装置において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書き込む手段と、
前記メモリからｒ行を読み出す手段と、
ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生する手段と、
回転因子を前記ｒ2部分ＦＦＴ値に適用し、ｒ2の重み付けされた部分ＦＦＴ値を発生する手段と、
前記ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書きこむ手段と、
前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生する手段と、
前記転置された値を前記メモリに書きこむ手段と、
前記メモリの内容からＦＦＴ値を決定する手段とを備えた装置。
【請求項２３】
サンプルを前記メモリに書き込む手段は、列方向に変換されるサンプルを、ｒn-1行およびｒ列を有するメモリに書き込むことを備えた、請求項２２の装置。
【請求項２４】
サンプルを前記メモリに書き込む手段は、変換される複素サンプルを前記メモリに書き込むことを備えた、請求項２２の装置。
【請求項２５】
前記メモリからｒ行を読む手段は、
ｒ行インデックスを決定する手段と、
前記ｒ行インデックスに対応する前記メモリから行を読む手段とを備えた、請求項２２の装置。
【請求項２６】
ｒ行インデックスを決定する手段は、式ａi＝ｉ×ｒn-k-1、但し、kはＦＦＴのステージを表し、ｉ＝０乃至（ｒ−１）である式に対応する行インデックスを決定することを備えた、請求項２４の装置。
【請求項２７】
回転因子を前記ｒ2部分ＦＦＴ値に印加する手段は、
少なくとも１つの複雑な回転因子を受信する手段と、
前記少なくとも１つの複雑な回転因子と、前記ｒ2部分ＦＦＴ値の対応する値との複雑な乗算を計算する手段とを備えた、請求項２２の装置。
【請求項２８】
前記ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書きこむ手段は、ｒ2の重み付けされた部分ＦＦＴ値をｒ行およびｒ列として構成されたレジスターブロックに書き込むことを備えた、請求項２２の装置。
【請求項２９】
前記ｒ2の重み付けされた部分ＦＦＴ値を転置する手段は、
前記レジスターバンクの行および列に対応する重み付けされた部分ＦＦＴ値を検索する手段と、
前記行および列インデックスを転置する手段と、
前記転置されたインデックスに対応する行および列に前記重み付けされた部分ＦＦＴを書き込む手段とを備えた、請求項２８の装置。
【請求項３０】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定する装置において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書き込む手段と、
ステージ値をイニシャライズする手段と、
ブロック値をイニシャライズする手段と、
ＦＦＴステージを処理する手段であって、
ａ）前記ステージ値に基づいてブロックの数を決定する手段と、
ｂ）前記メモリからｒ行を検索する手段と、
ｃ）ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2の部分ＦＦＴ値を発生する手段と、
ｄ）回転因子を前記ｒ2部分ＦＦＴ値に印加し、ｒ2の重み付けされた部分ＦＦＴ値を発生する手段と、
ｅ）前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生する手段と、
ｆ）前記転置された値を前記メモリに書きこむ手段と、
ｇ）前記ブロック値およびステージ値に基づいてステップｂ）乃至ｆ）を反復する手段
ｈ）前記ステージ値をインクリメントする手段とを備えた手段と、
前記ＦＦＴステージの処理をｎ回反復する手段と、
前記メモリの内容からＦＦＴ値を決定する手段とを備えた装置。
【請求項３１】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定する装置において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書き込む手段と、
ａ）ステージカウンターをイニシャライズする手段と、
ｂ）ブロックカウンターおよび部分ＦＦＴカウンターをイニシャライズする手段と、
ｃ）前記ステージカウンター値、ブロックカウンター値、および部分ＦＦＴカウンター値に基づいて前記メモリからｒ行を検索する手段と、
ｄ）ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生する手段と、
ｅ）回転因子を前記ｒ2部分ＦＦＴに印加し、ｒ2の重み付けされた部分ＦＦＴ値を発生する手段と、
ｆ）前記ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書き込む手段と、
ｇ）前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生する手段と、
ｉ）前記転置された値を前記メモリに書きこむ手段と、
ｊ）前記部分ＦＦＴカウンターと前記ブロックカウンターを更新する手段と、
ｋ）前記クロックカウンターおよび前記部分ＦＦＴカウンターの値に基づいてステップｃ）乃至ｊ）を反復する手段と、
ｌ）前記ステージカウンターの値を更新する手段と、
ｍ）前記ステージカウンターの値に基づいてステップｂ）乃至ｋ）を反復する手段と、
前記メモリの内容からＦＦＴ値を決定する手段とを備えた装置。
【発明の詳細な説明】
【関連出願のクロスリファレンス】
【０００１】
この出願は、２００３年１２月５日に出願された、「ハードウェアで高速ＦＦＴＳを実施するための新規なアーキテクチャー(NOVEL ARCHITECTURE FOR IMPLEMENTING HIGHSPEED FFTS IN HARDWARE)というタイトルの米国仮出願番号第６０／５２７，１９６の利益を主張する。この仮出願は、その全体が本明細書に組み込まれる。
【技術分野】
【０００２】
この開示は信号処理の分野に関する。特に、この開示は高速フーリエ変換（ＦＦＴ）を実施するための装置および方法に関する。
【背景技術】
【０００３】
フーリエ変換は時間領域信号をその周波数領域対応物にマッピングするために使用することができる。反対に、逆フーリエ変換は周波数領域信号をその時間領域対応物にマッピングするために使用することができる。フーリエ変換は、時間領域信号のスペクトル解析に特に有効である。さらに、直交周波数分割多重化（ＯＦＤＭ）を実施する通信システムのような通信システムは、フーリエ変換の特性を使用してリニアに離間された階調から複数の時間領域シンボルを発生することができ、シンボルから周波数をリカバーすることができる。
【０００４】
サンプルされたデータシステムは、プロセッサーが所定の数のサンプルに変換を実行することを可能にするために離散フーリエ変換（ＤＦＴ）を実施することができる。しかしながら、ＤＦＴは計算上集中的であり実行するために途方もない処理能力を必要とする。ＮポイントＤＦＴを実行するのに必要な計算の数はＮ2のオーダーであり、Ｏ（Ｎ2）として示される。多くのシステムにおいて、ＤＦＴを実行するためにささげられる処理能力の量は、他のシステム動作のために利用可能な処理量を低減するかもしれない。さらに、リアルタイムシステムとして動作するように構成されるシステムは、その計算のために割り当てられた時間内に所望のサイズのＤＦＴを実行するための十分な処理能力を持たないかもしれない。
【０００５】
高速フーリエ変換（ＦＦＴ）は、ＤＦＴ実施に比べて極めて少ない動作で実行されるフーリエ変換を可能にするフーリエ変換の離散的実施である。特定の実施に応じて、基数ｒのＦＦＴを実行するのに必要な計算の数は典型的にＮ×ｌｏｇr（Ｎ）のオーダーであり、Ｏ（Ｎｌｏｇr（Ｎ））として示される。
【０００６】
これまで、ＦＦＴを実施するシステムは、ＦＦＴを実行するために汎用プロセッサーまたはスタンドアロンデジタルシグナルプロセッサー（ＤＳＰ）を使用したかもしれない。しかしながら、システムは、装置に要求される機能性の大多数を実施するように特別にデザインされた特定用途向け集積回路（ＡＳＩＣ）をますます組み込みつつある。ＡＳＩＣ内でシステム機能性を実施することは、複数の集積回路をインターフェースするのに必要なチップカウント(chip count)およびグルーロジック(glue logic)を最小化する。縮小されたチップカウントは、機能性のいずれをも犠牲にすることなしに、デバイスのためのより小さな物理的設置面積を典型的に可能にさせる。
【０００７】
ＡＳＩＣダイ内の面積量は限られており、ＡＳＩＣ内で実施される機能ブロックは、全体のＡＳＩＣ設計の機能性を改良するために、サイズ、速度、および電力を最適化する必要がある。ＦＦＴにささげられるリソースの量は、ＦＦＴにささげられる利用可能なリソースのパーセンテージを制限するために最小でなければならない。それにもかかわらず、システム要件をサポートするのに十分な速度で変換を実行してもよいことを保証するために十分なリソースをＦＦＴにささげる必要がある。さらに、電源要件および関連する放熱を最小にするためにＦＦＴモジュールにより消費される電力量は最小にする必要がある。それゆえ、ＡＳＩＣのような集積回路内で実施するためのＦＦＴアーキテクチャーを最適化することは望ましいかもしれない。
【発明の概要】
【０００８】
ＦＦＴハードウェア実施および方法は、集積回路（ＩＣ）に必要とされるダイ領域を最小にしながら、効率的なＦＦＴ処理を提供する。ＦＦＴハードウェアはＮポイントのＦＦＴを実施するために使用することができる。但し、Ｎ＝ｒnは基数（ｒ）の関数である。ハードウェア実施は、各々がサンプルを記憶するＮ／ｒ行を有するサンプルメモリを含む。回転因子を記憶するために使用されるメモリは、１行あたりｋの回転因子を有する。但し、０＜ｋ＜ｒは、利用可能な複素回転乗算器の数を表す。ＦＦＴモジュールは、（行アドレスがＦＦＴのステージの関数である）メモリから行を読み、各行のサンプルに適所ｒ−ポイント複素ＦＦＴを実行し、それに続いて（最後のステージを除いて）回転乗算を実施し、結果を、ｒ×ｒのサイズのマトリクスメモリ（レジスターバンク）に書き込む。ｒ×ｒのサイズのマトリクスメモリの内容は、転置された順番で、または任意に転置なしで、サンプルメモリに書き戻される。この動作は、各ステージに対してＮ／ｒ2回反復され、次にｎステージに対して反復され、ＮポイントＦＦＴを生成する。
【０００９】
１つの観点において、ｒポイントの、基数がｒのＦＦＴを決定する方法が開示される。この方法、変換するサンプルを、行あたりｒのサンプルを有するメモリに書くことと、メモリからｒ行を読むことと、基数ｒの、ｒの部分ＦＦＴｓを決定してｒ2の部分ＦＦＴ値を発生させることと、回転因子をｒ2部分ＦＦＴ値に印加してｒ2の重み付けされた部分ＦＦＴ値を発生することと、ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書きこむことと、ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロック内で置き換えて転置された値を発生することと、転置された値をメモリに書くことと、メモリの内容からＦＦＴ値を決定することとを含む。
【００１０】
他の観点において、ｒnポイントの、基数ｒのＦＦＴを決定する方法が開示される。この方法は、変換されるサンプルを、行あたりｒのサンプルを有するメモリに書くことと、ステージ値をイニシャライズすることと、ブロック値をイニシャライズすることと、ＦＦＴステージを処理することと、ＦＦＴステージの処理をｎ回反復することと、メモリの内容からＦＦＴ値を決定することとを含む。ＦＦＴステージを処理することは、ａ）ステージ値に基づいてブロックの数を決定することと、ｂ）メモリから行を検索することと、ｃ）ｒ基数のｒの部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生することと、ｄ）回転因子をｒ2部分ＦＦＴ値に印加し、ｒ2の重み付けされた部分ＦＦＴ値を発生することと、ｅ）ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロック内で転置し転置された値を発生することと、ｆ）転置された値をメモリに書くことと、ｇ）ブロック値およびステージ値に基づいてステップｂ）乃至ステップｆ）を反復し、ステージ値をインクリメントすることを含む。
【００１１】
さらに、他の観点において、ｒn−ポイントの、基数ｒのＦＦＴを決定する方法が開示される。この方法は、行あたりｒのサンプルを有するメモリに変換されるサンプルを書き込むことと、ａ）ステージカウンターをイニシャライズすることと、ｂ）ブロックカウンターおよび部分ＦＦＴ出力カウンターをイニシャライズすることと、ｃ）ステージ値、ブロック値および部分ＦＦＴカウンター値に基づいてメモリからｒの行を検索することと、ｄ）ｒの基数のｒの部分ＦＦＴｓを決定してｒ2の部分ＦＦＴ値を発生することと、ｅ）回転因子をｒ2部分ＦＦＴ値に印加してｒ2の部分ＦＦＴ値を発生することと、ｆ）ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書くことと、ｇ）ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロック内で置き換えて転置された値を発生することと、ｉ）転置された値をメモリに書くことと、ｊ）部分ＦＦＴカウンターおよびブロックカウンターを更新することと、ｋ）ブロックカウンターと部分ＦＦＴカウンターの値に基づいて、ステップｃ）乃至ｊ）を反復することと、ｌ）ステージカウンターの値を更新することと、ｍ）ステージカウンターの値に基づいてステップｂ）乃至ステップｋ）を反復し、メモリの内容からＦＦＴ値を決定することとを含む。
【００１２】
他の観点において、ｒポイントの、基数ｒのＦＦＴ装置が開示される。
【００１３】
この装置は、メモリ行あたりｒのサンプルを有するサンプルを記憶するように構成されたメモリと、メモリのｒの行からのサンプルにｒのｒ−ポイント部分ＦＦＴを実行するように構成されたＦＦＴエンジンと、ｒ行ｒ列として構成されたｒ2のレジスターを有し、ＦＦＴエンジンから出力値を受信するように構成されたレジスターバンクと、レジスターバンク内の値を置換し転置された値を、ＦＦＴエンジンにより動作されるメモリからのｒ行に書き込むように構成された転置モジュールとを含む。
【発明を実施するための最良の形態】
【００１４】
本発明の特徴、性質及び利点は、類似による参照文字が相応して、全体で特定する図面と関連して解釈されるときに後述される詳細な説明からさらに明らかになるであろう。
【００１５】
ＦＦＴまたは逆ＦＦＴ（ＩＦＦＴ）、ＦＦＴモジュールを組み込んだ装置に適したハードウェアアーキテクチャーおよびＦＦＴまたはＩＦＦＴを実行する方法が開示される。ＦＦＴアーキテクチャーは任意の基数のＦＦＴの実施を可能にさせるために一般化される。ＦＦＴアーキテクチャーは小さなチップ面積を維持しながら、ＦＦＴを実行するために使用されるサイクルの数を最小化可能にする。特に、ＦＦＴアーキテクチャーは、しかるべく機能するＦＦＴの期間に実行されるメモリアクセスの数を最適化するためにメモリとレジスター空間を構成する。ＦＦＴアーキテクチャーはさらなる柔軟性をその実施において提供し、特定の設計制約に依存して、基数の変動および複雑な乗算器の数の変動を可能にさせる。速度に敏感に反応するが、ダイ領域にそれほど敏感でない実施において、ＦＦＴアーキテクチャーはさらなる複雑な乗算器およびより高次の基数を用いて実施することができる。ダイ領域により敏感である実施において、基数を低減することができ、複素乗算器の数を低減することができる。
【００１６】
ＦＦＴアーキテクチャーは、ＦＦＴ基数に等しいサンプルの数を記憶するのに十分である、メモリ行幅を有するように構成されるサンプルメモリを含む。従って、サンプルメモリは、行あたりｒサンプルのＮ／ｒ行を有するように構成される。但し、ＮはＦＦＴのサイズを表し、ｒはＦＦＴ基数を表す。ＦＦＴブロックは、メモリから行を検索して、各行内のサンプルにｒ−ポイントＦＦＴを実行するように構成される。ＦＦＴブロックは、ＦＦＴ基数に等しい多数の行を検索するが、各個々の行からのサンプルに対してｒ-ポイントＦＦＴを実行する。
【００１７】
ＦＦＴブロックはｒ-ポイントＦＦＴｓの結果を、ｒ2サンプルを記憶するように構成されるレジスターバンクに書く。レジスターバンクおよび回転因子メモリに接続された複素乗算器は、適切な回転因子でＦＦＴ結果を重み付けする。重み付けされた因子は同じレジスターに戻される。
【００１８】
レジスターバンクの内容は、サンプルメモリ内のオリジナル行に再書き込みされる前に転置される。レジスターバンク内の値の転置は、ＦＦＴサンプルの関係をサンプルメモリの同じ行内に維持することにより、ＦＦＴが適所で実行されることを可能にする。サンプルメモリ内のサンプルは検索され、処理され、Ｎ−ポイントＦＦＴを実行するために十分な多数のステージのためにサンプルメモリに戻される。開示されたアーキテクチャーにおいてハードウェアベースのトレードオフの議論に進む前に種々のＦＦＴアルゴリズムの算術の複雑性を最初に調べることは重要である。基数２、４、８、１６のＣｏｏｌｅｙ−Ｔｕｋｅｙアルゴリズムおよび分割基数アルゴリズムが調べられる。たとえ、これらのアルゴリズムの複雑性がＣｏｏｌｅｙ−Ｔｕｋｅｙベースアルゴリズムよりも低いかもしれないとしても、主要因ベースアルゴリズムは、正規構造を有さず、量子化により敏感であるので、主要因ベースアルゴリズムは、考慮されない。
【００１９】
アルゴリズムの複雑性はここでは、要求される実際の実質乗算および加算の数に基づいて評価される。複素乗算は４つの実質の乗算と２つの実質の加算に等しいと仮定される。
【００２０】
基数ｒアルゴリズムにより要求される実質乗算と実質加算の数は、これらのアルゴリズムがｒnポイントＤＦＴの計算を、（ｒn-1−１）（ｒ−１）回転乗算を犠牲にしてｒ、ｒn-1−ポイントＤＦＴｓの計算に分割することに留意して、さらにｒn-1ｒ-ポイントＴＦＴｓによる更なる処理によって決定することができる。図１は、この構造を実証する８ポイントの基数２  ＦＦＴの信号フローの例である。
【数１】
2007513431.tif 000003
【００２１】
によりｒnポイントＦＦＴに対して要求される実質乗算の数と、
【数２】
2007513431.tif 000004
【００２２】
により要求される実質加算の数を表示すると、処理の複雑性は再帰により定義される。
【数３】
2007513431.tif 000005
【００２３】
初期条件を用いて：
【数４】
2007513431.tif 000006
【００２４】
分割基数アルゴリズムの複雑性は同様の方法で評価される。分割基数アルゴリズムは、いくつかの回転乗算を犠牲にして、Ｎ−ポイントＦＦＴをサイズＮ／２の１つのＦＦＴとサイズＮ／４の２つのＦＦＴｓに分割する。アルゴリズムの複雑性は再帰により定義される。
【数５】
2007513431.tif 000007
【００２５】
これらの再帰に基づいて、いくつかの共通のＦＦＴアルゴリズムの複雑性は、表にして比較することができる。表１および２は、共通のＦＦＴアルゴリズムのための複雑性結果を編集する。表は、評価されなかったこれらの設定のための空のセルを含む。
【表１】
2007513431.tif 000008
【表２】
2007513431.tif 000009
【００２６】
表１および２における算術複雑性は、異なるアルゴリズムでＦＦＴを実施する際のハードウェアコストの全体像を与えない。メモリからのデータと回転因子をアクセスし、データをメモリに書くコストを考慮する必要がある。下記の表は、異なる基数サイズのための異なるアルゴリズムにより要求されるメモリアクセスの数（データアクセスのみがカウントされる）を示す。データアクセスの数は、Ｎ−ポイントＦＦＴ／ＩＦＦＴの基数ｒの実施の場合、ステージの合計数はｌｏｇr（Ｎ）であり、各ステージは２Ｎのリード動作およびライト動作を必要とし、２Ｎｌｏｇr（Ｎ）メモリ複素サンプルアクセス動作をもたらす。
【表３】
2007513431.tif 000010
【００２７】
ハードウェア内におけるＦＦＴ実施の解析は、使用されるサイクルの観点から主要なコストはメモリアクセスで消費されることを示す。メモリアクセスの数は増加する基数とともに減少する。しかしながら、１つの複雑なサンプル／サイクルをアクセスすることは多くのアプリケーションに対して重要ではないかもしれない。簡単な例は潜在的な問題を例証する。
【００２８】
４μｓのシンボル期間と４０ＭＨｚのクロックレートを有する直交周波数分割多重（ＯＦＤＭ）のための６４−ポイントＦＦＴを実施する問題を考える。そのようなシステムは、例えば、４０ＭＨｚのクロックを有した１ＥＥＥ８０２．１１ａシステムであってよい。４０ＭＨｚのクロックレートと組み合わせた４μｓのＯＦＤＭシンボル期間は、シンボル間で利用可能な１６０サイクルに変換する。
【００２９】
基数−２アルゴリズムを用いた６４ポイントＦＦＴを実施するコストが最初に調べられる。上記の表で示されるように、必要とされるメモリアクセスの合計数は７６８である。それゆえ、サイクルあたり１サンプルリードまたはライトのみを有するメモリを用いて基数−２アルゴリズムを実施することは、最小で７６８サイクルかかるであろう。これは、計算のために利用可能なサイクル数の約５倍である。分割基数アルゴリズムは、基数−２アルゴリズムとして比較可能な量のメモリアクセスを要求する同じ問題に苦しむ。
【００３０】
しかしながら、基数−４アルゴリズムを用いた６４ポイントＦＦＴの場合、要求されるメモリアクセスの数は３８４である。これはよりよいが依然として利用可能なサイクルの数よりはるかに高い。ＦＦＴ内のステージの数が減少するにつれ、ＦＦＴアルゴリズムの基数内のさらなる増加、メモリアクセスのさらなる減少が要求される。
【００３１】
任意の基数アルゴリズムのための高速実施は、並列リードおよびライトを可能にするメモリ構造の使用により達成することができる。特別の基数−ｒアルゴリズムの場合、リード動作のためであろうとまたはライト動作のためであろうと、１サイクル内のｒ−値のアクセスを可能にさせるメモリ構造は、アルゴリズムのスループットを改良する。概念的には、並列アクセスは、各行にワードを有するＲＡＭとみなすことができる。しかしながら、このメモリ構造から最大利益を得るために、ｒ−ポイントＦＦＴを計算するのに必要なｒ−サンプルは、アルゴリズムのあらゆる段階で同じ行にある必要がある。これは、サンプルメモリのｒ行をリードし、ｒ、ｒ−ポイントＦＦＴｓを計算し、サンプルメモリへの転置の後で結果を書き込むことにより達成することができる。転置動作は、ｒ2レジスターのマトリクスメモリ内で実行することができる。基数ｒが増加するにつれ、ＦＦＴエンジンのサイズおよびマトリクスメモリのサイズが増加する。速度に対する領域のトレードオフは、任意の特定の実施に対して実行することができる。
【００３２】
図２は、ＦＦＴモジュール２００の一実施形態の機能ブロック図である。ＦＦＴモジュール２００は、フォワード変換と逆変換との間の対称により、小さな変化のみを有したＩＦＦＴモジュールとして構成してもよい。ＦＦＴモジュール２００は、単一のＩＣダイ上に実施してもよく、ＡＳＩＣの一部として実施してもよい。あるいは、ＦＦＴモジュール２００は、互いに通信している複数のエレメントとして実施してもよい。さらに、ＦＦＴモジュール２００は特定のＦＦＴ構造に限定されない。例えば、ＦＦＴモジュール２００は、時間におけるデシメーション(decimation)または周波数におけるデシメーションを実行するように構成することができる。
【００３３】
ＦＦＴモジュール２００は変換されるサンプルを記憶するように構成されるメモリ２１０を含む。さらに、ＦＦＴモジュール２００は変換の適所計算を実行するように構成されるので、メモリ２１０は、ＦＦＴの各ステージの結果およびＦＦＴモジュール２００の出力を記憶するために使用される。
【００３４】
メモリ２１０は、ＦＦＴのサイズおよびＦＦＴの基数に一部基づいて分類することができる。基数ｒのＮポイントＦＦＴの場合であって、Ｎ＝ｒnの場合、メモリ２１０は、行あたりｒサンプルを用いて、ｒn-1行にＮのサンプルを記憶するように分類することができる。メモリ２１０は、行あたりのサンプルの数により乗算されるサンプルあたりのビットの数に等しい幅を有するように構成することができる。メモリ２１０は実成分と虚成分としてサンプルを記憶するように典型的に構成される。従って、基数２ＦＦＴの場合、メモリ２１０は行あたり２つのサンプルを記憶するように構成され、第１のサンプルの実部、第１のサンプルの虚部、第２のサンプルの実部、および第２のサンプルの虚部としてサンプルを記憶してもよい。サンプルの各コンポーネントが１０ビットとして構成されるなら、メモリ２１０は行あたり４０ビットを使用する。メモリ２１０はモジュールの動作をサポートするために十分な速度のランダムアクセスメモリ（ＲＡＭ）であり得る。
【００３５】
メモリ２１０は、ｒ−ポイントＦＦＴを実行するように構成されるＦＦＴエンジン２２０に接続される。ＦＦＴモジュール２００は、図１に示される構造に類似したＦＦＴを実行するように構成することができる。この場合、回転因子による重み付けは、ＦＦＴバタフライ(butterfly)と呼ばれる部分ＦＦＴの後で実行される。そのような構成は、ＦＦＴエンジン２２０が最少数の乗算器を用いて構成されることを可能にし、従ってＦＦＴエンジン２２０のサイズと複雑性を最小限にする。ＦＦＴエンジン２２０は、メモリ２１０から１行を検索し、その行内のサンプルにＦＦＴを実行するように構成することができる。従って、ＦＦＴエンジン２２０は単一サイクルでｒ−ポイントＦＦＴに対してサンプルのすべてを検索することができる。ＦＦＴエンジン２２０は、例えば、パイプライン化されたＦＦＴエンジンであり得、クロックの異なるフェーズで行内の値を操作してもよい。
【００３６】
ＦＦＴエンジン２２０の出力はレジスターバンク２３０につながれる。レジスターバンク２３０はＦＦＴの基数に基づいて多数の値を記憶するように構成される。一実施形態において、レジスターバンク２３０はｒ2の値を記憶するように構成することができる。サンプルの場合と同様に、レジスターバンクに記憶された値は、典型的に実成分と虚成分を有する複素値である。
【００３７】
レジスターバンクは一次記憶装置として使用されるが、高速アクセス用に構成され、アドレスバスを介してアクセスする必要がない記憶のための専用のロケーションを提供する。例えば、レジスターバンク２３０内のレジスターの各ビットはフリップフロップで実施することができる。結果として、レジスターは比較可能なサイズのメモリロケーションに比べて、さらにより多くのダイ領域を使用する。レジスター空間にアクセスするためのサイクルコストが事実上無いので、特定のＦＦＴモジュール２００実施は、レジスターバンク２３０のサイズおよびメモリ２１０を操作することによりダイ領域に対して速度をトレードオフすることができる。
【００３８】
ｒ2値の転置は、例えば行により値を書きこみ、列により値を読み出し、逆もまた同様であることにより直接実行できるように、レジスターバンク２３０はｒ2値を記憶するために有利に分類することができる。値転置は、ＦＦＴのすべてのステージに対してメモリ２１０内のＦＦＴ値の行配列を維持するために使用される。
【００３９】
第２のメモリ２４０は、ＦＦＴエンジン２２０の出力に重み付けをするために使用される回転因子を記憶するように構成される。いくつかの実施形態において、ＦＦＴエンジン２２０は部分ＦＦＴ出力（ＦＦＴバタフライ）の計算中に直接回転因子を用いるように構成することができる。回転因子は任意のＦＦＴに対してあらかじめ決めることができる。それゆえ、第２のメモリ２４０は、リードオンリーメモリ（ＲＯＭ）、不揮発性メモリ、不揮発性ＲＡＭ、またはフラッシュ（登録商標）プログラマブルメモリとして実施することができる。しかしながら、また、第２のメモリは、ＲＡＭまたはその他のタイプのメモリとして構成してもよい。第２のメモリ２４０は、ＮポイントのＦＦＴに対してＮ×（ｎ-１）の複素回転因子を記憶するように分類することができる。但し、Ｎ＝ｒnである。１、−１、ｊ、または−ｊのような回転因子は、第２のメモリ２４０から省略してもよい。さらに、同じ値の複製もまた第２のメモリ２４０から省略してもよい。それゆえ、第２のメモリ２４０内の回転因子の数は、Ｎ×（ｎ−１）未満であってよい。ＦＦＴが周波数におけるデシメーションアルゴリズムまたは時間におけるデシメーションアルゴリズムを実施するかどうかに応じて、効率的な実施は、ＦＦＴのステージのすべてがＦＦＴの第１ステージまたは最終ステージにおいて使用される回転因子のサブセットであるという事実を利用することができる。
【００４０】
複素乗算器２５０ａ−２５０ｂは、レジスターバンクおよび第２のメモリ２４０に接続される。複素乗算器２５０ａ−２５０ｂは、ＦＦＴエンジン２２０の出力に重み付けをするように構成される。ＦＦＴエンジン２２０の出力は、第２のメモリ２４０からの適切な回転因子とともにレジスターバンク２３０に記憶される。図２に示される実施形態は２つの複素乗算器２５０ａおよび２５０ｂを含む。しかしながら、ＦＦＴモジュール２００内に含まれる複素乗算器、例えば２５０ａの数は、ダイ領域に対する速度のトレードオフに基づいて選択することができる。より多くの複素乗算器は、ＦＦＴの実行を促進させるようにダイ上で実施することができる。しかしながら、増加した速度は、ダイ領域を犠牲にして成り立つ。ダイ領域が決定的に重要な意味を持つ場合、複素乗算器の数は減少してもよい。典型的には、設計は、ｒポイントのＦＦＴエンジン２２０が実施されるときｒ−１の複素乗算器より多い乗算器を含まないであろう。なぜならば、ｒ−１の複素乗算器は、重要な回転因子のすべてを、並列にＦＦＴエンジンの出力に印加するのに十分だからである。一例として、図１に示されるような８ポイント基数２のＦＦＴを実行するように構成されたＦＦＴモジュール２００は、２つの複素乗算器を実施することができるが、１つのみの複素乗算器を実施してもよい。
【００４１】
各複素乗算器、例えば２５０ａは、各乗算動作中に、レジスターバンク２３０からの単一の値および第２のメモリ２４０に記憶された対応する回転因子に対して動作する。実行される複素乗算よりも少ない複素乗算があるなら、複素乗算器は、レジスターバンク２３０からの複数のＦＦＴ値に対して演算を実行するであろう。
【００４２】
複素乗算器、例えば２５０ａの出力は、複素乗算器への入力に提供される位置と同じレジスターバンク２３０の位置に書かれる。それゆえ、複素乗算の後で、レジスターバンクの内容は、複素乗算器がＦＦＴエンジン２２０内で実施されたかまたは図２に示すようにレジスターバンクに関連するかどうかに関わらず、同じであるＦＦＴステージ出力を表す。
【００４３】
レジスターバンク２３０に接続される転置モジュール２３２は、レジスターバンク２３０の内容に対して転置を実行する。転置モジュール２３２は、レジスター値を配列し直すことによりレジスターの内容を転置することができる。あるいは、内容がレジスターブロック２３０から読まれるので転置モジュール２３２は、レジスターブロック２３０の内容を転置することができる。レジスターバンク２３０の内容は、ＦＦＴエンジン２２０への入力に供給した行において、メモリ２１０に書き戻される前に転置される。レジスターバンク２３０値を転置することは、ＦＦＴのすべてのステージにわたってＦＦＴ入力のための行構造を維持する。
【００４４】
命令メモリ２６４と結合するプロセッサー２６２はモジュール間のデータフローを実行するように構成することができ、図２のブロックの１つ以上のうちのいくつかまたはすべてを実行するように構成することができる。例えば、命令メモリ２６４は、ＦＦＴモジュール２００内のデータを操作するようにプロセッサー２６２に命令するソフトウェアとして１つ以上のプロセッサー使用可能な命令を記憶することができる。
【００４５】
プロセッサー２６２および命令メモリ２６４は、ＦＦＴモジュール２００の一部として実施することができるか、またはＦＦＴモジュール２００外部にあってもよい。あるいは、プロセッサー２６２はＦＦＴモジュール２００の外部にあってもよく、命令メモリ２６４はＦＦＴモジュール２００内部に存在することができ、例えば、サンプルのために使用されるメモリ２１０、または回転因子が記憶される第２のメモリ２４０と共通にすることができる。
【００４６】
図２に示される実施形態は、アルゴリズムの基数が変化するとき速度と領域の間のトレードオフを特徴とする。
【数６】
2007513431.tif 000011
【００４７】
ポイントＦＦＴを実施する場合、必要とされるサイクル数は以下のように推定することができる。
【数７】
2007513431.tif 000012
【００４８】
但し、
【数８】
2007513431.tif 000013
【００４９】
は、計算される、ｒの基数−ｒのＦＦＴｓの数である。ｒＮFFTは、１回リードし、ＦＦＴを実行し、回転乗算を実行し、ｒエレメントのベクトルに対して書き込みを行うのに費やされるｒＸ時間である。
【００５０】
ＮＦＦＴは基数と無関係に一定であると仮定される。サイクルカウントは、１／ｒ（Ｏ（１／ｒ））のオーダーで減少する。転置に必要とされるレジスターの数がｒ2として増加すると、実施に必要な領域はＯ（ｒ2）だけ増加する。レジスターの数およびレジスターを実施するのに必要な領域は、大きなＮのための領域を決定づける。
【００５１】
所望の速度を提供する最小基数は、関心のある異なるケースに対してＦＦＴを実施するように選択することができる。モジュールの速度が十分であるという条件で、基数を最小限にすることは、モジュールを実施するために使用されるダイ領域を最小限にする。
【００５２】
図３Ａ−３ＤはＦＦＴプロセス３００の実施形態のフローチャートである。プロセス３００は、例えば、図２のＦＦＴモジュール２００により実行することができる。あるいは、プロセス３００は、１つ以上のプロセッサー使用可能な命令群として実施することができ、メモリと結合してプロセッサーにより実行することができる。他の実施形態において、プロセス３００の一部をハードウェアで実行し、他の部分をソフトウェアで実行することができる。
【００５３】
プロセス３００はブロック３０２で始まり、例えばプロセッサーを使用するＦＦＴモジュールは、返還されるデータを、少なくともＦＦＴ基数に等しい多数のサンプルを記憶するのに十分な幅を有するメモリに書く。例えば、図１に示すように、ＦＦＴモジュールが８ポイント、基数２ＦＦＴを実行するように構成されるなら、メモリは２列の４行として構成され、各列は、２つの複素サンプルを記憶するように構成することができる。プロセッサーは、例えば、サンプルを第１列から初めて列方向にメモリに書き込み、第１列が満たされたら第２列に続けることができる。
【００５４】
サンプルデータがメモリに書かれると、ＦＦＴモジュールはブロック３０４に進み、プロセッサーはステージカウンターをイニシャライズする。上述しかつ図１に示すように、Ｎ＝ｒnポイントＦＦＴはｎステージを含む。ＦＦＴの開始において、プロセッサーは、ステージカウンターを１にイニシャライズすることができる。ステージカウンターをイニシャライズした後に、ＦＦＴモジュールはブロック３１０に進み、プロセッサーは部分ＦＦＴとブロックカウンターをイニシャライズする。部分ＦＦＴおよびブロックカウンターは例えば、０にイニシャライズすることができる。
【００５５】
図１の例で示されるように、ＦＦＴの各ステージにおいて実行される部分ＦＦＴｓの数は一定のままであるが、各ＦＦＴ計算に含まれるサンプルのインデックスを追跡するカウンターは、ステージに応じて変化する。
【００５６】
部分ＦＦＴおよびブロックカウンターをイニシャライズした後で、ＦＦＴモジュールはブロック３１２に進み、プロセッサーは行アドレスポインターをイニシャライズする。行アドレスポインターは、ＦＦＴエンジンにより演算されるメモリの行を決定する。例えば、プロセッサーは、次のようなものとして行アドレスポインターの値を決定することができる。
【数９】
2007513431.tif 000014
【００５７】
ＦＦＴモジュールはブロック３１４に進み、行アドレスポインターの値に基づいてサンプルメモリから行を読む。例えば、プロセッサーは、サンプルメモリから行を読み、それをＦＦＴエンジン内のロケーションに書き込むことができる。プロセッサーは、アドレスポインターにより決定される行を読むことができる。
【数１０】
2007513431.tif 000015
【００５８】
但し、ｎはステージの合計数を表し、ｋはステージカウンターを表す。
【００５９】
行がＦＦＴエンジンに読み込まれると、ＦＦＴモジュールはブロック３２０に進み、検索されたサンプルに対してｒポイントＦＦＴｓを計算する。この実施形態において、ＦＦＴエンジンにより実行されるｒ−ポイントＦＦＴｓの数は、メモリからリードした行の数に等しく、基数ｒに等しい。ＦＦＴエンジンの出力はｒ×ｒレジスターバンクに書かれる。
【００６０】
ＦＦＴモジュールはブロック３２２に進み回転因子メモリに記憶された回転因子をＦＦＴ出力値に印加し、回転因子で値を重み付けする。回転因子は１つ以上の乗算器を用いて印加することができ、乗算器は複雑な乗算器として構成することができる。回転因子で重み付けした後に、ステップ３２４において、乗算器は、ｒ×ｒのレジスターバンクに結果を書き戻す。
【００６１】
次に、ＦＦＴモジュールはステップ３３０に進み、レジスターバンク内の値の順番を転置する。一実施形態において、プロセッサーは、レジスターバンクに記憶された値の順番を転置することができる。他の実施形態において、値がレジスターバンクから読まれると、転置を生じることができる。例えば、乗算器の出力は、行の順番でレジスターバンクに書き込むことができ、列の順番でレジスターバンクから読み出すことができる。その結果、相対的に小さな処理で転置を生じることができる。
【００６２】
図３Ａおよび３Ｂに示されるコネクタＡ３３１は、２つの図面ページに示されるフローチャートの一部を接続するために使用され、プロセス３００の実質的な部分を形成しない。ＦＦＴモジュールは、コネクタＡ３３１を介してステップ３３２に進み、レジスターバンクからの転置された結果をサンプルメモリに書き込む。レジスターバンクからの転置された結果はブロック３１４において決定されたアドレスポインターにより同定される行に書きこまれる。列から行への変換を介して転置が実行されるなら、ＦＦＴモジュールは、プロセッサーを用いてレジスターバンクの列を読み出すことができ、行内の結果をアドレスポインターにより同定されるアドレスに書き込むことができる。
【００６３】
ＦＦＴモジュールはブロック３３４に進み、部分ＦＦＴおよびブロックカウンターを更新する。上述したように、ＦＦＴの各ステージ、基数ｒ部分ＦＦＴｓの１つ以上のブロックとして実行される。ステップ３３４において、ＦＦＴモジュールは部分ＦＦＴおよびブロックカウンターを更新する。
【００６４】
プロセッサーは、例えば、部分ＦＦＴカウンターｆk＝（ｆk+１）ｍｏｄ（ｒn-k-1)を更新することができ、部分ＦＦＴカウンターがゼロならばブロックカウンターをインクリメントする。
【００６５】
ＦＦＴモジュールは、判断ブロック３４０に進み部分ＦＦＴｓおよびブロックのすべてが計算されたかどうかを決定する。ブロックカウンターがステージ内のブロックの数未満、すなわちｃk＜ｒn-1なら、部分ＦＦＴｓのすべてが決定されない。すべての部分ＦＦＴｓおよびブロックが計算されなかったなら、ＦＦＴモジュールはブロック３４２に進み、部分ＦＦＴとブロックカウンターを更新し、さらなる部分ＦＦＴｓを処理する。次に、ＦＦＴモジュールはコネクタＣ３４３を介してブロック３１０のループバックし、現在のまたは次のＦＦＴブロックのための部分ＦＦＴｓを処理し続ける。コネクタＣ３４３はプロセス３００の実質的な部分ではないがページ間にまたがってフローチャートを接続するために使用される。
【００６６】
ＦＦＴモジュールが判断ブロック３４０において、現在のステージの全てのブロックが計算されたと決定するなら、ＦＦＴモジュールは判断ブロック３５０に進み、ｎ−１ステージが処理されたかどうか決定する。そうでなければ、ＦＦＴモジュールはブロック３５２に進み、ステージカウンターを更新し、コネクタＢ３５３を介してブロック３１０に戻る。コネクタＢ３５３はプロセス３００の実質的な部分でないが、ページ間にわたってフローチャートを接続するために使用される。
【００６７】
判断ブロック３５０において、ＦＦＴモジュールが、ｎ−１ステージが処理されたと決定するなら、ＦＦＴモジュールはコネクタＤ３５１を介してＦＦＴの最終ステージを処理するために進む。ＦＦＴモジュールは異なる実施形態においてＦＦＴの最終ステージを実施してもよい。図３ＣはＦＦＴモジュールが最終ＦＦＴステージを実施してもよい、一実施形態を図解する。図３Ｄは、ＦＦＴの最終ステージを実施するための代替実施形態を図解する。従って、ＦＦＴモジュールは図３Ｂ上のコネクタＤ３５１から図３Ｃまたは３Ｄ上のコネクタＤ３５１に進むことができるが、両方ではない。図３Ｃおよび３Ｄは、同じ最終ステージの代替実施形態を図解するからである。
【００６８】
一実施形態において、ＦＦＴモジュールは、図３Ｃに示す最終ＦＦＴステージプロセスを実施することができる。図３Ｃに図解された最終ステージプロセスにおいて、ＦＦＴモジュールは、連続して行をフェッチするが、部分ＦＦＴｓに続く任意の転置を実行しない。この結果は、イニシャルＦＦＴステージにおける場合のように分離された各行内にサンプルを有するＦＦＴ結果であるが、基数の逆の順番である行を有する。この順序付けは、ＦＦＴに続いてＩＦＦＴステージがあるなら利点がある。ＦＦＴモジュールは、ＦＦＴ結果をアクセスするとき基数の逆の順番を考慮することができる。順番の結果が所望なら、ＦＦＴモジュールは、行再順番づけエンジンを実施し、行を再順番づけすることができる。
【００６９】
図３Ｃに示される最終ステージプロセスを実行するために、ＦＦＴモジュールは、図３ＢのコネクタＤ３５１から図３ＣのコネクタＤ３５１に進む。ＦＦＴモジュールはブロック３６２に進み、行アドレスポインターをイニシャライズする。行アドレスポインターはＰrow＝ｃn・ｒにイニシャライズすることができる。但し、ｃnは最初にゼロに設定され、ｒはＦＦＴ基数である。次に、ＦＦＴモジュールは、以前のＦＦＴステージが処理されたとほぼ同じように最終ステージを処理するために進む。ブロック３６４において、ＦＦＴモジュールは、ａi＝Ｐrow＋ｉ，ｉ＝０．．．（ｒ−１）として計算することができるアドレス行ポインターにより識別されるメモリから行を読む。
【００７０】
ＦＦＴモジュールはブロック３６６に進み検索された行内の値のために部分ＦＦＴを計算する。ＦＦＴエンジンは、検索された行に対して、ｒの異なるｒ−ポイント部分ＦＦＴを計算する。
【００７１】
ＦＦＴモジュールはブロック３６８に進み、部分出力値をレジスターバンクに書く。ＦＦＴモジュールはブロック３７０に進み、レジスターブロック値を、データをＦＦＴエンジンに供給したサンプルメモリ行に書く。ＦＦＴモジュールはブロック３７０においてカウンターｃｎをインクリメントする。
【００７２】
ＦＦＴモジュールは判断ブロック３７２に進み、最終ブロック内の部分ＦＦＴｓのすべてが処理されたかどうか決定する。そうでなければ、ＦＦＴモジュールはブロック３６２に戻り、サンプルメモリの行を処理し続ける。最終ステージにおける全てのＦＦＴｓが処理されたなら、ＦＦＴモジュールは判断ブロック３７２からオプショナル行再順序付けブロック３７４に進み。ブロック３７４において、ＦＦＴモジュールは行の再順序付けを実行する。次に、ＦＦＴモジュールはブロック３９９に進み、Ｎ−ポイントＦＦＴが終了される。
【００７３】
代替の最終ＦＦＴステージとして、ＦＦＴモジュールは、図３Ｄに示されるプロセスを実行してもよい。図３Ｄのフローチャートに図解される最終ＦＦＴステージにおいて、ＦＦＴモジュールは、ＦＦＴの第１のステージに使用される同じ順番に従って行内のサンプルをフェッチする。この結果は、連続した順番でサンプルを有する行であるが、部分基数逆順における行を有する。さらに、ＦＦＴステージの数が３より大きいときにのみ、部分基数逆順が生じる。部分基数逆行順にもかかわらず、この最終ステージプロセスは、各行内のサンプルは連続的であるので利点があるかもしれない。
【００７４】
図３Ｄの最終ステージプロセスを実行するために、ＦＦＴモジュールは、図３ＢのコネクタＤ３５１から図３ＤのコネクタＤ３５１に進む。ＦＦＴモジュールはブロック３８２に進み、ＦＦＴのイニシャルステージに使用される同じアルゴリズムを用いて行アドレスポインターを設定する。
【００７５】
ＦＦＴモジュールはブロック３８４に進み、ポインターにより識別された行を読み、ブロック３８６に進み、行上の部分ＦＦＴを実行する。次に、ＦＦＴモジュールはブロック３８８に進み、部分ＦＦＴの結果をレジスターバンクに書き込む。次に、ＦＦＴモジュールは、ブロック３９０に進み、レジスターバンク内の値の順番を転置する。
【００７６】
次に、ＦＦＴモジュールは、ブロック３９２に進み、転置された値をサンプルメモリに書き戻す。次に、ＦＦＴモジュールは判断ブロック３９６に進み、最終ステージブロック内のすべての部分ＦＦＴｓが計算されたかどうかを決定する。そうでなければ、ＦＦＴモジュールはブロック３８２に進み、次の部分ＦＦＴのためのポインターを更新する。
【００７７】
判断ブロック３９６において、最終ステージ内の部分ＦＦＴｓの全てが計算されたとＦＦＴモジュールが決定するなら、ＦＦＴモジュールはブロック３９８に進み、行の再順序付けを実行する。図３Ｃに示される以前の最終ステージ実施形態と同様に、行の再順序付けステップはオプションである。行の再順序付けが実行されないなら、またはオプションの行の再順序付けを実行した後で、ＦＦＴモジュールはブロック３９９に進み、ＦＦＴが終了される。
【００７８】
図４は、図３Ａ−３Ｂのプロセスに従って実行される８ポイント基数２ＦＦＴ実施形態のためのメモリ内容およびレジスターブロック内容の機能ブロック図である。８ポイントＦＦＴは、４つの行と２つの列のサンプルメモリを使用する。レジスターブロックは、ｒ×ｒマトリクスとして構成される。この場合は２×２マトリクスである。
【００７９】
サンプルメモリ４１０の最初の内容は、２つの列４１２および４１４に配列されて示される。サンプルメモリは列の順番で書くことができる。満たされるまで値を第１の列４１２に書き込み、次に第２の列４１４に値を書きこむ。サンプルメモリ４１０の各行は、イニシャル２−ポイントＦＦＴｓを実行するために正しいサンプル値を含む。
【００８０】
行ａ０およびａ２は最初にサンプルメモリから検索され、ＦＦＴｓが、行内に記憶された値に対して実行される。この結果は、適切な回転因子で重み付けされ、結果は、レジスターバンク４２２に書き込まれる。次に、レジスターバンク値４２２は、サンプルメモリに書き戻す前に転置される。同様に、行ａ１とａ３はメモリから検索され、ＦＦＴエンジン内で処理され、適切な回転因子で重み付けされ、レジスターバンク４２４に書き込まれる。４２４内のレジスター値は、すでに転置されサンプルメモリに再書き込みされた以前のレジスター値４２２をオーバーライトする。新しいレジスターブロック値４２４は転置されメモリに再書き込みされる。
【００８１】
サンプルメモリ４３０は、第１のステージおよび第１の転置の完了の後に内容を示す。データは依然として２列４３２および４３４に組織されるが、一緒に処理されるサンプルの行の関係を維持するために転置に基づいて値が調節される。
【００８２】
行ａ０およびａ１は最初にサンプルメモリから検索され、ＦＦｔｓが行内に記憶された値に対して実行される。この結果は、適切な回転因子で重み付けされ、その結果は、レジスターバンク４４２に書き込まれる。次に、レジスターバンク値４４２は、サンプルメモリに書き戻される前に転置される。同様に、行ａ２およびａ３はメモリから検索され、ＦＦＴエンジン内で処理され、適切な回転因子で重み付けされ、レジスターバンク４４４内に書き込まれる。値は転置されサンプルメモリに書かれる。
【００８３】
サンプルメモリ４５０は、第２のステージおよび第２の転置の完了の後に内容を示す。第３のサンプルメモリ４５０配列から行ａ０およびａ１は最初にサンプルメモリから検索され、行内に記憶された値に対してＦＦＴｓが実行される。この結果は、適切な回転因子で重み付けされ、その結果は、レジスターバンク４６２に書き込まれる。次に、サンプルメモリに書き戻される前にレジスターバンク値４６２が転置される。同様に、行ａ２およびａ３はメモリから検索され、ＦＦＴエンジン内で処理され、適切な回転因子で重み付けされ、レジスターバンク４６４に書き込まれる。値は転置されサンプルメモリに再書き込みされる。サンプルメモリ４７０に書き込まれた転置された結果は、８−ポイントＦＦＴの出力を表す。
【００８４】
図５Ａおよび５Ｂは、ここに記載するようにＦＦＴモジュールを組み込むことができるＯＦＤＭシステムコンポーネントの機能ブロック図である。ＯＦＤＭ送信機５００およびＯＦＤＭ受信機５４０が議論される。ＯＦＤＭ送信機５００あるいは受信機５４０の各々は、ＯＦＤＭシステムと通信するように構成されたデバイスまたは装置内で実施することができる。そのようなデバイスは、無線電話に限定されないが、携帯電話、パーソナルデジタルアシスタンツ、および同等物またはその他の通信装置のような装置を含む。
【００８５】
図５Ａは、図２のＦＦＴモジュールおよび図３Ａおよび３Ｂのプロセスを実施してもよいＯＦＤＭ送信機５００の機能ブロック図である。図５ＡのＯＦＤＭ送信機のブロックのいくつかまたはすべては単一のＩＣまたはＡＳＩＣで実施してもよい。
【００８６】
ＯＦＤＭ送信機５００は、データサンプルを記憶するように構成されるあるタイプの記憶装置を典型的に含むデータソース５０２を含む。データサンプルはＯＦＤＭ送信機５００の外部で発生されてもよいし、メモリ装置に接続されたアナログ−デジタル変換器（ＡＤＣ）（図示せず）を用いて、ＯＦＤＭ送信機５００内部で発生されてもよい。
【００８７】
単一データストリームは、シリアルデータストリームとして特徴づけることができる。シリアル−並列変換器５１０はデータソース５０２に接続され、ＯＦＤＭ送信機５００内の各直交キャリアに対して並列データストリームを形成する。シリアル対並列変換器５１０の出力は変調器に接続される。並列データストリームの各々は、ＯＦＤＭキャリアの対応するキャリアを変調することができる。
【００８８】
次に、複数の変調されたＯＦＤＭキャリアはＩＦＦＴモジュール５２０に接続される。ＩＦＦＴモジュール５２０は、図２のＦＦＴモジュールから構成してもよく、図３Ａおよび３Ｂのプロセスを使用してもよい。ＩＦＦＴモジュール５２０は、直交周波数を時間領域ＯＦＤＭシンボルに変換する。ＩＦＦＴモジュール５２０の出力は並列−シリアル変換器５２２に接続され、並列出力を単一シリアルシンボルに変換する。並列−シリアル変換器５２２の出力は、送信機５３０に接続することができる。送信機５３０は、無線送信機であってもよい。
【００８９】
図５Ｂは、図５ＡのＯＦＤＭ送信機５００に相補的であるＯＦＤＭ受信機５４０の機能ブロック図である。ＯＦＤＭ送信機５００と同様に、ＯＦＤＭ受信機５４０は、単一のＩＣまたはＡＳＩＣで実施してもよい。ＯＦＤＭ送信機５００、ＯＦＤＭ受信機５４０は単一のＩＣまたはＡＳＩＣで実施してもよい。
【００９０】
ＯＦＤＭ受信機５４０は、送信機によってブロードキャストされたＯＦＤＭシンボルを受信する無線受信器として構成することができる受信機５４２を含む。受信機５４２は、受信した信号を増幅し、フィルターし、ダウンコンバートし、ベースバンド信号をリカバーするように構成されていてもよい。
【００９１】
ベースバンド信号は、処理のためにシリアルベースバンドデータストリームを並列データストリームに変換するように動作するシリアル−並列変換器５４４に接続される。シリアル−並列変換器５４４の出力は、ＦＦＴモジュール５５０に接続される。ＦＦＴモジュール５５０は、図３Ａおよび３Ｂのプロセスを実行する図２のＦＦＴモジュールであってよい。
【００９２】
ＦＦＴモジュール５５０は、時間領域シンボルを複数の直行周波数コンポーネントに変換する。ＦＦＴモジュール５５０の出力は、データをリカバーするために直交周波数を復調するように動作する復調器５６０に接続される。
【００９３】
並列−シリアル変換器５６２はＦＦＴモジュール５５０の出力に接続され、並列データをシリアルデータストリームに変換する。シリアルデータストリームはさらなる処理のためにデータプロセッサーに接続される。例えば、音声データは、増幅とスピーカーへの配信のためにアナログフォーマットに変換することができる。ビデオデータはさらに処理され表示装置に方向づけられてもよい。
【００９４】
ＦＦＴアーキテクチャーを実施するＦＦＴモジュールは、従来のＦＦＴ実施に比べて低減された数の命令で適所変換を実行することができる。ＦＦＴモジュールは、単一行に複数の値を配列するサンプルメモリを含む。ＦＦＴ演算は単一行のサンプルに対して実行され、レジスターブロックに書かれる。１つ以上の複雑な乗算器を用いて回転因子を部分ＦＦＴ結果に適用することができる。
【００９５】
レジスターバンク内の重み付けされた部分ＦＦＴは転置され、サンプルメモリに再書き込みされる。転置はサンプルメモリの同じ行内の単一部分ＦＦＴのためのＦＦＴ入力の関係を維持する。所望のＦＦＴが完了するまで、このプロセスは、ＦＦＴの複数のステージのために反復される。
【００９６】
ここに開示された実施形態に関連して説明された方法またはアルゴリズムのステップは、ハードウェア内、プロセッサーによって実行されるソフトウェアモジュール内、あるいは２つの組み合わせにおいて直接的に具現化されてよい。ソフトウェアモジュールはＲＡＭメモリ、フラッシュ（登録商標）メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスター、ハードディスク、取り外し可能ディスク、ＣＤ−ＲＯＭ、または技術的に既知である任意の他の形式の記憶媒体に常駐してよい。例示的な記憶媒体は、プロセッサーが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるようにプロセッサーに結合される。代替策では、記憶媒体はプロセッサーに一体化してよい。さらに、実施形態に示される順番で種々の方法を実行してもよく、またはステップの変更された順番を用いて実行してもよい。さらに、１つ以上のプロセスまたは方法が省略されてもよく、または１つ以上のプロセスまたは方法を、この方法およびプロセスに追加してもよい。さらなるステップ、ブロックまたはアクションは、この方法とプロセスの始めの、終わりの、または介在する既存のエレメントに追加してもよい。
【００９７】
開示された実施形態の上述の記載は、当業者がこの開示を製作または使用することを可能にするために提供される。これらの実施形態に対する種々の変更は、当業者に容易に明白であり、ここに定義される包括的原理は、この開示の精神および範囲から逸脱することなく他の実施形態に適用してもよい。従って、この開示は、ここに示される実施形態に制限されることを意図したものではなく、ここに開示される原理および新規な特徴に一致する最も広い範囲が許容されるべきである。
【図面の簡単な説明】
【００９８】
【図１】図１は８ポイント基数２ＦＦＴのフローグラフである。
【図２】図２は、ＦＦＴモジュールの一実施形態の機能ブロック図である。
【図３Ａ】図３ＡはＦＦＴプロセスの実施形態のフローチャートである。
【図３Ｂ】図３ＢはＦＦＴプロセスの実施形態のフローチャートである。
【図３Ｃ】図３ＣはＦＦＴプロセスの実施形態のフローチャートである。
【図３Ｄ】図３ＤはＦＦＴプロセスの実施形態のフローチャートである。
【図４】図４は８ポイント基数２ＦＦＴの一実施形態のステージのためのメモリ内容の機能ブロック図である。
【図５Ａ】図５Ａはここに開示されるＦＦＴモジュールを用いたＯＦＤＭシステムコンポーネントの実施形態の機能ブロック図である。
【図５Ｂ】図５Ｂはここに開示されるＦＦＴモジュールを用いたＯＦＤＭシステムコンポーネントの実施形態の機能ブロック図である。
【図１】
2007513431.tif 000016
【図２】
2007513431.tif 000017
【図３Ａ】
2007513431.tif 000018
【図３Ｂ】
2007513431.tif 000019
【図３Ｃ】
2007513431.tif 000020
【図３Ｄ】
2007513431.tif 000021
【図４】
2007513431.tif 000022
【図５Ａ】
2007513431.tif 000023
【図５Ｂ】
2007513431.tif 000024
【手続補正書】
【提出日】平成18年7月27日(2006.7.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
ｒn−ポイント、基数ｒ、高速フーリエ変換（ＦＦＴ）を決定するための方法において、
行あたりｒのサンプルを有するメモリに、変換されるサンプルを書き込むことと、
前記メモリからｒ行を読むことと、
ｒ基数ｒ部分ＦＦＴｓを決定し、ｒ2部分ＦＦＴ値を発生することと、
回転因子をｒ2部分ＦＦＴ値に印加してｒ2の重み付けされた部分ＦＦＴ値を発生することと、
前記ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書くことと、
前記レジスターブロック内の前記ｒ2の重み付けされた部分ＦＦＴを転置し、転置された値を発生することと、
前記転置された値を前記メモリに書くことと、
前記メモリの内容からＦＦＴ値を決定することとを備えた方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
前記少なくとも１つの乗算器は少なくとも１つの複素乗算器を備えた、請求項１２の装置。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
前記少なくとも１つの乗算器は、ｒ−１複素乗算器を備えた、請求項１２の装置。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２７
【補正方法】変更
【補正の内容】
【請求項２７】
回転因子を前記ｒ2部分ＦＦＴ値に印加する手段は、
少なくとも１つの複素回転因子を受信する手段と、
前記少なくとも１つの複素回転因子と、前記ｒ2部分ＦＦＴ値の対応する値との複素乗算を計算する手段とを備えた、請求項２２の装置。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
さらに、他の観点において、ｒn−ポイントの、基数ｒのＦＦＴを決定する方法が開示される。この方法は、行あたりｒのサンプルを有するメモリに変換されるサンプルを書き込むことと、ａ）ステージカウンターをイニシャライズすることと、ｂ）ブロックカウンターおよび部分ＦＦＴ出力カウンターをイニシャライズすることと、ｃ）ステージ値、ブロック値および部分ＦＦＴカウンター値に基づいてメモリからｒの行を検索することと、ｄ）ｒの基数のｒの部分ＦＦＴｓを決定してｒ2の部分ＦＦＴ値を発生することと、ｅ）回転因子をｒ2部分ＦＦＴ値に印加してｒ2の重み付けされた部分ＦＦＴ値を発生することと、ｆ）ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロックに書くことと、ｇ）ｒ2の重み付けされた部分ＦＦＴ値をレジスターブロック内で置き換えて転置された値を発生することと、ｉ）転置された値をメモリに書くことと、ｊ）部分ＦＦＴカウンターおよびブロックカウンターを更新することと、ｋ）ブロックカウンターと部分ＦＦＴカウンターの値に基づいて、ステップｃ）乃至ｊ）を反復することと、ｌ）ステージカウンターの値を更新することと、ｍ）ステージカウンターの値に基づいてステップｂ）乃至ステップｋ）を反復し、メモリの内容からＦＦＴ値を決定することとを含む。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
この装置は、メモリ行あたりｒのサンプルを有するサンプルを記憶するように構成されたメモリと、メモリのｒの行からのサンプルにｒのｒ−ポイント部分ＦＦＴを実行するように構成されたＦＦＴエンジンと、ｒ行ｒ列として構成されたｒ2のレジスターを有し、ＦＦＴエンジンから出力値を受信するように構成されたレジスターバンクと、レジスターバンク内の値を置換し転置された値を、ＦＦＴエンジンにより動作されるメモリからのｒ行に書き込むように構成された転置モジュールとを含む。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
ＦＦＴブロックはｒ-ポイントＦＦＴｓの結果を、ｒ2サンプルを記憶するように構成されるレジスターバンクに書く。レジスターバンクおよび回転因子メモリに接続された複素乗算器は、適切な回転因子でＦＦＴ結果を重み付けする。重み付けされた因子は同じレジスターに戻される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
ハードウェア内におけるＦＦＴ実施の解析は、使用されるサイクルの観点から主要なコストはメモリアクセスで消費されることを示す。メモリアクセスの数は増加する基数とともに減少する。しかしながら、１つの複素サンプル／サイクルをアクセスすることは多くのアプリケーションに対して重要ではないかもしれない。簡単な例は潜在的な問題を例証する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
任意の基数アルゴリズムのための高速実施は、並列リードおよびライトを可能にするメモリ構造の使用により達成することができる。特別の基数−ｒアルゴリズムの場合、リード動作のためであろうとまたはライト動作のためであろうと、１サイクル内のｒ−値のアクセスを可能にさせるメモリ構造は、アルゴリズムのスループットを改良する。概念的には、並列アクセスは、各行にワードを有するＲＡＭとみなすことができる。しかしながら、このメモリ構造から最大利益を得るために、ｒ−ポイントＦＦＴを計算するのに必要なｒ−サンプルは、アルゴリズムのあらゆる段階で同じ行にある必要がある。これは、サンプルメモリのｒ行をリードし、ｒ、ｒ−ポイントＦＦＴｓを計算し、サンプルメモリへの転置の後で結果を書き込むことにより達成することができる。転置動作は、ｒ2レジスターのマトリクスメモリ内で実行することができる。基数ｒが増加するにつれ、ＦＦＴエンジンのサイズおよびマトリクスメモリのサイズが増加する。速度に対する領域のトレードオフは、任意の特定の実施に対して実行することができる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
ＦＦＴモジュールはブロック３２２に進み回転因子メモリに記憶された回転因子をＦＦＴ出力値に印加し、回転因子で値を重み付けする。回転因子は１つ以上の乗算器を用いて印加することができ、乗算器は複素乗算器として構成することができる。回転因子で重み付けした後に、ステップ３２４において、乗算器は、ｒ×ｒのレジスターバンクに結果を書き戻す。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
ＦＦＴモジュールは判断ブロック３７２に進み、最終ブロック内の部分ＦＦＴｓのすべてが処理されたかどうか決定する。そうでなければ、ＦＦＴモジュールはブロック３６２に戻り、サンプルメモリの行を処理し続ける。最終ステージにおける全てのＦＦＴｓが処理されたなら、ＦＦＴモジュールは判断ブロック３７２からオプショナル行再順序付けブロック３７４に進む。ブロック３７４において、ＦＦＴモジュールは行の再順序付けを実行する。次に、ＦＦＴモジュールはブロック３９９に進み、Ｎ−ポイントＦＦＴが終了される。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
行ａ０およびａ１は最初にサンプルメモリから検索され、ＦＦＴｓが行内に記憶された値に対して実行される。この結果は、適切な回転因子で重み付けされ、その結果は、レジスターバンク４４２に書き込まれる。次に、レジスターバンク値４４２は、サンプルメモリに書き戻される前に転置される。同様に、行ａ２およびａ３はメモリから検索され、ＦＦＴエンジン内で処理され、適切な回転因子で重み付けされ、レジスターバンク４４４内に書き込まれる。値は転置されサンプルメモリに書かれる。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
ＦＦＴアーキテクチャーを実施するＦＦＴモジュールは、従来のＦＦＴ実施に比べて低減された数の命令で適所変換を実行することができる。ＦＦＴモジュールは、単一行に複数の値を配列するサンプルメモリを含む。ＦＦＴ演算は単一行のサンプルに対して実行され、レジスターブロックに書かれる。１つ以上の複素乗算器を用いて回転因子を部分ＦＦＴ結果に適用することができる。
【国際調査報告】
2007513431.tif 000025
2007513431.tif 000026
2007513431.tif 000027