11．高速フーリエ変換（ＦＦＴ）（続き）

４点のデータでのＤＦＴ

　

　
　
　
　　　　　という関係を利用すると

　

　２列目と３列目を入れ換えると

　

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

　

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

　

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

---

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

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

　
　
　
　

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

　１つのバタフライ演算では，複素乗算は１回のみ
　　　　　　　　　　↓
　４点ＤＦＴでは，４×４回の乗算が４回になる
　（４点ＦＦＴ）

ＦＦＴアルゴリズムの一般化

時間間引きアルゴリズム　

　Nが２のべき乗（，νは正の整数）とする

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

　

　ここで

　

　

　とおけば

　

　これは，Ｎ点ＤＦＴがN/2点ＤＦＴに
　分けられたことを示す
　さらに同様の操作を繰り返すことにより
　最終的には２点ＤＦＴにまで分解される
　（図4.5に対応）

---

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

　Nが２のべき乗（，νは正の整数）とする

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

　

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

　

　

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

---

ＦＦＴアルゴリズムの詳細

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

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


ビット逆順配列

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

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

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

---

　ビット逆順の例
（８点ＦＦＴの場合）

　　　　　入力　　　　　　　　出力
　　10進数　２進数　　　　10進数　２進数
　　　０　　　000　　　　　０　　　000
　　　４　　　100　　　　　１　　　001
　　　２　　　010　　　　　２　　　010
　　　６　　　110　　　　　３　　　011
　　　１　　　001　　　　　４　　　100
　　　５　　　101　　　　　５　　　101
　　　３　　　011　　　　　６　　　110
　　　７　　　111　　　　　７　　　111


ＦＦＴの応用

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

---

ＦＦＴの問題点・留意点

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

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

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

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