快速傅里叶变换教案 .pdf
快速傅里叶变换快速傅里叶变换(FFT)(FFT)一、教学目的及要求一、教学目的及要求1.了解 FFT 与 DFT 的关系；2.了解 DFT，FFT 存在的计算量的问题；3.熟悉 FFT 的理论依据；掌握时间抽取基2-FFT(即 DIT-FFT)算法的原理。二、教学重点及难点二、教学重点及难点重点重点：直接计算N点DFT的计算量；减少运算量的基本途径；时间抽取基2-FFT算法的基本思想(蝶式运算图)。nk难点难点：利用 DFT 的运算规律及其中某些算子的特殊性质（WN的周期性和对称性），找出减少乘法和加法运算次数的有效途径。三、教学内容三、教学内容1.1.直接计算直接计算 N N 点点 DFTDFT 的运算量的运算量knX(k)x(n)WN,k 0,1,N 1n0N1复数乘法次数：N2，复数加法次数：N(N-1)，N 很大近似为 N2思考题：如果计算机的速度为平均每次复数乘需要 510-6秒，每次复加需要 110-6秒，用来计算 N=1024 点 DFT，直接计算需要多少时间？直接计算所需时间为：T 5106 N2106 N(N 1)51061024210610241023 6.29s2.2.减少运算量的途径：减少运算量的途径：(1)用旋转因子的性质减少运算量nkWN e j2nkN性质nk-nk(Nn)k1)对称性：（WN）WNWNNn)knk2)周期性：W（WNNnkmnknknk/m3)可约性：WNWmN,WNWN/m4)特殊点：W 1，W0NN2N 1,WN(kN)2k WN(2)减少序列的长度，即把长度为N的序列分解为长度为N/2的序列(3)利用DFT的对称性及周期性(N)3.3.基基2-DIT-FFT2-DIT-FFT算法原理算法原理(N N=2=2MM)(1)(1)算法的推导过程算法的推导过程将x(n)按n的奇偶分为两组作DFT，n为偶数时：x(2r)x1(r),r 0,1,N21n为奇数时：x(2r 1)x2(r),r 0,1,N21则x(n)的DFT可以表示为：knX(k)x(n)WNn0N12r0N12r0N1n偶数x(n)WknNn奇数x(n)WknNx(2r)Wx(r)W1r0N12k2rNk(2r1)x(2r 1)WNN12r0k2rNk(2r1)x2(r)WNN12r0(1)x(r)W1r0N12krN/2kWNx2(r)WNr/2k X1(k)WNX2(k)k 0,1,N12(1)式即为序列x(n)分解为两个长度为N/2的奇、偶序列，其前N/2个点的DFT，对于其后N/2个点的DFT，可利用DFT的周期性求得。由DFT的隐含周期性，可得：X1(k NN)X1(k)和X2(k)X2(k)22NNNkN/2)X1(k)WNX2(k)从而有：222(2)k X1(k)WNX2(k)k 0,1,N/21X(k(2)式即为序列x(n)分解为两个长度为N/2的奇、偶序列后其后N/2个点的DFT。(2)(2)蝶式运算图蝶式运算图式(1)和式(2)可用如下的蝶式图表示：(3)(3)N N=8=8时，序列第一次分解的蝶式运算图时，序列第一次分解的蝶式运算图(4)(4)为减少运算量，进一步把长度为为减少运算量，进一步把长度为N N/2/2的两个序列进一步分解为长度为的两个序列进一步分解为长度为N N/4/4的序列的序列，则有：N14(3)NNkX1(k)X3(k)WNX(k)k 0,1,1/2444kX1(k)X3(k)WN/2X4(k)k 0,1,N14(4)NNkX2(k)X5(k)WN1/2X6(k)k 0,1,44kX2(k)X5(k)WN/2X6(k)k 0,1,(5)N=8(5)N=8时，序列完整分解的蝶式运算图时，序列完整分解的蝶式运算图(6)(6)对于长度为对于长度为N N(N N=2=2MM)的序列，的序列，经过经过MM-1-1次分解，次分解，分解为分解为2 2MM-1 1个长度为个长度为2 2的序列，的序列，其运算量如其运算量如下：共有M级分解，每一级有2M-1个蝶式运算，每一个蝶式运算包括一次复数乘法运算两次加法运算，所以经过基2-FFT后，其运算量为：复数乘法次数：M*2M-1=N/2*log2N复数加法次数：N*log2N与直接运算DFT的运算量相比，大大降低了运算量。(7)(7)蝶式运算的特点：蝶式运算的特点：FFTFFT输入序列的顺序看似杂乱无章，其实是正常顺序的倒序输入序列的顺序看似杂乱无章，其实是正常顺序的倒序(怎样实现？按序列长度的二进制位从低位到高位按照0、1抽取)。旋转因子的特点旋转因子的特点：蝶形类型随迭代次数成倍增加，每迭代一次，蝶形类型增加一倍，数据点间隔也蝶形类型随迭代次数成倍增加，每迭代一次，蝶形类型增加一倍，数据点间隔也增加一倍增加一倍。3.3.进一步利用进一步利用FFTFFT减少运算量的措施：减少运算量的措施：(1)怎样通过计算一次N点FFT，得到两个实序列的N点FFT。(2)怎样通过计算一次N点FFT，得到2N点FFT。思考题：在时域内把序列分成前后两半的序列，在频域内是否对应奇偶抽取的结论(基2DIFFFT)小结小结：(1)减少DFT运算量的途径(2)基2-DIT-FFT基本思想(3)蝶形运算的特点(4)进一步减少FFT运算量的途径
