fft4.m

radix 2 fft algorithm code

%
% Computes the fft of vector X 
% Using radix-4 FFT algorithm, time-decimation Programmed by
% F.PATIN aka YOV408
%


function [Y] = fft4(X)

N = length(X);

if (N==1)
    Y = -X;
    return;
end;    

if(rem(N,4)~=0)
    return;
else
        
    for j=1:N/4
        
        y0(j) = X(4*j);
        y1(j) = X(4*j-3);
        y2(j) = X(4*j-2);
        y3(j) = X(4*j-1);
    
    end
    
    fft00 = fft4(y0);
    fft11 = fft4(y1);
    fft22 = fft4(y2);
    fft33 = fft4(y3);
    
    for k=1:N/4
     
        Y(k) = fft00(k) + exp(-2*pi*i*(k-1)/N) * fft33(k) + exp(-4*pi*i*(k-1)/N) * fft22(k) + exp(-6*pi*i*(k-1)/N) * fft11(k);
        Y(k+N/4) = fft00(k) + exp(-2*pi*i*((k+N/4)-1)/N) * fft33(k) + exp(-4*pi*i*((k+N/4)-1)/N) * fft22(k) + exp(-6*pi*i*((k+N/4)-1)/N) * fft11(k);
        Y(k+N/2) = fft00(k) + exp(-2*pi*i*((k+N/2)-1)/N) * fft33(k) + exp(-4*pi*i*((k+N/2)-1)/N) * fft22(k) + exp(-6*pi*i*((k+N/2)-1)/N) * fft11(k);
        Y(k+3*N/4) = fft00(k) + exp(-2*pi*i*((k+3*N/4)-1)/N) * fft33(k) + exp(-4*pi*i*((k+3*N/4)-1)/N) * fft22(k) + exp(-6*pi*i*((k+3*N/4)-1)/N) * fft11(k);
        
    end
    
    %disp(Y);
    
end;

end;