Hi all,

I have been working on this for quite sometime and am frustrated. I am using the GNU Scientific Library gsl. I am wanting to compute a FFT over some n that is not nessecarily a multiple of 2. I have got the FFT Radix-2 function to work with 512. The Mixed-Radix function works for some values of n but not all. There is nothing in the documentation that says n has to anything in particular. I have found a work around and that is to zero-pad my data until it is a multiple of 2 and then transform, but the output is not as clear as compared without the zero-pad. I've included a link to the documentation of gsl's FFT. I've also included my code.

http://www.gnu.org/software/gsl/manual/gsl-ref_15.html#SEC237
//////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////

//FFT with n= 575 only outputs one frequency not both the 50Hz and 120Hz

//FFT with n=512 returns both frequencies, try it if you want to see the output

const int n= 575;

double dataFFT[2*n];

gsl_fft_complex_wavetable *wavetable;

gsl_fft_complex_workspace *workspace;

int index= 0;

for (index= 0; index < n; index++)

{

REAL(dataFFT,index)= 0.0;

IMAG(dataFFT,index)= 0.0;

}

wavetable= gsl_fft_complex_wavetable_alloc (n);

workspace= gsl_fft_complex_workspace_alloc (n);

for (index= 0; indexi < wavetable->nf; index++)

{

printf ("# factor %d: %d\n", testi, wavetable->factor[testi]);

}

//setup an array of time in seconds incrementing by .001

float t[n];

int index_t= 0;

for(index_t= 0; index_t < n; index_t++)

{

t[index_t]= 0.001* index_t;

// printf("%f\n", t[index_t]);

}

//equation to calculate, two frequencies are 50Hz and 120Hz

float x[n];

int index_x= 0;

for(index_x= 0; index_x < n; index_x++)

{

x[index_x]= (sin(2*M_PI*50*t[index_x])+ sin(2*M_PI*120*t[index_x]));

// printf("%f\n", x[index_x]);

}

int index_FFT= 0;

//setup the complex dataFFT array

for (index_FFT= 0; index_FFT < n; index_FFT++)

{

REAL(dataFFT,index_FFT) = x[index_FFT];

IMAG(dataFFT,index_FFT) = 0.0;

//printf("%f +%f\n", REAL(dataFFT2, index_FFT), IMAG(dataFFT2, index_FFT));

}

//Mixed-Radix FFT function

gsl_fft_complex_forward (dataFFT, 1, n, wavetable, workspace);

//Radix-2 Function for when n=512

//gsl_fft_complex_radix2_forward (dataFFT, 1, 512);

//Output dataFFT

for (index_FFT= 0; index_FFT < n; index_FFT++)

{

printf("%f+%fi\n", REAL(dataFFT, index_FFT), IMAG(dataFFT, index_FFT));

}

gsl_fft_complex_wavetable_free (wavetable);

gsl_fft_complex_workspace_free (workspace);

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

thank you,

m.
One deals with calculating FFT (that is, Fast Fourier Transform, strictly for 2^x samples) when you zero-pad your data then apply some windowing function so that the results of the transform will be more "nice".

The other thread is about your original question, the Mixed-Radix algorithm that is NOT (repeat, not) FFT, only an optimization to calculate DFT if N has small factors (such as 3, 4, ... 10).

As the two methods work in a completely different way, don't expect the results to be the same. For your example zero-padded FFT will never be accurate whichever windowing function do you apply to your samples. The Mixed-Radix algorithm is accurate, however, it's much slower. The difference is quite similar to the situation whether you calculate sine function with some accurate algorithm or using some components of its Chebishev polinomial. The second is fast but inaccurate. However, depending on the task its accuracy may be enough. Just as for zero-padded FFT.

I hope it clears the things a bit.