(57)【要約】radix-4バタフライ回路（１２）と、規定された数のデータ値を記憶するための分割メモリ（１６ａ，１６ｂ）を用いたＦＦＴ回路（１０）を実現する。radix-4バタフライ回路は、規定された数のステージ（３０ａ，３０ｂ，３０ｃ）においてＦＦＴオペレーションを実行するように構成され、各ステージは、規定された数のデータ値に対して、規定された数のその場での（in-place）計算オペレーション（３２）を含む。分割メモリは、第１メモリ部分と、第２メモリ部分とを含み、ＦＦＴ回路のためのデータ値（３４，３６）は、各Ｉ位置の計算オペレーションが第１および第２メモリ部分のそれぞれから取り出した等しい数のデータ値の取り出しに基づいて行われることを保証するような方法で、等しく分割されて第１、第２メモリ部分に記憶される。
2007527072.tif 000002
【特許請求の範囲】
【請求項１】
少なくともRadix-4バタフライ回路を持つ高速フーリエ変換（ＦＦＴ）回路（１０）において実行される方法において、
規定された数のデータ値の第１および第２の同等部分を、第１（１６ａ）および第２（１６ｂ）メモリ部分に、前記第１および第２メモリ部分が各インプレース計算オペレーションについてアクセスされることを保証する、規定されたマッピングに従って、それぞれ記憶するステップと、
規定数のデータ値に比例した規定数のインプレース計算オペレーション（３２）をそれぞれ持つ、規定数のＦＦＴステージ（３０ａ，３０ｂ，３０ｃ）を実行するステップとを含み、前記実行するステップは各インプレース計算オペレーションを、
（１）前記第１メモリ部分および前記第２メモリ部分から、等しい数の記憶データ値（３４，３６）に同時にアクセスするステップ、
（２）それぞれの計算結果の計算のために、前記アクセスされたデータ値を少なくともRadix-4バタフライ回路（１２）に供給するステップ、
によって行うステップを含む、方法。
【請求項２】
前記各インプレース計算を行うステップは、前記各アクセスされたデータ値を記憶したメモリ位置において、前記計算結果を前記第１メモリ部分および前記第２メモリ部分に記憶するステップを含む、請求項１記載の方法。
【請求項３】
前記第１および第２メモリ部分のそれぞれはデュアルポートメモリ装置であり、前記実行するステップは、前記各インプレース計算オペレーションについての前記計算結果を記憶する間に、前記インプレース計算オペレーションのその次のために前記記憶されたデータ値に同時にアクセスするステップを含む、請求項２記載の方法。
【請求項４】
前記実行するステップが、
前記ＦＦＴステージの第１のものについての前記インプレース計算オペレーションを、前記ＦＦＴステージの第２のものについての前記インプレース計算オペレーションの一つの入力シーケンスに基づいて、規定された順番で行うステップと、
前記入力シーケンスに関連する前記インプレース計算オペレーションの前記規定された順番を完了した後で、前記ＦＦＴステージの前記第２のものについての前記一つのインプレース計算オペレーションを開始するステップとを含む、請求項３記載の方法。
【請求項５】
前記同時にアクセスするステップは、各クロックサイクルにおいて、前記第１メモリ部分のリードポートからの対応する記憶データ値と、前記第２メモリ部分のリードポートからの対応する記憶データ値とにアクセスし、
前記記憶するステップは、前記各クロックサイクル中に、前記第１メモリ部分の書き込みポートを介して対応する計算結果を書き込み、前記第２メモリ部分の書き込みポートを介して対応する計算結果を書き込むステップを含む、請求項２記載の方法。
【請求項６】
高速フーリエ変換（ＦＦＴ）回路（１０）において、
アクセスされたデータ値の受信に応答して、計算結果を生成するように構成された、少なくとも一つのRadix-4バタフライ回路（１２）と、
インプレース計算オペレーションのために、規定数のデータ値の第１および第２の同等部分（３４，３６）を記憶するように構成された第１（１６ａ）および第２（１６ｂ）メモリ部分と、
前記第１および第２メモリ部分が各インプレース計算オペレーションについてアクセスされることを保証する規定されたマッピングに従って、前記第１および第２メモリ部分に、規定された数のデータ値の第１および第２の同等部分を記憶するように構成されたメモリコントローラ（１４）とを備え、
前記メモリコントローラは、前記規定数のデータ値に比例した規定数の前記インプレース計算オペレーションをそれぞれ持つ、規定数のＦＦＴステージを、下記のステップに基づいて実行するように構成される、ＦＦＴ回路。
（１）前記第１メモリ部分および前記第２メモリ部分から、等しい数の記憶データ値に同時にアクセスするステップ、
（２）それぞれの計算結果の計算のために、前記アクセスされたデータ値を少なくとも前記Radix-4バタフライ回路に供給するステップ。
【請求項７】
前記メモリコントローラは、前記各アクセスされたデータ値を記憶したメモリ位置において、各インプレース計算オペレーションについての前記計算結果を前記第１メモリ部分および前記第２メモリ部分に記憶するように構成される、請求項６記載のＦＦＴ回路。
【請求項８】
前記第１および第２メモリ部分のそれぞれはデュアルポートメモリ装置であり、
前記メモリコントローラは、前記各インプレース計算オペレーションについての前記計算結果を記憶する間に、前記インプレース計算オペレーションのその次のために前記記憶されたデータ値に並行してアクセスするように構成され、さらに前記ＦＦＴステージの第１のものについての前記インプレース計算オペレーションを、前記ＦＦＴステージの第２のものについての前記インプレース計算オペレーションの一つの入力シーケンスに基づいて、規定された順番で行わせるように構成される、請求項７記載のＦＦＴ回路。
【請求項９】
前記メモリコントローラは、前記入力シーケンスに関連する前記インプレース計算オペレーションの前記規定された順番を完了した後で、前記ＦＦＴステージの前記第２のものについての前記一つのインプレース計算オペレーションを開始するように構成されている、請求項１０記載のＦＦＴ回路。
【請求項１０】
前記メモリコントローラは、
各クロックサイクルにおいて、前記第１メモリ部分のリードポートからの対応する記憶データ値と、前記第２メモリ部分のリードポートからの対応する記憶データ値とにアクセスし、
前記少なくとも一つのRadix-4バタフライ回路による計算結果の生成の後に、前記各クロックサイクル中に、前記第１メモリ部分の書き込みポートを介して対応する計算結果を書き込み、前記第２メモリ部分の書き込みポートを介して対応する計算結果を書き込む、ように構成される請求項７記載のＦＦＴ回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＥＥＥ８０２．１１ａベースの直交周波数分割多重化（ＯＦＤＭ）受信器などの、リアルタイムシステムにおける高速フーリエ変換（ＦＦＴ）回路の実装に関連する。
【背景技術】
【０００２】
高速フーリエ変換（ＦＦＴ）および逆高速フーリエ変換（ＩＦＦＴ）は、ｘＤＳＬモデムや、高精細テレビ（ＨＤＴＶ）、無線ローカル・エリア・ネットワーク用途などのＯＦＤＭシステムにおける、その能率性のためにモダンな通信システムにおいてよく用いられている。無線ローカル・エリア・ネットワーク用途の例には、無線ＬＡＮ（つまり、固定アクセスポイントを持つ無線インフラストラクチャ）、モバイルアドホックネットワーク等が含まれる。特に、ＩＥＥＥ標準規格８０２．１１ａ、規格名”Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: High-speed Physical Layer in the 5GHz Band”は、データペイロード通信容量が最大５４Ｍｂｐｓの無線ＬＡＮのためのＯＦＤＭ  ＰＨＹを規定する。ＩＥＥＥ標準規格８０２．１１ａは、バイナリまたは直交位相シフトキーイング（ＢＰＳＫ／ＱＰＳＫ）、１６直交振幅変調（ＱＡＭ）または６４ＱＡＭを用いて変調される、５２のサブキャリア周波数を用いるＰＨＹシステムを規定する。
【０００３】
ＦＦＴの基本的な計算素子は「バタフライ回路」であって、その最も単純な形態（radix-2）では、２つの複素値を他の２つの複素値に変換する。バタフライ回路は、変換の異なるステージにおいて複数の計算を実行するのに用いられ、時間領域から周波数領域への統合またはその反対を実現する。
【０００４】
バタフライ回路によって実行される相当数の計算オペレーションは、無線ＬＡＮなどのリアルタイムシステムにおける実用性を確保するために、高効率の設計を要求する。例えば、４つの入力と４つの出力を持つRadix-4バタフライ回路はＦＦＴ処理の際に必要になる乗法演算の数を減らすために用いられる。高次のradixバタフライ回路は、メモリアクセス率、算術作業量、そして結果として電力消費を減少させる。効率的なメモリ割り当ても重要な考慮点であり、バタフライ回路に供給された入力値（例：時間領域）を、バタフライ回路で生成された対応する出力値（例：周波数領域）で上書きする、インプレース（in-place、その場での）計算を用いることによってメモリの必要性を減少させている。
【０００５】
しかしながら、バタフライ回路の使用は、入力値の取り出しおよび出力値の記憶のために、相当回数メモリの読み出しおよび書き込みの操作を繰り返す必要がある。したがって、ＦＦＴアーキテクチャを実装するための専用技術によって、メモリの非効率的な使用を産み、回路コストを増加させる相当のメモリコントローラ資源を必要とし、および／またはＦＦＴ回路の性能を低下させる。
【０００６】
したがって、レイテンシを最小化し、メモリ使用を最適化し、電力効率を最適化するような方法でＦＦＴ回路を実装することを可能にする構成が求められている。
また、最低限のアイドルタイムでＦＦＴ回路中のバタフライ回路の最適化された利用を可能にするための構成が求められている。
さらに、最低限の等化（equalization）エラーで受信した周波数変調信号の等化を無線トランシーバが実行可能にする構成が求められている。
【発明の開示】
【０００７】
これらの、およびその他の要求は本発明によって達成される。本発明において、radix-4バタフライ回路および規定数のデータ値を記憶するための分割されたメモリを用いて、ＦＦＴ回路が実装される。Radix-4バタフライ回路は規定のステージ数においてＦＦＴ演算を実行するように構成されている。各ステージは、規定数のデータ値に対応した規定数のインプレース計算オペレーションを含む。分割されたメモリは、第１メモリ部分と、第２メモリ部分とを含み、各インプレース計算オペレーションが、第１および第２メモリ部分のそれぞれから取り出された等しい数のデータ値の取り出しに基づいて行われることを保証するような方法で、ＦＦＴ回路のためのデータ値は第１および第２メモリ部分に記憶するために等しく分割される。
【０００８】
本発明の一態様は、少なくともRadix-4（またはより高次の）バタフライ回路を持つ高速フーリエ変換（ＦＦＴ）回路における方法である。
本方法は、規定された数のデータ値の第１および第２の同等部分を、第１および第２メモリ部分に、前記第１および第２メモリ部分が各インプレース計算オペレーションについてアクセスされることを保証する、規定されたマッピングに従って、それぞれ記憶するステップを含む。本方法はさらに、規定数のデータ値に対応した規定数のインプレース計算オペレーションをそれぞれ持つ、規定数のＦＦＴステージを実行するステップを含む。この実行するステップは各インプレース計算オペレーションを、
（１）第１メモリ部分および第２メモリ部分から、等しい数の記憶データ値に同時に（並行して）アクセスするステップと、
（２）それぞれの計算結果の計算のために、アクセスされたデータ値を少なくともRadix-4バタフライ回路に供給するステップと、
によって行うステップを含む。
【０００９】
本発明の他の態様は、高速フーリエ変換（ＦＦＴ）回路（１０）である。
ＦＦＴ回路は、アクセスされたデータ値の受信に応答して、計算結果を生成するように構成された、少なくとも一つのRadix-4（またはより高次のradix）バタフライ回路と、第１および第２メモリ部分と、メモリコントローラとを含む。第１および第２メモリ部分は、インプレース計算オペレーションのために、規定数のデータ値の第１および第２の同等部分を記憶するように構成されている。メモリコントローラは、第１および第２メモリ部分が各インプレース計算オペレーションについてアクセスされることを保証する規定されたマッピングに従って、第１および第２メモリ部分に、規定された数のデータ値の第１および第２の同等部分を記憶するように構成されている。メモリコントローラはさらに、規定数のデータ値に対応した規定数の前記インプレース計算オペレーションをそれぞれ持つ、規定数のＦＦＴステージを、下記のステップに基づいて実行するように構成される。
（１）第１メモリ部分および前記第２メモリ部分から、等しい数の記憶データ値に同時に（並行して）アクセスするステップ、
（２）それぞれの計算結果の計算のために、アクセスされたデータ値を少なくともRadix-4バタフライ回路に供給するステップ。
【００１０】
本発明のその他の優位点および新規な特徴は、その一部が以下の説明において説明され、別の一部は以下の説明を参照した当業者に明らかになり、または本発明を実施することによって学ぶことができる。本発明の優位点は、添付の特許請求の範囲に特に指摘した手段およびその組み合わせによって、実現され、達成されうる。
【発明を実施するための最良の形態】
【００１１】
ＦＦＴのためのメモリ分割方法
図１は、本発明の一実施形態である、規定数のデータ値に高速フーリエ変換（ＦＦＴ）または逆ＦＦＴ（ｉＦＦＴ）を実行する高速フーリエ変換（ＦＦＴ）回路（１０）を示す。ＦＦＴ回路１０は、Radix-4バタフライ回路１２と、メモリコントローラ１４と、メモリの部分（例えば、メモリバンク）１６ａ，１６ｂとを備える。
【００１２】
Radix-4バタフライ回路１２は、ＦＦＴ計算を実行する既知のRadix-4バタフライオペレーションに従って、並行して４つの入力（Ａ１，Ａ２，Ｂ１，Ｂ２）を受信し、４つの計算結果（Ａ‘１，Ａ’２，Ｂ‘１，Ｂ’２）を生成して、同時に（並行）出力する。
【００１３】
メモリの部分１６ａ，１６ｂは、インプレース計算オペレーションのために、規定数のデータ値の同等部分を記憶するように構成される。特に、６４ポイントＦＦＴを生成すると仮定すると、メモリの部分１６ａ，１６ｂのそれぞれは入力ポイントの半分を記憶するように構成され、この例ではメモリの部分はそれぞれ３２ポイントを記憶する。
【００１４】
以下で説明するように、メモリコントローラ１４は、メモリバンク１６ａ，１６ｂのそれぞれがそれぞれのインプレース計算オペレーションのためにアクセスされることを保証する規定のマッピングに応じて、メモリバンク１６ａ，１６ｂに６４ポイントデータ値を最初に記憶するように構成される。
【００１５】
図１に示すように、メモリコントローラ１４は、入力供給パス２０からの規定数のデータ値として、６４個のデータ値を受信し、規定マッピングに従ってその６４データポイントを最初に記憶する。図１に示すように、メモリコントローラ１４によるメモリバンク１６ａ，１６ｂに対するデータポイントの規定マッピングは次のとおりである。
メモリバンク１（１６ｂ）が記憶するポイント：０，２，５，７，８，１０，１３，１５，１７，１９，２０，２２，２５，２７，２８，３０，３２，３４，３７，３９，４０，４２，４５，４７，４９，５１，５２，５４，５７，５９，６０，６２
メモリバンク２（１６ａ）が記憶するポイント：１，３，４，６，９，１１，１２，１４，１６，１８，２１，２３，２４，２６，２９，３１，３３，３５，３６，３８，４１，４３，４４，４６，４８，５０，５３，５５，５６，５８，６１，６３
【００１６】
メモリコントローラ１４は、インプレース計算を用いて、このデータポイントの規定マッピングを維持する。従って、メモリバンク１６ａ，１６ｂの両方が各読み出し（リード）操作について並行してアクセスされ、メモリバンク１６ａ，１６ｂの両方が各書き込み（ライト）操作について並行して（同時に）アクセスされることを保証することによって、メモリアクセスは最適化される。さらに、メモリの部分１６ａ，１６ｂはデュアルポートメモリ装置として構成されるので、メモリバンク１６ａ，１６ｂについて同時に読み出しおよび書き込み操作を実行できる（つまり、並列に実行される）。従って、すべてのデータパス１８ａ，１８ｂ，１８ｃ，１８ｄは所与のクロックサイクルにおいて同時に利用可能であり、それによってメモリの利用を最適化し、レイテンシを最小化する。
【００１７】
メモリコントローラ１４は、バタフライ回路１２に４つの入力（Ａ１，Ａ２，Ｂ１，Ｂ２）を供給し、バタフライ回路１２からメモリの部分１６ａ，１６ｂに４つの出力（Ａ‘１，Ａ’２，Ｂ‘１，Ｂ’２）を転送することで、インプレース計算を実装する。特に、メモリコントローラ１４は、各クロックサイクルにおいて、メモリの部分（バンク２）１６ａからデータ値（Ａ）を、第２メモリ部分（バンク１）１６ｂからデータ値（Ｂ）を同時に、それぞれデータパス１８ａ，１８ｂを介して、取り出すように構成されている。また、メモリコントローラ１４は、各クロックサイクルにおいて、計算結果（Ａ‘）を第１メモリ部分１６ａに、同時に計算結果（Ｂ‘）を第２メモリ部分１６ｂに、それぞれデータパス１８ｃ、１８ｄを介して記憶するように構成される。
【００１８】
例えば、メモリコントローラ１４は、クロックサイクルＣ１において、対応するメモリの部分１６ａ，１６ｂから記憶されたデータ値Ａ１，Ｂ１を同時に取り出し、クロックサイクルＣ２において、対応するメモリの部分１６ａ，１６ｂから記憶されたデータ値Ａ２，Ｂ２を取り出すように構成され、メモリコントローラ１４は、第１クロックサイクルＣ１において取り出された、アクセスされたデータ値Ａ１，Ｂ１を一時記憶（バッファ）し、クロックサイクルＣ２において、４つの入力Ａ１，Ａ２，Ｂ１，Ｂ２をバタフライ回路１２に並行して供給することを可能にする。計算結果Ａ‘１，Ａ’２，Ｂ‘１，Ｂ’２はバタフライ回路１２から並行して出力される。
【００１９】
以下で説明するように、メモリコントローラ１４は、計算結果Ａ‘１，Ａ’２，Ｂ‘１，Ｂ’２を、元の入力Ａ１，Ａ２，Ｂ１，Ｂ２に対応するアドレス位置に出力することにより、インプレース計算を完了する。
【００２０】
図２は、本発明の一実施形態である、各インプレース計算オペレーションについて、第１および第２メモリ部分１６ａ，１６ｂのそれぞれからの等しい数の記憶データ値を用いた、ＦＦＴ回路１０によって実行される３ステージＦＦＴ計算を示す。図２に示すように、ＦＦＴ回路１０によるＦＦＴ計算は３ステージ３０ａ，３０ｂ，３０ｃ実行される。各ステージは１６個のオペレーション３２を含む。例えば、Radix-4バタフライ回路１２は、メモリコントローラ１４が４つのデータポイント“０”，“１６”，“３２”，“４８”を取り出して、バタフライ回路１２へ入力Ｂ１，Ａ１，Ｂ２，Ａ２として供給するのに基づいて、ステージ１、オペレーション０（Ｓ１＿Ｏｐ０）を実行する。インプレース計算は、計算結果Ｂ‘１，Ａ‘１，Ｂ’２，Ａ’２を元のデータポイント“０”，“１６”，“３２”，“４８”に利用していた、それぞれに対応する同じメモリ位置に記憶する、メモリコントローラ１４によって実現される。
【００２１】
図２に示すように、丸で囲まれた３４を持つ各データポイントは第１メモリバンク（バンク２）１６ａに記憶され、丸で囲まれない各データポイント３６は第２メモリバンク（バンク１）１６ｂに記憶される。従って、各ステージ３０ａ，３０ｂ，３０ｃについての計算オペレーションのそれぞれは、第１メモリ部分（バンク２）１６ａおよび第２メモリ部分（バンク１）から取り出された同じ数のデータポイントを含む。さらに、メモリバンク１６ａ，１６ｂに対するデータポイントの規定マッピングにより、第１および第２メモリバンク１６ａ，１６ｂが各インプレース計算オペレーションについてアクセスされることが保証される。
【００２２】
図３Ａおよび図３Ｂは図２の３ステージＦＦＴ計算を実行するための別の方法を示す。図３Ａは各ステージにおけるオペレーションの連続実行を示し、メモリコントローラ１４は、ステージシーケンス毎にデータ値を供給する。特に、メモリコントローラ１４は、ステップ４０において、ステップ４２の第２ステージのオペレーション３０ｂを開始する前に、ステージ１のオペレーション３０ａ（Ｓ１＿Ｏｐ０からＳ１＿Ｏｐ１５まで）を実行させる。従って、ステージ２のオペレーション３０ｂ（Ｓ２＿Ｏｐ０からＳ２＿Ｏｐ１５まで）は、規定順序のインプレースステージ１計算オペレーション３０ａが完了してから、ステップ４２で開始される。ステップ４２でステージ２オペレーション３０ｂが終わった後、メモリコントローラ１４はステップ４４でステージ３オペレーション３０ｃを開始する。
【００２３】
図４Ａは、図３Ａの方法に従った３ステージＦＦＴの実行を示すタイミング図である。図４Ａに示すように、メモリコントローラ１４は、イベント６０（クロックサイクル１）において、ステージ１オペレーション０の実行のために、メモリバンク１（１６ｂ）およびバンク２（１６ａ）に対して、それぞれデータポイント“０”および“１６”のための記憶されたデータ値を同時にアクセスする。カッコ内のすべてのオペレーションは（例えば、クロックサイクル１および２における“（０）”）、バタフライ回路１２によって実行されるべき次のオペレーションを示す。イベント６２（クロックサイクル２）において、メモリコントローラ１４は、メモリバンク１（１６ｂ）およびバンク２（１６ａ）に対して、それぞれデータポイント“３２”および“４８”のための記憶されたデータ値を同時にアクセスし、取り出された値を入力Ａ１，Ａ２，Ｂ１，Ｂ２として供給する。バタフライ回路１２は、イベント６４（クロックサイクル３）でステージ１、オペレーション０（Ｓ１＿Ｏｐ０）を実行し、結果物Ａ‘１，Ａ’２，Ｂ‘１，Ｂ’２を出力する。
【００２４】
イベント６４（クロックサイクル３）の間、メモリコントローラ１４は並行して、結果物Ｂ‘１をバンク１（１６ｂ）のデータポイント“０”のための位置に記憶し、結果物Ａ‘１をバンク２（１６ａ）のデータポイント“１６”のための位置に記憶し、ステージ１、オペレーション１（Ｓ１＿Ｏｐ１）の実行のためにバンク１（１６ｂ）からデータ値“１７”を取り出し、ステージ１、オペレーション１（Ｓ１＿Ｏｐ１）の実行のためにバンク２（１６ａ）からデータ値“１”を取り出す。メモリコントローラ１４は、ステージ１オペレーション３０ａの継続実行のために、メモリバンク１６ａ，１６ｂへのアクセスを続ける。
【００２５】
イベント６６（クロックサイクル３３）において、バタフライ回路は最後のステージ１オペレーション（Ｓ１＿Ｏｐ１５）を実行し、データポイント“１５”，“３１”，“４７”，“６３”についての計算結果を出力する。イベント６６の間、メモリコントローラ１４は、データポイント“１５”および“３１”についての計算結果を、バンク１およびバンク２にそれぞれ記憶し、バンク１およびバンク２の記憶された値“０”および“４”にそれぞれアクセスして、ステップ４２でステージ２オペレーション（Ｓ２＿Ｏｐ２）の実行を開始する。図４Ａおよび図４Ｂの“Ｄ”参照符号は対応するステージが「終了した」ことを示す。
【００２６】
バタフライ回路１２はイベント６８（クロックサイクル６５）において最後のステージ２オペレーション（Ｓ２＿Ｏｐ１５）を実行し、メモリコントローラ１４は並行して、結果物を記憶し、ステップ４４のステージ３オペレーションを開始するために、既述のとおり入力を取り出す。
【００２７】
図３Ｂは、入力シーケンスベースのオペレーション３２の実行を示し、ステージ２オペレーション３０ｂを実行可能にするために、選択されたステージ１オペレーション３０ａが実行される。例えば、ステージ２オペレーション（Ｓ２＿Ｏｐ０）は入力シーケンス“０”，“４”，“８”，“１２”を特定する。それ故に、ステップ４８でステージ２オペレーション（Ｓ２＿Ｏｐ０）を開始可能にするために、ステップ４６においてメモリコントローラ１４は、インプレース・ステージ１オペレーションＳ１＿Ｏｐ０（０，１６，３２，４８）、Ｓ１＿Ｏｐ４（４，２０，３６，５２）、Ｓ１＿Ｏｐ８（８，２４，４０，５６）Ｓ１＿Ｏｐ１２（１２，２８，４４，６０）を実行する。ステップ４８におけるステージ２オペレーション３０ｂの実行後、関連するステージ１オペレーション３０ａを実行することにより、次のステージ２オペレーション３０ｂのための入力シーケンスをステップ４６で実行する。
【００２８】
図２に示すように、ステージ２オペレーションのシーケンスは、ステージ３のオペレーションの実行に基づいて選択することができる。ステージ３のオペレーション（Ｓ３＿Ｏｐ０）は入力シーケンス“０”，“１”，“２”，“３”を特定する。それ故に、ステージ３、オペレーション０（Ｓ３＿Ｏｐ０）は、インプレース・ステージ２オペレーションＳ２＿Ｏｐ０，Ｓ２＿Ｏｐ１，Ｓ２＿Ｏｐ２，Ｓ２＿Ｏｐ３の実行に基づいて実行される。以上から明らかなように、ステージ２オペレーション３０ｂの実行は、関連する４つのステージ１オペレーション３０ａが完了していることを必要とする。従って、もしステップ４９で次のステージ３のオペレーションのために追加のステージ２オペレーションを実行する必要があり、さらにステップ５１でステージ１オペレーションが完了しなければ、ステップ４６を繰り返して関連するステージ１オペレーションを実行する。
【００２９】
よって、メモリコントローラ１４が、ステージ３のオペレーション（例えば、Ｓ２＿Ｏｐ０，Ｓ２＿Ｏｐ１，Ｓ２＿Ｏｐ２，Ｓ２＿Ｏｐ３）に関連する、４つのステージ２オペレーションの実行をステップ４８および４９で完了させた後（この時点では、すべてのステージ１オペレーション３０ａは完了している）、メモリコントローラ１４はステップ５０で４つのステージ３のオペレーション（Ｓ３＿Ｏｐ０）を開始することができる。ステップ５３でより多くのステージ３のオペレーションを実行することが必要であると仮定すると、ステージ２オペレーション３０ｂは４のグループで完了させることができ、続いて関連するステージ３オペレーション３０ｃを実行する。
【００３０】
図４Ｂは、図３Ｂによる実行を示すタイミング図である。ステージ１、オペレーション０の実行を準備するイベント６０，６２に続いて、イベント７０，７２で、メモリコントローラはステージ１オペレーション４の実行のためにデータ値にアクセスする。メモリコントローラ１４は、ステージ２オペレーション０の実行に必要なシーケンス、すなわちＳ１＿Ｏｐ０，Ｓ１＿Ｏｐ４，Ｓ１＿Ｏｐ８，Ｓ１＿Ｏｐ１２に従って、データ値を取り出し続ける。バタフライ回路１２がステージ１オペレーション“０”，“４”，“８”，“１２”を実行した後、イベント７４において、メモリコントローラ１４は、イベント７８におけるステージ２オペレーション０の実行のために、イベント７４，７６においてステージ１の結果“０”，“４”，“８”，“１２”のためのデータ値を取り出す。したがって、メモリコントローラ１４は、データパス１８ａ，１８ｂ，１８ｃ，１８ｄの効率を損なうことなしに、ステージ１オペレーション３０ａとステージ２オペレーション３０ｂとを切り替えることができる。イベント８０におけるステージ２オペレーション“０”，“１”，“２”，“３”を実行し、すべてのステージ１オペレーション３０ａを完了した後、メモリコントローラ１４はステージ２とステージ３のオペレーションの実行の切替えを開始できる。
【００３１】
図４Ａ，４Ｂに示すように、メモリコントローラ１４はデータパス１８ａ，１８ｂ，１８ｃ，１８ｄの使用を最適化し、メモリ部分１６ａ，１６ｂの読み出しおよび書き込みオペレーションを最適化することを保証し、９７クロックサイクル内に６４ポイントＦＦＴ計算を完了することを保証する。ステージ３オペレーションの完了後、メモリコントローラ１４は、図１に示すように、出力パス２２から６４ポイントＦＦＴスペクトラムを出力する。
【００３２】
開示した実施形態ではRadix-4バタフライを利用しているが、その他の高次元（例えば、Radix-8）バタフライ回路を、適切な修正を加えて、このメモリコントローラに使用してもよいことは理解できるであろう。
【００３３】
メモリパーティションの実装
６４ポイントＦＦＴの読み出しおよび書き込みオペレーションの際にアクセスする必要のあるデータにアドレスインデックスa[5:0]（a[0]は最下位ビット）を仮定する。メモリバンクを特定するために排他的論理和（ＸＯＲ）演算を用いる。もし、F(a)=XOR(a[4], a[2], a[0])=0なら、メモリバンク１が対応するメモリであり、メモリバンク１内の実アドレスはa[5:1]である。もし、F(a)=XOR(a[4], a[2], a[0])=1なら、メモリバンク２が対応するメモリであり、メモリバンク２内の実アドレスはa[5:1]である。選択されたメモリの実アドレスは、メモリパーティションなしのアドレスの最初の５ビットから得られる。従って、アドレス値Ａ１１，Ａ１２は次のマッピングを持つ。
Ａ１１＝１１（１０進）＝００１０１１（バイナリ）  Ｆ（Ａ１１）＝１  Ａ１１はメモリバンク２のアドレス５にマップされる
Ａ１２＝１２（１０進）＝００１１００（バイナリ）  Ｆ（Ａ１２）＝１  Ａ１２はメモリバンク２のアドレス６にマップされる
Ａ１３＝１３（１０進）＝００１１０１（バイナリ）  Ｆ（Ａ１３）＝０  Ａ１３はメモリバンク１のアドレス６にマップされる
【００３４】
メモリコントローラ１４の他の実施形態では、各データ値がどのメモリに帰属するかを特定し、その関連メモリインデックス（つまり、メモリバンク内のメモリアドレス）を特定するためにルックアップテーブルを用いる。
【００３５】
ＦＦＴ回路の実装
図５は、ＦＦＴ回路の実装を示す。Radix-4バタフライの３ステージによって実装された６４ポイントＦＦＴは、３つのステージ間でバタフライ回路の共有を可能にし、回路面積を減らす。メモリコントローラ１４の実装形態である、バタフライデータアドレス生成器（ＢＦＬＹ＿ＤＡＧ）は、バタフライ回路１２の入出力のための適切なデータアドレスを生成するために用いられる。第２ステージへの入力は第１ステージの出力に依存し、第３ステージへの入力は第２ステージの出力に依存するので、これまで説明したように、バタフライ回路をフルに利用するために、適切なデータアクセススケジュールが用いられる。
【００３６】
本発明を最も実際的かつ好適であると考えられる実施形態において説明したが、本発明は当該実施形態に限定されるものではなく、むしろ添付の特許請求の範囲およびその精神に含まれる様々な変形物および均等物をも含めようとするものであることを理解してもらいたい。
【産業上の利用可能性】
【００３７】
本発明は、高速フーリエ変換演算を実行する回路に適用可能である。
【図面の簡単な説明】
【００３８】
【図１】本発明の一実施形態である、第１および第２メモリ部分を持つ、高速フーリエ変換（ＦＦＴ）回路を示す図。
【図２】本発明の一実施形態である、各インプレース計算オペレーションのための、第１および第２メモリ部分それぞれに記憶された等しい数のデータ値を用いた、図１のＦＦＴ回路によって実行される、３ステージＦＦＴ計算を示す図。
【図３Ａ】図２の３ステージＦＦＴ計算を実行する代替方法を示す図。
【図３Ｂ】図２の３ステージＦＦＴ計算を実行する代替方法を示す図。
【図４Ａ】図３Ａのインプレース計算シーケンスにおける、３ステージＦＦＴ計算を実行する際の、メモリコントローラによって実行されるメモリ読み出しおよび書き込み操作を示すタイミング図。
【図４Ｂ】図３Ｂのインプレース計算シーケンスにおける、３ステージＦＦＴ計算を実行する際の、メモリコントローラによって実行されるメモリ読み出しおよび書き込み操作を示すタイミング図。
【図５】図１のＦＦＴ回路の実装を示す図。
【図１】
2007527072.tif 000003
【図２】
2007527072.tif 000004
【図３Ａ】
2007527072.tif 000005
【図３Ｂ】
2007527072.tif 000006
【図４Ａ】
2007527072.tif 000007
【図４Ｂ】
2007527072.tif 000008
【図５】
2007527072.tif 000009
【国際調査報告】
2007527072.tif 000010
2007527072.tif 000011