(57)【要約】【課題】  スカラー計算機向けの１次元フーリエ変換アルゴリズムを高速化する。【解決手段】  １次元フーリエ変換プログラムが、１次元データのデータ長Ｎを因子の積Ｎ１×Ｎ２×．．×Ｎｍに分解するステップと、該データ長ＮをＰ×ＱとしてＰとＱを変化させながら、長さＱのＰ本の１次元データのフーリエ変換結果に対する乗算のために必要とされる回転因子を、該Ｐ本の各々のフーリエ変換に対する乗算用の回転因子Q−１個の最初の１個に対して計算してテーブルに格納するステップと、該計算された回転因子を格納したテーブルを用いてｍ回のフェーズに分けてデータのフーリエ変換を行うステップとを備える。【選択図】図１
2005202911.tif 000002
【特許請求の範囲】
【請求項１】
１次元フーリエ変換を高速に処理するためのプログラムにおいて、
１次元データのデータ長Ｎをｍ個の因子の積Ｎ1×Ｎ2×．．×Ｎmに分解するデータ長分解ステップと、
該データ長ＮをＰ×Ｑとして、前記ｍ個の因子の積の順序を維持しつつ該ＰとＱを変化させながら、長さＱのＰ本の１次元フーリエ変換結果に対する乗算のために必要とされる回転因子を、該Ｐ本のおのおののフーリエ変換結果に対する乗算用の回転因子Ｑ−１個の最初の１個に対して計算し、テーブルに格納する回転因子格納ステップと、
該計算された回転因子を格納したテーブルを用いてｍ回のフェーズに分けてデータのフーリエ変換を行うフーリエ変換ステップとを計算機に実行させることを特徴とする１次元フーリエ変換プログラム。
【請求項２】
前記回転因子格納ステップにおいて、
前記ＱをＮ1、ＰをＮ2×Ｎ3×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル１に格納するステップと、
ＱをＮ2、ＰをＮ3×Ｎ4×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル２に格納するステップと、
順次ＱとＰを同様に変化させて同様の処理を行うステップと、
最後にＱをＮm-1、ＰをＮmとしてＰ−１個の回転因子を計算してテーブルｍ−１に格納するステップとを備えることを特徴とする請求項１記載の１次元フーリエ変換プログラム。
【請求項３】
前記フーリエ変換ステップにおける前記ｍ回のフェーズのうちの最後のフェーズを除くｎ＝１回目からｎ＝ｍ−１回目までの各フェーズにおいて、
該ｎ＝ｎ回目のフェーズに１対１に対応するテーブルとしての前記テーブルｎ（＝１，２，．．ｍ−１）の格納内容を用いて、フーリエ変換の対象となるデータへのアクセス期間中に、前記Ｐ本の１次元フーリエ変換結果に乗算すべき回転因子であって、テーブルｎに格納されていない他の回転因子を計算するステップと、
該Ｐ本の１次元フーリエ変換を行うステップと、
該フーリエ変換結果に対して前記テーブルｎに格納されていた回転因子と、計算された前記他の回転因子とを乗算する回転因子乗算のステップとを備えることを特徴とする請求項２記載の１次元フーリエ変換プログラム。
【請求項４】
前記他の回転因子を計算するステップにおいて、前記テーブルｎの格納内容を用いて漸化式によって該他の回転因子を計算することを特徴とする請求項３記載の１次元フーリエ変換プログラム。
【請求項５】
前記フーリエ変換ステップにおいて、
前記ｍ回のフェーズにおける入力データと出力データを格納するためのｍ次元配列領域として、領域１と領域２との２つを設け、
１回目のフェーズにおける領域１に格納されていた入力データに対するフーリエ変換処理の出力結果を領域２上でｍ次元配列に対する多次元転置を行った位置に格納し、
２回目のフェーズにおける領域２に格納された入力データに対するフーリエ変換処理の出力結果を領域１上でｍ次元配列に対する多次元転置を行った位置に格納し、
３回目以降のフェーズにおいて、領域１と領域２とを入力データ用と出力データ用とに交互に入れ替えながら同様の処理を実行することを特徴とする請求項１記載の１次元フーリエ変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各種のディジタル信号処理において利用されるフーリエ変換、特に高速フーリエ変換を処理するためのプログラムに関する。
【背景技術】
【０００２】
１次元フーリエ変換、および２次元以上の多次元フーリエ変換が各種の技術分野で広範に用いられている。特に多次元のフーリエ変換、例えば３次元のフーリエ変換に対する処理は、近年ではベクトル計算機を利用して行われることが多くなっていた。（特許文献１参照）
【特許文献１】特開平７−６１６０号公報「ベクトル計算機による複素高速フーリエ変換処理方法」
【０００３】
このようなベクトル計算機向けの３次元フーリエ変換アルゴリズムが、ベクトル長をなるべく大きくすることを目標にして開発されてきた。１次元目、２次元目の処理は並列化可能であり、連続アクセスによってマシン性能を上げるために、ベクトル長をｎ１（１次元目）×ｎ２（２次元目）にするアルゴリズムが採用されていた。
【０００４】
しかしながら、このｎ１やｎ２の値が大きくなると、メモリにアクセスしてデータをロードする場合にそのデータがキャッシュからあふれてしまい、キャッシュ性能を十分にいかせなくなるという問題点があった。
【０００５】
一方、最近ではスカラプロセッサのハードウェア的な進歩も目覚しく、スカラプロセッサを用いてフーリエ変換処理を行うことによって処理性能が向上することが期待されるが、近年主流であったベクトルプロセッサ向けのアルゴリズムをスカラプロセッサにそのまま用いることはできず、スカラプロセッサによるフーリエ変換処理を高速化するための新しいアルゴリズムが必要であるという問題点があった。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、上述の問題点に鑑み、特にフーリエ変換処理において、データのフーリエ変換結果に乗算される回転因子を格納する三角関数テーブルへのアクセス回数を減らし、かつアクセスを連続することによって、スカラ計算機向けの１次元フーリエ変換を高速に実行するためのプログラムを提供することである。
【課題を解決するための手段】
【０００７】
図１は、本発明の１次元フーリエ変換プログラムの原理的な機能ブロック図である。同図は１次元フーリエ変換を高速に行うための、スカラ計算機向けのプログラムの原理的な機能ブロック図である。
【０００８】
図１においてステップＳ１で、１次元データのデータ長Ｎが因子の積Ｎ1×Ｎ2×．．×Ｎmに分解され、ステップＳ２でデータ長ＮをＰ×Ｑとして、ｍ個の因子の積の順序を維持しつつＰとＱを変化させながら、長さＱのＰ本の１次元フーリエ変換結果に対する乗算のために必要とされる回転因子のうちで、Ｐ本のおのおのの１次元フーリエ変換結果に対する乗算用の回転因子Ｑ−１個の最初の１個だけ、Ｐ個計算されてテーブルに格納され、ステップＳ３でそのテーブルの内容を用いてｍ回のフェーズに分けてデータのフーリエ変換が行われる。
【０００９】
発明の実施の形態においては、図１のステップＳ２における回転因子のテーブルへの格納の処理において、ＱをＮ1、ＰをＮ2×Ｎ3×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル１に格納するステップと、ＱをＮ2、ＰをＮ3×Ｎ4×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル２に格納するステップと、順次ＱとＰを同様に変化させて同様の処理を行うステップと、最後にＱをＮm-1、ＰをＮmとしてＰ−１個の回転因子を計算してテーブルｍ−１に格納するステップとを備えることもできる。
【００１０】
また実施の形態においては、図１のステップＳ３においてｍ回のフェーズのうちの最後のフェーズを除く１回目からｍ−１回目までのそれぞれのフェーズにおいて、ｎ回目のフェーズに１対１に対応するテーブルｎの格納内容を用いて、フーリエ変換の対象となるデータへのアクセス期間中に、前述のＰ本の１次元フーリエ変換の結果に乗算すべき回転因子のうちで、テーブルｎに格納されていない他の回転因子を計算するステップと、Ｐ本の１次元フーリエ変換を行うステップと、そのフーリエ変換結果に対してテーブルｎに格納されていた回転因子と、漸化式で計算された他の回転因子とを乗算する回転因子乗算のステップとを備えることもできる。この場合、前述の他の回転因子を計算するステップにおいて、前述のテーブルｎの格納内容を用いて漸化式によって他の回転因子を計算することもできる。
【００１１】
さらに前述の回転因子の乗算のステップによって得られた乗算結果のデータをビットリバースした位置に格納して、前述のｎ回目のフェーズの出力とするステップを備えるとともに、最後のｍ回目のフェーズにおけるフーリエ変換結果のデータをビットリバースした位置に格納してｍ回目のフェーズの出力とするステップと、そのｍ回目のフェーズの出力に対してさらにビットリバースによる並べ替えを行うステップとを備えることもできる。
【００１２】
発明の実施の形態においては、図１のステップＳ３におけるｍ回のフェーズに対応して、入力データと出力データを格納するためのｍ次元の配列領域として領域１と領域２との２つを設け、１回目のフェーズにおける領域１に格納されていた入力データに対する処理出力結果を領域２上でｍ次元配列に対する多次元転置を行った位置に格納し、２回目のフェーズにおいて領域２に格納された入力データに対する処理出力結果を領域１上でｍ次元配列に対する多次元転置を行った位置に格納し、３回目以降のフェーズにおいて入力データと出力データを格納するための領域として、領域１と領域２とを交互に入れ替えながら処理を行うこともできる。
【００１３】
あるいは実施の形態において、ステップＳ３のｍ回のフェーズに分けたフーリエ変換ステップの終了後に、そのフーリエ変換ステップの結果を格納したｍ次元配列に対する多次元転置を行うステップをさらに備えることもできる。
【発明の効果】
【００１４】
本発明によれば、実際のフーリエ変換処理の前に必要な回転因子の一部のみを計算して三角関数テーブルに格納し、他の回転因子はデータへのアクセス期間中に計算を行うことによって、三角関数テーブルへのアクセス回数を大幅に減らすことが可能になり、またｍ回のフェーズの各フェーズにおいて三角関数テーブルへのアクセスを連続とすることができ、１次元フーリエ変換の処理を高速化することができる。さらにｍ回のフェーズに分けて再帰的に１次元フーリエ変換処理を行うことによって、各フェーズにおいてデータをＣＰＵにできるだけ近いキャッシュ上に保存して処理を行うことが可能となり、さらにフーリエ変換処理の高速化を行うことができる。
【発明を実施するための最良の形態】
【００１５】
本発明の実施形態について具体的に説明する前に、本実施形態において基本的にアルゴリズムとして利用する４ステップアルゴリズムを中心として、高速フーリエ変換の手法について最初に説明する。
【００１６】
一般にｎ個のデータ、ｘj（ｊ＝０，．．，ｎ−１）に対するフーリエ変換は次の（１）式によって定義される。ただし、ｉは虚数単位である。
【００１７】
【数１】
2005202911.tif 000003
【００１８】
しかしながら、データ数ｎが大きいときなどは、このまま（１）式を計算すると計算量が多くなるため、データ数ｎを基数に分解して計算する高速フーリエ変換が用いられる。
データ数ｎが２つの数ｐとｑの積に分解できるときには、（１）式におけるｊとｋは次の（２）式のように記述できる。
【００１９】
ｊ＝ｊ１＋ｊ２×ｐ，  ｋ＝ｋ１＋ｋ２×ｑ
ｊ１，ｋ２は０，．．．，ｐ−１，  ｊ２，ｋ１は０，．．．，ｑ−１
・・・（２）
例えば、ｊ１＝ｊ２＝０の時には、ｊは０となり、またｊ１＝ｐ−１、ｊ２＝ｑ−１の時、ｊはｎ−１となる。（２）式を用いて（１）式を展開すると次の（３）式が得られる。
【００２０】
【数２】
2005202911.tif 000004
【００２１】
ここで、ｎがｐとｑの積であることに注意して、ｅｘｐの項を整理すると、次の（４）式が得られる。
【００２２】
【数３】
2005202911.tif 000005
【００２３】
ここで、ｘj1+j2×Pをｐ行、ｑ列の行列の要素として表現すると、行列Ｘ（０：ｐ−１，０：ｑ−１）の要素Ｘ（ｊ１，ｊ２）となる。そこで第１ステップとして次の（５）式によって長さｑのフーリエ変換を行う。
【００２４】
【数４】
2005202911.tif 000006
【００２５】
次に第２ステップとしてフーリエ変換の結果としての各要素Ｘ（ｊ１，ｋ１）に次の（６）式に示されるように回転因子を乗算する。
Ｘ（ｊ１，ｋ１）＝ｅｘｐ（−２πｉｊ１×ｋ１）／ｎ×Ｘ（ｊ１，ｋ１）                                                    ・・・（６）
さらに第３ステップとしてａk1+q×k2の行列表示Ａ（０：ｑ−１，０：ｐ−１）に変更するために、次の（７）式によって転置を行う。
【００２６】
Ａ（ｋ１，ｊ１）＝Ｘ（ｊ１，ｋ１）                    ・・・（７）
そして第４ステップとして次の（８）式を用いて長さｐのフーリエ変換を行う。
【００２７】
【数５】
2005202911.tif 000007
【００２８】
以上の過程が４ステップアルゴリズムであり、本発明の実施形態においては、この４ステップアルゴリズムを基本として高速フーリエ変換を行うものとする。
すなわち、４ステップアルゴリズムは、データ数ＮがＰとＱとの積に分解できた時に、１次元データを入力Ｐ×Ｑ、出力Ｑ×Ｐの２次元データと見なして、４つのステップからなる処理で高速フーリエ変換の計算を行うものである。
【００２９】
第１ステップ  Ｐ本の長さＱの１次元フーリエ変換を行う。
第２ステップ  フーリエ変換後の各要素に回転因子を乗算する。
第３ステップ  Ｐ行、Ｑ列の行列をＱ行、Ｐ列の行列に転置する。
【００３０】
第４ステップ  Ｑ本の長さＰの１次元フーリエ変換を行う。
この４ステップアルゴリズムについては、次の文献に記述されている。この文献内では、４ステップアルゴリズムという名称はつけられてはいないが、その内容はこの文献の２．Ｅｘｉｓｔｉｎｇ  ＦＦＴｓのはじめに記述されている。
【００３１】
【非特許文献１】Ｐ．Ｎ．Ｓｗａｒｚｔｒａｕｂｅｒ，“Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  ＦＦＴｓ”，Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｉｎｇ  ５．ｐ．１９７−２１０、Ｎｏｒｔｈ−Ｈｏｌｌａｎｄ（１９８７）
【００３２】
このような４ステップアルゴリズムの変形として次のような３つのタイプが考えられる。第１のタイプとしては、データ数Ｎが２のべき、すなわち２nで表されるときに各ステップでＱの値を２とし、行列の転置については最後に一度行う方法が考えられる。この時、最後に行うべき転置はビットリバースと呼ばれる置き換えで実行できることが知られている。ビットリバースが有効となるように基数Ｑの値を４、８、１６などのように２より大きな数として、データのアクセスに対する演算密度を高めることができる。
【００３３】
第２のタイプとしては、Ｎがいくつかの代表的な基数のべきの積で表される場合に、同様に４ステップアルゴリズムを適用して計算する方法が考えられる。この時、行列の転置において別の作業域を用意しておき、後述するように再帰的に行われる４ステップアルゴリズムの１つのフェーズで転置結果をこの作業域に書き込み、次のフェーズではその領域、すなわち出力領域を入力として、入力、および出力の領域を入れ替えながら、計算を続ける方法である。
【００３４】
第３のタイプとしては、第２のタイプと同様にＮをいくつかの代表的な基数で表現し、計算を行うが、行列の転置は最後に一度にまとめて行う方法がある。
このような高速フーリエ変換のタイプの区別とは直接の関係がないが、変換の高速化のために次のような条件を考慮する必要がある。まず第１に各フェーズでのデータへのアクセスが連続となるように処理を行うことである。第２に４ステップアルゴリズムの第２ステップで用いられる回転因子を格納する三角関数テーブルへのアクセスが連続となるようにテーブルを構成することである。第３に基数を適当に大きくして、アクセスに対する演算密度が高くなるようにすることである。第４に三角関数テーブルへのアクセス回数を減らすことである。
【００３５】
本発明では、後述するように必要な回転因子の一部のみをあらかじめ計算してテーブルに格納し、残りの回転因子は、データのローディングに要する時間の間に漸化式を使って計算して、テーブルに対するアクセス回数を減らすことにする。
【００３６】
第５の条件は、計算結果のデータを再利用できるように変換を制御することであり、また第６の条件は変換で利用するデータが最もＣＰＵに近いＬ１キャッシュに保持できるように、再帰的な方法を利用して変換を行うことである。
【００３７】
以上で高速フーリエ変換の４ステップアルゴリズムについて説明したが、続いてこの４ステップアルゴリズムを基本的に利用する本発明の実施形態について説明する。図２は、本発明の第１の実施形態としての２基底のフーリエ変換の全体処理フローチャートである。この第１の実施形態は、基本的には前述の第１のタイプに相当する。
【００３８】
図２において処理が開始されると、まずステップＳ１０でデータ数Ｎがｍ個の因数Ｎ１、Ｎ２，．．，Ｎｍの積に分解される。ステップＳ１１で三角関数テーブルを作るための初回呼び出しであるか否かが判定され、すでに対応するテーブルが作られている場合にはステップＳ１３の処理に直ちに移行するが、作られていない場合にはステップＳ１２で三角関数テーブルの作成処理が行われる。
【００３９】
この三角関数テーブル作成処理では、まずデータ数ＮがＮｔに代入され、繰り返し回数ｋが１に初期化された後に、次の（１）と（２）の処理がｍ−１回繰り返される。
（１）ω＝ｅｘｐ（２πｉ／Ｎｔ）として、ωj（ｊ＝１，．．，Ｎｔ／Ｎｋ）をテーブルに格納する。
【００４０】
（２）ｋがｍ−１と等しくなければ、Ｎｔ＝Ｎｔ／Ｎｋとし、ｋの値をインクリメントして（１）以降を繰り返す。
図３は、後述する各フェーズのフーリエ変換において、データのフーリエ変換の結果に乗算されるべき回転因子を、Ｐ行、Ｑ列の配列に格納されたデータに対応して示すものである。すなわちテーブル作成処理において、まず（１）でＮｋ＝Ｎ１として、ステップＳ１０で、積に分解されたＮがＮ１と残りの因数の積とに分離され、Ｎ＝Ｐ×Ｑで、ＱがＮ１、ＰがＮ２×．．．×Ｎｍと分解されたと考えて、図３においてデータがＰ行、Ｑ列の配列に格納されたものとし、後述する各フェーズにおけるフーリエ変換結果としての各データに乗算されるべき回転因子が配列内の位置に対応して示されている。すなわち第１行と第１列の変換結果のデータに対しては、１が乗算されるのみであり、結果は変わらないが、第２行、あるいは第２列に対しては、それぞれのデータの変換結果に対してω0＝１、ω、ω2、ω3．．ωQ-1が、あるいは１、ω、ω2、ω3．．ωP-1が乗算されることになる。
【００４１】
そこで本実施形態では、まず第２列の変換結果のデータに対して乗算されるべき回転因子として、第２行のωから第Ｐ行のωP-1までの値が計算され、複素数型の１次元配列のテーブルｔｂ１ｅ１に格納される。この格納形式を図４に示す。すなわち図４において、１次元配列のテーブルの最初のｔｂ１ｅ１にＰ−１個の複素数型のデータが、長さＬ１にわたって格納されることになる。このｔｂ１ｅ１の内容は後述する第１フェーズで用いられる。
【００４２】
次に前述の（２）で、データ数ＮからＮ１を除いた残りの因数の積がＮｔとされ、ｋの値が２とされた後に、（１）の処理が行われる。ここでテーブルに格納される回転因子は、後述する全部でｍ回の各フェーズの第２フェーズにおいて使用されるものであり、第１フェーズに比べてＮｔの値が小さくなり、２πを分割する角度の単位が大きくなるために、第１フェーズ用に格納された回転因子の値をそのまま用いる場合には、飛び飛びのアクセスが必要となる。このためアクセスを連続的に行うために第２フェーズで図３に相当する配列におけるフーリエ変換後のデータの３列目に乗算されるべき回転因子を計算して、図４のｔｂ１ｅ２の部分に格納する処理が行われる。
【００４３】
すなわちｔｂ１ｅ１を作成する処理の後に、ＰがＮｔに代入され、Ｎ２をＱ、ＰをＮ３×．．×Ｎｍとしたときに必要な回転因子の計算が行われ、図４のｔｂ１ｅ２に格納される。その長さＬ２は、ｔｂ１ｅ１の長さＬ１よりも当然短い。
【００４４】
以下同様の処理が続けられ、図２のステップＳ１２のｍ−１回目の処理において、Ｎ（ｍ−１）とＮｍとの積をＮｔ、Ｎ（ｍ−１）をＱ、ＮｍをＰとして後述する最後から２番目の第（ｍ−１）フェーズにおいて使われるべき回転因子の計算が行われ、図４のｔｂ１ｅ（ｍ−１）に格納されて、ステップＳ１２の処理を終了する。なお、例えばＮ（ｍ−１）は図１の説明におけるＮm-1と同じである。
【００４５】
図２のステップＳ１３でｋの値が再び１に初期化され、ステップＳ１４からＳ１６の処理が、ｋの値がｍに達するまで続けられる。ステップＳ１４は各フェーズにおけるフーリエ変換処理（のサブルーチン）であり、その詳細は図５において説明する。ステップＳ１５で、ここではフェーズの回数を示すｋの値がｍに達していないと判定されると、ステップＳ１６でｋの値がインクリメントされ、次のフェーズに対する処理がステップＳ１４で行われ、ステップＳ１５でフェーズの回数がｍに達したと判定された時点で、ステップＳ１７でビットリバースによる並べ替えが行われて処理を終了する。すなわち前述のようにタイプ１では、行列の転置をビットリバースによる並べ替えで最後に一度に実行することになる。これに対応して、後述するように各フェーズのフーリエ変換において、回転因子が乗算された結果があらかじめビットリバースされて格納される。
【００４６】
図５は、図２のステップＳ１４における各フェーズのフーリエ変換処理の詳細フローチャートである。この処理は、図４で説明した各フェーズにおいて必要な回転因子を格納するテーブル、第１フェーズではｔｂ１ｅ１を利用して実行される。
【００４７】
図５において処理が開始されると、まずステップＳ２０で最後のフェーズであるか、すなわち図２のステップＳ１５で説明したように最後のｍ回目のフェーズであるか否かが判定される。最後のフェーズにおいては回転因子の乗算が不必要であり、第（ｍ−１）フェーズまでとは処理が異なるため、最後のフェーズでない場合にステップＳ２１の処理に移行する。
【００４８】
ステップＳ２１で、最初は１で、フェーズが進むごとに１つ前の変換の基数Ｎi-1を乗じた多重度ｍｔでNを割った値が４ステップアルゴリズムを適用して計算するべきフーリエ変換の長さＮｓとされ、ｉｘの値が１に初期化される。またｉｘは列のインデックスを示し、その値が１であることは１列目を示している。
【００４９】
ステップＳ２２で、Ｎｓとｉｘの値を用いてｎｂａｓｅの値が求められる。ここではｉｘが１であるためにｎｂａｓｅは０となる。そしてｎｂａｓｅ＋１からはじまる長さＮｓの１次元の配列ｘの部分が２次元の配列ｙと見なされる。この２次元配列の形式を図６に示す。
【００５０】
この１次元配列ｘ（１：Ｎｓ）が図６に示す２次元配列、すなわちＮｓ／Ｎｉ行、Ｎｉ列の２次元配列と見なされる。
そしてステップＳ２３で、この２次元配列の第１行、すなわちｙ１（１，１：Ｎｉ）のフーリエ変換が行われる。このデータは１行目のデータであるために、このフーリエ変換結果に回転因子を乗算する処理は必要がなく、ステップＳ２４でこの２次元配列の行を示すインデックスであると共に、図４で説明した三角関数テーブルのデータの格納位置を示すためのｉｚが２とされ、続いてステップＳ２５からステップＳ３１までの処理が、ｉｚの値がＮｓ／Ｎｉの値を超えるまで繰り返される。すなわち図６において２次元配列の各行に対する処理が２行目から最後のＮｓ／Ｎｉ行目まで繰り返されることになる。
【００５１】
ステップＳ２５で、図４で説明した三角関数テーブルが参照される。まず一番上のテーブルｔｂ１ｅ１の中で最も上に格納されている複素数型のデータがロードされる、すなわちｔｂ１ｅ１の中でｉｚ−１＝１番目のデータの実数部がＷＲ１に、虚数部がＷＩ１にロードされる。次にステップＳ２６で、２次元配列ｙ（ｉｚ，１：Ｎｉ）の要素、ここでは２行目の要素Ｎｉ個の要素の実数部がＺＲｉ、虚数部がＺＩｉ（ｉ＝１，．．，Ｎｉ）にロードされる。
【００５２】
図３と図４で説明したように、図４の三角関数テーブルは、図３の配列に対応する２列目のデータのフーリエ変換結果に乗算されるべき回転因子が図４のｔｂ１ｅ１に格納される形式となっている。すなわちステップＳ２５でロードされた回転因子は図３の２行、２列のωに相当し、第２列の３行目以下のフーリエ変換後のデータに乗算されるべき回転因子については、本実施形態では漸化式を用いて、このデータのロードの間に計算するものとする。この計算のための漸化式として次の（９）、（１０）式を用いる。
【００５３】
ＷＩ（ｉ＋１）＝ＷＩｉ×ＷＲ１＋ＷＲｉ×ＷＩ１      ・・・（９）
ＷＲ（ｉ＋１）＝ＷＲｉ×ＷＲ１−ＷＩｉ×ＷＩ１      ・・・（１０）
ここでＷＲ１、およびＷＩ１は、ステップＳ２５でロードされた回転因子ωの実数部と虚数部であり、（９）、（１０）式の計算を繰り返すことによって図３の第２行におけるω2、ω3．．が次々と計算されることになる。なお、この漸化式は三角関数の加法定理に相当する。
【００５４】
続いてステップＳ２７でｙ（ｉｚ，１：Ｎｉ）、ここでは図６の２行目のデータに対するフーリエ変換が一時的な作業域を使って計算され、ステップＳ２８でその計算結果に漸化式を用いて計算された回転因子が乗算され、ステップＳ２９で乗算結果としてのＮｉ個のデータがビットリバースされた位置に格納される。ここでビットリバースしてデータを格納する理由は、前述のようにタイプ１においては転置に相当するビットリバースを最後に行うため、そのビットリバースと矛盾しないようにあらかじめ回転因子の乗算されたフーリエ変換結果をビットリバースした位置に格納しておくものである。
【００５５】
ステップＳ３０で２次元配列ｙの行のインデックスとしてのｉｚの値がインクリメントされ、ステップＳ３１でその値がＮｓ／Ｎｉ、すなわち２次元配列ｙの行の数を超えていないかが判定され、超えていない場合にはステップＳ２５からの処理が２次元配列ｙの３行目以降に対して続けられる。この処理では、例えばステップＳ２５で、図４で説明したｔｂ１ｅ１の三角関数テーブルの対応する内容が、ＷＲ１、ＷＩ１にロードされた後に、ステップＳ２６以降の処理が２行目と同様に実行されることになる。
【００５６】
そしてステップＳ３１でｉｚがＮｓ／Ｎｉの値を超えたと判定されると、ステップＳ３２で図３と同じ配置のデータの配列における列のインデックスｉｘがインクリメントされ、ステップＳ３３でそのインデックスの値が多重度ｍｔを超えていないかが判定され、超えていない場合にはステップＳ２２以降の処理が繰り返される。
【００５７】
この繰り返しの処理では、まずｉｘの値が２となることによりベースポインタの値ｎｂａｓｅがＮｓとなり、１次元配列ｘの範囲はＮｓ＋１からＮｓの２倍までの範囲となる。すなわち図３に対応するデータの配列において、第１列の上から下、次に第２列の上から下という順序の位置として指定される１次元配列ｘが第２列の位置となり、この第２列の１次元配列が２次元配列ｙと見なされて、その２次元配列に対するステップＳ２３以降の処理が繰り返されることになる。
【００５８】
そしてステップＳ３３で、ｉｘがｍｔを超えた、すなわち対応する基数の計算がすべて終了したと判定された時点でリターンし、図２のステップＳ１５の処理に移行する。
図５のステップＳ２０で、最後のフェーズであると判定されると、データの１次元配列ｘ（１：Ｎ）に対するフーリエ変換が回転因子を乗算することなく実行される。すなわちステップＳ３５で１次元配列ｘが２次元配列ｙ（Ｎｍ，Ｎ／Ｎｍ）と見なされ、Ｎ／Ｎｍ本の長さＮｍの１次元フーリエ変換が行われる。
【００５９】
すなわちまず列のインデックスｉｘの値が１とされた後に、ステップＳ３６で２次元配列ｙにおいてインデックスｉｘ＝１で指定される列、ここでは第１列のフーリエ変換が行われ、ステップＳ３７でフーリエ変換結果が前述と同様に最後のビットリバースと対応させる意味でビットリバースした位置に格納され、ｉｘの値がインクリメントされ、ステップＳ３８でｉｘが列の数、すなわちＮ／Ｎｍを超えたか否かが判定され、超えていない場合には、２次元配列ｙの第２列以降に対するステップＳ３６以降の処理が繰り返され、ステップＳ３８で２次元配列に対する全ての処理が終了したと判定されると図２の処理にリターンし、ステップＳ１５以降の処理が行われる。
【００６０】
ここで以上の処理について３次元配列の考え方を用いてさらに説明する。最後のフェーズの処理で要素の添え字のビットリバースを使って要素を入れ替えるので、４ステップアルゴリズムを繰り返し適用するときに転置は行わない。この繰り返し処理は以下のようになる。
【００６１】
フローチャートに合せて、Ｎ＝Ｎ１×Ｎ２×．．．．×Ｎｍと分解できたときを考える。
（１）  Ｎ＝Ｐ×ＱのＱ＝Ｎ１、Ｐ＝Ｎ２×．．．．×Ｎｍ、Ｒ＝１と考えてＸ（Ｎ）を３次元配列ｗ（Ｐ、Ｑ、Ｒ）とみなして処理する。この処理では、長さＱのフーリエ変換をＰ回行い、各フーリエ変換の結果を格納する前に回転因子を掛ける。結果は長さＱに対してビットリバースした順に格納する。
【００６２】
４ステップアルゴリズムの第４ステップでは２次元目の長さＰのデータに関してフーリエ変換を行う。そして、長さＰのフーリエ変換ができた時点で、第２ステップで回転因子を結果に掛ける。しかし、第３ステップの転置はここでは行わない。最後にまとめてビットリバースの形で行うために転置は行わず、ビットリバースがうまく機能するように、基底Ｑの変換結果を長さＱの変換に対するビットリバースを施した順序に変えて格納する。これは、基数Ｑが決まった値であるため、格納場所がわかるので、その場所に格納するようプログラミングする。
【００６３】
第４ステップの長さＰのフーリエ変換は転置しないので１次元目のデータに対して行えばよいことになる。そこでこの長さＰのデータに対するフーリエ変換に対して４ステップアルゴリズムを再度適用して計算を行うことが考えられる。このため、１次元目を２次元に分割し、３次元目が多重度となる配列を考えることができる。この考えで、上のようにＱ、Ｐ、Ｒを更新してＷ（Ｐ，Ｑ，Ｒ）になる構造を考えて計算する。Ｒが前述の多重度ｍｔに当る。
【００６４】
次に、転置を行わずに、Ｎ←Ｐと置き換えた後、Ｑ←Ｎ２、Ｐ←Ｎ３×．．．．×Ｎｍ、Ｒ←Ｎ１として全体をＷ（Ｐ，Ｑ，Ｒ）と考えて各Ｒについて処理する。
処理の内容は最初のフェーズと同じ手順である。Ｎ←Ｐと置き換え後、Ｑ←Ｎ２、Ｐ←Ｎ３×．．．．×Ｎｍ、Ｒ←Ｎ１×Ｎ２として全体をＷ（Ｐ，Ｑ，Ｒ）と考えて各Ｒについて処理する。これを繰り返して、最後の１つ前のフェーズではＮ＝Ｎ（ｍ−１）×Ｎｍ、Ｑ＝Ｎ（ｍ−１）、      Ｐ＝Ｎｍ、Ｒ＝Ｎ１×Ｎ２×．．．×Ｎ（ｍ−２）として各Ｒについて処理する。処理の内容は最初と同じ手順である。
（２）  最後のフェーズでは別に、Ｒ←Ｎ１×Ｎ２×．．．×Ｎ（ｍ−１）としてｗ（Ｎｍ，１，Ｒ）の各Ｒに対して処理する。
（１）の処理、つまり最初のフェーズから最後の１つ前のフェーズまでの処理に関しては、１次元配列Ｘ（Ｎ）を３次元配列Ｗ（Ｐ，Ｑ，Ｒ）と見なしたものに各Ｒに関して、長さＱのフーリエ変換をＰ回行い、各フーリエ変換の結果を格納する前に回転因子を掛ける。結果は長さＱに対してビットリバースした順に格納する。Ｒが１つ増えるごとにｎｂａｓｅにＮｓ（（１）の処理のなかで繰り返しごとに更新されたＮの値）を加えてベースポインタｎｂａｓｅを更新する。
【００６５】
Ｘ（ｎｂａｓｅ＋１：ｎｂａｓｅ；Ｎｓ）は領域としてはｗ（１：Ｐ，１：Ｑ，Ｒ）であり、これをｙ（Ｎｓ／Ｎｉ，Ｎｉ）と見なしている。
（２）  最後は別に、Ｒ←Ｎ１×Ｎ２×．．．×Ｎ（ｍ−１）としてＷ（Ｒ，１，Ｎｍ）もしくはＺ（Ｒ，１，Ｎｍ）の各Ｒに対して基底Ｎｍのフーリエ変換を行う。もし入力が配列Ｗなら結果はＷに格納する。配列Ｚなら配列Ｗと同じ位置に格納する。これで計算は終了する。
【００６６】
以上において本発明の第１の実施形態のフローチャートについての説明を終了するが、本実施形態では図５のステップＳ２６で説明したように、図４の三角関数テーブルから、例えばｔｂ１ｅ１の一番上の複素数型のデータをロードし、２次元配列ｙの同じ行の計算に必要となる回転因子は漸化式を用いて計算し、三角関数テーブルへのアクセスを行う必要がなくなるため、処理の高速化が実現される。
【００６７】
また前述のようにフーリエ変換における基数を２でなく、４、８、１６など大きくすることによってデータのアクセスに対する演算密度を高めることも可能となる。例えば基数を８とすることはフローチャートではＮｉの値を８とすることに相当し、基数を４、または１６とすることも同様である。そして実際には処理の高速のためにハードウェア的に命令のスケジューリングを実行し、またコンパイラがそのスケジューリングを考慮して命令を生成し、計算処理可能なものは、ハードウェアがどんどん計算をダイナミックに進めていくことができる。
【００６８】
図７は、実施形態１における処理の流れを示している。同図においてはデータ（１）から（８）に対して、基数を８としてフーリエ変換を行うための回転因子の取り出しと、漸化式による計算の流れを示している。まず三角関数テーブルから図３の配列の形式では、２行、２列の回転因子ωが取り出される。同時に２つのデータ（１）と（５）の実数部、虚数部がロードされる。図３の２行目ではｉは１に対応し、次にω2、ω3が漸化式で計算されると同時にデータ（２）、および（６）がロードされる。同様の処理が繰り返され、その後フーリエ変換の計算が行われ、その結果に対して対応する回転因子の乗算が行われる。
【００６９】
これによって三角関数テーブルへのアクセスは１回で済み、アクセスによって取り出された回転因子を用いて、データのロードの間に必要な回転因子の漸化式による計算が行われる。これにより三角関数テーブルへのデータの格納量を約１／（Ｑ−１）に減らすことが可能となる。
【００７０】
なお、図７においては、データ長８の１次元配列が２次元配列Ｖ（４，２）と見なされて処理が行われている。すなわちデータ（１）から（４）が１列目に、また（５）から（８）までのデータが２列目に格納され、その２次元配列のデータを１行目から順次取り出すために、まず（１）と（５）のデータが取り出され、次に（２）と（６）のデータが取り出されるという順序で処理が行われる。
【００７１】
続いて本発明の第２の実施形態について説明する。この第２の実施形態は、前述のタイプ３に相当し、行列の転置を最後に一度にまとめて行う方式であり、図８は第２の実施形態におけるフーリエ変換処理の全体フローチャート、図９は各フェーズにおける変換処理の詳細フローチャートである。
【００７２】
図８の第２の実施形態における全体処理フローチャートを第１の実施形態における図２と比較すると、処理の開始からステップＳ１６までの処理は同じであるが、最後のステップＳ１７におけるビットリバースによる並べ替えの代りに、ステップＳ４０で出力領域Ｙ（Ｎ）に対する多次元の転置が行われる点だけが異なっている。この転置では、Ｉ＝１，．．．，Ｎのすべてに関して以下の転置が繰り返し行われる。
【００７３】
Ｉ＝Ｉｍ＋Ｉ（ｍ−１）×Ｎｍ＋．．．＋Ｉ２×（Ｎｍ×Ｎ（ｍ−１）×．．．×Ｎ３）＋Ｉ１×（Ｎｍ×Ｎ（ｍ−１）×．．Ｎ２）＋１  となるＩｍ，．．，Ｉ１（０≦Ｉｉ≦Ｎｉ−１）を決める。
【００７４】
Ｋ＝Ｉ１＋Ｉ２×Ｎ１＋．．．＋Ｉ（ｍ−１）×（Ｎ１×Ｎ２×．．．×Ｎ（ｍ−２））＋Ｉｍ×（Ｎ１×Ｎ２×．．．×Ｎ（ｍ−１））＋１
Ｙ（Ｋ）＝Ｘ（Ｉ）
ここで各Ｉｉは以下のように求めることができる。
１）  Ｊ＝Ｉ−１とする。
２）  ＤＯ  ｔ＝ｍ，１，−１
３）  Ｉｔ＝ｍｏｄ（Ｊ，Ｎｔ）
４）  Ｊ＝Ｉ／Ｎｔ
５）  ＥＮＤＤＯ
Ｋは求められたＩｔ（ｔ＝１，…，ｍ）を使って以下のように求めることができる。
１）  Ｋ＝Ｉ１＋Ｉ，Ｕ＝１
２）  ＤＯ  ｔ＝２，ｍ
３）  ｓ＝ｔ−１
４）  Ｕ＝Ｕ×Ｎｓ
５）  Ｋ＝Ｋ＋Ｉｔ×Ｕ
６）  ＥＮＤＤＯ
図９の各フェーズにおけるフーリエ変換処理の詳細フローチャートを第１の実施形態における図５と比較すると、最後のフェーズ以外のフェーズに対する処理としては、ステップＳ２８に対応するステップＳ４１で漸化式によって計算された回転因子をフーリエ変換の計算結果に乗算する処理において、ステップＳ２９のビットリバースを行うことなく、そのまま格納する点だけが異なっており、また最後のフェーズにおける処理においてもステップＳ３６に対応するステップＳ４２において、フーリエ変換した結果を、ステップＳ３７のようなビットリバースを行うことなくそのまま格納し、ステップＳ３７に対応するステップＳ４３では、インデックスｉｘのインクリメントだけが行われる点が異なっている。
【００７５】
図１０は第３の実施形態における全体処理のフローチャートである。この第３の実施形態は前述のタイプ２に相当し、各フェーズにおけるフーリエ変換処理の出力結果に対する転置を別の作業領域に書き込む形式で実行し、次のフェーズでは出力の領域と入力の領域とを入れ替えて計算を続けるものである。
【００７６】
図１０においてステップＳ１０からＳ１２までの処理は第１の実施形態における図２と同じである。しかしながらステップＳ１３に対応するステップＳ４４でｋの値が１とされると共に、入力と出力の領域が入れ替えられたか否かを示すｅｘｃｈｇの値が０とされ、後述するような３次元の配列におけるＲが１、ＰがＮ／Ｎ１、ＱがＮ１とされた後に、基本的に各フェーズにおける変換処理に移行する。
【００７７】
ステップＳ４４に続いてステップＳ４５で入力と出力の領域が入れ替えられているかを示すｅｘｃｈｇの値が０であるか、すなわち入れ替えられていない状態であるかが判定され、入れ替えられていない場合にはステップＳ４６でその値が１、すなわち入れ替えられた状態に変更された後にステップＳ４７で各フェーズのフーリエ変換処理が行われる。ステップＳ４７では入力をＸ（Ｎ）、出力をＹ（Ｎ）とし、回転因子を格納した三角関数テーブルの対応部分、ならびに３次元配列のＲ、Ｐ、Ｑの値がサブルーチンに渡され、基数Ｑのフーリエ変換が行われる。
【００７８】
ステップＳ４５でｅｘｃｈｇの値が０でない場合、すなわち１の場合にはステップＳ４８でその値が０とされた後、ステップＳ４９で各フェーズのフーリエ変換処理が行われる。ここではステップＳ４７と異なり、入力をＹ（Ｎ）、出力をＸ（Ｎ）として、ステップＳ４７におけると同様に基数Ｑのフーリエ変換が行われる。
【００７９】
続いてステップＳ１５で図２におけると同様にｋの値がｍに達したか否かが判定され、達していない場合にはステップＳ５０でＲとＱの積がＲに、ＮｋがＱに、Ｐ／ＱがＰに代入され、ｋの値がインクリメントされてステップＳ４５以降の処理が繰り返され、ステップＳ１５でｋの値がｍに達したと判定された時点で処理を終了する。
【００８０】
第３の実施形態における各フェーズの処理について説明する。今までと同じように、Ｎ＝Ｎ１×Ｎ２×．．．．×Ｎｍと分解できたときを考える。
４ステップアルゴリズムを繰り返し再帰的に適用し転置も行う。転置を行うためにもう１つの配列領域を用意する。入力側を配列Ｘ（Ｎ）、出力側を配列Ｙ（Ｎ）とする。フェーズの繰り返しごとに入力用の領域と出力用の領域を入れ換えて処理を実行する。最後のフェーズの処理は転置が不要であり、入力用の領域が最初のフェーズで入力として使った領域のときはその上で計算する。最後のフェーズの処理の入力側領域が最初のフェーズで出力として使った領域のときは、結果をもう１つの領域に書き出す。このようにすることで、最初に入力の領域として使った領域にフーリエ変換の結果が格納され、最初に出力として使った領域は作業域にすることができる。
【００８１】
繰り返し処理は以下のようになる。
Ｎ＝Ｐ×ＱのＱ＝Ｎ１、Ｐ＝Ｎ２×．．．．×Ｎｍ、Ｒ＝１と考えてＸ（Ｎ）を３次元配列Ｗ（Ｒ，Ｐ，Ｑ）とみなして処理する。この処理では、長さＱのフーリエ変Ｐ回行い、各フーリエ変換の結果を格納する前に回転因子を掛ける。出力はＹ（Ｎ）をＺ（Ｒ，Ｑ，Ｐ）に格納する。Ｗ（ｒ１，ｐ１，１：Ｑ）をフーリエ変換して結果に回転因子を掛けたものをＺ（ｒ１，１：Ｑ，ｐ１）に格納する。これで転置を行う。この結果に第１の実施形態と同様に、テーブルを引いて漸化式で必要な回転因子を計算して結果に掛ける。第１の実施形態とは異なり、基数Ｑのフーリエ変換結果をビットリバース順に格納することはしない。（忠実に４ステップアルゴリズムを実行しているため。）すべてのｐ１、ｒ１の組に対して長さＱのフーリエ変換を完了したら２番目の基数Ｎ２に対する処理を行う。最初の結果はＺ（Ｒ，Ｑ，Ｐ）に格納されている。４ステップアルゴリズムの第４ステップの長さＰのデータのフーリエ変換を行う。Ｚ（ｒ１，ｑ１，１：Ｐ）について適用するが、ここでＰに対して４ステップアルゴリズムを再帰的に適用するために、Ｎ←Ｐと置き換え後、Ｑ←Ｎ２、Ｐ←Ｎ３×．．．．×Ｎｍ、Ｒ←Ｎ１としてＰ×Ｑに分解する。Ｙ（Ｎ）を入力と考える。Ｙを３次元配列と見なしたＺ（Ｒ，Ｐ，Ｑ）を入力にし、出力領域をＸ（Ｎ）として計算を行う。Ｚ（ｒ１，ｐ１，１：Ｑ）に対して最初と同じように長さＱの変換を行い、回転因子を掛けた後、結果をＷ（ｒ１，１：Ｑ，ｐ１）に格納する。これで転置を行う。これをすべてのｒ１、ｐ１の組に対して計算する。
【００８２】
次にまた入力、出力を入れ換えて、このときの長さＰのフーリエ変換を４ステップアルゴリズムを再帰的に適用して計算する。このためにＮ←Ｐと置き換え後、Ｑ←Ｎ２、Ｐ←Ｎ３×．．．．×Ｎｍ、Ｒ←Ｎ１×Ｎ２として全体をＷ（Ｒ，Ｐ，Ｑ）と考えて基数Ｑの変換を行い、結果に回転因子を掛けてＺ（Ｒ，Ｑ，Ｐ）に格納する。これらを繰り返して、最後の一つ前のフェーズではＮ＝Ｎ（ｍ−１）×Ｎｍ、Ｑ＝（ｍ−１）、Ｐ＝Ｎｍ、Ｒ＝Ｎ１×Ｎ２．．．×Ｎ（ｍ−２）として処理する。処理の内容は最初のフェーズと同じ手順である。
図１１は、第３の実施形態における各フェーズのフーリエ変換処理の詳細フローチャートである。このフローチャートは以上の説明、すなわち２つの配列領域を用意して、フェーズの繰り返し毎に入力用の領域と出力用の領域を入れ替えて処理を実行する場合のフローチャートであり、各ステップ毎の詳細な説明は省略するが、以下に補足的説明を行う。
【００８３】
まず処理の開始に先立って２つの３次元配列領域Ａ（Ｒ，Ｐ，Ｑ）、およびＢ（Ｒ，Ｑ，Ｐ）を受け取り、必要とする三角関数テーブル、すなわち回転因子が格納されたテーブルと、Ｒ、Ｐ、Ｑ、およびｅｘｃｈｇの値を入力として受け取って、処理が開始される。
【００８４】
ステップＳ５６の処理は、ｉ１＝１，．．，Ｒに対してそれぞれ行われる。またステップＳ５９の処理の間に、図５のステップＳ２６におけると同様に、漸化式を用いて回転因子の計算が行われる。
【００８５】
ステップＳ６３における判定は、Ｒが１より大きい時に、Ａ（Ｒ，Ｐ，Ｑ）を１次元目から２次元、３次元とアクセスするように、１次元目の残りＡ（２：Ｒ，Ｐ，Ｑ）を計算するために行われる。またステップＳ７１、およびＳ７２における処理も、ｉ１＝１，．．，Ｒまでの全てに対してそれぞれ行われる。
【００８６】
なおこのフローチャートでは、リットリバースによる並べ替えを行う必要がないため、基数は２の冪の数に限定されることがなく、基数が２の冪でない数、例えば３、５、７，・・・の場合にも応用可能であり、より汎用的な方法である。
【００８７】
以上において、本発明の１次元フーリエ変換プログラムについて詳細に説明したが、このプログラムを部品として用いることにより、多次元のフーリエ変換を行うこともできる。例えば３次元の変換では、２次元目、３次元目を固定して１次元目に対する変換処理を実行する。２次元目に対する処理では、平面上でのアクセスに相当するため、例えばすでに計算されている１次元目の方向と垂直な方向にアクセスすることにより、１次元目の計算結果を利用することも可能となる。
【００８８】
（付記１）１次元フーリエ変換を高速に処理するためのプログラムにおいて、
１次元データのデータ長Ｎをｍ個の因子の積Ｎ1×Ｎ2×．．×Ｎmに分解するデータ長分解ステップと、
該データ長ＮをＰ×Ｑとして、前記ｍ個の因子の積の順序を維持しつつ該ＰとＱを変化させながら、長さＱのＰ本の１次元フーリエ変換結果に対する乗算のために必要とされる回転因子を、該Ｐ本のうちでフーリエ変換結果に対する乗算用の回転因子が必要な１本に対して計算し、テーブルに格納する回転因子格納ステップと、
該計算された回転因子を格納したテーブルを用いてｍ回のフェーズに分けてデータのフーリエ変換を行うフーリエ変換ステップとを計算機に実行させることを特徴とする１次元フーリエ変換プログラム。
【００８９】
（付記２）前記回転因子格納ステップにおいて、
前記ＱをＮ1、ＰをＮ2×Ｎ3×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル１に格納するステップと、
ＱをＮ2、ＰをＮ3×Ｎ4×．．×Ｎmとして、Ｐ−１個の回転因子を計算してテーブル２に格納するステップと、
順次ＱとＰを同様に変化させて同様の処理を行うステップと、
最後にＱをＮm-1、ＰをＮmとしてＰ−１個の回転因子を計算してテーブルｍ−１に格納するステップとを備えることを特徴とする付記１記載の１次元フーリエ変換プログラム。
【００９０】
（付記３）前記フーリエ変換ステップにおける前記ｍ回のフェーズのうちの最後のフェーズを除くｎ＝１回目からｎ＝ｍ−１回目までの各フェーズにおいて、
該ｎ＝ｎ回目のフェーズに１対１に対応するテーブルとしての前記テーブルｎ（＝１，２，．．ｍ−１）の格納内容を用いて、フーリエ変換の対象となるデータへのアクセス期間中に、前記Ｐ本の１次元フーリエ変換結果に乗算すべき回転因子であって、テーブルｎに格納されていない他の回転因子を計算するステップと、
該Ｐ本の１次元フーリエ変換を行うステップと、
該フーリエ変換結果に対して前記テーブルｎに格納されていた回転因子と、計算された前記他の回転因子とを乗算する回転因子乗算のステップとを備えることを特徴とする付記２記載の１次元フーリエ変換プログラム。
【００９１】
（付記４）前記他の回転因子を計算するステップにおいて、前記テーブルｎの格納内容を用いて漸化式によって該他の回転因子を計算することを特徴とする付記３記載の１次元フーリエ変換プログラム。
【００９２】
（付記５）前記回転因子乗算のステップにおいて得られた乗算結果のデータをビットリバースした位置に格納して、前記ｎ回目のフェーズの出力とするステップをさらに備えるとともに、
前記最後のｍ回目のフェーズにおけるフーリエ変換結果のデータをビットリバースした位置に格納して該ｍ回目のフェーズの出力とするステップと、
該ｍ回目のフェーズの出力に対応してビットリバースによる並べ替えを行うステップとをさらに備えることを特徴とする付記３記載の１次元フーリエ変換プログラム。
【００９３】
（付記６）前記ｍ回のフェーズに分けたフーリエ変換ステップの終了後に、該フーリエ変換ステップの結果を格納したｍ次元配列に対する多次元転置を行うステップをさらに備えることを特徴とする付記１記載の１次元フーリエ変換プログラム。
（付記７）  前記フーリエ変換ステップにおいて、
前記ｍ回のフェーズにおける入力データと出力データを格納するための領域１と領域２との２つを設け、これらを３次元配列と見なし、
１回目のフェーズにおける領域１に格納されていた入力データに対するフーリエ変換処理の出力結果を領域２上で３次元配列とみなしてその２次元部分で転置を行った位置に格納し、
２回目のフェーズにおける領域２に格納された入力データに対するフーリエ変換処理の出力結果を領域１上で３次元配列に対する同様の転置を行った位置に格納し、
３回目以降のフェーズにおいて、領域１と領域２とを入力データ用と出力データ用とに交互に入れ替えながら同様の処理を実行することを特徴とする付記１記載の１次元フーリエ変換プログラム。
（付記８）  １次元フーリエ変換を高速に処理する計算装置において、
１次元データのデータ長Ｎをｍ個の因子の積Ｎ1×Ｎ2×．．×Ｎmに分解するデータ長分解手段と、
該データ長ＮをＰ×Ｑとして、前記ｍ個の因子の積の順序を維持しつつ該ＰとＱを変化させながら、長さＱのＰ本の１次元フーリエ変換結果に対する乗算のために必要とされる回転因子を、該Ｐ本のおのおののフーリエ変換結果に対する乗算用の回転因子Ｑ−１個の最初の１個に対して計算し、テーブルに格納する回転因子格納手段と、
該計算された回転因子を格納したテーブルを用いてｍ回のフェーズに分けてデータのフーリエ変換を行うフーリエ変換手段とを備えることを特徴とする１次元フーリエ変換計算装置。
（付記９）  １次元フーリエ変換を高速に計算する方法において、
１次元データのデータ長Ｎをｍ個の因子の積Ｎ1×Ｎ2×．．×Ｎmに分解するデータ長分解過程と、
該データ長ＮをＰ×Ｑとして、前記ｍ個の因子の積の順序を維持しつつ該ＰとＱを変化させながら、長さＱのＰ本の１次元フーリエ変換結果に対する乗算のために必要とされる回転因子を、該Ｐ本のおのおののフーリエ変換結果に対する乗算用の回転因子Ｑ−１個の最初の１個に対して計算し、テーブルに格納する回転因子格納過程と、
該計算された回転因子を格納したテーブルを用いてｍ回のフェーズに分けてデータのフーリエ変換を行うフーリエ変換過程とを備えることを特徴とする１次元フーリエ変換計算方法。
【産業上の利用可能性】
【００９４】
本発明のフーリエ変換方式は、フーリエ変換による解析を必要とする全ての産業、例えば技術分野として波形解析やＣＴスキャンなど、高速フーリエ変換を必要とする技術分野に関連する産業において利用可能である。
【図面の簡単な説明】
【００９５】
【図１】本発明の１次元フーリエ変換プログラムの原理的な機能ブロック図である。
【図２】第１の実施形態における２基底のフーリエ変換の全体処理フローチャートである。
【図３】データのフーリエ変換結果に乗算される回転因子の配列形式の説明図である。
【図４】三角関数テーブルにおける回転因子の格納形式の説明図である。
【図５】図２における各フェーズのフーリエ変換処理の詳細フローチャートである。
【図６】１次元配列を２次元配列と見なすときの配列の形式の説明図である。
【図７】実施形態１におけるデータのローディングと回転因子の計算の流れを示す図である。
【図８】第２の実施形態におけるフーリエ変換処理の全体フローチャートである。
【図９】第２の実施形態における各フェーズのフーリエ変換処理の詳細フローチャートである。
【図１０】第３の実施形態におけるフーリエ変換処理の全体フローチャートである。
【図１１】第３の実施形態における各フェーズのフーリエ変換処理の詳細フローチャートである。
【図１】
2005202911.tif 000008
【図２】
2005202911.tif 000009
【図３】
2005202911.tif 000010
【図４】
2005202911.tif 000011
【図５】
2005202911.tif 000012
【図６】
2005202911.tif 000013
【図７】
2005202911.tif 000014
【図８】
2005202911.tif 000015
【図９】
2005202911.tif 000016
【図１０】
2005202911.tif 000017
【図１１】
2005202911.tif 000018