高速フーリエ変換（こうそくフーリエへんかん、、FFT）とは、離散フーリエ変換 (Discrete Fourier Transform、DFT) を計算機上で高速に計算するアルゴリズム。FFTの逆変換をIFFT (Inverse FFT) と呼ぶ。高速フーリエ変換といえば一般的には1965年、 (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見したとされているを呼ぶ。しかし、1805年ごろにガウスが同様のアルゴリズムを独自に発見していた。複素関数f(x)の離散フーリエ変換 (DFT)である複素関数F(t) は以下で定義される。このとき、formula_1を標本点と言う。これを直接計算したときの時間計算量は O ("N" ) である（Oはランダウの記号）。高速フーリエ変換は、この結果を、次数 "N" が2の累乗のときに O ("N" log "N" ) の計算量で得るアルゴリズムである。より一般的には、次数が formula_2 と素因数分解できるとき、formula_3 の計算量となる。次数が2の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、0詰めで次数を調整することもある。高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量をO ("N" ) → O ("N" log "N" ) に落とせる。現在は、初期の手法をより高速化したアルゴリズムが使用されている。逆変換 (IFFT) は正変換 (FFT) と同じと考えて良いが、指数の符号が逆であり、係数formula_4が掛かる。離散フーリエ変換を以下で定義したとき、逆変換は、となる。このため、formula_6の離散フーリエ逆変換を求めるには、とすれば良く、正変換の高速フーリエ変換のプログラムがあれば、逆変換は容易に作ることができる。Cooley-Tukey型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。分割統治法 (divide and conquer) を使ったアルゴリズムで、 "N" = "N" "N" のサイズの変換を、より小さいサイズである "N" 、"N" のサイズの変換に分割していくことで高速化を図っている。最もよく知られたCooley-Tukey型アルゴリズムは、ステップごとに変換のサイズをサイズ "N" / 2 の2つの変換に分割するので、2の累乗次数に限定される。しかし、一般的には次数は2の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。Cooley-Tukey型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、"N" ≤ 8 あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。離散フーリエ係数は、1の原始 "N" 乗根の1つ formula_9を使うと、次のように表せる。例えば、"N" = 4 のとき、離散フーリエ係数は行列を用いて表現すると（"W" ≡ "W" と略記）となる。入力列 "x" を添字の偶奇で分けて、以下のように変形する。すると、サイズ2のFFTの演算結果を用いて表現でき、サイズの分割ができる。また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。"N" ="PQ" とする。"N" 次離散フーリエ変換：を、"n" = 0, 1, ... , "N" -1 について計算することを考える。"n" , "k" を次のように書き換える。ただし0 ≤ "n" ≤ "N" -1、0 ≤ "k" ≤ "N" -1である。するとここで、と置くと、となる。即ち、formula_19の計算は、次の2ステップになる。ステップ1、2は、"N" = "PQ" 次の離散フーリエ変換を、"Q" 次の離散フーリエ変換と回転因子の掛け算の実行により、"Q" 組（"r" = 0, 1, ... , "Q" -1）の"P" 次離散フーリエ変換に分解したと見ることができる。"N" = "Q" （"P" = "Q" ）の場合には、上を繰り返せば、"Q" 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げることができ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、"F" ("t" )を求めることができる。特に、"Q" が2または4の場合は、"Q" 次の離散フーリエ変換は非常に簡単な計算になる。このため、2の累乗あるいは4の累乗次の離散フーリエ変換は簡単に計算できる。実務的に用いられるのは、"Q" = 2か"Q" = 4の場合のみである。なお、"Q" = 2か"Q" = 4の場合のこの部分の"Q" 次の離散フーリエ変換のことを、バタフライ演算と言う。また、"Q" = 2か"Q" = 4の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。"N" = "Q"の次数を1落とすために"N"回の「掛け算」が必要であり、次数を"k"から0に落とすにはそれを"k"回繰り返す必要があるため、「掛け算」の数は"Nk"="N"log"N"となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は O ("N"log"N" ) になる」という根拠になっている。上記の説明で、"N" = "Q" （"P" = "Q" ）の場合、"N" = "Q" 個のデータformula_26から、"N" = "Q" 個の計算結果を計算する場合に、メモリの節約のため、0≤"q" ≤"Q" -1、0≤"r" ≤"Q" -1 を利用し、計算結果"f"("p" ,"r" ) を元データformula_28 のあった場所に格納することが多い。これが次の次数"Q" でも繰り返されるため、formula_29とすると、次の次数の計算結果formula_30はformula_31のあった場所に格納される。繰り返せば、formula_32とすると、計算結果formula_33はformula_34のあった場所に格納される。一方、を、"r" を固定し"s" を変数とした"Q" 次離散フーリエ変換と見なして、formula_36とすると、となる。繰り替えせば、となるが、左辺についてよりformula_40、また右辺についてよりformula_42。このため、これはformula_44のあった場所に格納されている。このように、求める解formula_45 がformula_44 のあった場所に格納されていることを、ビット反転と言う。これは、"Q" 進数で表示した場合、formula_47 は formula_48となるのに対し、formula_49は逆から読んだformula_50となるためである。Microsoft Visual Basicの文法で、高速フーリエ変換のプログラムを書くと、次のような例が考えられる。この例では"Q" = 4である。この例では、最深部(For k、Next kの間の部分)の繰り返し回数がNdegformula_51Ndegとなっている。多くの実用面において、FFTへの入力は実数のみの列(実入力)であり、このとき出力の列は次の対称性を満たす（*は複素共役）：そして、多くの効率的なFFTアルゴリズム（例えば）はこの条件を前堤に設計されている。実入力への効率化には、次のような手段がある。かつては実入力に対するフーリエ係数は (DHT : Discrete Hartleytransform) でより効率的に計算できると思われていた。しかし、その後最適化された離散フーリエ変換(DFT：Discrete Fourier Transform)アルゴリズムが、離散ハートリー変換アルゴリズムよりも必要とする演算回数を下まわることがわかった。また、Bruun's FFTアルゴリズムは、はじめこそ実入力に対して有利といわれていたが、今ではそういわれてはいない。さらに偶奇の対称性を持つ実入力の場合にはさらに最適化ができ、DFTはDCTやになり、時間とメモリーの（ほとんど）2つに関して最適化が得られる。この場合には直接DFTのアルゴリズムを応用しないでも、DCTやDSTの計算によってフーリエ係数を求めることができる。

出典:wikipedia