Octaveレッスン(6) - FFTのイメージを掴む

ωN を１の原始N乗根とすると、離散フーリエ変換の式は、以下のように書ける。

『これなら分かる応用数学教室』 p.130 

離散フーリエ変換は、サンプル数Nのサンプルデータf0, ..., fN-1をN次元のベクトルとみなし、基本正弦波の0倍～N-1倍の高調波で直交展開することを意味している。

K≠Lのとき、K倍の高調波とL倍の高調波は常に直交する（p.114）。

FFT（高速フーリエ変換）とは、離散フーリエ変換のNを2のべき乗にすることで、フーリエ係数の計算を効率化する方式。
そうすることで、フーリエ係数を求める際に、ωN^kが計算過程で重複して登場するようになり、いちど算出した結果を使いまわすことで、計算量を減らすことができる。

サンプルfが実数のとき、フーリエ係数F0, ..., FN-1のうち、後ろ半分については、前半を折り返した複素共役になっていて、独立ではない(p.116)。
　∵)ωN^(N-k)l = conj(ωN^kl )なので、fが実数のときF(N - k) ｌ＝conj(Fｋl)

そのため、これまでOctaveで振幅スペクトルを求めてプロットする際は、プロットする範囲を0..N/2に半減し、F0, ..., FN/2 の絶対値を求めて2倍していた（省略した後半の分を加算するので2倍）。

• フーリエスペクトル（フーリエ係数）： Fk
• 振幅スペクトル： Fkの絶対値 |Fk|
• 位相スペクトル： Fkの偏角 ∠Fk
• エネルギースペクトル： |Fk|^2 

参考書籍： 『これなら分かる応用数学教室』p.129～p.139