用matlab实现DFT FFT
目录
实验目的    2
实验内容    2
1.用MATLAB实现DFT    2
2.用MATLAB实现FFT，分析有限离散序列的FFT    3
3.通过分别计算时间，得出DFT与FFT的算法差异    7
实验原理    7
1. 离散傅里叶变换的快速算法FFT    7
2. FFT提高运算速度的原理    8
3. 理论分析DFT与FFT算法差异    10
实验步骤    11
实验结果    11
实验分析    19
实验结论    24
实验体会    24
实验目的
1. 通过研究DFT,FFT性质，用语言实现DFT, FFT。不使用MATLAB现有的FFT函数，自己编写具体算法。
2. 掌握FFT基2时间抽选法，理解其提高减少乘法运算次数提高运算速度的原理。
短时傅里叶变换matlab程序3. 设计实验，得出DFT和FFT算法差异的证明，如复杂度等(精度、不同长度的序列等）。
实验内容
1.用MATLAB实现DFT
    N点序列x(n) 的DFT为：
    DFT的矩阵为：
    根据DFT公式与矩阵展开，通过MATLAB实现DFT：
2.用Matlab实现FFT
编程思想及程序框图：
● 原位计算
因为DIT-FFT与DIF-FFT的算法类似，这里我们以DIT-FFT为例。N=2M点的FFT共进行M级运算，且每一级都由N/2个蝶形运算组成，后一级的节点数据由前一级同处一条水平线位置
的节点数据产生，所以我们同样可以将后一级的节点数据储存到前一级的节点中，这样的方法叫做原位计算，它大大节省了内存资源，降低了成本，简化了运算。
● 序列的倒序
无论是进行DIT-FFT还是DIF-FFT都需要进行倒序，包括输入倒序与输出倒序，以一定的方式将数组进行重新排列。
倒序的方法： 首先由于N=2M,我们就可以用M位二进制数来表示节点的顺序，并且按照奇偶时域抽取。然后，如图1所示，第一次按最低位n0的0、1值分解为奇偶组，第二次按次低位n1的0、1值分解为奇偶组，以此类推。最后，所得二进制数所对应的十进制数即为序列倒序后产生的序列。
图1 序列倒序过程
倒序的MATLAB方法：
用雷德算法可以对输入信号序列进行倒序重排，流程图如下所示：
● 蝴蝶因子的变化规律
在DIT-FFT中，每一级都由N/2个蝶形运算构成，每个蝶形运算包含一个蝴蝶因子，每一级的蝶形因子又有一定的变化规律：
设L表示自左而右的运算级次（L=1,2,3,…,M），序数R，次数K。
每个蝶形运算的两个输入量相距B=2^(L-1)个点。
假设N=8， 则M=3，这时有：
L=1 时， B=1， S=N/2， R=0， K=1: N/2 则有 P=(K-1)*1，所以
=， J=0,1,2,3
L=2 时， B=2， S=N/4， R=0: N/2:N-1， K=1: N/4 则有 P=(K-1)*2，所以
=， J=0,2
L=3 时， B=4， S=N/8， R=0: N/4:N-1， K=1: N/8 则有 P=(K-1)*4，所以
=， J=0
所以对于一般情况N=2M，第L 级的旋转因子为P=(K-1)*B。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。