離散フーリエ変換
二つの(一般には複素数値の)関数 f ( x ) {\displaystyle f(x)} と g ( x ) {\displaystyle g(x)} の畳み込み f ∗ g {\displaystyle f*g} は次のように定義される。
( f ∗ g ) ( x ) = ∑ n = 0 N − 1 f ( n ) g ( x − n ) {\displaystyle (f*g)(x)=\sum _{n=0}^{N-1}f(n)g(x-n)}
ただし、 f {\displaystyle f} と g {\displaystyle g} は次のような周期性を持つとする。
f ( x + N ) = f ( x ) g ( x + N ) = g ( x ) {\displaystyle {\begin{aligned}f(x+N)&=f(x)\\g(x+N)&=g(x)\end{aligned}}}
周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる(畳み込み定理)。 つまり
F N ( f ∗ g ) = F N ( f ) F N ( g ) {\displaystyle {\mathcal {F}}_{N}(f*g)={\mathcal {F}}_{N}(f){\mathcal {F}}_{N}(g)}
畳み込み和を直接定義式を用いて計算すると O(N2) の計算量が掛かる。しかし、上式より一旦 DFT をしてから掛算をして、そして IDFT で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると O(N log N) の計算量で済む。