FFT とは離散フーリエ変換に関連する変換を高速に実行する一連の 計算方法のことです.ここでは,FFT の考え方とその設計方法について 具体的なプログラムを用いて示します.これは,FFT のライブラリを 作成したときのメモがもとになっています.専門的な説明は極力避けたので, エレガントでない説明になっているかもしれません.基礎知識として, 複素数の演算規則とフーリエ変換が何かということさえ知っていれば 理解できると思います.また,数学の知識がある程度あり 時間を節約したい方は, 1.2節と1.3節の要約(pdf 53KB) を一読していただければ速く理解できると思います.
1 FFT 概略
1.1 離散 Fourier 変換
1.1.1 DFT の定義
1.1.2 DFT と通常の Fourier 変換
1.1.3 DFT の性質
1.2 Cooley-Tukey 型 FFT
1.2.1 基本的な考え方
1.2.2 周波数間引きと時間間引きアルゴリズム
1.2.3 混合基数アルゴリズム
1.2.4 Split-Radix FFT アルゴリズム
1.2.5 データの並べ替えの方法
1.2.6 性能比較とルーチン設計
1.3 Prime Factor 型 FFT
1.3.1 基本的な考え方
1.3.2 Prime Factor アルゴリズム (PFA)
1.3.3 Winograd DFT アルゴリズム (WFTA)
1.3.4 Short DFT アルゴリズム
1.3.5 性能比較とルーチン設計
2 FFT が適用できる変換
2.1 実離散 Fourier 変換
2.1.1 複素 FFT を間接的に用いる方法
2.1.2 実数専用の FFT ルーチンを用いる方法
2.2 拡張離散 Fourier 変換
2.3 離散 Cosine/Sine 変換
2.3.1 DCT/DST のタイプ
2.3.2 実数の FFT を間接的に用いる方法
2.3.3 DCT/DST 専用の FFT ルーチンを用いる方法
2.4 離散 Hartley 変換
2.4.1 離散 Hartley 変換の定義
2.4.2 離散 Hartley 変換に対する FFT ルーチン
3 多次元 FFT
3.1 Row-Column 法
3.2 Vector-Radix FFT アルゴリズム
3.3 Winograd DFT アルゴリズム
参考文献
FFT プログラムのダウンロード
FFT Links
このページの更新記録
Copyright: Takuya OOURA, 1997
e
o-
om
ua
ri
al:
@.
k.
u.
r.
i..
m.
s.
..
k.
y.
o.
t.
o.
-.
u.
..
a.
c.
..
j.
p