高速フーリエ変換のソースを表示

'''高速フーリエ変換'''（こうそくフーリエへんかん、{{lang-en-short|fast Fourier transform, '''FFT'''}}）は、[[離散フーリエ変換]]（{{lang-en-short|discrete Fourier transform, DFT}}）を計算機上で高速に計算する[[アルゴリズム]]である。高速フーリエ変換の逆変換を逆高速フーリエ変換（{{lang-en-short|inverse fast Fourier transform, IFFT}}）と呼ぶ。

== 概要 ==
複素関数 {{math|''f''(''x'')}} の離散フーリエ変換である複素関数 {{math|''F''(''t'')}} は以下で定義される。
:<math>F(t)= \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N} \right) .</math>
このとき、{{math|1={{mset|''x'' {{=}} 0, 1, 2, ..., ''N'' − 1}}}} を標本点と言う。

これを直接計算したときの[[計算複雑性理論|時間計算量]]は、[[ランダウの記号]]を用いて表現すると {{math|''O''(''N''<sup>2</sup>)}} である。

高速フーリエ変換は、この結果を、次数{{mvar|N}}が2の累乗のときに {{math|''O''(''N'' log ''N'')}} の計算量で得るアルゴリズムである。より一般的には、次数が {{math|1=''N'' = ∏ ''n{{sub|i}}''}} と素因数分解できるとき、{{math|''O''(''N''∑''n''{{sub|''i''}})}} の計算量となる。次数が {{math|2}} の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、{{math|0}} 詰めで次数を調整することもある。

高速フーリエ変換を使って、[[畳み込み]]積分などの計算を高速に求めることができる。これも計算量を {{math|''O''(''N''<sup>2</sup>)}} から {{math|''O''(''N'' log ''N'')}} まで落とせる。

現在は、初期の手法<ref name=Math /> をより高速化したアルゴリズムが使用されている。

===逆変換===
逆変換は正変換と同じと考えて良いが、指数の符号が逆であり、係数 {{math|1/''N''}} が掛かる。

高速フーリエ変換のプログラム中、どの符号が逆転するかを一々分岐させると、分岐の判定に時間がかかり、パフォーマンスが落ちる。一方、正変換のプログラムと、逆変換のプログラムを両方用意しておくことも考えられるが、共通部分が多いため、無駄が多くなる。このため、複素共役を使った次のような方法が考えられる。

[[離散フーリエ変換]]を
:<math>F(t) = \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N}\right)</math>
で定義したとき、逆変換は
:<math> f(x) = \frac{1}{N} \sum_{t=0}^{N-1} F(t) \exp\left(i\frac{2\pi{tx}}{N}\right)
= \frac{1}{N} \overline{ \sum_{t=0}^{N-1} \overline{F(t)} \exp\left(-i\frac{2 \pi t x}{N} \right)}</math>
となる。

このため、{{math|''F''(''t'')}} の離散フーリエ逆変換を求めるには、
:(1) [[複素共役]]を取り、{{math|{{overline|''F''(''t'')}}}} を求める、
:(2) {{math|{{overline|''F''(''t'')}}}} の正変換の離散フーリエ変換を高速フーリエ変換で行う、
:(3) その結果の複素共役を取り、{{mvar|N}} で割る
とすれば良く、正変換の高速フーリエ変換のプログラムがあれば、逆変換は容易に作ることができる。

== アルゴリズム ==
=== クーリー–テューキー型FFTアルゴリズム ===
{{main|{{仮リンク|クーリー–テューキー型FFTアルゴリズム|en|Cooley–Tukey FFT algorithm}}}}
クーリー–テューキー型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。

[[分割統治法]]を使ったアルゴリズムで、{{math|1=''N'' = ''N''{{sub|1}} ''N''{{sub|2}}}} のサイズの変換を、より小さいサイズである {{math|''N''{{sub|1}}}},  {{math|''N''{{sub|2}}}} のサイズの変換に分割していくことで高速化を図っている。

最もよく知られたクーリー–テューキー型アルゴリズムは、ステップごとに変換のサイズをサイズ {{math|''N''/2}} の2つの変換に分割するので、{{math|2}} の累乗次数に限定される。しかし、一般的には次数は {{math|2}} の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。

伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。

クーリー–テューキー型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、{{math|''N'' &le; 8}} あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。

