fft＆ifft算法.m

按时间抽取基_2 快速傅立叶变化算法及其逆变换算法.

%%按时间抽取基_2 FFT算法及IFFT算法

%按时间存抽取的IDFFT运算
%输入inx,输出INX
clear all
inx=[1+2*j,2+3*j,4,5]
x=conj(inx);



%%输入顺序，输出顺序的按时间抽取的FFT算法
%input x;output X

%补零 输入x，输出A
%若序列x的长度NN不是2的整数次幂，则进行补零，补至2.^(log2NN)< N< 2.^((log2NN)+1)

%x=1:8;  %输入

NN=length(x);  %NN为原始序列的长度,N为补零后的序列长度，L＝log2（N）
LL=log2(NN);
if fix(LL)==LL
    N=NN;
    L=LL;
    A=x;
else
    L=fix(LL)+1;
    N=2.^L;
    A=[x,zeros(1,N-NN)];
end
A
L
N





%%倒位序运算

%生成数列 R'＝[2.^(L-1),2.^(L-2),. . . 2.^2,2,1];
k=1:L;
R=[];
for r=L-1:-1:0
    RR=2.^r;
    R=[R,RR];
end
R=R';
R

%十进制到二进制的转换
B=[];MB=[];

for p=0:N-1
    for pp=0:L-1
        BB=mod(fix(p/(2.^pp)),2);
        B=[B,BB];
    end   
end
B

%二进制转换为十进制数，同时生成BR,BR为倒位序列各元素在原序列中所占位置序号
for nn=0:N-1
    BBb=B((1+nn*L):(L+nn*L))
    MB=[MB
       BBb];
end
BR=MB*R;
BR=BR';
BR

%利用BR,进行倒位交换，得到a，即为对原始序列x的倒位序列，在下一步对a进行蝶型运算
a=zeros(1,N)
a(1)=A(1);
a(N)=A(N);
for g=2:N-1
    BRg=BR(g)
    a(g)=A(BRg+1)
end
a





%%蝶型运算
for m=1:L
    ld=2^m;
    ldd=ld/2;
    u=1;
    W=exp(-pi*j/ldd);
    for J=0:ldd-1
        for I=J:ld:N-1
            p=I+ldd;
            C=a(p+1)*u;
            a(p+1)=a(I+1)-C;
            a(I+1)=a(I+1)+C;
            
        end
        u=u*W;
    end
end
X=a;
X   %输出,FFT算法倒此结束

%进行idfft的运算
INX=conj(X)/N;
INX