離散フーリエ変換
また、二つの(一般には複素数値の)関数 f ( x ) {\displaystyle f(x)} と g ( x ) {\displaystyle g(x)} の相互相関 f ⋆ g {\displaystyle f\star g} は以下のように定義される。
h ( x ) = ( f ⋆ g ) ( x ) = ∑ n = 0 N − 1 f ( n ) g ( x + n ) {\displaystyle h(x)=(f\star g)(x)=\sum _{n=0}^{N-1}f(n)g(x+n)}
f , g {\displaystyle f,g} が上記の周期性を持てば、
( F N h ) ( u ) = ( F N ( f ⋆ g ) ) ( u ) = F N ( f ) ( − u ) F N ( g ) ( u ) {\displaystyle ({\mathcal {F}}_{N}h)(u)=({\mathcal {F}}_{N}(f\star g))(u)={\mathcal {F}}_{N}(f)(-u){\mathcal {F}}_{N}(g)(u)}
さらに f {\displaystyle f} の関数値が実数であれば、 F N ( f ) ( − u ) = F N ( f ) ( u ) ̄ {\displaystyle {\mathcal {F}}_{N}(f)(-u)={\overline {{\mathcal {F}}_{N}(f)(u)}}} となる.ここで上線をつけた z ̄ {\displaystyle {\bar {z}}} は z {\displaystyle z} の複素共役を表す。
離散フーリエ変換はフーリエ変換に類似した変換であるので、フーリエ変換と類似した性質を持つ。
DFTは多くの広い分野で利用されている。ここでは、その中の一部を示しているだけに過ぎない。これらの応用は高速フーリエ変換(FFT)とその逆変換(IFFT)で高速に計算できることを前提としていて、定義通りにDFTを計算しているのではない。
F v = W f {\displaystyle F_{v}=Wf}
F ( u , v ) = ∑ x = 0 M − 1 F v ( x , v ) e − 2 π i u x M {\displaystyle F(u,v)=\sum _{x=0}^{M-1}F_{v}(x,v)e^{-2\pi i{\frac {ux}{M}}}}
F = W F v T {\displaystyle F=WF_{v}^{T}}
F = W f T W {\displaystyle F=Wf^{T}W}
以下上式の 1 - 7 を解説すると、
2次元DFTの定義
式1から e を内側σから出した
内側のσは、信号 f ( x , y ) {\displaystyle f(x,y)} のyの次元( F y { f ( x , y ) } {\displaystyle {\mathcal {F}}_{y}\{f(x,y)\}} と書いた行)の1次元DFTであることを示している
式3で示した、 F y { f ( x , y ) } {\displaystyle {\mathcal {F}}_{y}\{f(x,y)\}} の行列表現
表中で、
W = e − i 2 π N {\displaystyle W=e^{-i{\frac {2\pi }{N}}}}