==== 原理の簡単な説明 ====
[[File:FFT visual 12.jpg|thumb|upright=1.5|データ数1２の離散フーリエ変換の模式図。時計を模した図形は1の12乗根の一つを表している。時計の針の向きと色は1の12乗根の偏角を表す。この図で表される行列をデータ列にかけることで離散フーリエ変換が得られる。上図で表されるような列の並べ替えを行うことで、元の行列のパターンはデータ数6の離散フーリエ変換のパターンに分解できる。この繰り返しにより最終的にはデータ数３のフーリエ変換に帰着される。]]
[[File:FFT visual 100.jpg|thumb|upright=1.5|データ数100の離散フーリエ変換の模式図。色は1の100乗根の偏角を表す。バタフライ演算により元の行列のパターンは最終的にデータ数5の離散フーリエ変換のパターンに分解される。]]
[[Image:FFT Butterfly radix8.svg|right|thumb|200px|FFTのバタフライ演算]]
離散フーリエ係数は、[[1の冪根|{{math|1}}の原始 {{mvar|N}} 乗根]]の1つ {{math|1=''W{{sub|N}}'' = ''e''{{sup|−2''&pi;i''/''N''}}}} を使うと、次のように表せる。
:<math>F(t) = \sum_{x=0}^{N-1} f(x) W_N^{tx} .</math>
例えば、{{math|1=''N'' = 4}} のとき、<math>F(t)=X_t</math>、<math>f(k
) = x_k</math>とすれば、離散フーリエ係数は[[行列 (数学)|行列]]を用いて表現すると（{{math|1=''W'' = ''W''{{sub|4}}}} と略記）
:<math>
\begin{bmatrix}X_0\\X_1\\X_2\\X_3\end{bmatrix}=
\begin{bmatrix}
W^0&W^0&W^0&W^0\\
W^0&W^1&W^2&W^3\\
W^0&W^2&W^4&W^6\\
W^0&W^3&W^6&W^9
\end{bmatrix}
\begin{bmatrix}x_0\\x_1\\x_2\\x_3\end{bmatrix}
</math>
となる。入力列 {{mvar|x{{sub|k}}}} を添字の偶奇で分けて、以下のように変形する。
:<math>
\begin{align}
\begin{bmatrix}X_0\\X_1\\X_2\\X_3\end{bmatrix}
& =
\begin{bmatrix}
W^0&W^0&W^0&W^0\\
W^0&W^2&W^1&W^3\\
W^0&W^4&W^2&W^6\\
W^0&W^6&W^3&W^9
\end{bmatrix}
\begin{bmatrix}x_0\\x_2\\x_1\\x_3\end{bmatrix} \\
& =
\begin{bmatrix}
W^0&W^0&W^0W^0&W^0W^0\\
W^0&W^2&W^1W^0&W^1W^2\\
W^0&W^0&W^2W^0&W^2W^0\\
W^0&W^2&W^3W^0&W^3W^2
\end{bmatrix}
\begin{bmatrix}x_0\\x_2\\x_1\\x_3\end{bmatrix}
\end{align}
</math>
<!--:<math>
\begin{bmatrix}X_0\\X_1\\X_2\\X_3\end{bmatrix}=
\begin{bmatrix}
W^0&W^0&W^0&W^0\\
W^0&W^2&W^1&W^3\\
W^0&W^4&W^2&W^6\\
W^0&W^6&W^3&W^9
\end{bmatrix}
\begin{bmatrix}x_0\\x_2\\x_1\\x_3\end{bmatrix}=
\begin{bmatrix}
W^0&W^0&W^0W^0&W^0W^0\\
W^0&W^2&W^1W^0&W^1W^2\\
W^0&W^0&W^2W^0&W^2W^0\\
W^0&W^2&W^3W^0&W^3W^2
\end{bmatrix}
\begin{bmatrix}x_0\\x_2\\x_1\\x_3\end{bmatrix}
</math>.-->

(<math>\because W^{k+N}=W^k</math>)

すると、サイズ {{math|2}} のFFTの演算結果を用いて表現でき、サイズの分割ができる。
:<math>\begin{bmatrix}X_0\\X_1\\X_2\\X_3\end{bmatrix}=
\begin{bmatrix}
1&0&W^0&0\\
0&1&0&W^1\\
1&0&W^2&0\\
0&1&0&W^3
\end{bmatrix}\,
\begin{bmatrix}
W_2^0&W_2^0&0&0\\
W_2^0&W_2^1&0&0\\
0&0&W_2^0&W_2^0\\
0&0&W_2^0&W_2^1
\end{bmatrix}\,
\begin{bmatrix}
x_0\\
x_2\\
x_1\\
x_3
\end{bmatrix}
</math>
また、この分割手順を図にすると蝶のような図になることから、'''バタフライ演算'''とも呼ばれる。

