function y=ctifft(x)
% algoritmo di Cooley-Tukey per il calcolo della IDFT
% utilizza il bit-reverse
% funziona solo con n potenza di due
% NOTA rispetto alla funzione di matlab ifft deve essere scalato con 1/n
% cioe' ctifft(x)=n*ifft(x)
n=length(x)
t=ceil(log2(n));

for j=0:n-1
    xt(j+1) = x(1+bitrev(j,t));
end

yt=zeros(n,1);
for c=t:-1:1
    m=2^(c-1);
    p=2^(t-c);
    W=exp((2*pi*i)/(2*p)*-(0:p-1)')
    for j=0:m-1
        xt((j*2+1)*p+1:(j+1)*2*p)=W.*xt((j*2+1)*p+1:(j+1)*2*p);
        yt(j*2*p+1:(j*2+1)*p)=xt(j*2*p+1:(j*2+1)*p)+xt((j*2+1)*p+1:(j+1)*2*p);
        yt((j*2+1)*p+1:(j+1)*2*p)=xt(j*2*p+1:(j*2+1)*p)-xt((j*2+1)*p+1:(j+1)*2*p);
    end
    xt=yt;
end
y=yt;

end

% calcola il bit reversal di a visto come numero di k bit
function b = bitrev(a,k)
if(a>=2^k)
    error('Input non valido');
end
b=0; 
for i=k:-1:1
    bit = rem(a,2);
    if(bit~=0)
        b = b + 2^(i-1);
    end
    a = floor(a/2);
end

end