高速フーリエ変換は離散フーリエ変換を高速に計算するアルゴリズムのことで、その定義と計算ライブラリ FFTW についてごく簡単にまとめました。
なお、離散フーリエ変換を含むディジタル信号処理については、東北大学の鏡先生の やる夫で学ぶディジタル信号処理 で非常に分かりやすく解説されておりとても勉強になります。
離散フーリエ変換対
昔勉強したFFTの教科書（E. Oran Brigham, 宮川・今井 (訳): 高速フーリエ変換, 科学技術出版社 (1979), p.110）の表記に従って書いてます。
離散フーリエ変換 (Discrete Fourier Transform, DFT)
$$ G\left( \frac{n}{NT} \right) =\sum_{k=0}^{N-1} g(kT) e^{-j2\pi n k/N} \enspace \enspace n=0,1,\dots, N-1$$
離散フーリエ逆変換 (Inverse Discrete Fourier Transform, IDFT)
$$ g(kT) =\frac{1}{N} \sum_{n=0}^{N-1} G\left( \frac{n}{NT} \right)e^{j2\pi n k/N} \enspace \enspace k=0,1,\dots, N-1$$
FFTW
FFTW は MIT で開発された高速な FFT 計算ライブラリで、任意サイズ・任意次元に対応したアルゴリズムを実装しており、GPL の下でライセンスされ MATLAB でも使用されています。
コメント