%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%一維的傅立葉變換的主函數，方便于二維傅立葉變換，以及DCT變換，以及反傅立葉變換調用使用%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function f=Y1FFT(x,N)
f=zeros(1,N);
for i=1:N
    f(i)=x(i);
end;
c=(-1)^(0.5);
r=log2(N);
for i=1:N/2
    w(i)=exp(-pi*2*i/N);
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%進行一維的快速傅立葉變換%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
j=0;    
    for i=0:1:N-1
        if (i<j)
            temp=f(j+1);
            f(j+1)=f(i+1);
            f(i+1)=temp;
        end;
        k=N/2;
        while k<(j+1)
            j=j-k;
            k=k/2;
        end;
        j=j+k;
    end;
    for i=1:1:r
        k=1;
        j=1;        
        for j=1:1:(i-1)
            k=k*2;
        end;
% %     for k=0:r-1
% %         for j=0:2^k-1
% %             bfsize=2^(r-k);
% %             for m=0:bfsize/2-1
% %                 p=j*bfsize;
% %                 temp(m+p+1)=f(m+p+1)+f(m+p+bfsize/2+1);
% %                temp(m+p+1+bfsize/2)=(f(m+p+1)-f(m+1+p+bfsize/2))*w(2^k*(m+1));
% %             end
% %         end
% %         tem=f;
% %         f=temp;
% %         temp=tem;
% %     end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%        對變換后的傅立葉的序列進行重新排序   %%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      W=(-c*2*pi)/2/k;
        j=0;
        while j<k
            m=j;
            while m<N
                l=m+k;
                temp=f(l+1)*exp(W*j);
                f(l+1)=f(m+1)-temp;
                f(m+1)=f(m+1)+temp;
                m=m+k*2;
            end;
            j=j+1;
        end;
    end;
end