不同Radix实现方式的快速傅里叶变换复杂度matlab仿真分析,对比基2,基4以及分裂基

1.算法仿真效果
matlab2022a仿真结果如下：

2.算法涉及理论知识概要
快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
FFT的基本思想是把原始的N点序列，依次分解成一系列的短序列。充分利用DFT计算式中指数因子 所具有的对称性质和周期性质，进而求出这些短序列相应的DFT并进行适当组合，达到删除重复计算，减少乘法运算和简化结构的目的。此后，在这思想基础上又开发了高基和分裂基等快速算法，随着数字技术的高速发展，1976年出现建立在数论和多项式理论基础上的维诺格勒傅里叶变换算法(WFTA）和素因子傅里叶变换算法。它们的共同特点是，当N是素数时，可以将DFT算转化为求循环卷积，从而更进一步减少乘法次数，提高速度。

基2 FFT

根据上面的对称性，我们可以将FFT计算分为两个较小的部分

    这样一个N点变换就分解为了两个N/2点变换，这里F 1 ( k ) F_1(k)F 1 (k)和F 2 ( k ) F_2(k)F 2(k)分别是序列x中的奇数号和偶数号序列的N / 2 N/2N/2点DFT变换。

分裂基快速傅里叶变换：

   由此可见，一个NN点的DFT 可以分解为一个N/2N/2点的DFT 和两个N/4N/4点的DFT 。这种分解既有基2的部分，又有基4的部分，因此称为分裂基分解。上面的N/2N/2点DFT 又可分解为一个N/4N/4点的DFT 和两个N/8N/8点的DFT, 而两个N/4N/4点的DFT也分别可以分解为一个N/8N/8点的DFT和两个N/16N/16点的DFT 。依此类推，直至分解到最后一级为止。这就是按频率抽取的分裂基快速傅立叶变换算法。

    分裂基快速算法是将基2和基4分解组合而成。在基2m2m类快速算法中，分裂基算法具有最少的运算量，且仍保留结构规则、原位计算等优点。

3.MATLAB核心程序

N     = 2.^(2:1:17);
L     = length(N);

TIMES = zeros(4,L);   

for k = 1:L

   for ij = 1:2000
       [k,ij]
        a  = randn(1,N(k)) + 1i*randn(1,N(k));

        tic
        A1 = fft(a);
        TIMES(1,k,ij) = toc; 


        tic
        A2 = radix2fft(a);
        TIMES(2,k,ij) = toc; 


        tic
        A3 = radix4fft(a);
        TIMES(3,k,ij) = toc; 


        tic
        A4 = splitradixfft(a);
        TIMES(4,k,ij) = toc; 
   end
end 


figure;
semilogy(log2(N),mean(TIMES(1,:,:),3),'-bs',...
    'LineWidth',1,...
    'MarkerSize',6,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.9,0.0,0.0]);
hold on;
semilogy(log2(N),mean(TIMES(2,:,:),3),'-mo',...
    'LineWidth',1,...
    'MarkerSize',6,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.5,0.9,0.0]);
hold on;
semilogy(log2(N),mean(TIMES(3,:,:),3),'-b^',...
    'LineWidth',1,...
    'MarkerSize',6,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.2,0.9,0.5]);
hold on;
semilogy(log2(N),mean(TIMES(4,:,:),3),'-r>',...
    'LineWidth',1,...
    'MarkerSize',6,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.9,0.9,0.0]);
grid on;
legend('MATLAB自带FFT函数','Radix-2 FFT','Radix-4 FFT','Split-Radix FFT');
xlabel('log_2(length(x))');
ylabel('复杂度');