function FD = exfft(TD,r)
%----------------------------------
%   Name:   exfft
%   Param: 
%           TD      -時域序列
%           r       -2的冪數，即迭代次數
%   Return:
%           FD      -頻域序列
%   Desc:   對給定的序列進行快速傅立葉變換
%   By:     
%-----------------------------------
count = 2^r;    % 計算變換點數

% 分別用來保存蝶形運算的輸入和輸出
X1 = zeros(1,2^r);
X2 = zeros(1,2^r);


% 計算加權系數
W = zeros(1,count/2);
for j=1:count/2
    angle = j*3.1415926*2/count;
    W(1,j)=cos(angle)-i*sin(angle);
end

% 采用蝶形算法進行快速傅立葉變換
X1=TD;
for k=1:r   % 迭代次數
    for j=1:(2^k)     % 該次迭代有 2*k 個部分
        bfSize = 2^(r-k);   % 每部分的點數
        for l=1:bfSize/2
            p=(j-1)*bfSize;
            X2(1,l+p) = X1(1,l+p) + X1(1,l+p+bfSize/2);
            X2(1,l+p+bfSize/2) = (X1(1,l+p) - X1(1,l+p+bfSize/2))*W(1,l*(2^k));
        end
    end
    % 將結果X2作為下一次迭代的輸入
    X=X1;
    X1=X2;
    X2=X;
end
% 重新排序
FD=bitrevorder(X2)