%逆FFT算法（由編寫的FFT算法，只用將加權系數(WN)^k變為(W(-N))^k，并乘以1/N即可）
function x=myifft(a,N)                         %編寫fft函數，輸入變量為數組a，數組長度N，N須為2^m，m為正整數
                                              %輸出為經ifft變換后的x
m=log2(N);                                     %m進位
x=a;                                           %把輸入數組賦給x

%碼位倒置
x1=(-1)*ones(size(x));                    %初始化x1，用于儲存數據，并用-1做標記
for jj=1:length(x);                       %逐個掃描x
    if(x1(jj)<0)                          %如果x1中的數未被修改，則進行計算
                                          %(由于一次計算，對x中數進行交換，有時可以確定x1中兩個數，用來減少計算量) 
    d=0;                                  %d用來計算倒序后的數
    mm=m;pp=jj-1;                         %用mm記錄m，pp記錄jj-1 
    while(mm>0)                           %mm進行逆序循環，從m到1
    ww=mod(pp,2);pp=floor(pp/2);          %計算pp mod2的余數ww，（即二進制數），以及除數pp，用于下一次計算
    if (ww~=0&mm~=1)
        d=d+2^(mm-1);                     %將jj化為二進制數，并進行倒序，再還原成10進制數
    end
    if (ww~=0&mm==1)
        d=d+1;
    end
    mm=mm-1;
    end
    x1(jj)=x(d+1);                       %將x中相應坐標數進行調換，儲存在x1中
    x1(d+1)=x(jj);
    end
end
x=x1;clear x1;                          %將調換后的數賦予x，清除x1 

%組裝，蝶形計算
for jj=1:m                              %組裝次數循環，總共m次組裝
    y=zeros(size(x));                   %初始化y，用于儲存數據 
    h=2^jj;                             %每次組裝的旋轉因子下標，(W(-N))^k,這里N=h;
    bb=2^(jj-1);                        %旋轉因子上標最大值，即(W(-N))^k,(k=1,..,bb-1)
                                        %bb還表示每次組裝的兩個數據間隔 
    ff=2^(m-jj);                        %分組數
    gg=N/ff;                            %每組個數 
    for kk=1:ff                         %分組數循環，對每組內部進行組裝
    for ii=0:bb-1;                      %每組內進行組裝，ii表征兩組裝數據中起始數據的下標，為(kk-1)*gg+ii+1
                                        %ii還表征對應的旋轉因子為(WN)^ii,N=h
            WW=exp((j*2*pi*ii/h));     %計算旋轉因子
            y((kk-1)*gg+ii+1)=x((kk-1)*gg+ii+1)+x((kk-1)*gg+ii+bb+1)*WW;     
            y((kk-1)*gg+ii+1+bb)=x((kk-1)*gg+ii+1)-x((kk-1)*gg+ii+bb+1)*WW;    %組裝，蝶形運算 
    end
    end
    x=y;                                                                       %將該次組裝后的結果賦予x,以進行下一次組裝 
end
x=1/N*x;                            %逆變換結果乘以1/N 
clear y;