バタフライ演算は、計算機上では[[ビット演算#NOT|ビット反転]]で実現される。[[デジタルシグナルプロセッサ|DSP]]の中には、このバタフライ演算のプログラムを容易にするため、ビット反転[[アドレッシングモード|アドレッシング]]を備えているものがある。

==== 原理の説明 ====
FFTの原理は、{{math|1=''N'' = ''PQ''}} として、{{mvar|N}} 次離散フーリエ変換を、{{mvar|P}} 次離散フーリエ変換と{{mvar|Q}} 次離散フーリエ変換に分解することである<ref>{{Cite journal|和書|author=高橋秀俊 |date=1973-08 |url=http://id.nii.ac.jp/1001/00008002/ |title=高速フーリエ変換（FFT）について |journal=情報処理 |publisher=情報処理学会 |volume=14 |issue=8 |CRID=1050564287833399424}}</ref>。

{{mvar|N}} 次離散フーリエ変換：
:<math>F(n) = \sum_{k=0}^{N-1}f(k)\exp\left(-2\pi i\frac{nk}{N}\right)</math>
を、{{math|1=''n'' = 0, 1, ..., ''N'' − 1}} について計算することを考える。{{mvar|''n''}}, {{mvar|''k''}} を次のように書き換える。ただし {{math|0 &le; ''n''  &le; ''N'' − 1}} また {{math|0 &le; ''k'' &le; ''N'' − 1}} である。
:<math>\begin{align}
n &= sQ+r \qquad 0\le s\le P-1,\,0\le r\le Q-1 \\
k &= qP+p \qquad 0\le p\le P-1,\;0\le q\le Q-1
\end{align}</math>
すると
:<math>\begin{align}
F(n) &= F(sQ+r) = \sum_{p=0}^{P-1}\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\frac{(qP+p)(sQ+r)}{PQ}\right) \\
&= \sum_{p=0}^{P-1}\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\left(\frac{rq}{Q}+\frac{sp}{P}+\frac{pr}{PQ}\right)\right) \\
&= \sum_{p=0}^{P-1}\left[\exp\left(-2\pi i\left(\frac{sp}{P}+\frac{pr}{PQ}\right)\right)\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\frac{rq}{Q}\right)\right]\end{align}</math>

ここで、
:<math>f_1(p,r) = \exp\left(-2\pi i\frac{pr}{PQ}\right)\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\frac{rq}{Q}\right)</math>
と置くと、
:<math>F(n) = F(sQ+r) = \sum_{p=0}^{P-1}\exp\left(-2\pi i\frac{sp}{P}\right)f_1(p,r)</math>
となる。即ち、{{math|1=''F''(''n'') = ''F''(''sQ'' + ''r'')}} の計算は、次の2ステップになる。

;ステップ1: {{math|1=''p'' = 0, 1, ..., ''P'' − 1}} と {{math|1=''r'' = 0, 1, ..., ''Q'' − 1}} について
::<math>f_1(p,r)= \exp\left(-2\pi i\frac{pr}{PQ}\right)\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\frac{rq}{Q}\right)</math>
:を計算する。これは、{{mvar|Q}}次の離散フーリエ変換
::<math>\sum_{q=0}^{Q-1}f(qP+p)\exp\left(-2\pi i\frac{rq}{Q}\right)</math>
:の実行と、回転因子 {{math|exp(−2''&pi;ipr''/''PQ'')}} の掛け算を、全ての {{mvar|p}}, {{mvar|r}} の組（{{math|1=''PQ'' = ''N''}} 通り）に対して行うことと見ることができる。

;ステップ2: {{math|1=''s'' = 0, 1, ..., ''P'' − 1}} と {{math|1=''r'' = 0, 1, ..., ''Q'' − 1}} について
::<math>F(sQ+r) = \sum_{p=0}^{P-1}\exp\left(-2\pi i\frac{sp}{P}\right)f_1(p,r)</math>
:を計算する。ここで、右辺は {{mvar|r}} を固定すれば、{{mvar|P}} 次の離散フーリエ変換である。

ステップ1、2は、{{math|1=''N'' = ''PQ''}} 次の離散フーリエ変換を、{{mvar|Q}} 次の離散フーリエ変換と回転因子の掛け算の実行により、{{mvar|Q}} 組 ({{math|1=''r'' = 0, 1, ..., ''Q'' − 1}}) の {{mvar|P}} 次離散フーリエ変換に分解したと見ることができる。
:{{math|1=''N''}} '''次離散フーリエ変換の問題'''　⇒　{{mvar|Q}} '''次離散フーリエ変換の実施'''　⇒　{{math|1=''N''/''Q''}} '''次離散フーリエ変換の問題に帰着'''

特に、{{mvar|Q}} が{{math|2}}または{{math|4}}の場合は、{{mvar|Q}}次離散フーリエ変換は非常に簡単な計算になる。
*{{math|1=''Q'' = 2}} の場合は、{{math|exp(−2''&pi;irq''/''Q'')}} は {{math|1}} か {{math|−1}} なので、{{mvar|Q}} 次離散フーリエ変換は符号の逆転と足し算だけで計算できる。
*{{math|1=''Q'' = 4}} の場合は、{{math|exp(−2''&pi;irq''/''Q'')}} は {{math|1}}, {{math|−1}}, {{mvar|i}}, {{math|−''i''}} のいずれかなので、{{mvar|Q}} 次離散フーリエ変換の計算は、符号の逆転、実部虚部の交換と足し算だけで計算できる。
{{math|1=''Q'' = 2}} か{{math|1=''Q'' = 4}} の場合のこの部分の{{mvar|Q}}次離散フーリエ変換のことを、'''バタフライ演算'''と言う。

