高速フーリエ変換

高速フーリエ変換（FFT）は、シーケンスの離散フーリエ変換（DFT）またはその逆変換（IDFT）を計算するアルゴリズムです。フーリエ変換は、信号を元の領域（多くの場合、時間または空間）から周波数領域の表現に変換し、またその逆も行います。

DFTは、一連の値を異なる周波数の成分に分解することによって得られます。^{[ 1 ]}この操作は多くの分野で有用ですが、定義から直接計算すると、実用的ではないほど遅くなることがよくあります。FFTは、DFT行列を疎な（ほとんどがゼロの）因子の積に因数分解することによって、このような変換を高速に計算します。[ 2 ]その結果^、^DFT^の計算の複雑さを軽減することができます。 ${\textstyle O(n^{2})}$ これは、DFTの定義を単純に適用した場合に生じるものです。 ${\textstyle O(n\log n)}$ ここで、 $n$ はシーケンスの長さです。速度の差は非常に大きくなる可能性があり、特に $nが$ 数千または数百万になるような長いシーケンスでは顕著です。

FFTはDFT内の項の単なる代数的リファクタリングであるため、すべての項が無限精度で計算されると仮定すれば、DFTとFFTはどちらも数学的に等価で互換性のある演算を実行します。しかし、丸め誤差が存在する場合、多くのFFTアルゴリズムは、DFTの定義を直接的または間接的に評価するよりもはるかに正確です。単純な複素数演算から群論や数論まで、幅広い公開理論に基づいたさまざまなFFTアルゴリズムがあります。最もよく知られているFFTアルゴリズムは $n$ の因数分解に依存しますが、 $O(n\log n)$ 素数を含むすべての $n$ の複雑さ。多くの FFT アルゴリズムは、 ${\textstyle e^{-2\pi i/n}}$ $はn$ 乗の原始根であり、したがって、数論的変換など、任意の有限体上の類似の変換に適用できます。逆 DFT は、指数の符号が逆で $1/$ $n$ の係数を持つ点を除いて DFT と同じであるため、任意の FFT アルゴリズムを容易に適用できます。

高速フーリエ変換は、工学、音楽、科学、数学の分野で広く利用されています。基本的な考え方は 1965 年に普及しましたが、一部のアルゴリズムは 1805 年という早い時期に考案されていました。 ^{[ 1 ]} 1994 年に、ギルバート・ストラングはFFT を「私たちの生涯で最も重要な数値アルゴリズム」と評し、^{[ 3 ]}^{[ 4 ]} IEEE の雑誌Computing in Science & Engineeringでは 20 世紀のトップ 10 アルゴリズムに選ばれました。^{[ 5 ]}

歴史

DFT の高速アルゴリズムの開発は、カール・フリードリヒ・ガウスが 1805 年に小惑星パラスとジュノーの軌道について行った未発表の研究で先駆けて行われた。ガウスはサンプル観測から軌道を補間しようとした。^{[ 6 ]}^{[ 7 ]}彼の方法は、現代の汎用 FFT アルゴリズムの発明者として一般的に認められているジェームズ・クーリーとジョン・テューキーが 1965 年に発表した方法と非常によく似ていた。ガウスの研究はジョセフ・フーリエの 1822 年の成果よりも前であったが、彼はその方法の複雑さを分析せず、最終的には同じ目的を達成するために他の方法を使用した。

1805年から1965年の間に、FFTのいくつかのバージョンが他の著者によって発表されました。 1932年にフランク・イェーツは、アダマール変換とウォルシュ変換の効率的な計算を提供する相互作用アルゴリズムと呼ばれるバージョンを発表しました。^[⁸^]イェーツのアルゴリズムは、統計的設計と実験分析の分野で今でも使用されています。1942年、GCダニエルソンとコーネリアス・ランチョスは、フーリエ変換の計算が大きなボトルネックとなっていた X線結晶学の分野でDFTを計算するために、彼らのバージョンを発表しました。 ^[⁹^]^[¹⁰^]過去の多くの方法は定数係数を減らすことに焦点を当てていましたが、 ${\textstyle O(n^{2})}$ 対称性を利用して計算を行うダニエルソンとランチョスは、周期性を利用して倍増トリックを適用することで「労力を2倍より少しだけ増やすだけで[ $n$ ]を2倍にできる」ことに気づいたが、ガウスと同様に、これが ${\textstyle O(n\log n)}$ スケーリング。^{[ 11 ]} 1958年、IJ Goodは、サイズの離散フーリエ変換に適用できる素因数FFTアルゴリズムを確立した論文を発表した。 ${\textstyle n=n_{1}n_{2}}$ 、どこ $n_{1}$ そして $n_{2}$ 互いに素である。^{[ 12 ]}

ジェームズ・クーリーとジョン・テューキーは、これらの初期のアルゴリズムを独自に再発見し^{[ 7 ]}、 $n$ が合成数で必ずしも2のべき乗ではない場合にも適用可能な、より一般的なFFTを1965年に発表した。 ${\textstyle O(n\log n)}$ スケーリング。^{[ 13 ]}テューキーはこのアイデアを、ケネディ大統領の科学諮問委員会の会議中に思いついた。その会議では、ソ連の核実験を外部から国を囲むようにセンサーを設置することで探知するという話題が議論された。これらのセンサーの出力を分析するには、FFT アルゴリズムが必要になる。リチャード・ガーウィンはテューキーとの議論の中で、このアルゴリズムが国家安全保障の問題だけでなく、彼がすぐに関心を持った問題、つまりヘリウム 3 の 3 次元結晶におけるスピン方向の周期性を決定する問題など、幅広い問題にも一般的に適用できることを認識した。^{[ 14 ]}ガーウィンは、テューキーのアイデアをクーリー (両者ともIBM のワトソン研究所に勤務) に渡して実装してもらった。^{[ 15 ]}クーリーとテューキーは、6 か月という比較的短い期間で論文を発表した。^{[ 16 ]} TukeyはIBMで働いていなかったため、このアイデアの特許性は疑われ、アルゴリズムはパブリックドメインとなり、次の10年間のコンピューティング革命を通じてFFTはデジタル信号処理に不可欠なアルゴリズムの1つとなった。

意味

させて $x_{0},\ldots ,x_{n-1}$ は複素数である。DFTは次の式で定義される。

X_{k}=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi km/n}\qquad k=0,\ldots ,n-1,

どこ $e^{i2\pi /n}$ は1の原始 $n$ 乗根です。

この定義を直接評価するには ${\textstyle O(n^{2})}$ $演算: n 個の$ 出力 $X k$ があり、各出力は $n$ 項の合計を必要とします。FFT は、同じ結果を計算する任意の方法です。 ${\textstyle O(n\log n)}$ 演算。既知のすべてのFFTアルゴリズムは、 ${\textstyle O(n\log n)}$ 演算は、より低い複雑性が不可能であるという既知の証明はない。^{[ 17 ]}

FFT の節約効果を説明するために、複素数の乗算と加算の回数を考えてみましょう。 ${\textstyle n=4096}$ データポイント。DFTの合計を直接評価するには、 ${\textstyle n^{2}}$ 複雑な乗算と ${\textstyle n(n-1)}$ 複雑な付加物のうち、 ${\textstyle O(n)}$ 1を掛けるなどの些細な演算を除外することで演算回数を削減でき、約3000万回の演算で済む。一方、 $nが2のべき乗である基数2の$ クーリー・テューキーアルゴリズムでは、同じ結果をわずかで計算できる。 ${\textstyle (n/2)\log _{2}(n)}$ 複雑な乗算（ここでも、1 による乗算などの簡略化は無視する）と ${\textstyle n\log _{2}(n)}$ 複雑な加算は合計で約70,000回の演算で、直接評価の場合よりも400倍以上少ない。実際には、現代のコンピュータでの実際のパフォーマンスは、通常、算術演算の速度以外の要因によって左右され、分析は複雑な問題である（例えば、Frigo & Johnson、2005を参照）^{[ 18 ]}が、全体的な改善は ${\textstyle O(n^{2})}$ に ${\textstyle O(n\log n)}$ 残骸。

アルゴリズム

クーリー・テューキーアルゴリズム

最も一般的に使用されているFFTは、クーリー・テューキーアルゴリズムです。これは分割統治アルゴリズムであり、任意の合成サイズのDFTを再帰的に分割します。 ${\textstyle n=n_{1}n_{2}}$ の中へ ${\textstyle n_{1}}$ サイズが小さいDFT ${\textstyle n_{2}}$ 、とともに $O(n)$ 複素数の根による乗算は、伝統的にツイドル因子と呼ばれている（ジェントルマンとサンデ、1966年による）。^{[ 19 ]}

この方法（およびFFTの一般的な考え方）は、1965年のクーリーとテューキーの論文^{[ 13 ]}によって普及しましたが、後に^{[ 1 ]} 、この2人の著者が1805年頃にカール・フリードリヒ・ガウスが知っていたアルゴリズムを共同で独自に再発明していたことが判明しました^{[ 20 ]}（そしてその後、限定的な形で何度か再発見されました）。

