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

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

时间:2023-05-24 15:35:23浏览次数:40  
标签:... Radix 变换 DFT 复杂度 FFT TIMES 算法 matlab

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('复杂度');

 

  

 

标签:...,Radix,变换,DFT,复杂度,FFT,TIMES,算法,matlab
From: https://www.cnblogs.com/51matlab/p/17428442.html

相关文章

  • 不同Radix实现方式的快速傅里叶变换复杂度matlab仿真分析,对比基2,基4以及分裂基
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要快速傅里叶变换(fastFouriertransform),即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶......
  • m基于UKF控制器的倒立摆控制系统matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:    2.算法涉及理论知识概要       倒立摆控制,使摆杆尽快达到平衡位置,且无大的振荡和过大的角度和速度的控制系统。当摆杆到达期望位置后,系统能克服随机扰动而保持稳定。该控制系统的输入为小车的位移(即位置)和摆杆的倾......
  • matlab中通过ode函数求解常微分方程附加简单的钟摆模型
    ✅作者简介:热爱科研的算法开发者,Python、Matlab项目可交流、沟通、学习。......
  • 基于PSO优化的SVM数据预测算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:     2.算法涉及理论知识概要         支持向量机(supportvectormachines,SVM)是二分类算法,所谓二分类即把具有多个特性(属性)的数据分为两类,目前主流机器学习算法中,神经网络等其他机器学习模型已经能很好完成二分......
  • m基于MIMO-OFDM-LDPC-STBC的通信链路matlab误码率仿真
    1.算法仿真效果matlab2013b仿真结果如下:使用一个二值图进行测试,并加入不同的均衡算法进行对比:2.算法涉及理论知识概要LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究......
  • m基于MIMO-OFDM-LDPC-STBC的通信链路matlab误码率仿真
    1.算法仿真效果matlab2013b仿真结果如下:    使用一个二值图进行测试,并加入不同的均衡算法进行对比:  2.算法涉及理论知识概要          LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎......
  • m基于matlab的LDPC译码算法性能仿真,对比BP译码,最小和译码以及归一化偏移最小和译码
    1.算法仿真效果matlab2022a仿真结果如下:  2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和......
  • MATLAB用GARCH-EVT-Copula极值理论模型VaR预测分析股票投资组合|附代码数据
    全文链接:http://tecdat.cn/?p=30426最近我们被客户要求撰写关于GARCH-EVT-Copula的研究报告,包括一些图形和统计输出。对VaR计算方法的改进,以更好的度量开放式基金的风险。本项目把基金所持股票看成是一个投资组合,引入Copula来描述多只股票间的非线性相关性,构建多元GARCH-EVT-Cop......
  • 基于matlab的LDPC译码算法误码率对比仿真,对比BP和BF译码
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现简单,易于进行理论分......
  • 基于matlab的LDPC译码算法误码率对比仿真,对比BP和BF译码
    1.算法仿真效果matlab2022a仿真结果如下: 2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现......