また､{{math|1=''N'' = ''Q<sup>k</sup>''}} ({{math|1=''P'' = ''Q''<sup>''k'' − 1</sup>}}) の場合には、上を繰り返すことができ、{{mvar|Q}} 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げられ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、{{math|''F''(''t'')}}を求めることができる。<br/>
このため、{{math|2}}の累乗あるいは{{math|4}}の累乗次の離散フーリエ変換は、両方の性質を利用でき、非常に簡単に計算できる。

また、{{math|1=''Q'' = 2}}か{{math|1=''Q'' = 4}}の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。{{math|1=''N'' = ''Q{{sup|k}}''}}の次数を1落とすために{{mvar|N}}回の「掛け算」が必要であり、次数を{{mvar|''k''}}から{{math|0}}に落とすにはそれを{{mvar|''k''}}回繰り返す必要があるため、「掛け算」の数は {{math|1=''Nk'' = ''N'' log{{sub|''Q''}} ''N''}} となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は {{math|''O''(''N'' log ''N'')}} になる」ことの根拠になっている。

==== ビットの反転 ====
上記の説明で、<math>N=Q^k (P=Q^{k-1})</math> の場合、{{math|1=''N'' = ''Q{{sup|k}}''}} 個のデータ<math>f(qQ^{k-1}+p)</math>から、{{math|1=''N'' = ''Q{{sup|k}}''}} 個の計算結果
:<math>f_1(p,r)= \exp\left(-2\pi i\frac{pr}{Q^k}\right)\sum_{q=0}^{Q-1}f(qQ^{k-1}+p)\exp\left(-2\pi i\frac{rq}{Q}\right)</math>
を計算する場合に、メモリの節約のため、{{math|0 &le; ''q'' &le; ''Q'' − 1}} と {{math|0 &le; ''r'' &le; ''Q'' − 1}} を利用し、計算結果 <math>f_1(p,r)</math> を元データ<math>f(rQ^{k-1}+p)</math> のあった場所に格納することが多い。これが次の次数 {{math| ''Q''{{sup|''k'' − 1}}}} でも繰り返されるため、<math>p=q_2Q^{k-2}+p_2</math>とすると、次の次数の計算結果<math>f_2(p_2,q_2,q)</math>は<math>f(qQ^{k-1}+q_2Q^{k-2}+p_2)</math>のあった場所に格納される。繰り返せば、<math>t=q_1Q^{k-1}+q_2Q^{k-2}+\cdots+q_k</math>とすると、計算結果<math>f_k(p_k,q_k,q_{k-1},\dots,q_2,q_1)</math>は<math>f(q_1Q^{k-1}+q_2Q^{k-2}+\cdots+q_{k-1}Q+p_k)</math>のあった場所に格納される。

一方、
:<math>F(sQ+r)=\sum_{p=0}^{Q^{k-1}-1}\exp\left(-2\pi i\frac{sp}{Q^{k-1}}\right)f_1(p,r)</math>
を、{{mvar|r}} を固定し {{mvar|s}} を変数とした {{math| ''Q''{{sup|''k'' − 1}}}} 次離散フーリエ変換と見なして、<math>s=s_2Q+r_2</math>とすると、
:<math>F(s_2Q^2+r_2Q+r) = \sum_{p_2=0}^{Q^{k-2}-1}\exp\left(-2\pi i\frac{s_2p_2}{Q^{k-2}}\right)f_2(p_2,r_2,r)</math>
となる。繰り替えせば、
:<math>F(s_kQ^k+r_kQ^{k-1}+\cdots+r_2Q+r_1)
 = \sum_{p_k=0}^{Q^{k-k}-1}\exp\left(-2\pi i\frac{s_kp_k}{Q^{k-k}}\right)f_k(p_k,r_k,r_{k-1},\dots,r_2,r_1)</math>
となるが、左辺について
:<math>s_kQ^k+r_kQ^{k-1}+\cdots+r_2Q+r_1<Q^k</math>
より {{math|1=''s{{sub|k}}'' = 0}}, また右辺について
:<math>Q^{k-k}-1=0</math>
より {{math|1=''p{{sub|k}}'' = 0}}。このため、
:<math>F(r_kQ^{k-1}+\cdots+r_2Q+r_1)=f_k(0,r_k,r_{k-1},\dots,r_2,r_1).</math>
これは <math>f(r_1Q^{k-1}+r_2Q^{k-2}+\cdots+r_{k-1}Q+r_k)</math> のあった場所に格納されている。

