FFT Algorithm Bug

Question

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?

Have you tried z = +1 if inverse else -1?

SleuthEye
– SleuthEye

2017-04-05 20:05:45 +00:00
Commented Apr 5, 2017 at 20:05 — SleuthEye
– SleuthEye, Commented Apr 5, 2017 at 20:05
Yup... that worked! Thanks

backwardsboy
– backwardsboy

2017-04-05 20:39:21 +00:00
Commented Apr 5, 2017 at 20:39 — backwardsboy
– backwardsboy, Commented Apr 5, 2017 at 20:39

SleuthEye · Accepted Answer · 2017-04-05 21:46:26Z

2

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

answered Apr 5, 2017 at 21:46

SleuthEye

14.6k2 gold badges37 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

FFT Algorithm Bug

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related