FFT破れたり〜はっはっはー。 - ほっしーの技術ネタ備忘録

FFT ( 高速フーリエ変換 ) がなんで速いのか。
どうして DFT ( 離散フーリエ変換 ) から FFT になるのか。
これを利用して DCT ( 離散コサイン変換 ) の高速版は作れないのか。

なんか大学レベルの知識がいるような雰囲気なので避けてたわけですが、
風呂上りに落ち着いて式を見てみると…

これって単なる式変形なのか！？

と気づいたわけで。忘れないうちに日記にメモしておこう...
何度も書くけど、内容は全く理解してません。式変形できただけです。(ぉ

まず DFT の式はこういう感じらしいです。
何のことだか全く分かりません。とにかくこういうものです。
$\Large A(k)=\Bigsum_{j=0}^{N-1}a(j)w(N)^{jk}, w(N)=e^{-2i\pi/N$

まずは $w(N)$ を整理します。オイラーの公式、
$\Large e^{ix}=cos(x)+sin(x)i$
から、
$\Large w(N)=e^{-2i\pi/N}=cos(-2\pi/N)+sin(-2\pi/N)i$
こうなります。

そして、両辺を二乗すると、
$\Large w(N)^2=cos^2(-2\pi/N)+2sin(-2\pi/N)cos(-2\pi/N)i-sin^2(-2\pi/N)$
cos の倍角、sin の倍角が含まれるので、
$\Large w(N)^2=cos(-4\pi/N)+sin(-4\pi/N)i$

ここで、
$\Large w(N/2)=e^{-4i\pi/N}=cos(-4\pi/N)+sin(-4\pi/N)i$
と、なるから、
$\Large w(N)^2=w(N/2)$
だと言えるわけです。

ここから、正の数 m に対して
$\Large w(N)^2^m=w(N/2^m)$
ということが証明されます。

あと、特別な場合として、
$\Large w(1)=cos(-2\pi)+sin(-2\pi)i=1$
と、直値で計算しておきます。

次は本体の式を見ます。例えば N=4 と仮定して、�瑤鯏験ǂ靴泙后�
$\Large A(k)=a(0)w(N)^{0k}+a(1)w(N)^{1k}+a(2)w(N)^{2k}+a(3)w(N)^{3k}$

ここで、k が偶数のときと奇数のときで場合分け。
奇数も偶数と似た方法なので略。

$k=2l$ つまり偶数のとき。
$\Large A(2l)=a(0)w(N)^{0\times2l}+a(1)w(N)^{1\times2l}+a(2)w(N)^{2\times2l}+a(3)w(N)^{3\times2l}$
後ろ半分は N を使って指数を分解しておきます。
$\Large A(2l)=a(0)w(N)^{0\times2l}+a(1)w(N)^{1\times2l}+a(2)w(N)^Nw(N)^{0\times2l}+a(3)w(N)^Nw(N)^{1\times2l}$

そして、n/2 個はなれた項が隣り合うように並び替えると…
$\Large A(2l)=a(0)w(N)^{0\times2l}+a(2)w(N)^Nw(N)^{0\times2l}+a(1)w(N)^{1\times2l}+a(3)w(N)^Nw(N)^{1\times2l}$

$\Large A(2l)=\{a(0)+a(2)w(N)^N\}w(N)^{0\times2l}+\{a(1)+a(3)w(N)^N\}w(N)^{1\times2l}$
と、括りだせることが分かります。

w を整理すると、
$\Large A(k)=\{a(0)+a(2)w(N/N)\}w(N)^{0\times k}+\{a(1)+a(3)w(N/N)\}w(N)^{1\times k}$

$w(N/N)=w(1)=1$ から、
$\Large A(k)=\{a(0)+a(2)\}w(N)^{0\times k}+\{a(1)+a(3)\}w(N)^{1\times k}$

奇数も同じ感じになるはずです。

こうすることで、４回だった乗算が半分になります。
そして、これも DFT の公式そのままなので、もう一回同じ計算をすれば、乗算が更に半分になります。
これが FFT が速い理由なんですね。

TeX 使うの初めてで疲れた...