離散フーリエ変換 (7)

sys.pdf sys-s.pdf 記事一覧

高速フーリエ変換の原型

離散フーリエ変換の高速計算法である高速フーリエ変換の原理はｚ変換で考えると分かり易い[12]．

    {x₀, x₁, ・・・・・・ , x_N-1}  ( N ＝ 2ⁿ )

の離散フーリエ変換を (DFT_N X)(k) ( 0 ≦ k ＜ N ) で表わすと，上記の式のように変形でき，0 ≦ k' ＜ N/2 に対して

    (DFT_N X)(k') ＝ (DFT_N/2 X₀)(k') + W_N^k (DFT_N/2 X₁)(k')
    (DFT_N X)(N/2 + k') ＝ (DFT_N/2 X₀)(k') - W_N^k (DFT_N/2 X₁)(k')

となる．ｚに直接 W_N^k を代入して (DFT_N X)(k) ( 0 ≦ k ＜ N )を計算するときの乗算回数は (N - 1)² であるが，(DFT_N/2 X₀)(k'), (DFT_N/2 X₁)(k') に分解すれば乗算回数は W_N^k との積を含めて との積を含めて 2(N/2 -1)² + (N/2 - 1) に減少する．N ＝ 2ⁿ としているので (n - 1) 段に分解でき，必要な乗算回数はほぼ ｎN に比例する．
蛇足： X₀(z²) ＝ X_0,0(z⁴) + z^-2 X_0,1(z⁴), etc.

[10] 高速フーリエ変換 - Wikipedia
  http://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
[11] 高速フーリエ変換（FFT) - 信州大学
  http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/basic/chap7/index.htm
[12] これなら分かる応用数学教室 ―最小二乗法からウェーブレットまで ...
  http://www.kyoritsu-pub.co.jp/kenpon/bookDetail/9784320017382
  pp.134-136