不同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('复杂度');
A548
4.完整算法代码文件
V
相关文章
- 倒立摆仿真_基于matlab单摆运动仿真模拟
- MATLAB绘制三维图形z=5_plot3用法
- matlab 求矩阵秩,求Matlab中矩阵的秩和迹 | 学步园[通俗易懂]
- 手眼标定算法Tsai-Lenz代码实现(Python、C++、Matlab)
- 各种智能优化算法比较与实现(matlab版)
- matlab中错误使用fmincon,MATLAB中fmincon 函数问题
- matlab fir带通滤波,基于Matlab的FIR带通滤波器设计与实现
- 卡尔曼滤波应用及其matlab实现
- 神经网络学习笔记1——BP神经网络原理到编程实现(matlab,python)[通俗易懂]
- matlab fopen fread_matlab中prctile函数
- 香农编码的matlab实现总结_matlab简单代码实例
- matlab将txt数据分类,MATLAB读取txt文件,txt里面有字符串和数值两种类型
- 遗传算法matlab程序简单实例_遗传算法的matlab实现
- matlab保存所有图,Matlab中图片保存的5种方法
- 直方图均衡化(Matlab实现)
- zigzag扫描matlab,ZIGZAG扫描的MATLAB实现
- matlab中ewma实现,ewma 移动平均模型
- butterworth matlab,Matlab实现Butterworth滤波器
- Matlab中的画图函数
- matlab 加权回归估计_Matlab:地理加权回归基本操作「建议收藏」
- Matlab循环语句_matlab中if语句的用法
- MATLAB仿真-抽取滤波