3 Attachment(s)

Having issues with my FFT

I coded up an FFT, and I'm having issues with it. I can't figure out what the problem is. It's not the 1st time I've coded the FFT, and I've compared my new FFT code (in C++) to a previous time I coded the FFT (in C#), and I don't personally see any mistakes in the way I've coded it (although the two implementations have some minor semantic differences).

Here is the graph of the signal I am sending into the function:

Attachment 9674

Here is the graph I should get as output:

Attachment 9672

And here is what I really am getting as output:

Attachment 9673

The output off the fft looks oddly like the sync function...which shouldn't be the result for a simple sine wave...

Here is my code:

Code:

`std::vector < std::complex<double> > InternalFastFourierTransform (std::vector < std::complex<double> > input)`

{

static std::complex<double> i = std::complex<double>(0, 1);

static std::complex<double> NegativeTwoPiI = -2.0 * PI * i;

int N = (int)input.size();

int halfN = N / 2;

if (N == 1)

{

return input;

}

else

{

//Recurse and get evens/odds

std::vector< std::complex<double> > evens = InternalFastFourierTransform( GetVectorRange(input, 0, N, 2) );

std::vector< std::complex<double> > odds = InternalFastFourierTransform( GetVectorRange(input, 1, N, 2) );

//Combine

std::vector< std::complex<double> > result = std::vector< std::complex<double> > (N);

for(int k = 0; k < halfN; k++)

{

std::complex<double> exponent = std::exp(NegativeTwoPiI * double(k / N));

result[k] = evens[k] + exponent * odds[k];

result[k + halfN] = evens[k] - exponent * odds[k];

}

return result;

}

}

Do you guys see anything wrong? The only thing that I could see is that possibly my function GetVectorRange which takes a slice of a vector from some starting index to some ending index at a stride of 2 could be functiong incorrectly...I haven't thoroughly tested that function...but is that really the problem, or do you think it could be some math mistake based off of the graph output?