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?