python - 快速傅立叶变换算法因单个减号而错误

Question

观看此有关快速傅立叶变换的视频后 https://www.youtube.com/watch?v=h7apO7q16V0

我分析了伪代码并在 python 中实现它，发现它产生的输出与许多 fft 计算器网站的输出不同。我的值(value)观似乎都在那里，这很奇怪，因为顺序不合适，任何人都知道为什么。是一种不同类型的算法实现还是什么。

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)。注意减号。