Cooley–Tukey アルゴリズムの最もよく知られた使用法は、各ステップで変換を $n /2$ サイズの 2 つの部分に分割することであり、そのためサイズは 2 のべき乗に制限されますが、一般的には任意の因数分解を使用できます (Gauss と Cooley/Tukey ^{[ 1 ]}の両方が知っていました)。これらはそれぞれ基数 2および混合基数の場合と呼ばれます(分割基数 FFTなどの他のバリアントにも独自の名前があります)。基本的なアイデアは再帰的ですが、ほとんどの従来の実装では、明示的な再帰を避けるためにアルゴリズムを再構成します。また、Cooley–Tukey アルゴリズムは DFT をより小さな DFT に分割するため、以下で説明するような他の DFT アルゴリズムと任意に組み合わせることができます。

その他のFFTアルゴリズム

のために ${\textstyle n=n_{1}n_{2}}$ 互いに素な ${\textstyle n_{1}}$ そして ${\textstyle n_{2}}$ 、中国剰余定理に基づく素因数分解（グッド・トーマス）アルゴリズム（PFA）を使用して、 DFT を Cooley–Tukey と同様に因数分解できますが、twiddle 因子は使用しません。Rader–Brenner アルゴリズム（1976 年）^[²¹^]は Cooley–Tukey に似た因数分解ですが、twiddle 因子は純虚数であり、乗算回数を減らしますが、加算回数が増え、数値安定性が低下します。これは後に、 Cooley–Tukey の分割基数バリアント（乗算回数は同じですが、加算回数が少なく、精度を犠牲にしない）に置き換えられました。DFT 以外のより小さな演算に DFT を再帰的に因数分解するアルゴリズムには、Bruun アルゴリズムとQFTアルゴリズムがあります。（Rader–Brenner ^[²¹^]および QFT アルゴリズムは 2 のべき乗のサイズに対して提案されたものですが、一般的な合成数 $n$ にも適用できる可能性があります。Bruun のアルゴリズムは任意の偶数の合成数に適用できます。）特にBruun のアルゴリズムは、FFT を多項式の再帰的因数分解として解釈することに基づいています。 $z^{n}-1$ ここでは、実係数多項式に、 $z^{m}-1$ そして $z^{2m}+az^{m}+1$ 。

別の多項式的な観点は、 Winograd FFT アルゴリズム^{[ 22 ]}^{[ 23 ]}によって利用されており、これは因数分解します。 $z^{n}-1$ 円分多項式に変換します。これらの係数はしばしば 1、0 、または -1 であり、したがって乗算はほとんど (あるいは全く) 必要ありません。そのため、ウィノグラードは最小乗算 FFT を取得するために使用でき、小さな因子に対する効率的なアルゴリズムを見つけるためによく使用されます。実際、ウィノグラードは DFT がわずかで計算できることを示しました。 $O(n)$ 無理数の乗算により、2 のべき乗サイズの乗算回数の達成可能な下限が証明されています。ただし、これは多くの加算回数の増加を伴い、ハードウェア乗算器を備えた現代のプロセッサではもはや好ましいトレードオフではありません。特に、Winograd は PFA と、素数サイズの FFT 用の Rader によるアルゴリズムも利用しています。

Rader のアルゴリズムは、乗法群の法 $n の素数に対する$ 生成子の存在を利用して、素数サイズ $n$ の DFT を(合成) サイズ $n$ $- 1$ の巡回畳み込みとして表現し、畳み込み定理を介して通常の FFT のペアで計算できます(ただし、Winograd は他の畳み込み方法を使用しています) ^[²⁴^]。別の素数サイズの FFT は LI Bluestein によるもので、chirp-z アルゴリズムと呼ばれることもあります。これも DFT を畳み込みとして再表現しますが、今回は同じサイズ (たとえば、 2 のべき乗にゼロパディングして基数 2 の Cooley–Tukey FFT で評価できます) で、恒等式^[²⁵^]を介して行われます。

