myifft.m

自己编写的matlab中的逆FFT变换

%逆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;