(57)【要約】高速フーリエ変換又は逆高速フーリエ変換を実行するプロセッサは、基数２のバタフライ構造及び基数４のバタフライ構造を備える。高速フーリエ変換又は逆高速フーリエ変換を実行する方法は、入力データストリームについて、基数２のバタフライ演算を選択的に実行することと、基数２のバタフライ演算によって生成された結果と入力データストリームとのうちの１つについて、基数４のバタフライ演算を選択的に実行することとを備える。高速フーリエ変換又は逆高速フーリエ変換を実行する装置は、入力データストリームについて、基数２のバタフライ演算を選択的に実行する手段と、基数２のバタフライ演算によって生成された結果と入力データストリームとのうちの１つについて、基数４のバタフライ演算を選択的に実行する手段とを備える。高速フーリエ変換モジュール又は逆高速フーリエ変換モジュールを含み、情報を送受信する通信デバイスは、入力及び出力を有する基数２のバタフライ構造と、基数２のバタフライ構造の出力に接続する入力を有する基数４のバタフライ構造と、データストリームを、基数２のバタフライ構造の入力、又は基数４のバタフライ構造の入力に交互に接続するマルチプレクサとを備え、モジュールは、選択された入力に依存する２つの異なる分解能の逆高速フーリエ変換又は高速フーリエ変換を実行することができる。
2009535937.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換又は逆高速フーリエ変換を実行するプロセッサであって、
基数２のバタフライ構造と、
基数４のバタフライ構造と
を備えるプロセッサ。
【請求項２】
請求項１に記載のプロセッサにおいて、
前記基数２のバタフライ構造に入力が接続され、前記基数２のバタフライ構造の出力が、前記基数４のバタフライ構造の入力に接続されるプロセッサ。
【請求項３】
請求項２に記載のプロセッサにおいて、
前記基数４のバタフライ構造の入力に交互に接続される入力を更に備え、選択された前記入力に依存する２つの異なる分解能の高速フーリエ変換を実行することができるプロセッサ。
【請求項４】
請求項１のプロセッサにおいて、
ＧＰＡＰインタフェースを更に備えるプロセッサ。
【請求項５】
高速フーリエ変換又は逆高速フーリエ変換を実行する方法であって、
入力データストリームについて、基数２のバタフライ演算を選択的に実行することと、
前記基数２のバタフライ演算によって生成された結果と、前記入力データストリームとのうちの１つについて、基数４のバタフライ演算を選択的に実行することと
を備える方法。
【請求項６】
高速フーリエ変換又は逆高速フーリエ変換を実行する装置であって、
入力データストリームについて、基数２のバタフライ演算を選択的に実行する手段と、
前記基数２のバタフライ演算によって生成された結果と、前記入力データストリームとのうちの１つについて、基数４のバタフライ演算を選択的に実行する手段と
を備える装置。
【請求項７】
逆高速フーリエ変換モジュールを含み、情報を送信する通信デバイスであって、
入力と出力とを有する基数２のバタフライ構造と、
前記基数２のバタフライ構造の出力に接続された入力を有する基数４のバタフライ構造と、
データストリームを、前記基数２のバタフライ構造の入力、又は前記基数４のバタフライ構造の入力に交互に接続するマルチプレクサとを備え、
前記モジュールは、選択された前記入力に依存する２つの異なる分解能の逆高速フーリエ変換を実行することができる通信デバイス。
【請求項８】
高速フーリエ変換モジュールを含み、情報を受信する通信デバイスであって、
入力と出力とを有する基数２のバタフライ構造と、
前記基数２のバタフライ構造の出力に接続された入力を有する基数４のバタフライ構造と、
データストリームを、前記基数２のバタフライ構造の入力、又は前記基数４のバタフライ構造の入力に交互に接続するマルチプレクサとを備え、
前記モジュールは、選択された前記入力に依存する２つの異なる分解能の高速フーリエ変換を実行することができる通信デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明される局面は、一般に、高速フーリエ変換（ＦＦＴ）及び逆ＦＦＴ（ＩＦＦＴ）を実行する方法及び装置に関する。特に、共有ハードウェアの１つのセットを用いる、異なる分解能を持つＦＦＴ及びＩＦＦＴを実行することに関する。
【背景技術】
【０００２】
ＦＦＴ及びＩＦＦＴは、通信技術、特に無線通信において広く用いられる。本明細書に開示される実施形態の局面は、アプリケーションのための条件が発見される多くのタイプの通信システムにおけるアプリケーションである。局面は、本願の出願時に公開され、参照によって本明細書に組み込まれているＩＥＥＥ  ８０２．１１ｎ規格の下での無線通信分野における典型的な実施形態と関連して説明されるので、ＩＥＥＥ  ８０２．１１ｎに準拠したシステムのいくつかの特徴が説明される。
【０００３】
ＩＥＥＥ  ８０２．１１ｎに準拠したシステムは、２０メガヘルツモードと４０メガヘルツモードとの２つのチャネリゼーションモードを有する。これらのモードは、システムの多重入出力（ＭＩＭＯ）アンテナアーキテクチャのサポートにおいて提供される。従来、直交データ記号のストリーム、すなわち受信機によって区別可能な記号のストリームを生成するために、６４ポイントＦＦＴ及びＩＦＦＴが（一方は送信機において、他方は受信機において）２０メガヘルツチャネリゼーションレートとともに用いられている。従来、４０メガヘルツチャネリゼーションレートをサポートするために、２倍の分解能が必要であろう。これは、１２８ポイントＦＦＴ及びＩＦＦＴを必要とする。
【発明の開示】
【０００４】
本特許出願は、本願の譲受人に譲渡され、参照することによって本願に明確に組み込まれた、２００６年４月２８日出願の“Multi-Port Mixed-Radix FFT”と題された米国特許仮出願６０／７９５，７７８号に対する３５Ｕ．Ｓ．Ｃ．１１９条の下での国内優先権を主張する。
【発明の概要】
【０００５】
実施形態の局面に従って、高速フーリエ変換又は逆高速フーリエ変換を実行するプロセッサは、基数２のバタフライ構造と、基数４のバタフライ構造とを備える。実施形態の局面に従って、入力は、基数２のバタフライ構造に接続され、基数２のバタフライ構造の出力は、基数４のバタフライ構造の入力に接続される。更なる局面に従って、入力が、基数４のバタフライ構造の入力に交互に接続され、プロセッサは、選択された入力に依存する２つの異なる分解能の高速フーリエ変換を実行することができる。プロセッサは更に、ＧＰＡＰインタフェースを備えることができる。
【０００６】
別の実施形態の局面に従って、高速フーリエ変換又は逆高速フーリエ変換を実行する方法は、入力データストリームについて、基数２のバタフライ演算を選択的に実行することと、基数２のバタフライ演算によって生成された結果及び入力データストリームのうちの１つについて、基数４のバタフライ演算を選択的に実行することとを備える。
【０００７】
また別の実施形態の局面に従って、高速フーリエ変換又は逆高速フーリエ変換を実行する装置は、入力データストリームについて、基数２のバタフライ演算を選択的に実行する手段と、基数２のバタフライ演算によって生成された結果及び入力データストリームのうちの１つについて、基数４のバタフライ演算を選択的に実行する手段とを備える。
【０００８】
更なる実施形態の局面に従って、逆高速フーリエ変換モジュールを含み、情報を送信する通信デバイスは、入力と出力とを有する基数２のバタフライ構造と、基数２のバタフライ構造の出力に接続された入力を有する基数４のバタフライ構造と、データストリームを基数２のバタフライ構造又は基数４のバタフライ構造に交互に接続するマルチプレクサとを備え、モジュールは、選択された入力に依存する２つの異なる分解能の逆高速フーリエ変換を実行することができる。
【０００９】
追加の実施形態の局面に従って、高速フーリエ変換モジュールを含み、情報を送信する通信デバイスは、入力と出力とを有する基数２のバタフライ構造と、基数２のバタフライ構造の出力に接続された入力を有する基数４のバタフライ構造と、データストリームを基数２のバタフライ構造又は基数４のバタフライ構造に交互に接続するマルチプレクサとを備え、モジュールは、選択された入力に依存する２つの異なる分解能の高速フーリエ変換を実行することができる。
【詳細な説明】
【００１０】
図面において、様々な図内に示される同一又はほぼ同一の構成要素は、同一の番号で表される。明確さのために、全ての図において全ての構成要素が符号を有するわけではない。
【００１１】
本発明は、そのアプリケーションにおいて、以下で説明され、又は図面に示される構成要素の構成及び配置の詳細に限定されない。本発明は、他の実施形態にも適用可能であり、様々な方法で実行又は実現されることができる。また、本明細書で用いられる語句及び用語は、説明を目的としており、限定することとして見なされるべきではない。「含む（including）」、「備える」、又は「有する」、「含む（containing）」、「含む（involving）」、及び様々な明細書中の語句は、その後に列挙された項目、それらの等価物、及び追加の項目を包含するように意図されている。
【００１２】
様々な実施形態が、１つ又は複数のコンピュータシステムにおいて実現されることができる。コンピュータシステムは、例えば、インテル社のペンティアム（登録商標）タイププロセッサ、モトローラ社のパワーＰＣ、サン社のウルトラＳＰＡＲＣ、ヒューレットパッカード社のＰＡ−ＲＩＳＣプロセッサ、又は他の任意のタイプのプロセッサに基づくコンピュータのような汎用コンピュータであることができる。又は、これらのコンピュータシステムは、例えば、内部に埋込み型システムを含むか、又は、例えばセルラー電話のような無線通信システム、８０２．１１無線通信システム、及び１つ又は複数のプロセッサを含むその他のシステムを備える特別目的システムであることができる。任意のタイプのコンピュータシステムのうちの１つ又は複数が、様々な実施形態に従ってＦＦＴ及びＩＦＦＴを実行するために組み合わされることができるということがよく理解されるべきである。つまり、システムは、単一のコンピュータ又はデバイスに配置されることができ、また、通信ネットワークによって接続される複数のコンピュータ又はデバイスに分散されることもできる。
【００１３】
１つの実施形態に従うコンピュータシステムが、説明される任意のＦＦＴ機能及びＩＦＦＴ機能を実行するように構成される。このシステムは、無線又は有線ネットワーク通信を含む他の機能を実行することができ、実施形態は、任意の特定の機能又は機能のセットを有するように限定されないことがよく理解されるべきである。
【００１４】
例えば、実施形態の様々な局面が、例えば図１に示すような汎用コンピュータシステム１００において実行する専用ソフトウェアとして実現されることができる。コンピュータシステム１００は、例えばディスクドライブ、メモリ、不揮発性メモリ、又はデータを格納するその他のデバイスのような１つ又は複数のメモリデバイス１０４に接続されたプロセッサ１０３を含むことができる。メモリ１０４は一般に、コンピュータシステム１００の動作中に、プログラム、ファームウェア、及びデータを格納するために用いられる。コンピュータシステム１００の構成要素は、（例えば、同じ機械に統合された構成要素間の）１つ又は複数のバス、及び／又は（例えば、別々のディスクリート機械に存在する構成要素間の）ネットワークを含むことができる相互接続メカニズム１０５によって接続されることができる。相互接続メカニズム１０５は、（例えばデータ、命令の）通信が、システム１００のシステム構成要素間で交換されることを可能とする。ネットワークは、無線又は有線であることができる。
【００１５】
コンピュータシステム１００はまた、例えばキーパッド、マウス、トラックボール、マイクロホン、タッチ画面などの１つ又は複数の入力デバイス１０２と、例えば印刷デバイス、ディスプレイ画面、スピーカなどの１つ又は複数の出力デバイス１０１とを含むことができる。加えて、コンピュータシステム１００は、（相互接続メカニズム１０５に加えて、又はその代わりとして）コンピュータシステム１００を通信ネットワークへ接続する１つ又は複数のインタフェース（図示せず）を含むことができる。
【００１６】
図２でより詳しく示される記憶システム１０６は、一般に、コンピュータ読取可能及び書込み可能不揮発性記録媒体２０１を含む。ここでは、プロセッサによって実行されるプログラム、又はプログラムによって処理される、媒体２０１に格納された情報を定める信号が格納される。この媒体は、例えばディスク又はフラッシュメモリであることができる。一般に、プロセッサは動作中、データを、不揮発性記録媒体２０１から、プロセッサによって媒体２０１よりも高速な情報へのアクセスを可能とする別のメモリ２０２へ読み取らせる。このメモリ２０２は一般に、例えばダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）又はスタティックメモリ（ＳＲＡＭ）のような揮発性のランダム・アクセス・メモリである。これは、図示されるように記憶システム１０６内に位置するか、又は図示されないがメモリシステム１０４に位置することができる。プロセッサ１０３は一般に、統合回路メモリ１０４、２０２内でデータを処理し、処理の完了後、データを媒体２０１にコピーする。媒体２０１と統合回路メモリ要素１０４、２０２との間のデータ移動を管理する様々なメカニズムが周知であり、実施形態はそれに限定されない。実施形態はまた、特定のメモリシステム１０４や記憶システム１０６にも限定されない。
【００１７】
コンピュータシステムは、例えば特定用途向け集積回路（ＡＳＩＣ）のような、特別にプログラムされた、特別目的ハードウェアを含むことができる。実施形態の局面は、ソフトウェア、ハードウェア、ファームウェア、又はこれらの組み合わせによって実現されることができる。更に、このような方法、動作、システム、システム要素、及び構成要素は、上記のコンピュータシステムの一部として、又は独立構成要素として実現されることができる。
【００１８】
実施形態の様々な局面が実現されうる１つのタイプのコンピュータシステムの例としてコンピュータシステム１００が示されたが、実施形態の局面は、図１に示されるコンピュータシステム上での実現に限定されないことがよく理解されるべきである。実施形態の様々な局面は、図１に示すものとは異なるアーキテクチャ又は構成要素を有する１つ又は複数のコンピュータにおいて実現されることができる。
【００１９】
コンピュータシステム１００は、高レベルコンピュータプログラミング言語を用いてプログラム可能な汎用コンピュータシステムであることができる。コンピュータシステム１００はまた、特別にプログラムされた、特別目的ハードウェアを用いて実現されることもできる。コンピュータシステム１００において、プロセッサ１０３は一般に、例えばインテル社から入手可能な周知のペンティアム・クラス・プロセッサのような市販のプロセッサである。その他多数のプロセッサが利用可能である。このようなプロセッサは通常、例えばマイクロソフト社から入手可能なＷｉｎｄｏｗｓ（登録商標）  ９５、Ｗｉｎｄｏｗｓ  ９８、Ｗｉｎｄｏｗｓ  ＮＴ、Ｗｉｎｄｏｗｓ  ２０００（Ｗｉｎｄｏｗｓ  ＭＥ）、又はＷｉｎｄｏｗｓ  ＸＰオペレーティングシステム、アップル・コンピュータから入手可能なＭＡＣ  ＯＳシステムＸオペレーティングシステム、サン・マイクロシステムから入手可能なＳｏｌａｒｉｓオペレーティングシステム、又は様々なソースから入手可能なＵＮＩＸ（登録商標）オペレーティングシステムなどのオペレーティングシステムを実行する。特に移動式又は固定式に設計された無線通信デバイスを含むその他多数のオペレーティングシステムを用いることができる。
【００２０】
プロセッサ及びオペレーティングシステムは合わせて、高レベルプログラミング言語のアプリケーションプログラムが書き込まれるコンピュータプラットフォームを定義する。実施形態は、特定のコンピュータシステムプラットフォーム、プロセッサ、オペレーティングシステム、又はネットワークに限定されないことが理解されるべきである。また、実施形態は、特定のプログラミング言語又はコンピュータシステムに限定されないことも、当業者には明らかであるだろう。更に、その他の適切なプログラミング言語やその他の適切なコンピュータシステムも用いられうることが、よく理解されるべきである。
【００２１】
コンピュータシステムの１つ又は複数の部分は、通信ネットワークに接続された１つ又は複数のコンピュータシステムに分散されることができる。これらのコンピュータシステムはまた、汎用コンピュータシステムであることができる。例えば、実施形態の様々な局面が、１つ又は複数のクライアントコンピュータへサービスを提供するように構成された１つ又は複数のコンピュータシステム（例えばサーバ）、又は分散されたシステムの一部として全てのタスクを実行するように構成された１つ又は複数のコンピュータシステムへ分散される。例えば、実施形態の様々な局面は、様々な実施形態に従って様々な機能を実行する１つ又は複数のサーバシステムへ分散される構成要素を含むクライアントサーバシステム又はマルチタイアシステムにおいて実行されることができる。これらの構成要素は、通信プロトコル（例えばＴＣＰ／ＩＰ）を用いて通信ネットワーク（例えばインターネット）を介して通信する実行可能コード、中間コード（例えばＩＬ）、又は解釈コード（例えばＪａｖａ（登録商標））であることができる。
【００２２】
実施形態は、任意の特定のシステム又はシステムのグループにおいて実行することに限定されないことがよく理解されるべきである。また、実施形態は、任意の特定の分散型アーキテクチャ、ネットワーク、又は通信プロトコルに限定されないこともよく理解されるべきである。
【００２３】
様々な実施形態が、例えばＳｍａｌｌＴａｌｋ、Ｊａｖａ、Ｃ＋＋、Ａｄａ、又はＣ＃（Ｃ−Ｓｈａｒｐ）のようなオブジェクト指向プラグラム言語を用いてプログラムされることができる。他のオブジェクト指向プログラミング言語も用いられることができる。あるいは、機能プログラミング言語、スクリプトプログラミング言語、論理プログラミング言語が用いられることができる。実施形態の様々な局面は、非プログラム環境（例えば、ＨＴＭＬ、ＸＭＬ、又は、ブラウザプログラムのウィンドウで閲覧すると、グラフィカル・ユーザ・インタフェース（ＧＩＵ）の局面をレンダリングするかその他の機能を実行するその他のフォーマットで作成された文書）において実現されることができる。実施形態の様々な局面は、プログラム要素や非プログラム要素、又はこれらの組み合わせとして実現されることができる。
【００２４】
ここで、実施形態の局面が、８０２．１１ｎ無線環境における通信機器への典型的なアプリケーションと関連して説明される。
【００２５】
８０２．１１ｎ仕様は、２０メガヘルツ及び４０メガヘルツの両方のチャネリゼーションを可能とする。従来のデバイスは、２０メガヘルツチャネルで直交データを作成する手段として、６４ポイントＩ／ＦＦＴを用いる。よって、従来の考え方は、２０メガヘルツチャネリゼーションのための６４ポイントＦＦＴを用いることが必要なモードと、４０メガヘルツチャネリゼーションのための１２８ポイントＦＦＴを用いることが必要なモードとの両方をサポートすることを提案する。このようなアプローチは、対象となる任意のＲＦ帯域（例えば２．４ギガヘルツ、５ギガヘルツ）に適用可能であろう。
【００２６】
ある局面において、混合基数実現は、データフロー技術及びアドレッシング技術を最適化し、両動作が同じアーキテクチャ及びメモリ空間内で実行されることを可能とすることが発見された。加えて、ある局面において、混合基数実現は、高いデータレート対クロック比を利用し、複素数回転乗算に汎用アレイプロセッサ（ＧＰＡＰ）を用いるために、回転乗算からバタフライ構造を分離する。結局、典型的な実施形態は、２つの並行データストリームをサポートすることができる２ｘ２  ＭＩＭＯシステムに特に適している。しかし、この設計は拡張可能であり、他のＭＩＭＯ構成に容易に適用することができる。
【００２７】
典型的な混合基数実現は、６４ポイント及び１２８ポイントのＦＦＴ及びＩＦＦＴを実行するために、基数２のバタフライ構造及び基数４のバタフライ構造を用いる。この構成は、必要とされるように、その他の数の入力ポイントに拡張されることもできる。１つの構成に従って、１２８ポイントＦＦＴが実行される。時間領域サンプルポイントを基数２のバタフライに適用して、１２８ポイントＦＦＴ演算を、２つの６４ポイントＦＦＴ演算に分解する。基数４のバタフライは、最小倍数を用いて２つの６４ポイントＦＦＴを実行する。図３は、混合基数バタフライの構成を示す。示されるように構成されると、図３の混合基数構成は、両方の基数構成を用いて１２８ポイントＦＦＴの演算全体を分解することを示す。
【００２８】
図３の構成は、マルチプレクサを用いて最初の基数２のバタフライをバイパスするように再構成され、基数４のバタフライステージ内へ直接入力することができる。従って、１２８ポイントＦＦＴ及び６４ポイントＦＦＴの両方の演算が、基数２のバタフライ及び基数４のバタフライのみを用いて実行されることができる。
【００２９】
基数２のバタフライ及び基数４のバタフライの両方は、デシメーション・イン・フレケンシ（ＤＩＦ）方法を実現して、ステージ間の制御ロジックを簡素化する。その他の演算パラメータ又は構成パラメータに最適化されたその他の方法を用いることができる。図３が示すように、典型的な実施形態に従って、１２８ポイントＦＦＴの２つの６４ポイントＦＦＴへの分解は、１２８ポイントの単位円全体に関する回転因子を出力値に乗ずることを必要とする。このステージに従って、基数４のステージの各々も回転因子乗算を含む。ＤＩＦアプローチを用いて基数４のバタフライを実現することは、バタフライ、回転、バタフライ、回転、の順番を維持する。
【００３０】
逆ＦＦＴ演算（ＩＦＦＴ）は、構成的にはＦＦＴと同一である。ＩＦＦＴは、各回転因子の符号を反転し、また、基数４のバタフライ内のｊ乗算（j-multiplication）を逆数を求めることによって、上記の構成から得られる。
【００３１】
ハードウェアを最小化するために、全ての処理は順次的であり、ＧＲＡＰを用いて回転乗算を実行する。例えば、共に適切なストレージを伴う１つの基数２のバタフライ及び１つの基数４のバタフライだけで、必要な演算を実行するために十分である。ポイントは、１２８ポイント又は６４ポイントＦＦＴ（又はＩＦＦＴ）をそれぞれ実行するために、２つ１組で基数２のバタフライに適用されるか、又は４つ１組で基数４のバタフライに適用される。このタイプのアーキテクチャは、説明されたＦＦＴ／ＩＦＦＴ機能を必要とする任意のデバイスに関して、著しいエリア節約をもたらすであろう。
【００３２】
上記のアーキテクチャは、単一のデータストリームの処理に適している。２ｘ２  ＭＩＭＯシステムの場合のように、多数の並行するストリームをサポートするには、単純に、追加のＧＰＡＰと同様、データ格納及びバタフライ相互接続のための追加のハードウェアを追加する。同じ制御信号、アドレッシング、及び回転係数が他の並行ストリームによって用いられ、様々なＭＩＭＯ構成に適用可能である拡張可能な設計をもたらす。
【００３３】
この構成は、制御セクションとデータ経路セクションとの、モジュールの２つのセクション又は集合に明確に分割される。実施形態を拡張する場合、同一のデータ経路セクションが用いられるので、追加ストリームを追加することは、単純にデータ経路セクションを追加するが、制御セクションは、異なる数のストリーム及びデータ経路についても同じままである。
【００３４】
ＦＦＴ演算及びＩＦＦＴ演算の両方に関して、６４ポイント演算及び１２８ポイント演算を容易にサポートするメモリ構成を用いることができる。一般的な８０２．１１実現において、ＩＦＦＴはパケット送信のために用いられる。入力データは、比較的高い処理速度、すなわち、２００メガヘルツでモジュール内へバーストされることができる。一方、出力データは、送信データレート、すなわち毎秒２０メガ記号（２０Ｍｓｐｓ）又は４０Ｍｓｐｓによって規定される。逆に、パケット受信中のＦＦＴへの入力データは、同じ送信データレート、すなわち２００Ｍｓｐｓ又は４０Ｍｓｐｓに制限される。ＦＦＴ出力データは、復調及び復号のために、処理速度、すなわち２００メガヘルツでバーストされることができる。
【００３５】
５０又は１００のデータレート対クロック比の何れかを用いて、図４に示すように、ダブルバッファ構成はこれらの仮定を満たす。ダブルバッファは、制御割当てに基づいて、使用を循環させる。図５のタイミング図に示すように、入力書込みと、バタフライ読取及び書き込みと、出力読取との３つのモードが定められる。モード割当ては、上述したように、異なる入力及び出力シナリオを操作するように順番付けられる。ＩＦＦＴモードにおいて、１つのバッファがバースト入力を受け取り、その後、クロック速度で基数演算を実行する。この時間中、第２のバッファが、送信データレートで読み出される。これは、出力データが読み取られる方式を限定するものではない、ということを留意されたい。出力データは、サンプル間で、バーストアウトされるかストールされることができる。バッファは、送信レートの間隔において、例えば８０２．１１の場合４μｓ毎に規定される。第１のＯＦＤＭ記号の場合、各モードは、第１のバッファを通して進行する。送信レートが維持されることを確実にするために、第２のＯＦＤＭ記号は、第１の記号出力データが読み出される間のある時点で処理を開始しなければならない。この時点で、入力モードが第２のバッファにおいて開始し、処理が反復する。ＦＦＴモードでは、第１のＯＦＤＭ記号も同様に、第１のバッファを通して進行する。しかし、入力データが連続的であるために、第２のＯＦＤＭ記号は、第２のバッファにおいて直ちに開始される。処理比率を考慮すると、第１のＯＦＤＭ記号バタフライ及び出力演算は、第２のＯＦＤＭ記号が完全に書き込まれる前に完了されることを保証される。図５は、ＦＦＴ及びＩＦＦＴ処理に関してオーバーラップするメモリモードを示す。もし処理比率が、図示されたタイミングを保証するために十分なほど高くなければ、メモリ構成は、図示された例において、各モードに専用のバッファを必要とするか、あるいは３つのバッファを必要とする。
【００３６】
図４のメモリ構成の別の特徴は、６４ポイント及び１２８ポイントの演算をサポートするために、データがバッファ内で処理される方式である。各バッファは、最大１２８エントリ条件の大きさであるが、１ｘ１２８、すなわち１つの１２８エントリのバンクではなく、２ｘ６４、すなわち２つの並行する６４エントリのバンクとして構成される。６４で区切られたエントリが、同じアドレス可能場所の２つの隣接する半分へ書き込まれるように、入力データは順次的に書き込まれる。すなわち、６５番目のエントリは、０番目のエントリとして、同じアドレスの後半を占有する。すなわち、（ｉ、ｉ＋６４）となる。例えば、もし各エントリが１バイト幅で、各アドレス可能場所が１ワード幅、すなわち２バイト幅であれば、エントリｉはワードの最上位バイトへ書き込まれ、エントリｉ＋６４は同じワードの最下位バイトへ書き込まれることができる。実現要求及び性能要求を満たすために、他のエントリサイズが用いられることができる。ワードアドレス可能メモリの場合において、ワードアドレス可能メモリ場所の１つのバイトのみが、他のバイトを妨害することなく書き込まれる特別アドレッシングモードを提供するバッファバイト書込みは、エントリペア（ｉ、ｉ＋６４）全体が、説明されるように、６４ポイント及び１２８ポイントの両方の演算で一度に読み出されるために、６４ポイント及び１２８ポイントの両方の演算に関して制御ロジックを再利用するキーである設計仮定を可能とすることができる。基数２のバタフライ中、分解は、６４で分けられたデータペアを組み合わせる。両方のセットを並行して利用可能とすることで、バタフライは、単一のサイクル、すなわち、全部で６４のサイクルで実行されることが可能となる。基数４のバタフライ中、４つのアクセスが６４ポイント演算に必要であるが、１２８ポイントＦＦＴの場合、読取は、両方の６４ポイント演算にデータを提供する。この並行アクセスは、第２の６４ポイント演算が追加のレイテンシを一切課さないということを意味する。６４ポイントのみの演算の場合、エントリ６４乃至１２７内のデータは単に無視される。
【００３７】
このメモリ構成は、単一のデータストリームに必要な機能を説明する。Ｎ個の並行するストリームに関して、この構成はＮ回繰り返されるであろう。
【００３８】
入力書込み、バタフライアクセス（読取及び書込み）、及び出力読取の３つのメモリモードをトラックする３つのアドレッシングモードがある。上述したように、全てのアドレス生成は、並行ストリームの数であるＮと独立している。同じアドレッシングロジックが、全ての処理ストリームによって共有される。
【００３９】
入力書込みは、順序正しく連続している。しかし、インタフェースは、（順方向又は逆方向の）演算及び（６４ポイント又は１２８ポイントの）順番をマッチさせるために異なる条件をサポートする。パケット受信中、入力は、順番にかかわらずに一度に１サンプルずつ到着する。受信モードは順方向演算にマッチするので、この条件下では、入力は、インデックス０から６３へ順番に低いメモリペアへ書き込まれる。１２８ポイントモードにおいて、入力書込みは、インデックス０から６３へ再び継続するが、同じメモリバッファのより高いメモリペアへ書き込まれる。６４ポイントモードの場合、入力書込みは、低いメモリペアへ再度書き込まれるが、他のバッファへ書き込まれる。パケット送信中、又は逆演算中、データは１２８ポイントモードでは、ペアで利用可能であることが想定される。このようにして、メモリペアの全てが、各サイクルについて、インデックス０から６３まで書き込まれる。６４ポイントモードでは、低いメモリペアのみが書き込まれる。
【００４０】
バタフライアクセスに関して、基数２のステージ及び基数４のステージに関するアドレッシング順番を格納するためにＬＵＴを用いるのではなく、オンザフライでアドレスを生成するために、簡略化された制御ロジックが作成された。最初に基数４の演算を考えると、６４ポイントＦＦＴは、各々が１６バタフライを伴う３ステージを必要とする。ＤＩＦアルゴリズムの各ステージ内のアドレッシング順序をより精密に検査すると、バッファアドレスは、モジュール６４カウンタ（６ビット）の単純な並び替えである。第１のステージにおいて、各バタフライへの４入力は１６ずつ離される。カウンタビットを［１：０］［５：２］のように並べ替えることによって、シーケンシャルなカウントは、０、１６、３２、４８、１、１７、３３、４９、・・・１５、３１、４７、６３という値を生成する。第２のステージにおいて、４入力は４ずつ離される。カウンタビットを［５：４］［１：０］［３：２］のように並べ替え、０、４、８、１２、１、５、９、１３、２、６、１０、１４、３、７、１１、１５、・・・５１、５５、５９、６３という値を生成する。第３すなわち最終ステージにおいて、４入力はシーケンシャルであるので、カウンタビットは並べ替えられない。
【００４１】
基数２演算は、６４ずつ離された入力を有する６４のバタフライに関する。上述した、ペアになるバッファメモリを考慮すると、基数２のアドレッシングは、各読取アクセスが既に６４ずつ離された２つの入力を提供するので、任意の順序を用いることができる。簡略化のために、この順序付けは、基数４演算の第１のステージにマッチする。そのため、ＦＦＴ順序（６４又は１２８）にかかわらず、全てのアドレッシングは、１つの６ビットカウンタ内に含まれる。
【００４２】
出力読取は、特別な操作を必要とする。しかし基数処理は行われると代わりに、逆ビット順で出力を生成する。従って、出力アドレッシングはインデックスを並べ替えなければならない。所望の出力シーケンスのために、これは、アドレスビットの［５：０］から［１：０］［３：２］［５：４］へのビットスワッピングを必要とするのみである。１２８ポイント演算の場合、メモリペアは同時に出力される。入力において６４ずつ離されているので、バタフライはシーケンシャルなペアを出力として生成する。６４ポイントモードにおいて、出力制御は単純に、高いメモリペアに有効な出力をトリガしない。この出力制御は、シームレスな６３ポイント及び１２８ポイントの処理を自身に与える。
【００４３】
回転因子は、処理の基数及びステージに依存する。基数２のステージの場合、回転因子は、図６に示すように、１２８ポイントの単位円の円周に沿ってシーケンシャルであり、Ｗｎ１２８、ただしｎ＝０・・・６３、である。基数４の第１のステージの場合、回転因子は、６４ポイント単位円の円周に沿ってシーケンシャルであるが、４つのグループに分けられており、Ｗｎｋ６４、ただしｎ＝０・・・１５、ｋ＝０・・・３である。基数４の第２のステージの場合も、回転因子は、４つのグループに分けられるが、１６ポイント単位円の円周に沿っており、Ｗｎｋ１６、ただしｎ＝０・・・３、ｋ＝０・・・３である。基数４の最終のステージの場合、回転因子は、全て１である。
【００４４】
全ての係数をルックアップテーブル（ＬＵＴ）内に格納するのではなく、この典型的な実施形態は、モジュロアドレッシングと部分的ＬＵＴとのハイブリッド方法を用いてオンザフライで回転因子を生成することを選択する。参照のように（図６を見られたい）１２８ポイントの単位円を用いると、各象限のサイン値及びコサイン値は他方のミラーコピーであり、更に所与の象限の値は、中点を中心としてミラー化される。従って、部分的ＬＵＴは、「ｘ」値及び「ｙ」値からなる象限の半分、すなわち、１２８／４／２＋１＝１７エントリ（１７番目のエントリが周辺の値をミラーする中点）しか格納する必要はない。図６は、１／２事象がどのようにコサイン値及びサイン値を単位円にマップするかを示す。
【００４５】
このように、少なくとも１つの実施形態のいくつかの局面が説明されたが、様々な変更、修正、及び改良が当業者には容易に想到するであろうことがよく理解される。これらの変更、修正、及び改良は本開示の一部であるように意図されており、本開示の主旨及び範囲内であるように意図されている。
【図面の簡単な説明】
【００４６】
【図１】図１は、説明される実施形態の局面に関するコンピュータシステム又はプロセッサの接続のブロック図である。
【図２】図２は、図１のコンピュータシステムのメモリサブシステムのブロック図である。
【図３】図３は、実施形態の局面に従う混合基数バタフライ構造のブロック図である。
【図４】図４は、実施形態の局面を示すメモリ構成のブロック図である。
【図５】図５は、図４のメモリに関するタイミング図である。
【図６】図６は、実施形態の局面に従う回転因子間の関係を示す単位円の図である。
【図１】
2009535937.tif 000003
【図２】
2009535937.tif 000004
【図３】
2009535937.tif 000005
【図４】
2009535937.tif 000006
【図５】
2009535937.tif 000007
【図６】
2009535937.tif 000008
【国際調査報告】
2009535937.tif 000009
2009535937.tif 000010
2009535937.tif 000011