what is correct result after FFT, if input array is {0,1,2,3,4,5,6,7}

can anyone tell me what is correct result after Fast Furier Transform, if input array is {0,1,2,3,4,5,6,7}.

I got {28,0,0,0,0,0,0,0}. It isn't correct right?

just want开发者_如何学C to test FFT implementation in C.

thanks, Andrey

The correct answer to a FFT for {0,1,2,3,4,5,6,7} is

{28.0000 + 0.0000i, 
-4.0000 + 9.6569i,
-4.0000 + 4.0000i,
-4.0000 + 1.6569i,
-4.0000 + 0.0000i, 
-4.0000 - 1.6569i,
-4.0000 - 4.0000i,
-4.0000 - 9.6569i}

No, it isn't correct (a single non-zero output element implies that your input consists of either a constant value, or a single complex-exponential component).

Why don't you use an existing FFT implementation, such as FFTW to provide a reference result? Or just implement a straightforward DFT?

According to Wolfram Alpha it's:

Note that there is no single "correct answer" as there is more than one definition of the DFT/FFT, the difference between each one being what scaling factor you include for forward and inverse transform. (The difference between this answer and the earlier accepted answer is just a scaling factor of sqrt(8)).

Divij answer assumes that input {0,1,2,3,4,5,6,7} has size=8, that is:

{0,0i},{1,0i},{2,0i},{3,0i},{4,0i},{5,0i},{6,0i}

for input considered as binary complex with size=4, that is:

{0,1i},{2,3i},{4,5i},{6,7i}, the result is:

{12, 16i}
{-8, 0i}
{-4, -4i}
{0, -8i}