11. 離散フーリエ変換（DFT）
tctyam離散フーリエ変換（Discrete Fourier Transform：DFT）は、離散的な信号やデータ列を周波数成分に変換する手法である。これは、信号処理やデータ解析の分野で広く使用されている。離散フーリエ変換は、離散時間信号から成る有限の信号を、異なる周波数成分に分解する操作である。この変換によって、元の信号がどのような周波数成分で構成されているかを分析することが可能になる。また、離散フーリエ変換は、計算が比較的簡単であり、効率的にアルゴリズム化できるため、実用的なアプリケーションで広く利用されている。一般的に、高速フーリエ変換（Fast Fourier Transform：FFT）アルゴリズムが使用され、効率的な計算が行われる。
離散時間フーリエ変換
サンプル値信号\(x_s(t)\)は連続時間信号\(x(t)\)と単位インパルス関数\(\delta(t)\)を使って、$$x_s(t) = \sum_{n=-\infty}^{\infty} x(nT) \delta(t - nT)$$と表せる。この\(x_s(t)\)のフーリエ変換\(X_s(\omega)\)は、$$X_s(\omega) = \sum_{n=-\infty}^{\infty} x(nT) e^{-j n \omega T}$$となる。ここで、\(x(nT) = x(n)\)、\(\omega T = \Omega \)（\(\omega T = 2 \pi f/f_s = 2\pi f_N\) \(f_N\)：正規化周波数）とおいて、非因果性の離散時間信号\(x(n)\)のフーリエ変換\(X(\Omega)\)を式(1)で定義する。$$X(\Omega) = \sum_{n=-\infty}^{\infty} x(n) e^{- j n \Omega} \;\cdots\cdots(1)$$この式(1)を離散時間フーリエ変換（DTFT）という。（注意：離散フーリエ変換ではない）\(X(\Omega)\)は周期\(2 \pi \)の周期関数となるので、その１周期区間\(0 \le \Omega \le 2 \pi \)の情報が分かれば十分である。逆離散時間フーリエ変換は、式(2)で与えられる。$$x(n) = \frac{1}{2 \pi} \int_{-\pi}^{\pi} X(\Omega)e^{j n \Omega} d \Omega \;\cdots\cdots (2)$$また、連続時間信号の場合と同様に、\(X(\Omega)\)が存在するための十分条件は、$$\sum_{n=-\infty}^{\infty}|x(n)| < \infty$$である。
離散フーリエ変換
式(1)、式(2)の離散時間フーリエ変換、逆離散時間フーリエ変換をコンピュータ等でデータ処理しようとした場合、次の問題がある。
１）離散時間信号\(x(n)\)が\(-\infty < n <+\infty\)の範囲で定義されており、計算不能である。有限範囲の信号での計算が必要である。
２）\(X(\Omega)\)は周波数\(\Omega\)の連続関数になっており、コンピュータ処理には不向きである。離散化した計算が必要である。
これらの点を修正したのが、離散フーリエ変換である。
離散時間信号\(x(n)\)が任意の整数\(n\)に対して、\(n<0 , \; n \ge N\)の範囲でゼロとなる有限の離散時間信号を考える。この信号\(x(n)\)の離散フーリエ変換（DFT）を\(X(k)\)として、式(3)で定義する。$$X(k) = \sum_{n=0}^{N-1} x(n) e^{-j 2 \pi k n /N} , \;\;(k = 0,1,\cdots ,N-1) \;\cdots\cdots (3)$$ 一方、式(1)の離散時間フーリエ変換は、\(n<0 , \; n \ge N\)の範囲で\(x(n) = 0\)なので、$$X(\omega) = \sum_{n=0}^{N-1} x(n) e^{-j n \Omega}$$となる。この式と式(3)を比較すると、$$ X(k) = \left. X(\Omega)\right|_{\Omega = 2 \pi k/N} = X\left(\frac{2 \pi k}{N}\right) $$が成立する。つまり、式(3)の離散フーリエ変換\(X(k)\)は、整数\(k\)に対して、一定の周波数間隔\(\Omega = 2\pi k/N\)でサンプルされたときの値\(X(\Omega)\)に等しい。また、\(X(k)\)から\(x(n)\)の変換は、$$x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j2 \pi k n/N},\;\;(n=0,1, \cdots ,N-1) \;\cdots\cdots(4)$$で求まり、逆離散フーリエ変換（IDFT）という。DFTの\(X(k)\)は離散変数の関数、DTFTの\(X(\Omega)\)は連続変数の関数である。
ここで、$$W_N = e^{-j\frac{2 \pi}{N}}$$と定義すると、DFT,IDFTは $$X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn} \\ x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) W_N^{-kn}$$と表せる。\(W_N^{kn}\)の対称性と周期性を使って、これらの演算を効率よく実行するアルゴリズムが高速フーリエ変換（FFT）である。このFFTはfft関数として、Scilabを始めとして、多くの数値計算ソフトウェアに実装されている。
