一次负号错误的快速傅里叶变换算法

Question

所以在快速傅里叶变换https://www.youtube.com/watch?v=h7apO7q16V0上看了这段视频之后

我分析了伪代码，并在python中实现了它，以发现它产生的输出与许多fft计算器站点的输出不同。我的价值观似乎都在那里是一种不同的算法实现还是别的什么。

import cmath
import math
def FFT(P):
    n= len(P)

    if n == 1:
        return P

    omega = cmath.exp((2 * cmath.pi * 1j)/n)

    p_even = P[::2]
    p_odd = P[1::2]

    y_even = FFT(p_even)
    y_odd = FFT(p_odd)

    y = [0] * n

    
    for i in range(n//2):
        y[i] = y_even[i] + omega**i*y_odd[i]
        y[i+n//2] = y_even[i] - omega**i*y_odd[i]
    return y

    
poly = [0,1,2,3]
print(FFT([0,1,2,3]))

我测试它的网站是https://tonysader.github.io/FFT_Calculator/？我输入这个站点0,1,2,3，得到: 6，-2+2J，-2，-2+-2J

而我的python程序输出: 6，-2-2J，-2，-2+2J

我所遵循的伪码：

​

​

Answer 1

我认为你正在运行的程序正在执行逆FFT。试试omega = cmath.exp((-2 * cmath.pi * 1j)/n)。注意减号。