fft_self.m

OFDM系统

%自己定义的FFT函数，算法采用的就是课本上讲的雷德算法

function y = FFT_self(x,M)

%--------------------------------------------------------------------------
%下面这部分是当输入序列的长度不为2的指数幂时在序列后补零达到2的指数幂的长度
q = nextpow2(M);                          %返回第一个q使得 2^q >= abs(M)
N = 2^q;
if M<N
    x=[x,zeros(1,N-M)];                   %在序列后面补零
end
%--------------------------------------------------------------------------
%实际的FFT算法
%--------------------------------------------------------------------------
%这一部分是用于变址
nv2=N/2;
nm1=N-1;
i=0;                                      %用于表示自然顺序的输入数据
p=0;                                      %用于表示倒位序的数据
while i<nm1                        
    if i<p                                %当i<p时要进行变址，在i>p时不需要变址，可以避免重复换址
        t=x(p+1);
        x(p+1)=x(i+1);
        x(i+1)=t;
    end
    k=nv2;                                %nv2二进制的高位为1，其他位为0
%---------------------------------已知某个倒位序数，求下一个倒位序数
    while k<=p                            %P的高位为1，减去N/2将高位变为0
        p=p-k;
        k=k/2;                            %用于次高位的处理
    end
    p=p+k;                                %当P的高位为0时，直接加N/2变为1
    i=i+1;
end
%--------------------------------------------------------------------------
%L级递推计算
l=1;                              
m=log2(N);                                %蝶形运算的级数
while l<=m                        
    le=2^l;                               %各蝶形结依次的距离
    le1=le/2;                             %同一种蝶形结构中参加运算的两节点的间距
    u=1;                                  %开始的exp(-j*2*pi*0/N)
    w=exp(-j*2*pi/le);                    %每一级的系数
    p=0;
    while p<le1;                          %这层循环控制不同旋转因子的碟形结
        i=p;
        while i<N                         %这层循环控制同一种蝶形结的运算
            ip=i +le1;                    %i为蝶形结中一个点，ip是另一个点
            t=u*x(ip+1);                  %下面三句就是进行相应的蝶形运算
            x(ip+1)=x(i+1)-t;
            x(i+1)=t+x(i+1);
            i=i+le;                       
        end
        u=u*w;                            %改变不同蝶形结的旋转因子
        p=p+1;
    end
    l=l+1;
end
y = x;                                    %把经过FFT处理后的输入序列x传递给输出序列y