FFT算法错误

Question

尝试在python中实现FFT算法，并遇到一个我似乎无法解决的错误。

这里是我的代码：

def FFT(co, inverse=False): 
    if len(co) <= 1: 
    return co 

    even = FFT(co[::2], inverse) 
    odd = FFT(co[1::2], inverse) 

    y = [0] * len(co) 
    z = -1 if inverse else 1 

    for k in range(0, len(co)//2): 
    w = np.round(math.e**(z*1j*math.pi*(2*k/len(co))), decimals=10) 
    y[k] = even[k] + w*odd[k] 
    y[k + len(co)//2] = even[k] - w*odd[k] 

return y 

当我运行

x1 = FFT([1, 1, 2, 0]) 
print x1 

print np.fft.fft([1, 1, 2, 0]) 

我得到：

[(4+0j), (-1+1j), (2+0j), (-1-1j)] 
[ 4.+0.j -1.-1.j 2.+0.j -1.+1.j] 

所以对于指数1和指数3，它的复共轭。有任何想法吗？

Answer 1

的definition of the forward Discrete Fourier Transform used by np.fft.fft由下式给出：

你应该注意到在参数复指数的负号。

在您的实现，另一方面，你正在使用的一个积极的迹象变换，并在共轭频谱中的参数复指数结果符号这样的反演。

因此，对于您的实现产生相同的结果np.fft.fft你只需要翻转向前和向后转换的标志：

z = +1 if inverse else -1 

（而不是z = -1 if inverse else 1）。