回路計算 - 離散フーリエ変換

概要

離散フーリエ変換(DFT）とは、次式で定義される変換であり、信号処理等で離散化されたデジタル信号の周波数解析等によく用いられる。
また、偏微分方程式や畳み込み積分の数値計算を効率的に行うためにも用いられる。
離散フーリエ変換 : $X(k)=\sum _{n=0}^{N-1}x(n)\exp \left(-j{\frac {2\pi nk}{N}}\right)$
逆離散フーリエ変換 : $x(n)={\frac {1}{N}}\sum _{k=0}^{N-1}X(k)\exp \left(j{\frac {2\pi nk}{N}}\right)$

離散フーリエ変換は、（計算機上で）高速フーリエ変換(FFT)を使用して高速に計算することができる。

離散フーリエ変換の定義

まず、単位円をN分割した点に相当する変数Wを定義する。
$W=\exp \left(-j{\frac {2\pi }{N}}\right)$

変数Wを用いて、離散フーリエ変換と逆変換の定義式を、次式のように書くことができる。
離散フーリエ変換 : $X(k)=\sum _{n=0}^{N-1}x(n)W^{nk}$
逆離散フーリエ変換 : 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) W^{-nk}}

変数Wは回転子と呼び、以下の関係が成立する。
$W^{N}=e^{-j2\pi }=1$
$W^{k+N}=W^{k+2N}=\cdots =W^{k}$

行列を用いた表現

上記で定義した離散フーリエ変換を、行列を用いて表現することができる。
この表現を用いることにより、変換と逆変換の関係をより直感的に理解することができる。

• 回転子W
  

$W={\begin{pmatrix}W^{0}&W^{0}&W^{0}&\ldots &W^{0}\\W^{0}&W^{1}&W^{2}&\ldots &W^{N-1}\\W^{0}&W^{2}&W^{4}&\ldots &W^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\W^{0}&W^{N-1}&W^{2(N-1)}&\ldots &W^{(N-1)^{2}}\\\end{pmatrix}}$

• 離散フーリエ変換
  

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\\vdots \\X_{N-1}\end{pmatrix}}={\begin{pmatrix}W^{0}&W^{0}&W^{0}&\ldots &W^{0}\\W^{0}&W^{1}&W^{2}&\ldots &W^{N-1}\\W^{0}&W^{2}&W^{4}&\ldots &W^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\W^{0}&W^{N-1}&W^{2(N-1)}&\ldots &W^{(N-1)^{2}}\\\end{pmatrix}}{\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\\vdots \\x_{N-1}\end{pmatrix}}$

• 逆離散フーリエ変換
  

${\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\\vdots \\x_{N-1}\end{pmatrix}}={\begin{pmatrix}W^{0}&W^{0}&W^{0}&\ldots &W^{0}\\W^{0}&W^{-1}&W^{-2}&\ldots &W^{-(N-1)}\\W^{0}&W^{-2}&W^{-4}&\ldots &W^{-2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\W^{0}&W^{-(N-1)}&W^{-2(N-1)}&\ldots &W^{-(N-1)^{2}}\\\end{pmatrix}}{\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\\vdots \\X_{N-1}\end{pmatrix}}$

離散フーリエ変換の計算例

ディジタル信号(1, 1, 0, 0)という周期4(N = 4)の信号において、離散フーリエ変換を使用して、スペクトルを計算する。
${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}1&1&1&1\\1&-j&-1&j\\1&-1&1&-1\\1&j&-1&-j\\\end{pmatrix}}{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}2\\1-j\\0\\1+j\end{pmatrix}}$

上記のスペクトルを逆離散フーリエ変換の式に代入する。
${\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\frac {1}{4}}{\begin{pmatrix}1&1&1&1\\1&j&-1&-j\\1&-1&1&-1\\1&-j&-1&j\\\end{pmatrix}}{\begin{pmatrix}2\\1-j\\0\\1+j\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}$

離散フーリエ変換および逆離散フーリエ変換の式より、これらの変換にはある対称性が存在する。
この性質を用いて、乗算数を飛躍的に少なくする方法(高速フーリエ変換（FFT))がある。