このように、求める解 <math>F(r_kQ^{k-1}+\cdots+r_2Q+r_1)</math> が <math>f(r_1Q^{k-1}+r_2Q^{k-2}+\cdots+r_{k-1}Q+r_k)</math> のあった場所に格納されていることを、'''ビット反転'''と言う。これは、{{mvar|Q}} 進法で表示した場合、<math>r_kQ^{k-1}+\cdots+r_2Q+r_1</math> は <math>(r_kr_{k-1}\dots r_2r_1)_Q</math>となるのに対し、<math>r_1Q^{k-1}+r_2Q^{k-2}+\cdots+r_{k-1}+r_k</math>は逆から読んだ<math>(r_1r_2\dots r_{k-1}r_k)_Q</math>となるためである。

==== プログラムの例 ====
以下は、高速フーリエ変換のプログラムを {{math|1=''Q'' = 4}} の場合に[[Microsoft Visual Basic]]の文法を用いて書いた例である。

<syntaxhighlight lang="vb">
Const pi As Double = 3.14159265358979   '円周率
Dim Ndeg As Long '4^deg
Dim Pdeg As Long '4^(deg-i)
Dim CR() As Double   '入力実数部
Dim CI() As Double   '入力虚数部
Dim FR() As Double   '出力実数部
Dim FI() As Double   '出力虚数部

deg=5 '任意に設定。5ならN=4^5=1024で計算
Ndeg=4^deg
ReDim CR(Ndeg - 1) As Double '入力実数部
ReDim CI(Ndeg - 1) As Double '入力虚数部
ReDim FR(Ndeg - 1) As Double '出力実数部
ReDim FI(Ndeg - 1) As Double '出力虚数部
'ここで、変換される関数の実部をCR(0)からCR(Ndeg-1)に、虚部をCI(0)からCI(Ndeg-1)に入力しておくこと

'フーリエ変換
For i = 1 To deg
 Pdeg = 4 ^ (deg - i)
 For j0 = 0 To 4 ^ (i - 1) - 1
  For j1 = 0 To Pdeg - 1
   j = j1 + j0 * Pdeg * 4
   'バタフライ演算(Q=4)
   w1 = CR(j) + CR(j + Pdeg) + CR(j + 2 * Pdeg) + CR(j + 3 * Pdeg)
   w2 = CI(j) + CI(j + Pdeg) + CI(j + 2 * Pdeg) + CI(j + 3 * Pdeg)
   w3 = CR(j) + CI(j + Pdeg) - CR(j + 2 * Pdeg) - CI(j + 3 * Pdeg)
   w4 = CI(j) - CR(j + Pdeg) - CI(j + 2 * Pdeg) + CR(j + 3 * Pdeg)
   w5 = CR(j) - CR(j + Pdeg) + CR(j + 2 * Pdeg) - CR(j + 3 * Pdeg)
   w6 = CI(j) - CI(j + Pdeg) + CI(j + 2 * Pdeg) - CI(j + 3 * Pdeg)
   w7 = CR(j) - CI(j + Pdeg) - CR(j + 2 * Pdeg) + CI(j + 3 * Pdeg)
   w8 = CI(j) + CR(j + Pdeg) - CI(j + 2 * Pdeg) - CR(j + 3 * Pdeg)
   CR(j) = w1
   CI(j) = w2
   CR(j + Pdeg) = w3
   CI(j + Pdeg) = w4
   CR(j + 2 * Pdeg) = w5
   CI(j + 2 * Pdeg) = w6
   CR(j + 3 * Pdeg) = w7
   CI(j + 3 * Pdeg) = w8
   '回転因子
   For k = 0 To 3
    w1 = Cos(2 * pi * j * k / Pdeg / 4)
    w2 = -Sin(2 * pi * j * k / Pdeg / 4)
    w3 = CR(j + k * Pdeg) * w1 - CI(j + k * Pdeg) * w2
    w4 = CR(j + k * Pdeg) * w2 + CI(j + k * Pdeg) * w1
    CR(j + k * Pdeg) = w3
    CI(j + k * Pdeg) = w4
   Next k
  Next j1
 Next j0
Next i
'ビット反転
For i = 0 To Ndeg - 1
 k = i
 k1 = 0
 For j = 1 To deg
  k1 = k1 + (k - Int(k / 4) * 4) * 4 ^ (deg - j)
  k = Int(k / 4)
 Next j
 FR(i) = CR(k1)
 FI(i)=CI(k1)
Next i
</syntaxhighlight>

この例では、最深部 (<code lang="vb">For k</code>、<code lang="vb">Next k</code> の間の部分)の繰り返し回数が <code lang="vb">Ndeg</code> {{math|log{{sub|4}}}} <code lang="vb">Ndeg</code> となっている。

