function Y=CooleyTukey(X,p); 

% Y = CooleyTukey(X,p); 
%Etant donné un entier naturel non nul p et un vecteur colonne 
%X de longueur N=2^p, multiplie à gauche le vecteur X par la matrice 
%de transformée de Fourier discrète d'entrées exp(-2i*pi*j*k/2^p)
%pour j,k entre 0 et 2^p-1. Le résultat est identique à celui 
%fourni par la routine Y=fft(X,N) avec N=2^p.  
 
if p == 1
    Y=[X(1)+X(2);X(1)-X(2)]; 
else 
    Y=zeros(2^p,1); 
    Xpair=X(1:2:2^p); 
    Ximpair=X(2:2:2^p); 
    Ypair=CooleyTukey(Xpair,p-1); 
    Yimpair=CooleyTukey(Ximpair,p-1); 
    K=0:2^(p-1)-1; 
    W=exp(-2*i*pi*K'/2^p); 
    Yimpair=Yimpair.*W; 
    for k=1:2^(p-1)
        Y(k)=Ypair(k)+Yimpair(k); 
        Y(2^(p-1)+k)=Ypair(k)-Yimpair(k); 
    end
end

    
