１の原始N乗根による表現を使った離散フーリエ変換

これなら分かる 応用数学教室4.6 「１の原始N乗根による表現」

$$ \omega_N = e^{i 2\pi/N} $$

とすると

$$ \begin{align*} F_k &= \frac{1}{N} \sum_{l=0}^{N-1} f_l e^{-i 2\pi kl/N} \\ &= \frac{1}{N} \sum_{l=0}^{N-1} f_l(\omega_N)^{-kl} \\ \end{align*} $$

 \(\overline{\omega_N} = \omega_N^{-1}\) より（上バーは複素数の共役をあらわす）

$$ = \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{\omega_N^{kl} } $$

\(\overline{ab} = \overline{a} \cdot \overline{b}\) より

$$ \begin{align*} &= \frac{1}{N} \overline{\overline{ \sum_{l=0}^{N-1} f_l \overline{\omega_N^{kl} } }} \\ &= \frac{1}{N} \overline{ \sum_{l=0}^{N-1} \overline{f_l} \omega_N^{kl} } \\ \end{align*} $$

となる。

\(b_k = \sum_{l=0}^{N-1} a_l \omega_N^{kl}\) , \(a_l = \overline{f_l}\) とすれば、

$$ F_k = \overline{b_k} / N. $$

プログラム化

RubyのComplexを使って

require 'complex'

# 原始N乗根
def primitiveNthRoot(n, k=1)
  t = 2 * Math::PI * k / n
  Complex(Math.cos(t), Math.sin(t))
end

# 係数計算
def calcb(a, k)
  n = a.length
  (0...n).inject(Complex(0, 0)) do |r, l|
    wklN = primitiveNthRoot(n, k * l)
    r + a[l] * wklN
  end
end

# 離散フーリエ変換
def dft(fs)
  n = fs.length
  a = fs.map{|fl| Complex(fl, 0)}
  b = (0...n).map {|k| calcb(a, k)}
  b.map {|be| be.conjugate / n}
end

p dft([1,7,3,2,0,5,0,8])

結果：

[(3.25-0.0i), (0.8321067811865474-0.021446609406726047i), (-0.2500000000000002-0.25i), (-0.5821067811865479+0.7285533905932745i), (-2.25-1.3471114790620886e-15i), (-0.5821067811865464-0.7285533905932751i), (-0.2500000000000022+0.25i), (0.8321067811865511+0.02144660940672849i)]

• O(N^2)

• 次：高速フーリエ変換の実装
• 前：普通の（fastじゃない）離散フーリエ変換