=== その他のアルゴリズム ===
* {{仮リンク|Prime Factor Algorithm|en|Prime-factor FFT algorithm}} (PFA)
* {{仮リンク|Bruun's FFT algorithm|en|Bruun's FFT algorithm}}
* [[レーダーのFFTアルゴリズム]]
* {{仮リンク|Bluestein's FFT algorithm|en|Bluestein's FFT algorithm}} (see "Chirp Z-transform")　任意長のデータ列に対する変換が高速に可能である。
* {{仮リンク|オドリツコ・ショーンハーゲ法|en|Odlyzko–Schönhage algorithm}} - {{仮リンク|アンドリュー・オドリツコ|en|Andrew Odlyzko}}、{{仮リンク|アーノルド・ショーンハーゲ|en|Arnold Schönhage}}。
* {{仮リンク|Fast Walsh–Hadamard transform|en|Fast Walsh–Hadamard transform}}
{{節スタブ}}

== 実数および対称的な入力への最適化 ==
多くの応用において、FFTに対する入力データは実数の列(実入力)であり、このとき変換された出力の列は次の対称性を満たす（{{math|{{overline|&nbsp;&nbsp;&nbsp;}}}} は複素共役）：
:<math>F(-t) = \overline{F(t)} .</math>
そこで、多くの効率的なFFTアルゴリズム<ref>例えば、（{{Cite journal |author=Sorensen, H V and Jones, D and Heideman, Michael and Burrus, C |year=1987 |url=https://doi.org/10.1109/TASSP.1987.1165220 |title=Real-valued fast Fourier transform algorithms |journal=IEEE Transactions on acoustics, speech, and signal processing |volume=35 |issue=6 |pages=849-863 |publisher=IEEE |doi=10.1109/TASSP.1987.1165220
}}）</ref> は入力データが実数であることを前提に設計されている。

入力データが実数の場合の効率化の手段としては、次のようなものがある。
*クーリー-テューキー型アルゴリズムなど典型的なアルゴリズムを利用して、時間とメモリーの両方のコストを低減する。
*入力データが偶数の長さのフーリエ係数はその半分の長さの複素フーリエ係数として表現できる（出力の実数/虚数成分は、それぞれ入力の偶関数/奇関数成分に対応する）ことを利用する。

かつては実数の入力データに対するフーリエ係数を求めるのには、実数計算だけで行える{{仮リンク|離散ハートリー変換|en|Discrete Hartley transform}} (discrete Hartley transform, DHT)を用いると効率的であろうと思われていた。しかしその後に、最適化された[[離散フーリエ変換]] (discrete Fourier transform, DFT) アルゴリズムの方が、離散ハートリー変換アルゴリズムに比べて必要な演算回数が少ないということが判明した。また当初は、実数入力に対してブルーン (Bruun) FFT アルゴリズムは有利であると云われていたが、その後そうではないことが判った。

また、[[偶関数と奇関数|偶奇の対称性を持つ]]実入力の場合には、DFTは[[離散コサイン変換|DCT]]や{{仮リンク|離散サイン変換|en|Discrete sine transform|label=DST}}となるので、演算と記憶に関してほぼ2倍の効率化が得られる。よって、そのような場合にはDFTのアルゴリズムをそのまま適用するよりも、DCTやDSTを適用してフーリエ係数を求める方が効率的である。

