CODEWITHSUNDEEP
pythonalgorithmfft
backwardsboy
backwardsboy

Reputation: 45

FFT Algorithm Bug

Attempting to implement the FFT Algorithm in python, and hitting a bug that I can't seem to figure out.

Here is my code:

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

when I run

x1 = FFT([1, 1, 2, 0])
print x1

print np.fft.fft([1, 1, 2, 0])

I get:

[(4+0j), (-1+1j), (2+0j), (-1-1j)]
[ 4.+0.j -1.-1.j  2.+0.j -1.+1.j]

So for index 1 and index 3, it's the complex conjugate. Any ideas?

Upvotes: 1

Views: 127

Answers (1)

SleuthEye
SleuthEye

Reputation: 14579

The definition of the forward Discrete Fourier Transform used by np.fft.fft is given by:

\begin{align}A_k &= \sum_{m=0}^{n-1} a_m \exp\left{-2\pi i \frac{m k}{n}\right}, &k=0,\dots,n-1\end{align}

You should notice the negative sign in the argument to the complex exponential.

In your implementation on the other hand, you are using a positive sign for the forward transform, and such an inversing in the sign of the arguments to the complex exponential results in conjugating the frequency spectrum.

So, for your implementation to yield the same results as np.fft.fft you simply have to invert the sign of the forward and backward transforms with:

z = +1 if inverse else -1

(instead of z = -1 if inverse else 1).

Upvotes: 2

Related Questions