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

2009-05-15

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

普通の(fastじゃない)離散フーリエ変換に引き続き。

とすると

より(上バーは[複素数の共役](http://onohiro.hp.infoseek.co.jp/amanojack2/a/kisokaku018.htm)をあらわす) より

となる。

, とすれば、

プログラム化

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)