(57)【要約】【課題】  二次元以上の高速フーリエ変換を計算するためのデータ処理システムを提供する。【解決手段】  データを通る各通過で半分になるブロック・サイズ及びストライド値を用いて全体としてデータ・セットをトラバースすることによりメモリ内でエンドツーエンドに並べられた２ｍデータ値の２ｎ行に対して、多次元ＦＦＴが計算される。データ値は、多次元データを表すので、データ内に１つまたは２つ以上の次元境界があり、それらがクロスされるとき、複素バタフライ計算によって与えられている係数値は、行われている操作を考慮するよう調整される。バタフライ計算の基礎を為すマトリクス計算の線形性は、これらの計算が行われる順番が重要ではなく、従って、各次元についての計算の異なった要素がデータ・セットを通る異なった通過上に生じたとしても、適切な係数変化を有する多数の通過が多次元計算を行うことができるということを意味する。【選択図】  図５
2006313518.tif 000002
【特許請求の範囲】
【請求項１】
データ値のアレイに多次元高速フーリエ変換を行うようデータ処理装置を制御する方法であって、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを、前記データ値メモリ内に格納する段階と、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択する段階と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択する段階と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値において前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行う段階と、
（ｖ）  前記データ値メモリに前記高速フーリエ変換バタフライ計算からの結果のデータ値を格納する段階と、
（ｖｉ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新する段階と、
（ｖｉｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、段階（ｉｖ）、（ｖ）及び（ｖｉ）を反復する段階と、
（ｖｉｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新する段階と、
（ｉｘ）  前記多次元高速フーリエ変換が完了するまで段階（ｉｖ）から（ｖｉｉｉ）までを反復する段階と、
を含む方法。
【請求項２】
フーリエ係数値の前記セットは係数値メモリ内に格納され、フーリエ係数値の作業セットとして係数値の初期セットを選択する段階と、フーリエ係数値の前記作業セットを更新する段階とは、係数値アドレスに依存して前記係数メモリから１つまたは２つ以上のフーリエ係数値を読取る段階を含む請求項１に記載の方法。
【請求項３】
前記フーリエ係数値は、実数部と虚数部を有する複素値であり、前記データ値は、実数部と虚数部を有する複素数データ値である。
【請求項４】
アドレス計算ハードウェアは、前記段階（ｖｉ）における前記作業アドレス値を更新する請求項１に記載の方法。
【請求項５】
アドレス計算ハードウェアは、前記段階（ｖｉ）における前記作業アドレス値を更新し、そして前記アドレス計算ハードウェアは、新しい係数値アドレスを計算し、そこから、段階（ｖｉ）におけるフーリエ係数値の前記作業セットを更新する際に、フーリエ係数値の前記作業セットが読取られる請求項２に記載の方法。
【請求項６】
前記アドレス計算ハードウェアは、段階（ｖｉｉｉ）における前記初期データ・アドレス値及び係数値の前記初期セットを更新する請求項４に記載の方法。
【請求項７】
前記高速フーリエ変換バタフライ計算は、ストライド値によって分離されたメモリ・アドレスにおける前記データ値メモリ内に格納されたデータ値に対して行われ、前記ストライド値は、前記２ｎ行の前記データ値のすべてが段階（ｉｖ）、（ｖ）、（ｖｉ）及び（ｖｉｉ）においてトラバースされてしまったときごとに半分にされる請求項１に記載の方法。
【請求項８】
データ値の前記２ｎ行をトラバースする際に前記高速フーリエ変換バタフライ計算において用いられる前記フーリエ係数値は、単位円上に複素数のシーケンスを含み、複素数の前記シーケンスは、角度のシーケンスによる複素回転に対応し、角度の前記シーケンスの各々は、πで始まる複素分離角度だけ異なっており、前記複素分離角度は、その点において該複素分離角度がπにリセットされる行われている高速フーリエ変換のレベルにおいて次元境界がクロスされるまで、前記２ｎ行の各トラバースで半分になる請求項１に記載の方法。
【請求項９】
アドレス計算ハードウェアは、前記段階（ｖｉ）における前記作業アドレス値を更新し、そして前記アドレス計算ハードウェアは、段階（ｖｉｉｉ）における前記初期データ・アドレス値及び係数値の前記初期セットを更新し、データ値の前記２ｎ行をトラバースする際に前記高速フーリエ変換バタフライ計算において用いられる前記フーリエ係数値は、単位円上に複素数のシーケンスを含み、複素数の前記シーケンスは、角度のシーケンスによる複素回転に対応し、角度の前記シーケンスの各々は、πで始まる複素分離角度だけ異なっており、前記複素分離角度は、その点において該複素分離角度がπにリセットされる行われている高速フーリエ変換のレベルにおいて次元境界がクロスされるまで、前記２ｎ行の各トラバースで半分になり、前記フーリエ係数値は、複素分離角度を減少する順番で連結されたグループ内の前記係数メモリ内に格納され、前記アドレス計算ハードウェアは、前記２ｎ行上のデータ値がトラバースされるにつれて前記係数値アドレスを増分し、かつ前記次元境界がクロスされる際に前記係数メモリの開始に前記係数値アドレスをリセットする請求項２に記載の方法。
【請求項１０】
前記多次元高速フーリエ変換は、段階（ｉｖ）、（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）及び（ｉｘ）が行われる際に行われている高速フーリエ変換のレベルにおいて一次元境界とクロスすることを含む二次元高速フーリエ変換である請求項１に記載の方法。
【請求項１１】
前記高速フーリエ変換バタフライ計算は、基数（ラディックス）２の計算であり、フーリエ係数の前記作業セットは、１のフーリエ係数を含む請求項１に記載の方法。
【請求項１２】
入力データ・セットは、各々が実数である２ｍ値の２ｎ行から成り、実データの高速フーリエ変換は、交互アドレス上に実数部及び虚数部を有する２ｍ−１の複素値の２ｎ行として入力データ・セットを解釈することにより計算され、最終の実データの高速フーリエ変換の出力は、後処理により２ｍ−１複素データの２ｎ行の高速フーリエ変換から回収される請求項１に記載の方法。
【請求項１３】
データ値のアレイに多次元高速フーリエ変換を行うための装置であって、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを格納するよう動作するデータ値メモリと、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択するよう動作する初期係数値選択器と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択するよう動作する初期データ・アドレス値選択器と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値において前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行うよう動作する計算ユニットであって、前記高速フーリエ変換バタフライ計算からの結果のデータ値は前記データ値メモリに格納されるものである前記計算ユニットと、
（ｖ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新するよう動作する作業値更新器と、
（ｖｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、前記計算すること、前記格納すること、及び前記作業値を更新することの反復を制御するよう動作する第１の制御器と、
（ｖｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新するよう動作する初期値更新器と、
（ｖｉｉｉ）  前記多次元高速フーリエ変換が完了するまで、前記計算すること、前記格納すること及び前記作業値を更新すること、並びに前記初期値を更新することの反復を制御するよう動作する第２の制御器と、
を備えた装置。
【請求項１４】
データ値のアレイに多次元高速フーリエ変換を行うためにデータ処理装置を制御するように動作するプログラムを担持するプログラム・プロダクトであって、前記多次元高速フーリエ変換は、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを、前記データ値メモリ内に格納する段階と、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択する段階と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択する段階と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値において前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行う段階と、
（ｖ）  前記データ値メモリに前記高速フーリエ変換バタフライ計算からの結果のデータ値を格納する段階と、
（ｖｉ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新する段階と、
（ｖｉｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、段階（ｉｖ）、（ｖ）及び（ｖｉ）を反復する段階と、
（ｖｉｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新する段階と、
（ｉｘ）  前記多次元高速フーリエ変換が完了するまで段階（ｉｖ）から（ｖｉｉｉ）までを反復する段階と、
を含むプログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理システムの分野に関する。一層詳細には、本発明は、二またはそれ以上の次元の高速フーリエ変換を計算するためのデータ処理システムに関する。
【背景技術】
【０００２】
高速フーリエ変換の計算は、多くの応用領域におけるデータ処理要件である。多次元高速フーリエ変換は、しばしば、画像処理のような領域において用いられる。高速フーリエ変換の計算に関連した計算のオーバーヘッドは重要であり、従って、高速フーリエ変換の速度を改善するために取られ得る対策を講じることは長所的である。ディジタル信号処理集積回路内におけるような高速フーリエ変換を計算するための特別な目的のハードウェアを提供することが知られている。このような特別な目的のハードウェアは、行われるべき特別な計算のための制御及び構成をさらに必要とする。ハードウェアが一層特殊化されるようになるにつれて、それに応じて制御の複雑さが増す。このことは、ハードウェアの応用性を「その」ＦＦＴに特別に制限する、固定のハードワイヤード・コントローラに導くか、または「その」ＦＦＴだけの計算に制限しない「共有資源アーキテクチュア」に関してプログラムのサイズを増すことに導く。さらに、そのような特別な目的のハードウェアを構成し、それを処理ループ間でリセットすることに費やされる計算サイクルは、減らすことが長所的である処理オーバーヘッドである。
【０００３】
既知の技術による多次元高速フーリエ変換を計算するに際し、多次元の結果を最終的に創設するように各次元における高速フーリエ変換の要素を順次に別々に計算することが知られている。従って、二次元の高速フーリエ変換の場合には、最初に一次元の行の高速フーリエ変換の結果のすべてを計算し、その後、一次元の列の高速フーリエ変換の結果のすべてを計算することが普通であろう。このようなシステムにおいて、コードの内部ループは特別な目的のハードウェア（例えば、ＦＦＴバタフライのためのパイプライン）を効率的に用いてまたはソフトウェアの場合にはハンドクラフトされた（手細工で作られた）／最適化されたコードを効率的に用いて履行され得るが、行及び列の間で循環させられることが必要とされる外部ループは、不利なことに、追加コードのサイズのオーバーヘッド並びに処理サイクルを消費する。
【発明の開示】
【課題を解決するための手段】
【０００４】
一態様に鑑みて、本発明は、データ値のアレイに多次元高速フーリエ変換を行うようデータ処理装置を制御する方法であって、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを、前記データ値メモリ内に格納する段階と、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択する段階と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択する段階と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値に前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行う段階と、
（ｖ）  前記データ値メモリに前記高速フーリエ変換バタフライ計算からの結果のデータ値を格納する段階と、
（ｖｉ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新する段階と、
（ｖｉｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、段階（ｉｖ）、（ｖ）及び（ｖｉ）を反復する段階と、
（ｖｉｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新する段階と、
（ｉｘ）  前記多次元高速フーリエ変換が完了するまで段階（ｉｖ）から（ｖｉｉｉ）までを反復する段階と、
を含む方法を提供する。
【０００５】
本発明は、高められたＤＳＰに一層効率的かつ一層安価にＦＦＴを、特にそのソフトウェア履行において行うために、少量のハードウェア支援を追加する。本発明の技術は、操作されるべきデータが連結される行に並べられ得、かつ処理されているデータの多次元の性質並びにそれが処理されている順番を考慮するためにパス（通過）中に作られている適切なフーリエ係数変化に従属する効率的な特別目的のハードウェアを用いて単一パスにおける単一ループ内で処理され得るということを認識する。特別目的のハードウェアが動作する処理ループの数を減少することは、システムを構成し、制御するために必要なコード・サイズを減少するという利点を有する。さらに、バタフライ計算のための命令が局部ループ・バッファに保持され得るので、命令を取り出して（フェッチし）格納するための必要性が減少することに起因して、電力消費が減少される。ソフトウェア制御のルーピング構造における変化よりもむしろ係数データ及びデータ・サイズ値における変化によって、変換が関係する次元数における変化が収容され得るので、変換のために用いられる処理カーネルも、また、一層容易に再使用される。データのレイアウトも、また、効率的なキャッシングを容易にする。
【０００６】
使用されるフーリエ係数は、特別目的のハードウェアによって生成され得る、またはソフトウェア内でコード化され得るということが理解されるであろうけれども、フーリエ係数値のセットが係数メモリ内に格納され、フーリエ係数値の作業セットとして係数値の初期セットを選択しかつフーリエ係数値の前記作業セットを更新する前記段階が、係数値アドレスに依存して前記係数メモリから１つまたは２つ以上のフーリエ係数値を読取ることを含む、という実施形態において、技術の柔軟性及び再使用可能性が改善される。
【０００７】
操作されておりかつ高速フーリエ変換に従属するデータは、種々の異なった物理的または抽象的なエンティティを表し得るが、長所的実施形態によれば、複素数である前記フーリエ係数値は、複素数の実数部及び虚数部を含む、単一アドレスと関連した単一のエンティティとして取り扱われる。実数部及び虚数部を個々に取り扱うのではなくむしろこの単一のエンティティの使用は、それらを複素形態に置くための前処理、該複素形態内での処理及び次に、それらを実数形態に戻すための後処理に長所的に従属し得る純粋な実数データ値の操作の場合でさえ、処理の全体効率を改善する。
【０００８】
本発明技術は、それが純粋にソフトウェアの履行内で用いられるときにも利点を有するが、アドレス生成ユニットを拡大するために特に良く適している。該技術は、それが専用のハードウェアＦＦＴ処理コアにおいて用いられるときにも利点を提供するが、資源共用データ経路上にソフトウェアＦＦＴの効率的な計算を許容するために特に良く適している。少なくとも好適な実施形態の重要な利点は、１）データ値アドレス及びそれらのストライドが追加の制御無しですべてのＦＦＴ次元に渡って単一のループ内で計算されるということであり、２）係数値アドレス及びストライド値が追加の制御無しですべてのＦＦＴ次元に渡って単一のループ内で計算されるということである。
【０００９】
本発明技術の長所的に単純化された履行は、前記高速フーリエ変換バタフライ計算がストライド値によって分離されたメモリ・アドレスにおいて前記データ値メモリ内に格納されたデータ値に対して行われ、前記ストライド値は、前記２ｎ行のすべてが段階（ｉｖ）、（ｖ）、（ｖｉ）及び（ｖｉｉ）においてトラバースされてしまったときごとに半分にされるというものである。
【００１０】
前述したように、用いられるフーリエ係数値は、表示されているデータの多次元性質を考慮するためにデータ・セットがトラバースされるときに変化する。長所的な実施形態によれば、データ値の前記２ｎ行をトラバースする際に前記高速フーリエ変換バタフライ計算において用いられる前記フーリエ係数値は、単位円上に複素数のシーケンスを含み、複素数の前記シーケンスは、角度のシーケンスによる複素回転に対応し、角度の前記シーケンスの各々は、πで始まる複素分離角度だけ異なっており、前記複素分離角度は、その点において該複素分離角度がπにリセットされる行われている高速フーリエ変換のレベルにおいて次元境界がクロスされるまで、前記２ｎ行の各トラバースで半分になる（開始角度がリセットされるのと同時にリセットされるまで、係数は２πまたは０にリセットし：複素数｛１，０｝、その初期のストライドはπであり、複素数｛−１，０｝、π／２，π／４・・・・・等、に半分にする）。
【００１１】
前述したように、フーリエ係数値は、特別目的のハードウェアによって生成され得るかまたはソフトウェア制御にハード・コード化され得るが、好適な実施形態においては、係数メモリ内に格納される。このような実施形態内では、前記フーリエ係数値は、複素分離角度を減少する順番で前記係数メモリ内の連結されたグループ（［｛１，０｝］、［｛０，ｊ｝］、［ｅｘｐ（ｊπ／４），ｅｘｐ（ｊ３π／４）］、［ｅｘｐ（ｊπ／８），ｅｘｐ（ｊ３π／８），ｅｘｐ（ｊ５π／８），ｅｘｐ（ｊ７π／８）］、［｛１，３，５，７，９，１１，１３，１５｝／１６］、［｛１，３，５，．．．．，３１｝／３２］、［｛．．．｝／６４］，．．．．，［｛．．．．｝／２ｍａｘ（ｎ，ｍ）］）に格納されるのが好ましく、前記アドレス計算ハードウェアは、前記２ｎ行のデータ値がトラバースされるときに前記係数値アドレスを増分し、次元境界がクロスされるときに前記係数値アドレスを前記係数メモリの開始にリセットする。
【００１２】
本発明技術は、次元の数における広範囲を有する多次元高速フーリエ変換に適用可能であると理解されるであろうけれども、該技術は、データ・セットがトラバースされるときにフーリエ空間における一次元境界とクロスすることを代表的には含む二次元高速フーリエ変換に特に良く適している。二次元変換を行うための必要性は、比較的一般的である。
【００１３】
高速フーリエ変換バタフライ計算は、２、４、８等のような広範な種類のラディックス値を有し得ることが理解されるであろうが、本技術は、基数（ラディックス）２の計算に良く適しており、この場合において、フーリエ係数のセットが、任意に与えられた時刻において用いられる１つのフーリエ係数を含む。
【００１４】
もう１つの態様に鑑みて、本発明は、データ値のアレイに多次元高速フーリエ変換を行うための装置であって、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを格納するよう動作するデータ値メモリと、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択するよう動作する初期係数値選択器と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択するよう動作する初期データ・アドレス値選択器と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値において前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行うよう動作する計算ユニットであって、前記高速フーリエ変換バタフライ計算からの結果のデータ値は前記データ値メモリに格納されるものである前記計算ユニットと、
（ｖ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新するよう動作する作業値更新器と、
（ｖｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、前記計算すること、前記格納すること、及び前記作業値を更新することの反復を制御するよう動作する第１の制御器と、
（ｖｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新するよう動作する初期値更新器と、
（ｖｉｉｉ）  前記多次元高速フーリエ変換が完了するまで、前記計算すること、前記格納すること及び前記作業値を更新すること、並びに前記初期値を更新することの反復を制御するよう動作する第２の制御器と、
を備えた装置を提供する。
【００１５】
さらなる態様に鑑みて、本発明は、データ値のアレイに多次元高速フーリエ変換を行うためにデータ処理装置を制御するように動作するプログラムを担持するプログラム・プロダクトであって、前記多次元高速フーリエ変換は、
（ｉ）  データ値メモリ内に行の連結されたシーケンスとして格納される各々２ｍデータ値の２ｎ行を有するデータ値のアレイを、前記データ値メモリ内に格納する段階と、
（ｉｉ）  前記データ値のセットに与えられるべきフーリエ係数値の作業セットとして係数値の初期セットを選択する段階と、
（ｉｉｉ）  作業データ・アドレス値として初期データ・アドレス値を選択する段階と、
（ｉｖ）  前記作業データ・アドレス値に依存するアドレス値において前記データ値メモリから読取られたデータ値の前記セットにフーリエ係数値の前記作業セットを用いて高速フーリエ変換バタフライ計算を行う段階と、
（ｖ）  前記データ値メモリに前記高速フーリエ変換バタフライ計算からの結果のデータ値を格納する段階と、
（ｖｉ）  フーリエ係数値の前記作業セットと、前記作業データ・アドレス値とを更新する段階と、
（ｖｉｉ）  前記２ｎ行の前記データ値のすべてがトラバースされてしまうまで、段階（ｉｖ）、（ｖ）及び（ｖｉ）を反復する段階と、
（ｖｉｉｉ）  係数値の前記初期セットと、前記初期データ・アドレス値とを更新する段階と、
（ｉｘ）  前記多次元高速フーリエ変換が完了するまで段階（ｉｖ）から（ｖｉｉｉ）までを反復する段階と、
を含むプログラム・プロダクトを提供する。
【００１６】
本発明の上述並びに他の目的、特徴及び長所は、添付図面と共に読まれるべき例示的実施形態の以下の詳細な説明から明瞭となるであろう。
【発明を実施するための最良の形態】
【００１７】
図１は、二次元ＦＦＴに従属すべき２ｍのデータ値を各々が含む２ｎのデータ行を備えるデータのアレイを示す。第１段として、一次元ＦＦＴのシーケンスが各データ行の上に順次に行われる。引き続き、一次元ＦＦＴの別のシーケンスがデータ内の各列の下で計算される。この方法は、不利益なオーバーヘッドを表す、比較的大きいループ構造を必要とする。
【００１８】
図２は、メモリ内に隣接して並べられた２ｍのデータ値を各々が含む２ｎの行を備えるデータのアレイを概略的に示す。この例の隣接レイアウトの場合、行は順次であり、互いに隣接する。この配列は、標準のキャッシング及びページ・テーブリング技術が長所的に用いられるのを許容する。バタフライは、アドレス・ゼロ、行ゼロ及びアドレス・ゼロ、行２（ｎ−１）、例えば、ハーフウェイ、からのデータを検索するクロスとして示されている。それは、次に、行のすべてのアドレスに渡って進み、次に、行２（ｎ−１）のアドレス２ｍ−１に達するまで次の行で続く。
【００１９】
初期ブロックの長さは、２（ｎ＋ｍ）、すなわち、全データ・セットである。初期のストライド（バタフライにおける点間のサンプリング距離）は、２（ｎ＋ｍ−１）である。ラディックス（基数もしくは底）２に対して、ストライドは、ブロック長さの半分である。図２は、１Ｄ  ＦＦＴのフォーマットにおいてであるが、ＦＦＴの回帰的（もしくは帰納的）性質を示す。反復（イテレーション）１において、１つのブロック及びＮ／２のバタフライ、従って、１の係数がある。反復（イテレーション）２において、２つのブロックがあり、各々、Ｎ／４のバタフライを有し、各ブロックごとに異なった係数を有する。このことは、各々が単一のバタフライと特定の係数とを有するＮ／２のブロックがあるまで続く。アドレス更新の動作は、ブロックが消失するまで（１だけ）増分することであり、次に、次のブロックにジャンプする。（これは、ＦＦＴフォーマット（バタフライの前または後にマルチプライア［乗数］が加わる）に依存する。４つの順列もしくは置換があるが、一層早期の例に従って、これは、アドレスの増分が係数及びデータ（ブロックをジャンプするようにリセットされる予備もしくは臨時データ）に対して常に１であるように、特別の係数オーダを有することによって単純化され、他のバリアント（varianets）は、データ・アドレスが、増分などをする前にブロックをジャンプするようにする。）
【００２０】
データ値が多次元データを表すので、全データ・セットがトラバースされるにつれ、フーリエ空間内の一次元または二次元以上の境界がクロス（交差）されてしまうであろうということが理解される。これらの次元境界の各々がクロスされるとき、係数アドレスの生成が、次元境界のジャンプを考慮するようリセットされる。しかしながら、全データ値がトラバース（横断）されるまで、データ・メモリ内のデータ値のアドレス指定が順次に継続し得る。従って、エンドツーエンドで配列された行でデータを横たえることによって、全データ・セットが、適切なフーリエ係数変化を有する単一のシーケンスでトラバースされ得、単純化されたルーピング及び制御構造を有する多次元ＦＦＴを行う。データ・セットを通る第１のパス（通過）が完了されてしまうと、ブロック・サイズＢ及びストライド長さは各々半分にされ、そして初期係数値の新しいセットが選択される。データは、次に、再度トラバースされる。この方法でデータ・セットを通る多数の通過を行うことにより、完全な必要とされるＦＦＴ結果が最終的に計算され得る。
【００２１】
各バタフライ計算が行われるにつれ、計算結果の値は格納されなければならず、それらが読取られた同じ場所に長所的には格納し戻される。しかしながら、所望ならば、異なった格納場所が、計算された値のために用いられ得る。特に、転置（トランスポーズ）されビット反転された出力フォーマットよりもむしろインオーダの（整然とした）出力フォーマットに帰結する、インラインのビット反転された格納が容易に達成され、その理由は、必要とされるアドレス・リセットが、図５に示されるアドレス生成器においてすでに説明された決定モーメントと一致するからである。
【００２２】
図３は、図２に対する記載されたシステムの代替的な図を概略的に示す。特に、データの行が、エンドツーエンドで横たえられかつデータを通る第１のパス（通過）に従属するものとして、図３に示されている。この第１の通過時に、与えられたストライド値は、データ・セット・サイズの半分である。示されているように、必要とされるバタフライ計算は、次に、各行ごとに行われる。
【００２３】
図４は、本技術を概略的に示すフロー図である。ステップ２において、操作されるべきデータ値が、各々が２ｍデータ値を含む２ｎ行（ｒｏｗ）としてメモリ内に横たえられる。この例で行われる計算は、図２及び３に示されるように、基数（ラディックス）２のバタフライ計算である。所望ならば、一層高い基数（ラディックス）の値（４、８等のような）が用いられ得ることが理解されるであろう。２の基数（ラディックス）の値によれば、ステップ４は、係数メモリ・アドレス値によって指定された係数メモリ・アドレスからこれを読取ることにより、初期の作業フーリエ係数値を選択する。ステップ６は、メモリ内で操作されるべきデータ値の開始を指定する初期のデータ・アドレス値を選択する。ステップ８は、現在のデータ・アドレス値に従って、メモリから複素数データ値の読取りを行い、現在のフーリエ係数を用いて、これらのデータ値に基数（ラディックス）２のＦＦＴバタフライ計算を行う。ステップ１０は、計算されたＦＦＴ結果の値をメモリに格納し戻す。ステップ１２は、操作されるべき次のデータ・メモリ・アドレス位置と、与えられるべき係数値が取られる適切なアドレスとを指定するために必要に応じて係数メモリ・アドレスと、データ・メモリ・アドレスとを更新する。
【００２４】
データ・アドレス値は、代表的には内部ループを通る各パス（通過）ごとに変化し、係数メモリ・アドレス値は、長さＢのブロックが空にされるときのみに変化するということが理解されるであろう。当業者に理解されるように、ＦＦＴ計算は、データ対を結合し、その後該データに対して複素回転のシーケンスを行う、反復計算として考慮されることができ、与えられる回転は、角度のシーケンスを通して増加し、それらの角度は、データを通る各通過で半分になる複素分離角度によって分離される。与えられるべき複素回転のこのシーケンス、及び分離角度における減少は、係数メモリ内に格納された係数値に反映され、ＦＦＴバタフライ計算が行われるときに、各データ値ごとに与えられるよう選択される。
【００２５】
分離角度が計算の進行につれ、単調に増加するまたは減少する通常の一次元ＦＦＴ計算とは対照的に、多次元データが単一のパス（通過）でトラバースされる本技術の代表的な実施形態は、現在のストライドで操作されるデータ値と、これらデータ値の次元関係との間の適切な関係を反映するよう各次元境界がクロスされるときに効果的にリセットされる係数値を用いる。
【００２６】
ステップ１４は、データ・セット内の行（ｒｏｗ）のすべてがトラバースされてしまったか否かをチェックし、もしチェックされていないならば、行われるべき次のバタフライ計算のためにステップ８への処理に戻る。ステップ８、１０、１２及び１４は、ルーピング構造が、制御ソフトウェア内で支援される必要のないように特別の目的のハードウェアで履行され得、それにより、二次元ＦＦＴの場合におけるルーピング制御オーバーヘッドを単一のループに減少するということが理解されるであろう。
【００２７】
データ・セット内の行のすべてがトラバース（横断）されてしまったということが、ステップ１４において決定されたならば、次に、処理はステップ１６に進み、そこで、全ＦＦＴ計算が完了されてしまったか否かを決定する。全ＦＦＴ計算が完了されてないならば、次に、処理はステップ４に戻り、そこで、新しい初期の作業フーリエ係数値が計算され、ブロック・サイズ及びストライドの長さが半分にされる。データ・ステップのトラバース（横断）は、次に、これらの新しい係数値、ブロック・サイズ及びストライドの長さのペリメータ（境界面）を用いて繰り返される。
【００２８】
このような動作は擬似コードで表せ得るということが当業者には理解されるであろう。このような擬似コードは、所望に応じてまたは適切に、ハードウェアで、部分的にハードウェアかつ部分的にソフトウェアで、または全体的にソフトウェアで履行され得る。このような擬似コード表示を、基数（ラディックス）２のＦＦＴに対して以下に与える。
【００２９】
２Ｄ−ＦＦＴアルゴリズム及びＡＣＵ命令“ａｄｒ＿ｄａｔａ（）”（状態で）の擬似コードを以下に特定する。
【００３０】
【数１】
2006313518.tif 000003
【００３１】
図５は、特別目的のハードウェア支援された本技術の履行で使用するためのアドレス計算ユニットを概略的に示す。特に、このアドレス計算ユニットは、バタフライの第１のサンプルのデータ・アドレス１８（他はストライドＢにある）と、係数値２０のセットのアドレスとを生成し、これらはそれぞれ、データ・メモリと、係数値メモリとに与えられ、ＦＦＴバタフライ計算回路（図示せず）によって用いられるようデータ値と係数値とを戻す。アドレス計算回路を通る主経路２２、２４、２６、２８、３０、３２は、操作されるべきデータ値を回復するよう、与えられるべきデータ・アドレスの増分シーケンスを生成するよう働く。このような各値が生成されるとき、比較器３４は、処理されている現在のブロックの終わりに達してしまったか否かを識別するように働く。このようなブロックの終わりに達してしまったとき、次に、現在のアドレス値は、加算器２８を用いてブロック値だけ進められる。ブロック・インジケータ値Ｉ０＿ｅｎｄの終わりも、ブロック・インジケータ・エンド・ポイントを計算するデータ経路内の加算器３６を用いて現在のブロック値の２倍だけ進められる。経路３８、４０、４２、４４、４６によって生成される係数値アドレスも、プロセスへの次のブロックに達したとき、一増分だけ進む。
【００３２】
一次元ＦＦＴ計算を行うよう係数値のセット及びデータのためのアドレスを生成するであろうハードウェアと比較して、現在の技術の多次元性質を支援するよう用いられるアドレス生成ロジック内の追加の回路素子が、図５内に陰影形態で示されている。これらの追加の素子は、行われているＦＦＴ処理のレベルにおいてクロスされている次元境界を示す値にブロック・サイズが達したときを検出するよう働く比較器４８を含む。例として、二次元ＦＦＴにおいて、データ・セットのトラバースの全数を通るポイント・ハーフ・ウェイ、すなわちＦＦＴのレベル間の境界がクロスされ、それに応じて与えられている係数値は、ＦＦＴ係数に対する初期開始複素分離角度を用いるように調節されることが必要である。次元境界クロスにおけるこのリセット動作は、マスク経路５２、５４、５６、５８、６０、６２の回りで巡回する増分するマスク値と共にＡＮＤゲート５０を用いて達成される。このマスク値は、生成されるブロック・リセット信号に従ってアドレス値が進められるときにマスクによって最大セットまで増分されているアドレス値を再循環するようＡＮＤ回路４６によって用いられる。
【００３３】
図５の例示的アドレス計算ユニットは、少なくとも部分的にハードウェア支援される履行内でこのようなアドレス計算ユニットが如何に与えられ得るかの単に１つの例示的実施形態であることが理解されるであろう。
【００３４】
図６は、ソフトウェアだけの履行において本技術を履行するために用いられ得る型の汎用コンピュータ２００を概略的に示す。このような汎用コンピュータは、処理の監視または高レベル制御を提供するために、部分的にハードウェア支援されるＦＦＴの実施形態と一緒にも、もしくは完全にハードウェア支援される実施形態と一緒にも用いられ得る。
【００３５】
汎用コンピュータ２００は、中央処理装置２０２、ランダム・アクセス・メモリ２０４、リード・オンリ・メモリ２０６、ネットワーク・インターフェース・カード２０８、ハード・ディスク・ドライブ２１０、ディスプレイ・ドライバ２１２及びモニタ２１４、並びにキーボード２１８及びマウス２２０を有するユーザ入力／出力回路２１６を含み、これら全ては、共通バス２２２を介して接続される。動作中、中央処理装置２０２は、１つまたは２つ以上のランダム・アクセス・メモリ２０４、リード・オンリ・メモリ２０６及びハード・ディスク・ドライブ２１０に格納され得る、またはネットワーク・インターフェース・カード２０８を介して動的にダウンロードされるコンピュータ・プログラム命令を実行する。行われる処理の結果は、ディスプレイ・ドライバ２１２及びモニタ２１４を介してユーザに表示され得る。汎用コンピュータ２００の動作を制御するためのユーザ入力は、キーボード２１８またはマウス２２０からユーザ入力／出力回路２１６を介して受信され得る。コンピュータ・プログラムは、種々の異なったコンピュータ言語で書かれ得ることが理解されるであろう。コンピュータ・プログラムは、記録媒体上に格納されかつ配分され、または汎用コンピュータ２０２に動的にダウンロードされ得る。適切なコンピュータ・プログラムの制御下での動作時に、汎用コンピュータ２００は、上述の技術を行うことができ、かつ上述の技術を行うための装置を形成するよう考慮され得る。汎用コンピュータ２００のアーキテクチュアは、大いに変えることができ、図６は単に一例である。
【００３６】
本発明の図示的実施形態が添付図面を参照してここに詳細に説明されてきたけれども、本発明は、これらの正確な実施形態に制限されるものではなく、種々の変化及び変更が、特許請求の範囲によって限定された本発明の範囲及び精神から逸脱することなく当業者によってそれら実施形態に為され得るということが理解されるべきである。
【図面の簡単な説明】
【００３７】
【図１】２Ｄ ＦＦＴを行うための既知の方法を概略的に示す図である。
【図２】本発明技術に従って行われる多次元ＦＦＴを概略的に示す図である。
【図３】アレイとして横たわるデータと、メモリ内に線形態様で横たわるデータとの間の関係を示す図２の代替的表示を示す図である。
【図４】本発明技術の動作を概略的に示すフロー図である。
【図５】本発明技術による多次元ＦＦＴを行うための特別目的のハードウェアのアドレス計算部分を概略的に示す図である。
【図６】図６に示されたＣＰＵの一体部分として本発明技術のソフトウェアの実施形態を履行するために用いられ得る汎用コンピュータを概略的に示す図である。
【符号の説明】
【００３８】
２００      汎用コンピュータ
２０２      中央処理装置
２０４      ランダム・アクセス・メモリ
２０６      リード・オンリ・メモリ
２０８      ネットワーク・インターフェース・カード
２１０      ハード・ディスク・ドライブ
２１２      ディスプレイ・ドライバ
２１４      モニタ
２１６      ユーザ入力／出力回路
２１８      キーボード
２２０      マウス
２２２      共通バス
【図１】
2006313518.tif 000004
【図２】
2006313518.tif 000005
【図３】
2006313518.tif 000006
【図４】
2006313518.tif 000007
【図５】
2006313518.tif 000008
【図６】
2006313518.tif 000009