高速フーリエ変換

高速フーリエ変換（こうそくふーりえへんかん, Fast Fourier Transform, FFT）とは、離散フーリエ変換 (Discrete Fourier Transform, DFT) を計算機上で高速に計算するアルゴリズム。逆変換をIFFT (Inverse FFT) という。

高速フーリエ変換といえば一般的には1965年、ジェイムズ・クーリー (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見した^[1]とされているCooley-Tukey型FFTアルゴリズムを呼ぶ。しかし、1805年ごろにガウスが同様のアルゴリズムを独自に発見していた^[2]。

概要

離散フーリエ変換 (DFT) は以下の級数で定義される。

$f_j = \sum_{k=0}^{N-1} f_k \exp\left( - \frac{2 \pi i j k}{N} \right) \qquad j = 0,\dots,N-1$ .

これを直接計算したときの時間計算量は O ( N² ) である（Oはランダウの記号）。

高速フーリエ変換は、この結果を、次数 N が2の累乗のときに O ( N log N ) の計算量で得るアルゴリズムである。より一般的には、次数が $N = \prod n_i$ と素因数分解できるとき、 $O ( N \sum n_i )$ の計算量となる。次数が2の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、0詰めで次数を調整することもある。

逆変換 (IFFT) は正変換 (FFT) と同じと考えて良いが、指数の符号が逆であり、係数 1 / N が掛かる。高速フーリエ変換のアルゴリズムはこれらの変更点を簡単に適用できるため、逆変換も同じアルゴリズムを使って計算できる。

高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量をO ( N² ) → O ( N log N ) に落とせる。

現在は、初期の手法^[1]をより高速化したアルゴリズムが使用されている。

Cooley-Tukey型FFTアルゴリズム

Cooley-Tukey型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。

分割統治法 (divide and conquer) を使ったアルゴリズムで、再帰的に N = N₁ N₂ のサイズの変換を、ガウス平面における回転因子である1の冪根を N 程度のオーダーかけて、より小さいサイズである N₁, N₂ のサイズの変換にしていくことで高速化を図っている。

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

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

Cooley-Tukey型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、N ≤ 8 あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。

原理の簡単な説明

FFTのバタフライ演算

離散フーリエ係数は、1の原始 N 乗根の1つ W_N ≡ exp( -2 π i / N ) を使うと、次のように表せる。

$f_j = \sum_{k=0}^{N-1} x_k W_N^{jk} \qquad j = 0,\dots,N-1$ .

例えば、N = 4 のとき、離散フーリエ係数は行列を用いて表現すると（W ≡ W₄ と略記）

$\begin{bmatrix}f_0\\f_1\\f_2\\f_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}$ .

入力列 x_k を添字の偶奇で分けて、以下のように変形する。

$\begin{matrix} \begin{bmatrix}f_0\\f_1\\f_2\\f_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{matrix}.$

すると、サイズ2のFFTの演算結果を用いて表現でき、サイズの分割ができる。

$\begin{bmatrix}f_0\\f_1\\f_2\\f_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}$ .

また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。

バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。

その他のアルゴリズム

Prime Factor Algorithm (PFA)
Bruun's FFT algorithm
Rader's FFT algorithm
Bluestein's FFT algorithm

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

実数および対称的な入力への最適化

多くの実用面において、FFTへの入力は実数のみの列(実入力)であり、このとき出力の列は次の対称性を満たす (*は複素共役):

$f_{ - j} = f_j^* \quad j = 0, \dots ,N - 1$ .

そして、多くの効率的なFFTアルゴリズム（例えば^[3]）はこの条件を前堤に設計されている。

実入力への効率化には、次のような手段がある。

Cooley-Tukey型アルゴリズムなど典型的なアルゴリズムを利用して、時間とメモリーの両方の浪費を低減する。
偶数区分数のフーリエ係数はその半分の長さの複素フーリエ係数として表現することできる（出力の実数/虚数成分は、それぞれ入力の偶関数/奇関数成分に対応する）ことを利用する。

かつては実入力に対するフーリエ係数は離散ハートリー変換 (DHT : Discrete Hartley transform) でより効率的に計算できると思われていた。しかし、その後最適化された離散フーリエ変換(DFT：Discrete Fourier Transform)アルゴリズムが、離散ハートリー変換アルゴリズムよりも必要とする演算回数を下まわることがわかった。また、Bruun's FFTアルゴリズムは、はじめこそ実入力に対して有利といわれていたが、今ではそういわれてはいない。

さらに偶奇の対称性を持つ実入力の場合にはさらに最適化ができ、DFTはDCTやDSTになり、時間とメモリーの（ほとんど）2つに関して最適化が得られる。この場合には直接DFTのアルゴリズムを応用しないでも、DCTやDSTの計算によってフーリエ係数を求めることができる。

応用

スペクトラムアナライザ
OFDM変復調器

日本および欧州で地上デジタルテレビジョン放送に用いられる変調方式であるOFDMの実装は、LSI化されたFFTおよびIFFT（逆変換）をそれぞれ復調器および変調器を用いて行われている。

CT、MRI等

受像素子を360度回転させながら連続撮影した映像をフーリエ変換する事により、回転面の透過画像を合成する。

多倍精度の乗除算

参考文献

^ ^a ^b J. W. Cooley and J. W. Tukey: Math. of Comput. 19 (1965) 297.
^ Carl Friedrich Gauss, "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).
^ H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35, 849–863 (1987).

フーリエ変換
離散フーリエ変換 (DFT)

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History