快速傅里叶变换基2时间抽取FFT算法

快速傅里叶变换基2时间抽取FFT算法

7.4实验4：快速傅里叶变换-基2时间抽取FFT算法matlab实现

7.4.1实验目的

1.练习利用matlab6.5中工具箱中的信号处理函数

2.熟悉快速傅里叶变换的基本原理

3.熟悉基2DIT-FFT运算的MATLAB程序并运用

7.4.2涉及函数

信号处理函数X=fft(x)或者X=fft(x,N):

自定义功能函数function y=myfft(xr,n)

7.4.3实验原理与方法

1 DIT-FFT算法的基本原理

有限长序列x(n)的N点DFT定义为：，式中，其整数次幂简称为旋转因子。N符合2的整数幂，N为2的几次幂，则需要进行几次分解。碟形运算流图符号如下：

2 DIT-FFT算法的运算规律及编程思想

为了编写DIT-FFT算法的运算程序，首先要分析其运算规律，总结编程思想并绘出程序框图。由右图可知，DIT-FFT算法的运算过程很有规律。

2.1原位计算

对点的FFT共进行M级运算，每级由N/2个蝶形运算组成。在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素(存储单元)，这种原位(址)计算的方法可节省大量内存。

2.2蝶形运算

实现FFT运算的核心是蝶形运算，找出蝶形运算的规律是编程的基础。

for mm=1:m %将DFT做m次基2分解，从左到右，对每次分解作DFT运算

Nmr=2^mm;

u=1; %旋转因子u初始化x(k)=x(k)+t;M=nextpow2(length(xn)), N=2^M,1N=1024xlabel('

标签：FFT,傅里叶,抽取