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）。

FFT算法错误

FFT Algorithm Bug

python

algorithm

fft