# Fourier transformation

Could someone be kind enough to review this Fourier transformation, please? I'm especially interested in going about unit testing the code (I don't really know where to begin, beyond applying the fft twice to retrieve the input), and have left test functions blank.

If you do spot a bug (and no doubt there are some), please don't tell me. I'd like to find them myself.

/*
A simple radix 2 fast fourier transform.
*/

#include <complex>
#include <iostream>
#include <cassert>
#define _USE_MATH_DEFINES
#include <cmath>

typedef std::complex<double> Complex;

void TestSpike(Complex* data, int length){
assert( 1.0 == data[1]);
}

//Generates a spike in the DC bin, used for testing the fft
void GenerateSpike(Complex* data, int length){
for(int i = 0 ; i < length ; i++)
{
if(1 == i){
data[i] = 1.0;
} else {
data[i] =  0.0;
}
}
TestSpike(data, length);
}

void TestTwiddle(){
}

void TestButterfly(){
}

Complex w(int bin, int length){
return (cos(2*M_PI*bin/length), sin(2*M_PI*bin/length));
}

void butterfly(Complex* data, int bin, int stepSize, int fftlength){
Complex x0 = data[bin];
Complex x1 = data[bin+stepSize];

data[bin]          = x0 + w(bin, fftlength)*x1;
data[bin+stepSize] = x0 - w(bin, fftlength)*x1;
}

//Decimation in time
void FFT(Complex *data, int length){
for(int bflySize = 2 ; bflySize < length ; bflySize *= 2)
{
int numBflys = length/bflySize;
for(int i = 0 ; i < numBflys ; i++)
{
int stepSize = bflySize/2;
for(int j = 0 ; j < bflySize ; j+= stepSize)
{
butterfly(data, (bflySize*i)+j, bflySize/2, length);
}
}
}
}

int Reverse(unsigned int i, int size){
int reversed = 0;
while(size > 1){
reversed = (reversed >> 1) | (i & 1);
i >>= 1;
size >>= 1;
}
return reversed;
}

int main(int argv, char** argc){

int length;
std::cout << "Please input the length of the FFT" << std::endl;
std::cin >> length;
std::complex<double> data[length];
GenerateSpike(data, length);
FFT(data, length);
for(int i = 0 ; i < length ; i++)
{
int j = Reverse(i,length);
std::cout << data[j] << std:: endl;
}
return 0;
}

• Wish I knew enough C++ to be of help here. I remember the fourier transform from image processing class - it was fun. – George Mauer Mar 2 '12 at 21:59

Using operator== on doubles isn't usually a good idea, although it may be okay in the TestSpike case as you know you've assigned exactly 1.0 to it previously.

I would write GenerateSpike as follows:

void GenerateSpike(Complex* data, int length) {
std::fill(data, data+length, 0.0);
if (length >= 2)
data[1] = 1.0;
}


By the way, you're not checking that the array is of sufficient length in TestSpike.

stepSize in FFT does not depend on the parameters of the second-outermost loop, so it should be in the outermost loop. You should also use stepSize instead of bflySize/2 in the call to butterfly.

About testing: w, butterfly, Reverse, and FFT all seem to be pure functions, so you can test them simply by checking the return value. You might want to get a framework like GTest or Boost.Test to make them easier to write.