== 応用 ==
* [[スペクトラムアナライザ]]
* [[直交周波数分割多重方式|OFDM変復調器]]
*:[[直交周波数分割多重方式|OFDM]]（[[日本]]および[[欧州]]で[[地上デジタルテレビジョン放送]]や[[ADSL]]等に用いられる[[変調方式]]）の実装は、[[集積回路|LSI]]化されたFFTおよびIFFT（逆変換）をそれぞれ復調器および変調器を用いて行われている。
* [[フーリエ変換NMR]]
*:[[核磁気共鳴]] (NMR) スペクトルを得るために使用される。
* [[コンピュータ断層撮影]] (CT)、[[核磁気共鳴画像法]] (MRI) 等
*:受像素子を360度回転させながら連続撮影した映像をフーリエ変換する事により、回転面の透過画像を合成する。
* 多[[倍精度浮動小数点数|倍精度]]の乗除算
* [[自動列車停止装置]] (例: [[西日本旅客鉄道|JR西日本]]の最新型車両。[[地上子]]が[[発振]]する周波数の検出に、高速フーリエ変換が用いられている)
* [[FFTアナライザ]]
*:周波数の分布を調べるために使用される。以前はハードウェアで信号を処理していたが、近年は[[CPU]]の性能が向上した為[[ソフトウェア]]で処理される。[[ノートパソコン]]と[[USB]]で接続して使用するもの<ref>[http://www.stjapan.co.jp/products/1004 FFT spectrum analyzer]</ref> や、近年は[[デジタルオシロスコープ]]にFFTの機能を内蔵している物もある。
* [[電波天文学]]
*:[[FX型デジタル分光相関器]]等を使用して[[星間分子]]のスペクトルを解析する<ref>[http://www.astro.s.osakafu-u.ac.jp/research/spart.html 惑星大気の観測「SPART」]</ref><ref>[http://search.ieice.org/bin/summary.php?id=j98-a_3_296 空間FFT電波干渉計による電波天体の高速撮像]</ref>。

== 歴史 ==
高速フーリエ変換といえば一般的には1965年、{{仮リンク|ジェイムズ・クーリー|en|James Cooley}} (J. W. Cooley) と[[ジョン・テューキー]] (J. W. Tukey) が発見した<ref name=Math>J. W. Cooley and J. W. Tukey: Math. of Comput. '''19''' (1965) 297.</ref> とされている{{仮リンク|クーリー–テューキー型FFTアルゴリズム|en|Cooley–Tukey FFT algorithm}}のことをさす<ref>[http://www.ieeeghn.org/wiki/index.php/Archives:History_of_FFT_with_Cooley_and_Tukey IEEE Archives: History of FFT with Cooley and Tukey].</ref>。同時期に[[高橋秀俊]]がクーリーとテューキーとは全く独立にフーリエ変換を高速で行うためのアルゴリズムを考案していた<ref>{{cite journal|和書|journal=東京大学大型計算機センターニュース |volume=2 |issue=Supplement 2 |date=1970 }}</ref>。しかし、[[1805年]]頃に既に[[カール・フリードリヒ・ガウス|ガウス]]が同様のアルゴリズムを独自に発見していた。それは彼の没後に刊行された全集に収録されている<ref>Carl Friedrich Gauss, "[https://books.google.co.jp/books?id=WFxYAAAAYAAJ&hl=ja&pg=PA265#v=onepage&q&f=false Nachlass: Theoria interpolationis methodo nova tractata]", Werke band 3, 265–327 (Konigliche Gesellschaft der Wissenschaften, Gottingen, 1866). See also　M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine 1 (4), 14–21 (1984).</ref>（本ページの外部リンク先に同じ文章PDFへのリンクがある）。ガウスの論文以降、地球物理学や気候や潮位解析などの分野などで測定値に対する調和解析は行われていたので、計算上の工夫を必要とする応用分野で受け継がれていたようである（たとえば、Robart L. Nowack: "Development of the FFT and Applications in Geophysics", in Proceedings of the Cornelius Lanczos International Centenary Conference,SIAM, ISBN 978-0898713398 (1994), pp.395-397、の中では Danielson and Lanczos（1942年）などの先行例をあげている。和書でも沼倉三郎：「測定値計算法」、森北出版、（1956年）には，一般の合成数Nに対してではないが、人が計算を行う場合にある程度の大きさまでの合成数Nについてどのように計算すればよいかについての説明をみることができる）。
以下の書籍にも、天体観測の軌道の補間のためにガウスが高速フーリエ変換を利用したことが書かれている。
* Elena Prestini:"The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004)のSec.3.10 'Gauss and the asteroids: history of the FFT'.

== ライブラリ ==
=== 特定のデバイスに限定していない汎用の実装 ===
* [[FFTPACK]]
* [[FFTW]]

=== ハードウェアベンダーによる、特定のデバイス向けの実装 ===
* Accelerate vDSP - Apple のデバイス用<ref>{{cite web |url=https://developer.apple.com/documentation/accelerate/vdsp |title=vDSP - Accelerate - Apple Developer Documentation |date=  |author= |accessdate= May 25, 2024}}</ref>
* AOCL-FFTW - AMD CPU 用<ref>{{Cite web |title=AOCL-FFTW (Fastest Fourier Transform in the West) |author= |work=AMD |date= |access-date=25 May 2024 |url= https://www.amd.com/en/developer/aocl/fftw.html}}</ref>
* Arm Performance Libraries - Arm64 用<ref>{{cite web |url=https://developer.arm.com/Tools%20and%20Software/Arm%20Performance%20Libraries |title=Arm Performance Libraries |date=  |author= |accessdate= May 25, 2024}}</ref>
* cuFFT - NVIDIA GPU 用<ref>{{Cite web |title=cuFFT |author= |work=NVIDIA Developer |date= |access-date=25 May 2024 |url= https://developer.nvidia.com/cufft}}</ref>
* [[Intel Math Kernel Library|Intel oneAPI Math Kernel Library]] - Intel CPU, GPU 用
* MathKeisan - [[NEC SX]] 用<ref>{{Cite web |title=NEC Corporation of America |author= |work=mathkeisan.com |date= |access-date=25 May 2024 |url= https://www.mathkeisan.com/}}</ref>
* rocFFT - AMD GPU 用<ref>{{Cite web |title=rocFFT documentation — rocFFT Documentation |author=AMD |work=rocm.docs.amd.com |date= |access-date=25 May 2024 |url= https://rocm.docs.amd.com/projects/rocFFT/en/latest/}}</ref>

== 参考文献 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連記事 ==
* [[フーリエ変換]]
* [[離散フーリエ変換]] (DFT)
* {{仮リンク|Butterfly diagram|en|Butterfly diagram}}
* {{仮リンク|Overlap–add method|en|Overlap–add method}} / {{仮リンク|Overlap–save method|en|Overlap–save method}}
* {{仮リンク|Spectral music|en|Spectral music}}
* [[スペクトラムアナライザ]]
* [[時系列]]
* [[ショーンハーゲ・ストラッセン法]]（{{仮リンク|乗算アルゴリズム|en|Multiplication algorithm}}）
* {{仮リンク|Sparse Fourier transform|en|Sparse Fourier transform}} ※ （高速）スパース・フーリエ変換(SFT)

== 学習用図書 ==
今後記述を追加の予定
* Henri J. Nussbaumer: ''Fast Fourier Transform and Convolution Algorithms'', 2nd Ed., Springer-Verlag, ISBN 978-3-540-11825-1, (1982年).
* E.Oran Brigham：「高速フーリエ変換」、科学技術出版社 (1985年). 
* Rafael G. Campos: ''The XFT Quadrature in Discrete Fourier Analysis'', Birkhäuser, ISBN 978-3-030-13422-8, (2019年). ※離散フーリエ変換の拡張
* Douglas F. Elliott and K.Ramamohan Rao: ''Fast Transforms: Algorithms, Analyses, Applications'', Academic Press, ISBN 0-12-237080-5, (1982).
* Henri J. Nussbaumer:「高速フーリエ変換のアルゴリズム」、科学技術出版社、ISBN 978-4-87653006-9,（1989年）．
* Charles Van Loan: ''Computational Frameworks for the Fast Fourier Transform'', SIAM, ISBN 978-0-89871-285-8, (1992年).
* William L. Briggs and Van Emden Henson: ''The DFT: An Owners' Manual for the Discrete Fourier Transform'', SIAM, ISBN 978-0-898713-42-8, (1995年).
* Eleanor Chu and Alan George: ''Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms'', CRC Press, ISBN 978-0-84930270-1, (1999).
* Audrey Terras: ''Fourier Analysis on Finite Groups and Applications'', London Mathematical Society, Cambridge Univ. Press, ISBN 978-0-521-45718-7 (1999). ※ 群上の調和解析
* Gerlind Plonka, Daniel Potts, Gabriele Steidl and Manfred Tasche: ''Numerical Fourier Analysis'', Birkhaeuser, ISBN 978-3-03004305-6, (2019年2月）.
* 谷萩隆嗣：「高速アルゴリズムと並列信号処理」、コロナ社、ISBN 4-339-01124-X,（2000年7月26日）．
* Daisuke Takahashi: ''Fast Fourier Transform Algorithms for Parallel Computers'', Springer, ISBN 978-981139967-1, (2020).
* David K. Maslen and Daniel N. Rockmore: ''The Cooley-Tukey FFT and Group Theory'', Notices of the AMS, (Nov, 2001), Vol.48, No.10, pp.1151-1161. ※ 群上の調和解析
* David K. Maslen and Daniel N. Rockmore: ''The Cooley-Tukey FFT and Group Theory'', Modern Signal Processing, MSRI Publications, Vol.46,(2003), pp.281-300. ※ 群上の調和解析
* Rockmore, D.N. (2004). ''Recent Progress and Applications in Group FFTs''. In: Byrnes, J. (eds) ''Computational Noncommutative Algebra and Applications. NATO Science Series II: Mathematics, Physics and Chemistry'', Vol.136, Springer, ISBN 978-1-4020-1982-1. ※ 群上の調和解析

==外部リンク==
*{{britannica|topic|fast-Fourier-transform|fast Fourier transform (Mathematics)}}
*{{Kotobank|2=世界大百科事典 第２版}}
*[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Michael T. Heideman, Don H. Johnson, and C. Sidney Burrus: "Gauss and the History of the Fast Fourier Transform", IEEE ASSP Magazine, Vol.1,pp.14-21(1984). (PDF File)]
*[https://arxiv.org/abs/1808.06736 Alex H. Barnett, Jeremy F. Magland, Ludvig af Klinteberg:A parallel non-uniform fast Fourier transform library based on an "exponential of semicircle" kernel]
*[http://www.rist.or.jp/rnews/57/57s4.pdf 高橋大介：「高速フーリエ変換におけるキャッシュ最適化」、RISTニュース、No.57,pp.24-31 (2014).]
*[https://qiita.com/HMMNRST/items/14b990534d7b6d04307d 「2の累乗専用のFFTを用いて任意長FFTを実装：チャープZ変換」(Qiita記事，2018年11月13日）]
*[http://www.fft.report WEB SITE "FFT Report"]
*[http://www.na.scitec.kobe-u.ac.jp/~yamamoto/lectures/parallelFFT/parallelFFT1.PDF 山本有作:「高速フーリエ変換とその並列化 (I)」(2003年6月6日)]

{{normdaten}}

{{デフォルトソート:こうそくふうりえへんかん}}
[[Category:数値解析]]
[[Category:アルゴリズム]]
[[Category:信号処理]]
[[Category:フーリエ解析]]
[[Category:ジョゼフ・フーリエ]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]