资源描述：
《快速傅里叶变换(FFT)描述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、卢光跃通信与信息工程学院第4章快速傅里叶变换第4章快速傅里叶变换4.1引言4.2直接计算DFT的问题及改进的途径4.3按时间抽取（DIT）的基2-FFT算法4.4按频率抽取（DIF）的基2-FFT算法4.5IDFT的高效算法4.6FFT的其他应用—快速卷积学习目标理解按时间抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点；理解按频率抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点；理解IFFT算法；§4.1引言快速傅里叶变换（FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种
2、快速算法。在信号的频谱分析、系统的分析、设计和实现中都会用到DFT计算，但计算量太大，难以对问题进行实时处理。1965年首次发现DFT的一种快速算法后，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，这就是快速傅里叶变换（FFT）的算法。FFT出现后使DFT的运算大大简化，运算时间一般可缩短一二个数量级之多，使DFT的运算在实际中真正得到了广泛的应用。§4.2直接计算DFT的问题及改进的途径一、直接计算DFT的运算量问题设x(n)为N点有限长序列，其DFT为k=0,1,…,
3、N-1反变换（IDFT）为n=0,1,…,N-1正变换运算量一个X(k)复数乘法复数加法NN-1N2N(N-1)N个X(k)N2二、改进的途径与两个因素有关x(n)长序列——>短序列WNkn（根据短序列生成方式的不同）旋转因子（在将数据抽取时充分利用旋转因子的性质来降低运算量）§4.3按时间抽取（DIT）的基-2FFT算法一、算法原理1.一次分解N→N/2设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：k=0,1,…..,N/2-1X1(k)与X2(k)分别是
4、x1(r)及x2(r)的N/2点DFT：一个N点DFT已分解成两个N/2点的DFT利用DFT的隐含周期性,求X(k)的后半部分k=N/2,…..,N-1将k+N/2代入，于是k=0,…..,N/2-1蝶形运算可见，为得到原始序列的DFT，需要的步骤：1）分别抽取奇数点序列和偶数点序列2）分别对奇数点序列和偶数点序列进行DFT运算3）完成上述运算（蝶形运算）N点（N=8）DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)
5、X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X2(0)-1-1-1-1WN0WN1WN2WN3N/2点DFTN/2点DFTx(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)N点DFT分解为两个N/2点DFT+N/2个蝶形运算2.二次分解N/2→N/4对奇数点序列继续进行奇数点和偶数点的抽取，得到新序列如下：2.二次分解N/2→N/4X2(k)也可进行同样的分解：x(0)=x1(0)x(2
6、)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)N/2点DFTN/2点DFTX1(0)X(0)X1(1)X(1)X1(2)X(2)X1(3)X(3)X2(1)X(5)X2(2)X(6)X2(3)X(7)X2(0)X(4)-1-1-1-1WN0WN1WN2WN3N/2点DFT分解为两个N/4点DFT+2个蝶形运算一个N=8点DFT分解为四个N/4点DFT+相应的蝶形运算N=8，四个N/4点DFT即四个2点DFT，其输出分别为：X
7、3(k)，X4(k)，X5(k)，X6(k)，k=0,1k=0,1以X3(k)为例N=8按时间抽取的FFT运算流图N=8时共有三级蝶形运算，每一级有N/2=4个蝶形X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)二、按时间抽取的FFT算法与直接计算DFT运算量的比较N=2M时，共有M级蝶形，每级都由N/2个蝶形运算组成；每
8、个蝶形需要一次复乘、二次复加；每级运算都需N/2次复乘和N次复加；M级运算总共需要：复乘数复加数以乘法为例，直接DFT复数乘法次数是N2，FFT复数乘法次数是(N/2)log2N；直接计算DFT与FFT算法的复数乘法计算量之比为：当N=2048时，这一比值为372.4，即直接计算DFT的运算量是FFT运算量的372.4倍；当点数N越大时，FFT的优点更为明显。对一个连续时间信号xa(t
