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

Question

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 to test FFT implementation in C.

thanks, Andrey

score 7 · Accepted Answer · edited Jun 08 '11 at 14:42

7

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}

edited Jun 08 '11 at 14:42

Alberto Zaccagni

30,779
11
72
106

answered Jun 07 '11 at 21:25

Divij

878
2
9
18

2

Note that there is more than one "correct" answer and this is just one of them - there are at least 3 different ways of dealing with scaling factors. – Paul R Jul 31 '11 at 08:30

Oliver Charlesworth · Answer 2 · 2011-05-30T15:37:33.700

1

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?

edited May 30 '11 at 15:37

answered May 30 '11 at 14:52

Oliver Charlesworth

267,707
33
569
680

score 1 · Answer 3 · answered Jul 31 '11 at 08:28

1

According to Wolfram Alpha it's:

enter image description here

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

answered Jul 31 '11 at 08:28

Paul R

208,748
37
389
560

Where is the scaling factor coming from? – Rekin Nov 29 '12 at 21:53
@Rekin: as I mentioned above, there are at least 3 different ways of defining DFT and IDFT when it comes to scaling factor. You can scale by 1, sqrt(N) or N for each direction. – Paul R Nov 29 '12 at 21:56
Ok. Do you know of any advantages of having DFT scaled by the factor? Like, it seems to me the Factor and InverseFactor (the WolframAlpha functions) give the same results. Could it be because of the scaling? – Rekin Nov 29 '12 at 21:59
Yes, it really doesn't matter - it's just a convention - you just need to know which scaling factors your particular FFT implementation uses. – Paul R Nov 29 '12 at 22:34

score 0 · Answer 4 · answered Oct 11 '17 at 13:51

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}

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

4 Answers4