快速傅里叶变换教案

1、学习必备欢迎下载快速傅里叶变换(FFT)一、教学目的及要求1.了解FFT与DFT的关系；2.了解DFT，FFT存在的计算量的问题；3.熟悉FFT的理论依据；掌握时间抽取基2-FFT(即DIT-FFT)算法的原理。二、教学重点及难点重点：直接计算N点DFT的计算量；减少运算量的基本途径；时间抽取基2-FFT算法的基本思想(蝶式运算图)。N的周期性和对称性），找出难点：利用DFT的运算规律及其中某些算子的特殊性质（WnkX(k)x(n)Wkn,k0,1,N1减少乘法和加法运算次数的有效途径。三、教学内容1.直接计算N点DFT的运算量N1Nn0复数乘法次数：N2，复数加法次数：N(N-1)，N很大近

2、似为N2思考题：如果计算机的速度为平均每次复数乘需要510-6秒，每次复加需要110-6秒，用来计算N=1024点DFT，直接计算需要多少时间？直接计算所需时间为：T5106N2106N(N1)510610242106102410236.29s2.减少运算量的途径：(1)用旋转因子的性质减少运算量WnkNej2Nnk性质1)对称性：（Wnk）W-nkW(Nn)kNNN2)周期性：W（Nn)kWnkNN,3)可约性：WnkWmnkWnkWnk/mNmNNN/m4)特殊点：W01，WNN2N1,W(kN2)WkNN(2)减少序列的长度，即把长度为N的序列分解为长度为N/2的序列(3)利用DFT的对

3、称性及周期性(N)3.基2-DIT-FFT算法原理(N=2M)(1)算法的推导过程将x(n)按n的奇偶分为两组作DFT，n为偶数时：x(2r)x(r),r0,1,N112n为奇数时：x(2r1)x(r),r0,1,N122则x(n)的DFT可以表示为：学习必备欢迎下载X(k)x(n)WknNN1n0Nx(n)Wn偶数knx(n)Wn奇数knNx(2r)Wx(2r1)Wk(2r1)N12r0k2rNN12r0Nx(r)Wk2rx(r)Wk(2r1)N12r01NN12r02N(1)x(r)WWkx(r)WrN211krN/2N2N/2N212r0r0X(k)WkX(k)k0,1,N1N21X(k

4、N22(1)式即为序列x(n)分解为两个长度为N/2的奇、偶序列，其前N/2个点的DFT，对于其后N/2个点的DFT，可利用DFT的周期性求得。由DFT的隐含周期性，可得：N)X(k)和X(k)X(k)1122X(kN222(2)从而有：NN)X(k)WkN/2X(k)1N2X(k)WkX(k)k0,1,N/211N2(2)式即为序列x(n)分解为两个长度为N/2的奇、偶序列后其后N/2个点的DFT。(2)蝶式运算图式(1)和式(2)可用如下的蝶式图表示：(3)N=8时，序列第一次分解的蝶式运算图(4)为减少运算量，进一步把长度为N/2的两个序列进一步分解为长度为N/4的序列，则有：44444

5、4学习必备欢迎下载NX(k)X(k)WkX(k)k0,1,113N/24NNX(k)X(k)WkX(k)k0,1,113N/24NX(k)X(k)WkX(k)k0,1,125N/26NNX(k)X(k)WkX(k)k0,1,125N/26(5)N=8时，序列完整分解的蝶式运算图(3)(4)(6)对于长度为N(N=2M)的序列，经过M-1次分解，分解为2M-1个长度为2的序列，其运算量如下：共有M级分解，每一级有2M-1个蝶式运算，每一个蝶式运算包括一次复数乘法运算两次加法运算，所以经过基2-FFT后，其运算量为：复数乘法次数：M*2M-1=N/2*log2N复数加法次数：N*log2N与直接运算DFT的运算量相比，大大降低了运算量。(7)蝶式运算的特点：FFT输入序列的顺序看似杂乱无章，其实是正常顺序的倒序(怎样实现？按序列长度的二进制位从低位到高位按照0、1抽取)。旋转因子的特点：蝶形类型随迭代次数成倍增加，每迭代一次，蝶形类型增加一倍，数据点间隔也增加一倍。3.进一步利用FFT减少运算量的措施：(1)怎样通过计算一次N点FFT，得到两个实序列的N点FFT。(2)怎样通过计算一次N点FFT，得到2N点FFT。思考题：在时域内把序列分成前后两