fft2.m

radix 2 fft algorithm code

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


function [Y] = fft2(X)

N = length(X);

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

if(rem(N,2)~=0)
    return;
else
        
    for j=1:N/2
        
        yeven(j) = X(2*j);
        yodd(j) = X(2*j-1);
    
    end
    
    fftYEven = fft2(yeven);
    fftYOdd = fft2(yodd);
    
    for k=1:N/2
     
        Y(k) = fftYEven(k) + exp(-2*pi*i*(k-1)/N) * fftYOdd(k);
        Y(k+N/2) = fftYEven(k) - exp(-2*pi*i*(k-1)/N) * fftYOdd(k);
        
    end
    
    %disp(Y);
    
end;

end;