FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法

はじめに

 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
-
o
m
u
a
r
i
a
l:
@
.
k
.
u
.
r
.
i
..
m
.
s
.
.
.
k
.
y
.
o
.
t
.
o
.
-
.
u
.
.
.
a
.
c
.
.
.
j
.
p

数値計算ライブラリのページ