CODEWITHSUNDEEP
pythonimage-processingsignal-processingfft
Simon Balfe
Simon Balfe

Reputation: 55

Fast Fourier Transform algorithm wrong by a single minus sign

So after watching this video on the fast fourier transform https://www.youtube.com/watch?v=h7apO7q16V0

I analysed the pseudocode and implemented it in python to find out that it was producing a different output to that of many fft calculator sites. My values seem to be all there its just odd, as the order is out of place, anyone know why. Is it a different kind of algorithm implementation or something.


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]))

The site I tested it against was https://tonysader.github.io/FFT_Calculator/? and I input into this site 0,1,2,3 and obtained: 6, -2+2J, -2, -2+-2J

whilst my python program output : 6, -2-2J, -2, -2+2J

The pseudocode I followed:

enter image description here

Upvotes: 2

Views: 407

Answers (1)

Frank Yellin
Frank Yellin

Reputation: 11240

I think the program you're running is executing the inverse FFT. Try omega = cmath.exp((-2 * cmath.pi * 1j)/n). Note the minus sign.

Upvotes: 2

Related Questions