needed help in radix 4 algorithm

hello friends,

here i do my ifft coding with the help of the radix 4 algorithm

formulae is

y(l) = x(l) + x(l+N/2) + x(l+N/4) + x(l+3N/4);
z(l) = x(l) - x(l+N/2)+j(x(l+N/4) - x(l+3N/4);
g(l) = x(l) + x(l+N/2) - x(l+N/4) - x(l+3N/4);
h(l) = x(l) - x(l+N/2)-j(x(l+N/4) - x(l+3N/4);

with respect to above if i design for the 64 point i put N = 64.AND I
first i calculate the first stage of 4 16 points and after that i do
16 point ifft for 4 times.

here, i got the result of only 16 point ifft very correctly have to
check with matlab and correct result is obtained. if i go to 64 point
, i'm not able to obtain the output.

so pls guide me,, and i post my coding tomorrow.

senthil wrote:
> hello friends,
> 
> here i do my ifft coding with the help of the radix 4 algorithm
> 
> formulae is
> 
> y(l) = x(l) + x(l+N/2) + x(l+N/4) + x(l+3N/4);
> z(l) = x(l) - x(l+N/2)+j(x(l+N/4) - x(l+3N/4);
                           ^ what does this '(' match?
> g(l) = x(l) + x(l+N/2) - x(l+N/4) - x(l+3N/4);
> h(l) = x(l) - x(l+N/2)-j(x(l+N/4) - x(l+3N/4);
                           ^ what does this '(' match?

I assume:
   - twiddle factors were omitted from your description
   - y,z,g,h correspond to f0,f1,f2,f3
   - the missing parentheses above should be at the end of the line, 
just  before the ';'

If these assumptions are correct, the problem is your 'h' definition.

Compare your code above to the IDFT of size 4,

f0     | 1  1  1  1 |   F0
f1  =  | 1  j -1 -j | * F1
f2     | 1 -1  1 -1 |   F2
f3     | 1 -j -1  1 |   F3


I must ask, why are writing your own FFT?

Take a look at
http://sourceforge.net/projects/kissfft

If your needs are still not met by kissfft, fftw, or any of the other 
fine fft libraries around, you might still need to write your own.  The 
derivation in the files section of kissfft's project page could help.

It is a one-page derivation the mixed radix,decimation-in-time forward 
fft. The inverse fft is roughly the same derivation with sign changes. 
(I guess I should mention that in the pdf.)


Regards,
Mark Borgerding