快速傅里叶变换算法错了一个减号

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

快速傅里叶变换算法错了一个减号

Fast Fourier Transform algorithm wrong by a single minus sign

python

signal-processing

fft

image-processing