11.高速フーリエ変換(FFT)(続き)

4点のデータでのDFT

 

 
 
 
     という関係を利用すると

 

 2列目と3列目を入れ換えると

 


 偶数番目と奇数番目のデータを分けると

 

 さらに,これは回転因子の性質を用いて
 次のように表せる

 

 この式には, という配列が4つ含まれること
 に着目する


 この演算をシグナルフローグラフで示すと
 

 これは,以下の演算に対応している

 
 
 
 

 たすき掛けの部分の演算をバタフライ演算という
 (図4.2 (b)に対応)

 1つのバタフライ演算では,複素乗算は1回のみ
          ↓
 4点DFTでは,4×4回の乗算が4回になる
 (4点FFT)


FFTアルゴリズムの一般化

時間間引きアルゴリズム 

 Nが2のべき乗(,νは正の整数)とする

 を,添字nの偶数・奇数で分けると

 

 ここで

 

 

 とおけば

 

 これは,点DFTがN/2点DFTに
 分けられたことを示す
 さらに同様の操作を繰り返すことにより
 最終的には2点DFTにまで分解される
 (図4.5に対応)


周波数間引きアルゴリズム

 Nが2のべき乗(,νは正の整数)とする

 を,前半と後半で分けると

 

 ここで,を,添字kの偶数・奇数で分けると

 

 

 偶数の方は,という列の
 N/2点DFTであり,奇数の方は,
 という列の
 N/2点DFTであることを示している
 さらに同様の操作を繰り返すことにより
 最終的には2点DFTにまで分解される


FFTアルゴリズムの詳細

バタフライ演算の定位置計算

 点FFTアルゴリズムに必要な複素配列は
 次元のもの1つだけでよい


ビット逆順配列

 時間間引きアルゴリズムでは,入力側()を
 偶数と奇数に分けたため,一見すると複雑な
 順序の並びになっている(図4.6参照)

 しかし,入力側と出力側の添字をそれぞれ
 2進数で表現すると,ビットの順序を逆転した
 関係になっているという規則性が見出せる
 すなわち,入力側がビット逆順配列になっている

 なお,周波数間引きアルゴリズムでは,
 出力側()がビット逆順配列になる


 ビット逆順の例
(8点FFTの場合)

     入力        出力
  10進数 2進数    10進数 2進数
   0   000     0   000
   4   100     1   001
   2   010     2   010
   6   110     3   011
   1   001     4   100
   5   101     5   101
   3   011     6   110
   7   111     7   111


FFTの応用

 スペクトル解析
 畳込み
 フィルタリング
 インパルス応答
 相関関数
 ケプストラム分析


FFTの問題点・留意点

 エイリアシング
  サンプリング定理に従えば問題はないが,
  一般的には,事前に周波数成分は分からない
  →現実的にはローパスフィルタを用いる

 観測範囲が有限
  観測データが周期的に繰り返されていること
  になってしまい,不連続点が生じ,ギブス現象が
  起きる
  →窓関数による処理が必要

 標本データ数の問題
  観測データ数は,2の整数べき乗である必要がある
   ↓
  観測データ数が多い場合は,適当な長さを切り出す
  データ列に0を付加する方法もある

 スペクトルの精度の限界
  観測データ数がそのままスペクトルの
  分解の数になる
  観測データ数が少ない場合は精度に問題が生じる
   ↓
  FFT以外のスペクトル推定法が必要
  (観測データに線形モデルを当てはめるなど)