ギター用チューナーを作る② 離散フーリエ変換(DFT)

 

marblog.hatenablog.jp

これの続き。

 

離散フーリエ変換

フーリエ変換

まずおさらい。フーリエ変換はこういう定義である。

 {\displaystyle X(\omega) = \int_{- \infty}^{\infty} x(t) e^{-i \omega t} dt }

この x(t)から X(\omega)への変換の過程をフーリエ変換と呼ぶ。

括弧内を X(\omega)と置いた式

 {\displaystyle x(t) = \frac{1}{2\pi} \int_{- \infty}^{\infty} X(\omega) e^{i \omega t} d\omega }

この X(\omega)から x(t)への変換の過程をフーリエ逆変換と呼ぶ。

アナログデータをデジタルへ

今までは連続関数のフーリエ変換及びフーリエ逆変換について考えてきた。その結果、音波に関して言えば時間関数と周波数関数を自由に行き来できるようになった。しかし、コンピュータでは連続的な数値を扱うことができない。そこで、アナログの波を一定間隔でサンプリングすることで、離散的な波へと変換される。この操作を標本化ともいう。(さらにデジタルデータに変換する(数値化する)作業を量子化という)

ここで、サンプリング間隔を t_s、サンプル数を Nとする。このとき、標本化周波数は {\displaystyle f_s = \frac{1}{t_s}}と表される。

いままでの x(t),X(\omega)t,\omegaはそれぞれ、 {\displaystyle t \to nt_s,\omega \to 2\pi \frac{kf_s}{N}} (n=0 \cdots N-1, k=0 \cdots N-1)と変換することができる。
サンプルの値は、 \{ x(0),x(t_s),x(2t_s), \cdots, x((N-1)t_s) \} と書くことができる。

離散フーリエ変換(DFT)

 i番目のサンプルの値 x(i t_s) x(i)と置くことで、サンプルの値は \{ x(0),x(1),x(2), \cdots, x(N-1) \} と書くことができる。このとき、 x(t) {\displaystyle x(t) = \sum_{n=0}^{N-1} x(n)\delta (t-nt_s) }と表すことが出来る。ただし \delta (x)ディラックデルタ関数で、 \displaystyle{\int_{-\infty}^{\infty} x(t) \delta (t)dt = x(0) }を満たす関数である。
これをフーリエ変換の式に代入すると、
 {\displaystyle X(\omega) = \int_{-\infty}^{\infty} \sum_{n=0}^{N-1} x(nt_s)\delta (t-nt_s) e^{-i\omega t} dt}
 {\displaystyle = \sum_{n=0}^{N-1} x(nt_s) \int_{-\infty}^{\infty} \delta (t-nt_s) e^{-i\omega t} dt }

 {\displaystyle = \sum_{n=0}^{N-1} x(nt_s) e^{-i\omega nt_s} }

 \omega {\displaystyle 2\pi \frac{kf_s}{N}} のように離散化すると、 t_s f_s = 1を考慮して
 {\displaystyle X(k) = \sum_{n=0}^{N-1}x(n) e^{ -i \frac{2\pi k n}{N}} }

次に離散フーリエ逆変換を考える。
 {\displaystyle \frac{1}{N} \sum_{k=0}^{N-1}X(k) e^{ i \frac{2\pi k n}{N}} }

 {\displaystyle = \frac{1}{N} \sum_{k=0}^{N-1} ( \sum_{m=0}^{N-1}x(m) e^{ -i \frac{2\pi k m}{N}} ) e^{ i \frac{2\pi k n}{N}} }

 {\displaystyle = \frac{1}{N} \sum_{m=0}^{N-1}x(m) \sum_{k=0}^{N-1} e^{ i \frac{2\pi k}{N} (n-m) }}

 {\displaystyle = \frac{1}{N} \sum_{m=0}^{N-1}x(m) N \delta_{m,n}}

 {\displaystyle = x(n)}

もとの関数に戻ることがわかった。

以上から、
 {\displaystyle X(k) = \sum_{n=0}^{N-1}x(n) e^{ -i \frac{2\pi k n}{N}} }
この x(n)から X(k)への変換を離散フーリエ変換

 {\displaystyle x(n) = \frac{1}{N} \sum_{k=0}^{N-1}X(k) e^{ i \frac{2\pi k n}{N}} }
この X(k)から x(n)への変換を離散フーリエ逆変換と呼ぶ。

課題

離散フーリエ変換の直接計算を行うとき、 N^2回の複素乗算、 N(N-1)回の複素加算が必要になる。以上から N点のDFTの計算量は O(N^2)である。これは Nが大きい場合に問題となる。

あとがき

ということで次回は高速フーリエ変換。本当はこの記事に高速フーリエ変換を書きたかったけれど、離散フーリエ変換が思ったより書くこと多かったので次に回します。