nk=-{\frac {(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}.

六角形高速フーリエ変換（HFFT）は、アレイセットアドレッシング（ASA） ^{[ 26 ]}と呼ばれる六角形グリッドの新しいアドレッシング方式を使用して、六角形サンプリングされたデータの効率的なFFTを計算することを目的としています。

実数データまたは対称データに特化したFFTアルゴリズム

多くのアプリケーションでは、DFTへの入力データは純粋に実数であり、その場合、出力は対称性を満たす。

X_{nk}=X_{k}^{*}

そして、この状況のために効率的なFFTアルゴリズムが設計されている（例えば、Sorensen、1987を参照）。^{[ 27 ]}^{[ 28 ]} 1つのアプローチは、通常のアルゴリズム（例えば、Cooley–Tukey）を取り、計算の冗長な部分を削除することで、時間とメモリを約2倍節約することである。あるいは、偶数長の実数入力DFTを、半分の長さの複素DFT（実部と虚部は元の実数データの偶数/奇数要素）として表現し、その後、 $O(n)$ 後処理操作。

かつては、実数入力のDFTは離散ハートレー変換（DHT）によってより効率的に計算できると考えられていましたが、その後、同じ入力数に対して対応するDHTアルゴリズム（FHT）よりも少ない演算で済む特殊な実数入力DFTアルゴリズム（FFT）が一般的に見つかることが主張されました。^{[ 27 ]}ブルーンのアルゴリズム（上記）は、実数入力を活用するために最初に提案された別の方法ですが、普及しませんでした。

偶数/奇数対称性を持つ実データの場合、FFT にはさらに特殊化があり、その場合、時間とメモリを約 2 倍に短縮でき、DFT は離散コサイン/サイン変換( DCT / DST ) になります。これらのケースでは、FFT アルゴリズムを直接変更する代わりに、実データの FFT と組み合わせることで DCT/DST を計算することもできます。 $O(n)$ 前処理と後処理。

計算上の問題

複雑さと操作回数の上限

コンピュータサイエンスにおける未解決問題

高速フーリエ変換アルゴリズムの複雑さの下限はどれくらいですか？それらはより高速になることができますか？

O(N\log N)

？

コンピュータサイエンスにおける未解決問題

長年にわたり理論的に関心を集めてきた根本的な問題は、高速フーリエ変換の複雑さと正確な演算回数の下限を証明することであり、多くの未解決問題が残っている。DFTが本当に必要とするかどうかは厳密には証明されていない。 ${\textstyle \Omega (n\log n)}$ （つまり、順序） $n\log n$ （またはそれ以上の）演算は、単純な2のべき乗の場合でさえ、より低い複雑さのアルゴリズムは知られていない。特に、このような問題では算術演算の回数が焦点となることが多いが、現代のコンピュータにおける実際のパフォーマンスは、キャッシュやCPUパイプラインの最適化など、他の多くの要因によって決まる。

Shmuel Winograd (1978)の研究に続いて、 ^{[ 22 ]}緊密な $\Theta (n)$ FFTに必要な実数乗算の回数の下限は既知である。 ${\textstyle 4n-2\log _{2}^{2}(n)-2\log _{2}(n)-4}$ 2のべき乗の長さのDFTを計算するには、無理数実数の乗算が必要です。 $n=2^{m}$ さらに、このカウントを実現する明示的なアルゴリズムが知られています (Heideman & Burrus、1986 年; ^{[ 29 ]} Duhamel、1990 年^{[ 30 ]} )。しかし、これらのアルゴリズムは、少なくともハードウェア乗算器を備えた現代のコンピュータでは、実用的であるには加算回数が多すぎます (Duhamel、1990 年; ^{[ 30 ]} Frigo & Johnson、2005 年)。^{[ 18 ]}

必要な追加回数の厳密な下限は知られていないが、アルゴリズムに関するいくつかの制限的な仮定の下で下限が証明されている。1973年、Morgenstern ^{[ 31 ]}は、 $\Omega (n\log n)$ 乗法定数の大きさが制限されているアルゴリズム（ほとんどのFFTアルゴリズムに当てはまるが、すべてではない）の加算回数の下限。Pan （1986）^[³²^]は、 $\Omega (n\log n)$ 下限はFFTアルゴリズムの非同期性の尺度に上限があると仮定しているが、この仮定の一般性は不明である。nが $2$ のべき乗の場合、Papadimitriou（1979）^{[ 33 ]}は、その数が ${\textstyle n\log _{2}n}$ クーリー・テューキーアルゴリズムによって達成される複素数加算は、アルゴリズムのグラフに関する特定の仮定の下で最適である（彼の仮定は、とりわけ、1の根における加法恒等式が利用されないことを意味する）。（この議論は、少なくとも ${\textstyle 2N\log _{2}N}$ 実際の加算が必要ですが、複素数乗算の一部として追加の加算が必要となるため、これは厳密な上限ではありません。）これまでのところ、発表されたFFTアルゴリズムでこれより少ない数を達成したものはありません。 ${\textstyle n\log _{2}n}$ 2のべき乗 $n$ に対する複素数の加算（またはそれに相当するもの）。

3つ目の問題は、実数乗算と加算の総数を最小化することです。これは算術的複雑度と呼ばれることもあります（ただし、この文脈では漸近的な複雑度ではなく、正確な回数が考慮されています）。ここでも、厳密な下限は証明されていません。しかし、1968年以来、2のべき乗 $nに対する最小の公表回数は$ 、分割基数FFTアルゴリズムによって長らく達成されており、このアルゴリズムは、 ${\textstyle 4n\log _{2}(n)-6n+8}$ $n > 1$ の実数乗算と加算。これはさらに簡略化され、 ${\textstyle \sim {\frac {34}{9}}n\log _{2}n}$ (Johnson and Frigo, 2007; ^{[ 17 ]} Lundy and Van Buskirk, 2007 ^{[ 34 ]} )。わずかに大きいカウント (ただし、 $n \geq 256$ の場合は分割基数よりは優れている) は、可能なアルゴリズム (単位法乗法因子を持つ分割基数のようなフローグラフ) に対する追加の制約の下で、総当たりで解ける理論による充足可能性問題に還元することにより、 $n \leq 512$ に対して証明可能に最適であることが示された(Haynal & Haynal, 2011)。^[³⁵^]

FFT アルゴリズムの複雑さを軽減または証明しようとする試みのほとんどは、最も単純な通常の複素データの場合に焦点を当ててきました。しかし、複素データ FFT は、実データ FFT、離散コサイン変換、離散ハートレー変換など、関連する問題のアルゴリズムと非常に密接に関連しているため、これらの 1 つを改善すれば、すぐに他の改善につながります (Duhamel & Vetterli、1990)。^{[ 36 ]}

近似値

上記で説明したすべての FFT アルゴリズムは、DFT を正確に計算します (つまり、浮動小数点誤差を無視します)。ただし、計算量の増加を犠牲にして誤差を任意に小さくできる、DFT を近似的に計算する FFT アルゴリズムもいくつか提案されています。このようなアルゴリズムは、近似誤差を速度の向上やその他の特性と交換します。たとえば、Edelman ら (1999) ^{[ 37 ]}による近似 FFT アルゴリズムは、高速多重極法の助けを借りて並列計算の通信要件を低くします。Guoと Burrus (1996) ^[³⁸^]によるウェーブレットベースの近似 FFTは、正確な FFT で可能なよりも効率的に疎な入力/出力 (時間/周波数局所化) を考慮します。DFT 出力のサブセットを近似的に計算する別のアルゴリズムは、Shentov ら (1995) によるものです。^[³⁹^]エデルマンアルゴリズムは、データの圧縮性（疎性）ではなく、フーリエ行列自体の圧縮性（ランク不足）に基づいているため、疎データと非疎データの両方で同様に機能します。逆に、データが疎である場合、つまり、 $n 個の$ フーリエ係数のうち $k 個$ だけが非ゼロである場合、複雑さは次のように削減できます。 $O(k\log n\log n/k)$ 、これは確率的近似アルゴリズム（最大の $k$ 係数を数桁の小数点以下まで推定する）を使用した大規模な $n$ の例（ $n$ $= 2$ $22$ ）において、 $n / k > 32$ の場合の通常のFFTと比較して実用的な高速化につながることが実証されている。 ^[⁴⁰^]

正確さ

FFTアルゴリズムは有限精度浮動小数点演算を使用すると誤差が生じますが、これらの誤差は通常非常に小さいです。クーリー・テューキーなどのほとんどのFFTアルゴリズムは、アルゴリズムのペアワイズ加算構造の結果として優れた数値特性を持っています。クーリー・テューキーアルゴリズムの相対誤差の上限は ${\textstyle O(\varepsilon \log n)}$ 、に比べ ${\textstyle O(\varepsilon n^{3/2})}$ 単純な DFT 式の場合、^{[ 19 ]} $𝜀$ はマシンの浮動小数点相対精度です。実際には、二乗平均平方根(rms) 誤差はこれらの上限よりもはるかに優れており、わずかです。 ${\textstyle O(\varepsilon {\sqrt {\log n}})}$ クーリー・テューキー法と ${\textstyle O(\varepsilon {\sqrt {n}})}$ ナイーブ DFT の場合 (Schatzman、1996)。^{[ 41 ]}ただし、これらの結果は FFT で使用される回転係数 (つまり三角関数の値) の精度に非常に敏感であり、不正確な三角関数の漸化式を使用する場合など、不注意な FFT 実装では精度がはるかに悪くなることは珍しくありません。Cooley–Tukey 以外の FFT の中には、Rader–Brenner アルゴリズムのように、本質的に安定性が低いものもあります。

固定小数点演算では、FFTアルゴリズムによって蓄積される有限精度誤差はさらに悪化し、rms誤差は次のように増加します。 ${\textstyle O({\sqrt {n}})}$ クーリー・テューキーアルゴリズム（ウェルチ、1969年）の場合。^{[ 42 ]}この精度を達成するには、精度損失を最小限に抑えるためにスケーリングに細心の注意を払う必要があり、固定小数点FFTアルゴリズムでは、クーリー・テューキーのような分解の各中間段階で再スケーリングが行われます。

FFT実装の正しさを検証するために、厳密な保証を得ることができます。 ${\textstyle O(n\log n)}$ ランダム入力に対する変換の線形性、インパルス応答、および時間シフト特性をチェックする簡単な手順によって時間を測定する（Ergün、1995）。^{[ 43 ]}

中間周波数の値は、様々な平均化方法によって得ることができる。

多次元FFT

多次元DFTの記事で定義されているように、多次元DFT

X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }

配列 $x n を$ $d$ 次元のインデックスベクトルに変換します ${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$ $d$ 個の入れ子になった合計によって( ${\textstyle n_{j}=0\ldots N_{j}-1}$ 各 $j$ について、除算は ${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}$ は要素ごとに実行されます。言い換えれば、これは、1次元DFTのdセットのシーケンスを、1次元ずつ（任意の順序で）実行することによって構成されます。

この構成的観点により、最も単純で一般的な多次元DFTアルゴリズム、すなわち行列アルゴリズム（後述の2次元の場合に続く）がすぐに得られます。つまり、 $d$ 個の1次元FFTを（上記のいずれかのアルゴリズムで）連続して実行するだけです。まず $n1次元に沿って変換し、次に$ $n2$ 次元に沿って変換 $し、$ $以下$ 同様に行います（実際には、どのような順序でも構いません）。この方法は、通常の ${\textstyle O(n\log n)}$ 複雑さ、 ${\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}$ は変換されたデータ点の総数です。具体的には、サイズ $n$ $1の変換が$ $n / n 1$ 回など行われるため、FFT シーケンスの複雑さは次のようになります。

{\begin{aligned}&{\frac {n}{n_{1}}}O(n_{1}\log n_{1})+\cdots +{\frac {n}{n_{d}}}O(n_{d}\log n_{d})\\[6pt]={}&O\left(n\left[\log n_{1}+\cdots +\log n_{d}\right]\right)=O(n\log n).\end{aligned}}

2次元では、x _{k は}次のように見なすことができます。 $n_{1}\times n_{2}$ このアルゴリズムは、まずすべての行（または列）のFFTを実行し、結果として得られた変換された行（または列）を別の行列としてグループ化することに対応します。 $n_{1}\times n_{2}$ まず、2番目の行列を作成し、次にこの2番目の行列の各列（または各行）に対してFFTを実行し、同様に結果を最終結果行列にまとめます。

2次元を超える場合、キャッシュの局所性を高めるために次元を再帰的にグループ化することが有利になることが多い。例えば、3次元FFTでは、まず固定されたn1ごとに各平面スライスの2次元FFTを実行し、次にn1方向に沿って1次元FFTを実行する。より一般的には、漸近的に最適なキャッシュ非依存アルゴリズムは、_{次元を再帰的に}₂つのグループに分割することから構成される。 ${\textstyle (n_{1},\ldots ,n_{d/2})}$ そして ${\textstyle (n_{d/2+1},\ldots ,n_{d})}$ 再帰的に変換される（ $dが$ 偶数でない場合は丸め）（FrigoとJohnson、2005を参照）。^{[ 18 ]}それでも、これは行列アルゴリズムの単純な変形であり、最終的には基本ケースとして1次元FFTアルゴリズムのみを必要とし、依然として $O(n\log n)$ 複雑さ。もう一つのバリエーションは、連続する次元の変換の間に行列転置を実行することで、変換が連続したデータに対して行われるようにすることです。これは、非連続データへのアクセスに非常に時間がかかるアウトオブコアおよび分散メモリの状況で特に重要です。

行列アルゴリズムとは異なる多次元FFTアルゴリズムも存在するが、それらはすべて ${\textstyle O(n\log n)}$ 複雑さ。おそらく最も単純な行列非FFTはベクトル基数FFTアルゴリズムであり、これは変換次元をベクトルで割る通常のCooley–Tukeyアルゴリズムの一般化である。 ${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$ 各ステップで基数の数。（これはキャッシュの利点にもなり得る。）ベクトル基数の最も単純なケースは、すべての基数が等しい場合（例えば、ベクトル基数2はすべての次元を2で割り切る）だが、これは必須ではない。一度に1つの非単位基数のみを持つベクトル基数、つまり ${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$ は、本質的には行列アルゴリズムです。その他のより複雑な方法としては、Nussbaumer (1977) ^{[ 44 ]}による多項式変換アルゴリズムがあり、これは変換を畳み込みと多項式の積の観点から捉えます。詳細と参考文献については、Duhamel と Vetterli (1990) ^{[ 36 ]を参照してください。}

その他の一般化

1 ${\textstyle O(n^{5/2}\log n)}$ $n$ $2$ ノードを持つ球面 $S$ $2$ 上の球面調和関数への一般化はMohlenkamp ^[⁴⁵^]によって記述され、アルゴリズムは推測されているが証明されていない。 ${\textstyle O(n^{2}\log ^{2}(n))}$ 複雑さ。Mohlenkamp は libftsh ライブラリにも実装を提供している。^{[ 46 ]}球面調和アルゴリズム ${\textstyle O(n^{2}\log n)}$ 複雑性はロクリンとタイガートによって説明されている。^{[ 47 ]}

高速折り畳みアルゴリズムはFFTに類似していますが、実数または複素数のスカラー値の系列ではなく、ビン化された波形の系列に対して動作する点が異なります。回転（FFTでは複素フェーザによる乗算）は、成分波形の円形シフトです^{[ 48 ]}。

さまざまなグループが、等間隔でないデータ用の FFT アルゴリズムも発表しており、Pottsら(2001) でレビューされている。^{[ 49 ]}このようなアルゴリズムは、厳密には DFT (等間隔データに対してのみ定義されている) を計算するのではなく、その近似値 (非一様離散フーリエ変換、NDFT であり、それ自体も多くの場合近似的に計算される) を計算する。より一般的には、スペクトル推定にはさまざまな他の方法がある。

アプリケーション

FFTは、デジタル録音、サンプリング、加算合成、ピッチ補正ソフトウェアで使用されています。^{[ 50 ]}

FFTの重要性は、周波数領域での作業を時間領域や空間領域での作業と同等に計算可能にしたという事実から生じます。FFTの重要な応用例には、次のものがあります。^{[ 16 ]}^{[ 51 ]}

高速な大整数乗算アルゴリズムと多項式乗算、
トプリッツ行列、巡回行列、その他の構造化行列に対する効率的な行列ベクトル乗算、
フィルタリングアルゴリズム（オーバーラップ追加法およびオーバーラップ保存法を参照）、
離散コサイン変換またはサイン変換のための高速アルゴリズム（例：JPEGおよびMPEG / MP3のエンコードおよびデコードに使用される高速DCT ）、
高速チェビシェフ近似、
差分方程式を解く、
同位体分布の計算。^{[ 52 ]}

電気通信

現代の無線通信規格では、FFTは信号処理の重要な構成要素です。具体的には、4G LTEや5G NRなどの直交周波数分割多重（OFDM）システムで利用されています。^[⁵³^] FFTの効率性により、広帯域信号を複数の近接した直交サブキャリアに分割することで高速データ伝送が可能になります。^[⁵⁴^]この技術は、モバイルデバイスにおける干渉を低減し、消費電力を最適化するために不可欠です。^[⁵⁴^]

代替案

FFTは、周波数特性が時間とともに変化する非定常周波数成分を持つ信号の解析には適さない場合があります。DFTは、信号全体にすべての周波数成分が存在することを前提として、全体的な周波数推定値を提供するため、信号内の短命な特徴や過渡的な特徴を検出することが困難になります。

信号に周波数情報が短時間現れる場合や、一般的に時間とともに変化する場合には、短時間フーリエ変換、離散ウェーブレット変換、離散ヒルベルト変換などの代替手段の方が適している場合があります。^{[ 55 ]}^{[ 56 ]}これらの変換は、周波数と時間ベースの情報の両方を捉えることで、局所的な周波数分析を可能にします。

研究分野

ビッグFFT: 天文学などの分野でビッグデータが爆発的に増加したことで、特定の干渉計算のために512K FFTが必要になった。WMAPやLIGOなどのプロジェクトで収集されたデータには、数百億ポイントのFFTが必要である。このサイズはメインメモリに収まらないため、いわゆるアウトオブコアFFTが活発な研究分野となっている。^[⁵⁷^]
近似FFT: MRIなどのアプリケーションでは、不均一な間隔のグリッド点や周波数に対してDFTを計算する必要があります。多重極ベースのアプローチでは、実行時間が増加する係数で近似値を計算できます。^{[ 58 ]}
グループFFT: FFT は、群表現理論を使用して説明および解釈することもでき、さらなる一般化が可能になります。非巡回群を含む任意のコンパクト群上の関数は、既約行列要素の基底に関して展開されます。この基底変換を実行するための効率的なアルゴリズムを見つけることは、依然として活発な研究分野です。効率的な球面調和展開、特定のマルコフ過程の分析、ロボット工学などの応用があります。 ^{[ 59 ]}
量子FFT: 量子コンピュータ上でのショアの高速整数因数分解アルゴリズムには、バイナリベクトルのDFTを計算するサブルーチンがあります。これは、現在量子FFTとして知られる1ビットまたは2ビットの量子ゲートのシーケンスとして実装されており、実質的にはフーリエ行列の特定の因数分解として実現されたクーリー・テューキーFFTです。これらのアイデアの拡張は現在研究されています。^{[ 60 ]}

言語リファレンス

参考文献

1 2 3 4 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "ガウスと高速フーリエ変換の歴史" (PDF) . IEEE ASSP Magazine . 1 (4): 14– 21. Bibcode : 1984IASSP...1...14H . CiteSeerX 10.1.1.309.181 . doi : 10.1109/MASSP.1984.1162257 . S2CID 10032502 . 2013年3月19日にオリジナルからアーカイブ(PDF)。
↑ Van Loan, Charles (1992).高速フーリエ変換のための計算フレームワーク。SIAM 。
↑ストラング、ギルバート（1994年5月～6月）。「ウェーブレット」。アメリカン・サイエンティスト。82 （ 3）：250–255。Bibcode：1994AmSci..82..250S。JSTOR 29775194。
↑ケント、レイモンド D.、リード、チャールズ (2002)。音声の音響分析（第 2版）。Singular/Thomson Learning。p. 61。ISBN 978-0-7693-0112-9。
↑ Dongarra, Jack; Sullivan, Francis (2000年1月)「トップ10アルゴリズムに関するゲスト編集者による紹介」Computing in Science & Engineering . 2 (1): 22– 23. Bibcode : 2000CSE.....2a..22D . doi : 10.1109/MCISE.2000.814652 . ISSN 1521-9615 .
↑ガウス、カール・フリードリヒ(1866)。「Theoria interpolationis methodo nova tractata」[新しい補間方法に関する理論]。ナクラス（未発表原稿）。 Werke (ラテン語とドイツ語)。 Vol. 3. ゲッティンゲン、ドイツ: Königlichen Gesellschaft der Wissenschaften zu Göttingen。265–303ページ。
1 2 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). "ガウスと高速フーリエ変換の歴史". Archive for History of Exact Sciences . 34 (3): 265–277 . CiteSeerX 10.1.1.309.181 . doi : 10.1007/BF00348431 . ISSN 0003-9519 . S2CID 122847826 .
↑ Yates, Frank (1937). "要因実験の設計と分析".連邦土壌局技術報告第35号. 142 (3585): 90–92 . Bibcode : 1938Natur.142...90F . doi : 10.1038/142090a0 . S2CID 23501205 .
↑ Danielson, Gordon C. ; Lanczos, Cornelius (1942). "Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids". Journal of the Franklin Institute . 233 (4): 365– 380. doi : 10.1016/S0016-0032(42)90767-1 .
↑ランチョス、コーネリアス(1956)。応用解析。プレンティス・ホール。
↑ Cooley, James W. ; Lewis, Peter AW; Welch, Peter D. (1967 年 6 月). "高速フーリエ変換に関する歴史的注釈". IEEE Transactions on Audio and Electroacoustics . 15 (2): 76– 79. Bibcode : 1967ITAuE..15...76C . CiteSeerX 10.1.1.467.7209 . doi : 10.1109/TAU.1967.1161903 . ISSN 0018-9278 .
↑ Good, IJ (1958年7月) 「相互作用アルゴリズムと実用的フーリエ解析」 . Journal of the Royal Statistical Society, Series B (Methodological) . 20 (2): 361– 372. doi : 10.1111/j.2517-6161.1958.tb00300.x .
1 2 Cooley, James W. ; Tukey, John W. (1965). "複素フーリエ級数の機械計算のためのアルゴリズム" . Mathematics of Computation . 19 (90): 297– 301. doi : 10.1090/S0025-5718-1965-0178586-1 . ISSN 0025-5718 .
↑ Cooley, James W. (1987). "高速フーリエ変換アルゴリズムの再発見" (PDF) . Microchimica Acta . Vol. III. ウィーン、オーストリア。pp. 33–45 . 2016年8月20日にオリジナルからアーカイブ(PDF) 。 {{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)
↑ガーウィン、リチャード（1969年6月）。「新しい技術の普及の難しさの一例としての高速フーリエ変換」（PDF）。IEEE Transactions on Audio and Electroacoustics。AU -17（2）：68–72。2006年5月17日のオリジナルからアーカイブ（PDF）。
1 2 Rockmore, Daniel N. (2000 年 1 月). "FFT: 家族全員が使えるアルゴリズム". Computing in Science & Engineering . 2 (1): 60–64 . Bibcode : 2000CSE.....2a..60R . CiteSeerX 10.1.1.17.228 . doi : 10.1109/5992.814659 . ISSN 1521-9615 . S2CID 14978667 .
1 2 Frigo, Matteo; Johnson, Steven G. (2007 年 1 月) [2006-12-19]. "算術演算が少ない修正スプリット基数 FFT". IEEE Transactions on Signal Processing . 55 (1): 111– 119. Bibcode : 2007ITSP...55..111J . CiteSeerX 10.1.1.582.5497 . doi : 10.1109/tsp.2006.882087 . S2CID 14772428 .
1 2 3 Frigo, Matteo; Johnson, Steven G. (2005). "FFTW3 の設計と実装" (PDF) . Proceedings of the IEEE . 93 (2): 216– 231. Bibcode : 2005IEEEP..93..216F . CiteSeerX 10.1.1.66.3097 . doi : 10.1109/jproc.2004.840301 . S2CID 6644892 . 2005-02-07 のオリジナルからアーカイブ(PDF) 。
1 2 Gentleman, W. Morven; Sande, G. (1966). "高速フーリエ変換 ― 楽しみと利益のために" . Proceedings of the AFIPS . 29 : 563– 578. doi : 10.1145/1464291.1464352 . S2CID 207170956 .
↑ガウス、カール・フリードリヒ(1866) [1805]。理論補間は新しい手法です。 Werke (ラテン語とドイツ語)。 Vol. 3. ゲッティンゲン、ドイツ: Königliche Gesellschaft der Wissenschaften。265–327ページ。
1 2 Brenner, Norman M.; Rader, Charles M. (1976). "高速フーリエ変換の新しい原理". IEEE Transactions on Acoustics, Speech, and Signal Processing . 24 (3): 264– 266. Bibcode : 1976ITASS..24..264R . doi : 10.1109/TASSP.1976.1162805 .
1 2 Winograd, Shmuel (1978). "離散フーリエ変換の計算について" . Mathematics of Computation . 32 (141): 175– 199. doi : 10.1090/S0025-5718-1978-0468306-4 . JSTOR 2006266 . PMC 430186 . PMID 16592303 .
↑ Winograd, Shmuel (1979). "離散フーリエ変換の乗法的な複雑さについて" . Advances in Mathematics . 32 (2): 83– 117. doi : 10.1016/0001-8708(79)90037-9 .
↑ Rader, CM (1968). "データサンプル数が素数の場合の離散フーリエ変換" .Proceedings of the IEEE . 56 (6): 1107–1108 . doi : 10.1109/PROC.1968.6477 . ISSN 0018-9219 .
↑ Bluestein, L. (1970 年 12 月). 「離散フーリエ変換の計算に対する線形フィルタリングアプローチ」 . IEEE Transactions on Audio and Electroacoustics . 18 (4): 451– 455. doi : 10.1109/TAU.1970.1162132 . ISSN 0018-9278 .
↑ Wilson, Joseph N. (2011-04-01). "アレイセットアドレッシング: 六角形サンプリング画像の効率的な処理を可能にする技術" . Journal of Electronic Imaging . 20 (2): 023012. doi : 10.1117/1.3589306 . ISSN 1017-9909 .
1 2 Sorensen, Henrik V.; Jones, Douglas L. ; Heideman, Michael T.; Burrus, Charles Sidney (1987). "実数値高速フーリエ変換アルゴリズム". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (6): 849– 863. Bibcode : 1987ITASS..35..849S . CiteSeerX 10.1.1.205.4523 . doi : 10.1109/TASSP.1987.1165220 .
↑ソレンセン、ヘンリック V.、ジョーンズ、ダグラス L.、ハイデマン、マイケル T.、バーラス、チャールズシドニー(1987)。「実数値高速フーリエ変換アルゴリズム」の訂正 ". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (9): 1353. Bibcode : 1987ITASS..35R1353S . doi : 10.1109/TASSP.1987.1165284 .
↑ Heideman, Michael T.; Burrus, Charles Sidney (1986). "長さ2 ^nのDFTを計算するために必要な乗算回数について". IEEE Transactions on Acoustics, Speech, and Signal Processing . 34 (1): 91–95 . Bibcode : 1986ITASS..34...91H . doi : 10.1109/TASSP.1986.1164785 .
1 2 Duhamel, Pierre (1990). "長さ2 ⁿ DFTの乗法複雑性の下限を満たすアルゴリズムと実用アルゴリズムとの関連". IEEE Transactions on Acoustics, Speech, and Signal Processing . 38 (9): 1504– 1511. doi : 10.1109/29.60070 .
↑ Morgenstern, Jacques (1973). "高速フーリエ変換の線形複雑度の下限に関する注記" . Journal of the ACM . 20 (2): 305–306 . doi : 10.1145/321752.321761 . S2CID 2790142 .
↑ Pan, Victor Ya. (1986-01-02). "線形アルゴリズムと双線形アルゴリズムの加算的複雑性と非同期性のトレードオフ" . Information Processing Letters . 22 (1): 11– 14. doi : 10.1016/0020-0190(86)90035-9 . 2017-10-31に取得。
↑ Papadimitriou, Christos H. (1979). "高速フーリエ変換の最適性" . Journal of the ACM . 26 (1): 95– 102. doi : 10.1145/322108.322118 . S2CID 850634 .
↑ Lundy, Thomas J.; Van Buskirk, James (2007). "長さ 2 ^kの実 FFT と畳み込みに対する新しい行列アプローチ". Computing . 80 (1): 23– 45. doi : 10.1007/s00607-007-0222-6 . S2CID 27296044 .
↑ Haynal, Steve; Haynal, Heidi (2011). "FFTアルゴリズムのファミリーの生成と探索" (PDF) . Journal on Satisfiability, Boolean Modeling and Computation . 7 (4): 145– 187. arXiv : 1103.5740 . Bibcode : 2011arXiv1103.5740H . doi : 10.3233/SAT190084 . S2CID 173109 . 2012年4月26日にオリジナル(PDF)からアーカイブ済み。
1 2 Duhamel, Pierre; Vetterli, Martin (1990). "高速フーリエ変換:チュートリアルレビューと最新技術" . Signal Processing . 19 (4): 259– 299. Bibcode : 1990SigPr..19..259D . doi : 10.1016/0165-1684(90)90158-U .
↑エデルマン、アラン、マコーコデール、ピーター、トレド、シヴァン (1999)。「未来の高速フーリエ変換？」(PDF)。SIAM Journal on Scientific Computing。20 (3): 1094– 1114。CiteSeerX 10.1.1.54.9339 。doi : 10.1137/S1064827597316266。 2017年7月5日にオリジナルからアーカイブ(PDF) 。
↑ Guo, Haitao; Burrus, Charles Sidney (1996). "高速近似フーリエ変換によるウェーブレット変換". In Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F. (eds.). Wavelet Applications in Signal and Image Processing IV . Proceedings of SPIE . Vol. 2825. pp. 250–259 . Bibcode : 1996SPIE.2825..250G . CiteSeerX 10.1.1.54.3984 . doi : 10.1117/12.255236 . S2CID 120514955 .
↑シェントフ、オグニャン V.。ミトラ、サンジット K.ホイテ、ウルリッヒ;ホッセン、アブドゥル N. (1995)。「サブバンド DFT。I. 定義、解釈、および拡張」。信号処理。41 (3): 261–277。土井: 10.1016/0165-1684(94)00103-7。
↑ Hassanieh, Haitham; Indyk, Piotr ; Katabi, Dina; Price, Eric (2012年1月)。「スパースフーリエ変換のためのシンプルで実用的なアルゴリズム」(PDF)。ACM -SIAM離散アルゴリズムシンポジウム。2012年3月4日のオリジナルからアーカイブ(PDF) 。（注：sFFTのウェブページも参照してください。）
↑ Schatzman, James C. (1996). "離散フーリエ変換と高速フーリエ変換の精度" . SIAM Journal on Scientific Computing . 17 (5): 1150– 1166. Bibcode : 1996SJSC...17.1150S . CiteSeerX 10.1.1.495.9184 . doi : 10.1137/s1064827593247023 .
↑ Welch, Peter D. (1969). "固定小数点高速フーリエ変換誤差解析". IEEE Transactions on Audio and Electroacoustics . 17 (2): 151–157 . Bibcode : 1969ITAuE..17..151W . doi : 10.1109/TAU.1969.1162035 .
↑ Ergün, Funda (1995). 「多変数線形関数のテスト」.第27回ACM理論計算機科学シンポジウム（STOC '95）論文集. 京都、日本. pp. 407–416 . doi : 10.1145/225058.225167 . ISBN 978-0897917186. S2CID 15512806 . {{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)
↑ Nussbaumer, Henri J. (1977). "多項式変換を用いたデジタルフィルタリング". Electronics Letters . 13 (13): 386–387 . Bibcode : 1977ElL....13..386N . doi : 10.1049/el:19770280 .
↑ Mohlenkamp, Martin J. (1999). "球面調和関数の高速変換" (PDF) . Journal of Fourier Analysis and Applications . 5 ( 2– 3): 159– 184. Bibcode : 1999JFAA....5..159M . CiteSeerX 10.1.1.135.9830 . doi : 10.1007/BF01261607 . S2CID 119482349 . 2017-05-06 のオリジナルからアーカイブ(PDF) . 2018-01-11に取得.
↑ "libftshライブラリ"。2010年6月23日にオリジナルからアーカイブされました。2007年1月9日に取得。
↑ Rokhlin, Vladimir; Tygert, Mark (2006). "球面調和展開のための高速アルゴリズム" (PDF) . SIAM Journal on Scientific Computing . 27 (6): 1903– 1928. Bibcode : 2006SJSC...27.1903R . CiteSeerX 10.1.1.125.7415 . doi : 10.1137/050623073 . 2014-12-17 のオリジナルからアーカイブ(PDF) . 2014-09-18に取得.
↑ Staelin, DH (1969). "周期パルス列検出のための高速折り畳みアルゴリズム" . Proceedings of the IEEE . 57 (4): 724–725 . doi : 10.1109/PROC.1969.7051 . ISSN 0018-9219 .
↑ Potts, Daniel; Steidl, Gabriele ; Tasche, Manfred (2001). "非等間隔データに対する高速フーリエ変換: チュートリアル" (PDF) . In Benedetto, JJ; Ferreira, P. (eds.). Modern Sampling Theory: Mathematics and Applications . Birkhäuser . 2007年9月26日のオリジナルからアーカイブ(PDF) 。
↑バージェス、リチャード・ジェームズ（2014）。音楽制作の歴史。オックスフォード大学出版局。ISBN 978-01993571782019年8月1日に取得。
↑ Chu, Eleanor; George, Alan (1999-11-11) [1999-11-11]. 「第16章」. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms . CRC Press . pp. 153–168 . ISBN 978-1-42004996-1。
↑ Fernandez-de-Cossio Diaz, Jorge; Fernandez-de-Cossio, Jorge (2012-08-08). "フーリエ変換による同位体ピーク中心質量分布の計算". Analytical Chemistry . 84 (16): 7052– 7056. doi : 10.1021/ac301296a . ISSN 0003-2700 . PMID 22873736 .
↑「高速フーリエ変換とその応用」、IEEE Signal Processing Magazine。
1 2 Anwar, K., et al.「LTE規格のためのダブルFFT」IEEE Xplore。
↑ Kijewski-Correa, T.; Kareem, A. (2006 年 10 月). "時間周波数解析におけるヒルベルト変換とウェーブレット変換の有効性" . Journal of Engineering Mechanics . 132 (10): 1037– 1049. doi : 10.1061/(ASCE)0733-9399(2006)132:10(1037) . ISSN 0733-9399 .
↑ Stern, Richard M. (2020). "短時間フーリエ変換に関する注記" (PDF) . 2025年2月8日のオリジナルからアーカイブ(PDF) . 2025年2月8日に取得.
↑ Cormen, Thomas H.; Nicol, David M. (1998). "並列ディスクシステムでのアウトオブコアFFTの実行". Parallel Computing . 24 (1): 5–20 . CiteSeerX 10.1.1.44.8212 . doi : 10.1016/S0167-8191(97)00114-2 . S2CID 14996854 .
↑ Dutt, Alok; Rokhlin, Vladimir (1993-11-01). "非等間隔データに対する高速フーリエ変換". SIAM Journal on Scientific Computing . 14 (6): 1368–1393 . Bibcode : 1993SJSC...14.1368D . doi : 10.1137/0914081 . ISSN 1064-8275 .
↑ Rockmore, Daniel N. (2004). "Recent Progress and Applications in Group FFTs". In Byrnes, Jim (ed.). Computational Noncommutative Algebra and Applications . NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 136. Springer Netherlands. pp. 227–254 . CiteSeerX 10.1.1.324.4700 . doi : 10.1007/1-4020-2307-3_9 . ISBN 978-1-4020-1982-1. S2CID 1412268 .
↑朝香亮、酒井和光、矢萩涼子 (2020). 「高速フーリエ変換のための量子回路」 .量子情報処理. 19 (277): 277. arXiv : 1911.03055 . Bibcode : 2020QuIP...19..277A . doi : 10.1007/s11128-020-02776-5 . S2CID 207847474 .
↑ 「Arm Performance Libraries」 . Arm . 2020. 2020年12月16日取得。
↑ 「C/C++ FFTライブラリの完全なリスト」。VCVコミュニティ。2020年4月5日。 2021年3月3日取得。

さらに読む

ブリガム、エルバート・オラン（1974）。高速フーリエ変換（Nachdr 編）。ニュージャージー州エングルウッド・クリフス：プレンティス・ホール。ISBN 978-0-13-307496-3。
ブリッグス、ウィリアム・L.、ヘンソン、ヴァン・エムデン（1995）。『DFT：離散フーリエ変換の取扱説明書』フィラデルフィア：応用数理学会。ISBN 978-0-89871-342-8。
Chu, Eleanor; George, Alan (2000). Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms . Computational mathematics series. Boca Raton, Fla. London: CRC Press . ISBN 978-0-8493-0270-1。
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「第 30 章: 多項式と FFT」.アルゴリズム入門(第 2 版). Cambridge (Mass.): MIT Press . ISBN 978-0-262-03293-3。
エリオット、ダグラス F.、ラオ、K. ラマモハン(1982)。高速変換：アルゴリズム、解析、応用。ニューヨーク：アカデミックプレス。ISBN 978-0-12-237080-9。
Guo, H.; Sitton, GA; Burrus, CS (1994). 「高速離散フーリエ変換」. ICASSP '94 会議録. IEEE 国際音響・音声・信号処理会議. 第 3 巻. IEEE . pp. III/445–III/448. doi : 10.1109/ICASSP.1994.389994 . ISBN 978-0-7803-1775-8. S2CID 42639206 .
Johnson, Steven G.; Frigo, Matteo (2007 年 1 月). "算術演算回数を減らした修正版分割基数 FFT" (PDF) . IEEE Transactions on Signal Processing . 55 (1): 111– 119. Bibcode : 2007ITSP...55..111J . CiteSeerX 10.1.1.582.5497 . doi : 10.1109/TSP.2006.882087 . ISSN 1053-587X . S2CID 14772428 . 2005 年 5 月 26 日にオリジナルからアーカイブ( PDF) 。
ヌスバウマー、ヘンリ J. (1990)。高速フーリエ変換および畳み込みアルゴリズム。情報科学における Springer シリーズ (2.、修正および更新版)。ベルリンハイデルベルク：シュプリンガー。ISBN 978-3-540-11825-1。
Press, William H. ; Teukolsky, Saul A. ; Vetterling, William T.; Flannery, Brian P. (2007). 「第 12 章高速フーリエ変換」. Numerical Recipes: the art of scientific computing (PDF) . Numerical Recipes (第 3 版). Cambridge: Cambridge University Press . pp. 600–639 . ISBN 978-0-521-88068-8。
Singleton, R. (1969年6月). 「高速フーリエ変換に関する短い参考文献」. IEEE Transactions on Audio and Electroacoustics . 17 (2): 166–169 . Bibcode : 1969ITAuE..17..166S . doi : 10.1109/TAU.1969.1162040 . ISSN 0018-9278 . （注：詳細な参考文献リストが含まれています。）
Prestini, Elena (2004).応用調和解析の進化：現実世界のモデル. 応用および数値調和解析. ボストン; ベルリン: Springer Media . セクション 3.10: ガウスと小惑星: FFT の歴史. ISBN 978-0-8176-4125-2。
ヴァン・ローン、チャールズ・F. (1992).高速フーリエ変換のための計算フレームワーク. 応用数学の最前線. フィラデルフィア:応用数理学会. ISBN 978-0-89871-285-8。
テラス、オードリー（1999）。有限群上のフーリエ解析とその応用。ロンドン数学会学生テキスト。ケンブリッジ（英国）：ケンブリッジ大学出版局。ISBN 978-0-521-45718-7。（第9章およびその他の章）

外部リンク

多項式乗算のための高速フーリエ変換–高速フーリエアルゴリズム
高速フーリエ変換（FFT） – C ++によるFFTプログラミング–クーリー・テューキーアルゴリズム
オンラインドキュメント、リンク、書籍、コード
Sri Welaratna、「FFTアナライザーの30年の歴史（2014年1月12日にWayback Machineにアーカイブ）」、Sound and Vibration（1997年1月号、創刊30周年記念号）–ハードウェアFFTデバイスの歴史的レビュー
ALGLIB FFTコード–デュアル/GPLライセンスの多言語（VBA、C++、Pascalなど）対応数値解析およびデータ処理ライブラリ
SFFT：スパース高速フーリエ変換– MITのスパース（準線形時間）FFTアルゴリズム、sFFT、およびその実装
VB6 FFT –ソースコード付きのVB6最適化ライブラリ実装
インタラクティブFFTチュートリアル–フーリエ変換とFFTメソッドの視覚的インタラクティブ入門
時系列データのフーリエ解析入門–時系列解析におけるフーリエ変換の使い方に関するチュートリアル

[Heideman_Johnson_Burrus_1984-1] 1 2 3 4 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "ガウスと高速フーリエ変換の歴史" (PDF) . IEEE ASSP Magazine . 1 (4): 14– 21. Bibcode : 1984IASSP...1...14H . CiteSeerX 10.1.1.309.181 . doi : 10.1109/MASSP.1984.1162257 . S2CID 10032502 . 2013年3月19日にオリジナルからアーカイブ(PDF)。

[Loan_1992-2] Van Loan, Charles (1992).高速フーリエ変換のための計算フレームワーク。SIAM 。

[Strang_1994-3] ストラング、ギルバート（1994年5月～6月）。「ウェーブレット」。アメリカン・サイエンティスト。82 （ 3）：250–255。Bibcode：1994AmSci..82..250S。JSTOR 29775194。

[4] ケント、レイモンド D.、リード、チャールズ (2002)。音声の音響分析（第 2版）。Singular/Thomson Learning。p. 61。ISBN 978-0-7693-0112-9。

[Dongarra_Sullivan_2000-5] Dongarra, Jack; Sullivan, Francis (2000年1月)「トップ10アルゴリズムに関するゲスト編集者による紹介」Computing in Science & Engineering . 2 (1): 22– 23. Bibcode : 2000CSE.....2a..22D . doi : 10.1109/MCISE.2000.814652 . ISSN 1521-9615 .

[Gauss_1866-6] ガウス、カール・フリードリヒ(1866)。「Theoria interpolationis methodo nova tractata」[新しい補間方法に関する理論]。ナクラス（未発表原稿）。 Werke (ラテン語とドイツ語)。 Vol. 3. ゲッティンゲン、ドイツ: Königlichen Gesellschaft der Wissenschaften zu Göttingen。265–303ページ。

[Heideman_Johnson_Burrus_1985-7] 1 2 Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). "ガウスと高速フーリエ変換の歴史". Archive for History of Exact Sciences . 34 (3): 265–277 . CiteSeerX 10.1.1.309.181 . doi : 10.1007/BF00348431 . ISSN 0003-9519 . S2CID 122847826 .

[Yates_1937-8] Yates, Frank (1937). "要因実験の設計と分析".連邦土壌局技術報告第35号. 142 (3585): 90–92 . Bibcode : 1938Natur.142...90F . doi : 10.1038/142090a0 . S2CID 23501205 .

[Danielson_Lanczos_1942-9] Danielson, Gordon C. ; Lanczos, Cornelius (1942). "Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids". Journal of the Franklin Institute . 233 (4): 365– 380. doi : 10.1016/S0016-0032(42)90767-1 .

[Lanczos_1956-10] ランチョス、コーネリアス(1956)。応用解析。プレンティス・ホール。

[Cooley_Lewis_Welch_1967-11] Cooley, James W. ; Lewis, Peter AW; Welch, Peter D. (1967 年 6 月). "高速フーリエ変換に関する歴史的注釈". IEEE Transactions on Audio and Electroacoustics . 15 (2): 76– 79. Bibcode : 1967ITAuE..15...76C . CiteSeerX 10.1.1.467.7209 . doi : 10.1109/TAU.1967.1161903 . ISSN 0018-9278 .

[12] Good, IJ (1958年7月) 「相互作用アルゴリズムと実用的フーリエ解析」 . Journal of the Royal Statistical Society, Series B (Methodological) . 20 (2): 361– 372. doi : 10.1111/j.2517-6161.1958.tb00300.x .

[Cooley_Tukey_1965-13] 1 2 Cooley, James W. ; Tukey, John W. (1965). "複素フーリエ級数の機械計算のためのアルゴリズム" . Mathematics of Computation . 19 (90): 297– 301. doi : 10.1090/S0025-5718-1965-0178586-1 . ISSN 0025-5718 .

[Cooley_1987-14] Cooley, James W. (1987). "高速フーリエ変換アルゴリズムの再発見" (PDF) . Microchimica Acta . Vol. III. ウィーン、オーストリア。pp. 33–45 . 2016年8月20日にオリジナルからアーカイブ(PDF) 。 {{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

[Garwin_1969-15] ガーウィン、リチャード（1969年6月）。「新しい技術の普及の難しさの一例としての高速フーリエ変換」（PDF）。IEEE Transactions on Audio and Electroacoustics。AU -17（2）：68–72。2006年5月17日のオリジナルからアーカイブ（PDF）。

[Rockmore_2000-16] 1 2 Rockmore, Daniel N. (2000 年 1 月). "FFT: 家族全員が使えるアルゴリズム". Computing in Science & Engineering . 2 (1): 60–64 . Bibcode : 2000CSE.....2a..60R . CiteSeerX 10.1.1.17.228 . doi : 10.1109/5992.814659 . ISSN 1521-9615 . S2CID 14978667 .

[Frigo_Johnson_2007-17] 1 2 Frigo, Matteo; Johnson, Steven G. (2007 年 1 月) [2006-12-19]. "算術演算が少ない修正スプリット基数 FFT". IEEE Transactions on Signal Processing . 55 (1): 111– 119. Bibcode : 2007ITSP...55..111J . CiteSeerX 10.1.1.582.5497 . doi : 10.1109/tsp.2006.882087 . S2CID 14772428 .

[Frigo_Johnson_2005-18] 1 2 3 Frigo, Matteo; Johnson, Steven G. (2005). "FFTW3 の設計と実装" (PDF) . Proceedings of the IEEE . 93 (2): 216– 231. Bibcode : 2005IEEEP..93..216F . CiteSeerX 10.1.1.66.3097 . doi : 10.1109/jproc.2004.840301 . S2CID 6644892 . 2005-02-07 のオリジナルからアーカイブ(PDF) 。

[Gentleman_Sande_1966-19] 1 2 Gentleman, W. Morven; Sande, G. (1966). "高速フーリエ変換 ― 楽しみと利益のために" . Proceedings of the AFIPS . 29 : 563– 578. doi : 10.1145/1464291.1464352 . S2CID 207170956 .

[Gauss_1805-20] ガウス、カール・フリードリヒ(1866) [1805]。理論補間は新しい手法です。 Werke (ラテン語とドイツ語)。 Vol. 3. ゲッティンゲン、ドイツ: Königliche Gesellschaft der Wissenschaften。265–327ページ。

[Brenner_Rader_1976-21] 1 2 Brenner, Norman M.; Rader, Charles M. (1976). "高速フーリエ変換の新しい原理". IEEE Transactions on Acoustics, Speech, and Signal Processing . 24 (3): 264– 266. Bibcode : 1976ITASS..24..264R . doi : 10.1109/TASSP.1976.1162805 .

[Winograd_1978-22] 1 2 Winograd, Shmuel (1978). "離散フーリエ変換の計算について" . Mathematics of Computation . 32 (141): 175– 199. doi : 10.1090/S0025-5718-1978-0468306-4 . JSTOR 2006266 . PMC 430186 . PMID 16592303 .

[Winograd_1979-23] Winograd, Shmuel (1979). "離散フーリエ変換の乗法的な複雑さについて" . Advances in Mathematics . 32 (2): 83– 117. doi : 10.1016/0001-8708(79)90037-9 .

[24] Rader, CM (1968). "データサンプル数が素数の場合の離散フーリエ変換" .Proceedings of the IEEE . 56 (6): 1107–1108 . doi : 10.1109/PROC.1968.6477 . ISSN 0018-9219 .

[25] Bluestein, L. (1970 年 12 月). 「離散フーリエ変換の計算に対する線形フィルタリングアプローチ」 . IEEE Transactions on Audio and Electroacoustics . 18 (4): 451– 455. doi : 10.1109/TAU.1970.1162132 . ISSN 0018-9278 .

[26] Wilson, Joseph N. (2011-04-01). "アレイセットアドレッシング: 六角形サンプリング画像の効率的な処理を可能にする技術" . Journal of Electronic Imaging . 20 (2): 023012. doi : 10.1117/1.3589306 . ISSN 1017-9909 .

[Sorensen_Jones_Heideman_Burrus_1987_1-27] 1 2 Sorensen, Henrik V.; Jones, Douglas L. ; Heideman, Michael T.; Burrus, Charles Sidney (1987). "実数値高速フーリエ変換アルゴリズム". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (6): 849– 863. Bibcode : 1987ITASS..35..849S . CiteSeerX 10.1.1.205.4523 . doi : 10.1109/TASSP.1987.1165220 .

[Sorensen_Jones_Heideman_Burrus_1987_2-28] ソレンセン、ヘンリック V.、ジョーンズ、ダグラス L.、ハイデマン、マイケル T.、バーラス、チャールズシドニー(1987)。「実数値高速フーリエ変換アルゴリズム」の訂正 ". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (9): 1353. Bibcode : 1987ITASS..35R1353S . doi : 10.1109/TASSP.1987.1165284 .

[Heideman_Burrus_1986-29] Heideman, Michael T.; Burrus, Charles Sidney (1986). "長さ2 ^nのDFTを計算するために必要な乗算回数について". IEEE Transactions on Acoustics, Speech, and Signal Processing . 34 (1): 91–95 . Bibcode : 1986ITASS..34...91H . doi : 10.1109/TASSP.1986.1164785 .

[Duhamel_1990-30] 1 2 Duhamel, Pierre (1990). "長さ2 ⁿ DFTの乗法複雑性の下限を満たすアルゴリズムと実用アルゴリズムとの関連". IEEE Transactions on Acoustics, Speech, and Signal Processing . 38 (9): 1504– 1511. doi : 10.1109/29.60070 .

[Morgenstern_1973-31] Morgenstern, Jacques (1973). "高速フーリエ変換の線形複雑度の下限に関する注記" . Journal of the ACM . 20 (2): 305–306 . doi : 10.1145/321752.321761 . S2CID 2790142 .

[Pan_1986-32] Pan, Victor Ya. (1986-01-02). "線形アルゴリズムと双線形アルゴリズムの加算的複雑性と非同期性のトレードオフ" . Information Processing Letters . 22 (1): 11– 14. doi : 10.1016/0020-0190(86)90035-9 . 2017-10-31に取得。

[Papadimitriou_1979-33] Papadimitriou, Christos H. (1979). "高速フーリエ変換の最適性" . Journal of the ACM . 26 (1): 95– 102. doi : 10.1145/322108.322118 . S2CID 850634 .

[Lundy_Buskirk_2007-34] Lundy, Thomas J.; Van Buskirk, James (2007). "長さ 2 ^kの実 FFT と畳み込みに対する新しい行列アプローチ". Computing . 80 (1): 23– 45. doi : 10.1007/s00607-007-0222-6 . S2CID 27296044 .

[Haynal_2011-35] Haynal, Steve; Haynal, Heidi (2011). "FFTアルゴリズムのファミリーの生成と探索" (PDF) . Journal on Satisfiability, Boolean Modeling and Computation . 7 (4): 145– 187. arXiv : 1103.5740 . Bibcode : 2011arXiv1103.5740H . doi : 10.3233/SAT190084 . S2CID 173109 . 2012年4月26日にオリジナル(PDF)からアーカイブ済み。

[Duhamel_Vetterli_1990-36] 1 2 Duhamel, Pierre; Vetterli, Martin (1990). "高速フーリエ変換:チュートリアルレビューと最新技術" . Signal Processing . 19 (4): 259– 299. Bibcode : 1990SigPr..19..259D . doi : 10.1016/0165-1684(90)90158-U .

[Edelman_McCorquodale_Toledo_1999-37] エデルマン、アラン、マコーコデール、ピーター、トレド、シヴァン (1999)。「未来の高速フーリエ変換？」(PDF)。SIAM Journal on Scientific Computing。20 (3): 1094– 1114。CiteSeerX 10.1.1.54.9339 。doi : 10.1137/S1064827597316266。 2017年7月5日にオリジナルからアーカイブ(PDF) 。

[Guo_Burrus_1996-38] Guo, Haitao; Burrus, Charles Sidney (1996). "高速近似フーリエ変換によるウェーブレット変換". In Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F. (eds.). Wavelet Applications in Signal and Image Processing IV . Proceedings of SPIE . Vol. 2825. pp. 250–259 . Bibcode : 1996SPIE.2825..250G . CiteSeerX 10.1.1.54.3984 . doi : 10.1117/12.255236 . S2CID 120514955 .

[Shentov_Mitra_Heute_Hossen_1995-39] シェントフ、オグニャン V.。ミトラ、サンジット K.ホイテ、ウルリッヒ;ホッセン、アブドゥル N. (1995)。「サブバンド DFT。I. 定義、解釈、および拡張」。信号処理。41 (3): 261–277。土井: 10.1016/0165-1684(94)00103-7。

[Hassanieh_2012-40] Hassanieh, Haitham; Indyk, Piotr ; Katabi, Dina; Price, Eric (2012年1月)。「スパースフーリエ変換のためのシンプルで実用的なアルゴリズム」(PDF)。ACM -SIAM離散アルゴリズムシンポジウム。2012年3月4日のオリジナルからアーカイブ(PDF) 。（注：sFFTのウェブページも参照してください。）

[Schatzman_1996-41] Schatzman, James C. (1996). "離散フーリエ変換と高速フーリエ変換の精度" . SIAM Journal on Scientific Computing . 17 (5): 1150– 1166. Bibcode : 1996SJSC...17.1150S . CiteSeerX 10.1.1.495.9184 . doi : 10.1137/s1064827593247023 .

[Welch_1969-42] Welch, Peter D. (1969). "固定小数点高速フーリエ変換誤差解析". IEEE Transactions on Audio and Electroacoustics . 17 (2): 151–157 . Bibcode : 1969ITAuE..17..151W . doi : 10.1109/TAU.1969.1162035 .

[Ergün_1995-43] Ergün, Funda (1995). 「多変数線形関数のテスト」.第27回ACM理論計算機科学シンポジウム（STOC '95）論文集. 京都、日本. pp. 407–416 . doi : 10.1145/225058.225167 . ISBN 978-0897917186. S2CID 15512806 . {{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

[Nussbaumer_1977-44] Nussbaumer, Henri J. (1977). "多項式変換を用いたデジタルフィルタリング". Electronics Letters . 13 (13): 386–387 . Bibcode : 1977ElL....13..386N . doi : 10.1049/el:19770280 .

[Mohlenkamp_1999-45] Mohlenkamp, Martin J. (1999). "球面調和関数の高速変換" (PDF) . Journal of Fourier Analysis and Applications . 5 ( 2– 3): 159– 184. Bibcode : 1999JFAA....5..159M . CiteSeerX 10.1.1.135.9830 . doi : 10.1007/BF01261607 . S2CID 119482349 . 2017-05-06 のオリジナルからアーカイブ(PDF) . 2018-01-11に取得.

[libftsh-46] "libftshライブラリ"。2010年6月23日にオリジナルからアーカイブされました。2007年1月9日に取得。

[Rokhlin_Tygert_2006-47] Rokhlin, Vladimir; Tygert, Mark (2006). "球面調和展開のための高速アルゴリズム" (PDF) . SIAM Journal on Scientific Computing . 27 (6): 1903– 1928. Bibcode : 2006SJSC...27.1903R . CiteSeerX 10.1.1.125.7415 . doi : 10.1137/050623073 . 2014-12-17 のオリジナルからアーカイブ(PDF) . 2014-09-18に取得.

[48] Staelin, DH (1969). "周期パルス列検出のための高速折り畳みアルゴリズム" . Proceedings of the IEEE . 57 (4): 724–725 . doi : 10.1109/PROC.1969.7051 . ISSN 0018-9219 .

[Potts_Steidl_Tasche_2001-49] Potts, Daniel; Steidl, Gabriele ; Tasche, Manfred (2001). "非等間隔データに対する高速フーリエ変換: チュートリアル" (PDF) . In Benedetto, JJ; Ferreira, P. (eds.). Modern Sampling Theory: Mathematics and Applications . Birkhäuser . 2007年9月26日のオリジナルからアーカイブ(PDF) 。

[50] バージェス、リチャード・ジェームズ（2014）。音楽制作の歴史。オックスフォード大学出版局。ISBN 978-01993571782019年8月1日に取得。

[Chu_George_1999-51] Chu, Eleanor; George, Alan (1999-11-11) [1999-11-11]. 「第16章」. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms . CRC Press . pp. 153–168 . ISBN 978-1-42004996-1。

[Fernandez-de-Cossio_2012-52] Fernandez-de-Cossio Diaz, Jorge; Fernandez-de-Cossio, Jorge (2012-08-08). "フーリエ変換による同位体ピーク中心質量分布の計算". Analytical Chemistry . 84 (16): 7052– 7056. doi : 10.1021/ac301296a . ISSN 0003-2700 . PMID 22873736 .

[IEEE_FFT-53] 「高速フーリエ変換とその応用」、IEEE Signal Processing Magazine。

[Anwar_LTE-54] 1 2 Anwar, K., et al.「LTE規格のためのダブルFFT」IEEE Xplore。

[55] Kijewski-Correa, T.; Kareem, A. (2006 年 10 月). "時間周波数解析におけるヒルベルト変換とウェーブレット変換の有効性" . Journal of Engineering Mechanics . 132 (10): 1037– 1049. doi : 10.1061/(ASCE)0733-9399(2006)132:10(1037) . ISSN 0733-9399 .

[56] Stern, Richard M. (2020). "短時間フーリエ変換に関する注記" (PDF) . 2025年2月8日のオリジナルからアーカイブ(PDF) . 2025年2月8日に取得.

[Cormen_Nicol_1998-57] Cormen, Thomas H.; Nicol, David M. (1998). "並列ディスクシステムでのアウトオブコアFFTの実行". Parallel Computing . 24 (1): 5–20 . CiteSeerX 10.1.1.44.8212 . doi : 10.1016/S0167-8191(97)00114-2 . S2CID 14996854 .

[Dutt_Rokhlin_1993-58] Dutt, Alok; Rokhlin, Vladimir (1993-11-01). "非等間隔データに対する高速フーリエ変換". SIAM Journal on Scientific Computing . 14 (6): 1368–1393 . Bibcode : 1993SJSC...14.1368D . doi : 10.1137/0914081 . ISSN 1064-8275 .

[Rockmore_2004-59] Rockmore, Daniel N. (2004). "Recent Progress and Applications in Group FFTs". In Byrnes, Jim (ed.). Computational Noncommutative Algebra and Applications . NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 136. Springer Netherlands. pp. 227–254 . CiteSeerX 10.1.1.324.4700 . doi : 10.1007/1-4020-2307-3_9 . ISBN 978-1-4020-1982-1. S2CID 1412268 .

[60] 朝香亮、酒井和光、矢萩涼子 (2020). 「高速フーリエ変換のための量子回路」 .量子情報処理. 19 (277): 277. arXiv : 1911.03055 . Bibcode : 2020QuIP...19..277A . doi : 10.1007/s11128-020-02776-5 . S2CID 207847474 .

[Arm_Performance_Libraries-61] 「Arm Performance Libraries」 . Arm . 2020. 2020年12月16日取得。

[62] 「C/C++ FFTライブラリの完全なリスト」。VCVコミュニティ。2020年4月5日。 2021年3月3日取得。

[ 1 ]

、

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[

[ 22 ]

[ 23 ]

[

[

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[

[ 33 ]

[ 34 ]

[

[ 36 ]

[ 37 ]

[

[

[

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[

[

[ 55 ]

[ 56 ]

[

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ 62 ]

高速フーリエ変換

歴史

意味

アルゴリズム

クーリー・テューキーアルゴリズム

その他のFFTアルゴリズム

実数データまたは対称データに特化したFFTアルゴリズム

計算上の問題

複雑さと操作回数の上限

近似値

正確さ

多次元FFT

その他の一般化

アプリケーション

電気通信

代替案

研究分野

言語リファレンス

関連項目

参考文献

さらに読む

外部リンク

関連するトピック

シーケンスの

離散フーリエ変換

アルゴリズム

フーリエ変換は