《快速傅立叶变换FFT课件.ppt》由会员分享，可在线阅读，更多相关《快速傅立叶变换FFT课件.ppt（48页珍藏版）》请在三一办公上搜索。
1、第四章 快速傅立叶变换(FFT),4.1 引言,FFT是DFT的快速算法,提出与发展,由库利(J.K.Cooly)和图基(J.K Tuky),相继出现了桑得(G.Sand)-图基等快速算法,价值,使运算效率提高了12个数量级,推动了数字信号处理技术的应用和发展,分裂基FFT,FFT是DFT的一类快速算法,4.2 基2 FFT算法,4.2.1 直接计算DFT的问题及改进的方法,4.2.2 时域抽取法基2 FFT基本原理,4.2.3 DIT-FFT算法运算量,4.2.4 DIT-FFT的运算规律及编程思想,4.2.5 频域抽取法FFT（DIF-FFT),4.2.6 IDFT的高效算法,(实验:要求
2、购买数字信号处理实习指导书,熟悉MATLAB语言等),4.2 基2 FFT算法,4.2.1 直接计算DFT的问题及改进的方法,DFT的定义,两者形式类似，差别只在于的指数符号不同，及常数因子。运算量是相同的,（1）正变换的运算量,每计算一个X(k)需要,N次复数乘法,(N-1)次复数加法,计算 N 点X(k),则需要,N2次复数乘法，N(N-1)次复数加法即:计算量正比于N2,这也是产生快速算法的思想由来.,因为 均为复数,注意:指数运算,（2）减少运算量的途径(利用DFT的性质),对称性,周期性,具有如下特性：旋转因子,利用这些特性：,1.使DFT运算中的有些项可以合并。2.可将长序列的DF
3、T分解为短序列的DFT。,更加有用的性质,FFT的基本思想在于,将原有的N点序列分成两个较短的序列,这两个序列的DFT组合起来,得出原序列的DFT。剩下的问题是怎么分?:前后分或抽取分.?,4.2.2 时域抽取法基2 FFT基本原理,FFT算法分为两大类,时域抽取法(DIT),频域抽取法(DIF),此处可以说明基2的由来,设,M为自然数,将长度为N的序列x(n)按n的奇偶分成两组,则x(n)的DFT为,一、时域抽取法基本原理,由于,所以,式中，,是x(2r)与x(2r+1)的N/2点DFT(因为长度,求和范围和W均是针对N/2的。,上式可见，一个N点DFT已分解为两个N/2点的DFT X1(k
4、)与X2(k)的组合。此时计算量已经变化。为使这种计算量变化更明显地表现出来:,把 分成两部分来求，此时必须应用旋转因子的周期性：,由于,分成两部分来求：,X(k)的后半部分为：,再考虑到旋转因子的特性:,所以,只要求出0N/2-1区间上X1(k)与X2(k)的值，即可得到0N-1区间内所有X(k)的值。,X(k)的运算可用蝶形信号流图表示,简记为下图形式：,N点DFT一次时域抽取分解图（N=8）,N/2点DFT,N/2点DFT,计算量分析:分成两部分(1)DFT(2)蝶形运算(1)每个N/2点的DFT需要（N/2)2次复数乘，N/2(N/2-1)次复数加。两个N/2点的DFT需要N2/2次复
5、数乘，N(N/2-1)次复数加。(2)计算一个蝶形，需要1次复乘，2次复加。将两个N/2点的DFT合并成N点DFT，有N/2个蝶形运算，还需要N/2次复数乘及N次复数加。总计算量:计算N点DFT共需要 N2/2 N/2 N2/2 次复数乘，N(N/2-1)N N2/2次复数加。只分解一次运算量就减少一半。这种分解方法可一直进行到左侧为两点DFT为止。,与第一次分解相同，将x1(r)按r的奇偶分成两个长为N/4的子序列：,且,x2(r)也可以进行同样的处理，得到X2(k),其中，,将旋转因子统一为，则一个N点DFT就可分解为4个N/4点的DFT.,N点DIT-FFT运算流图,N/4点DFT,N/
6、4点DFT,N/4点DFT,N/4点DFT,最后剩下的是2点DFT，当N=8时，其输出为：,以X4(k)为例，,因为,即x(2),x(6)通过蝶形运算得到X4(k),N点DIT-FFT运算流图,N点DIT-FFT运算流图,N点DIT-FFT运算流图N=8 此图的重要性:理解FFT算法实质;分析计算量;设计FFT算法程序等,当,时，可分解为M级蝶形，每级都有N/2个蝶形运算。(基2由来),每一级,N/2次复数乘；N 次复数加。,则,M级,次复数乘,次复数加,与直接计算DFT的运算量之比,4.2.3 DIT-FFT算法运算量,与直接计算DFT的运算量之比计算速度的提高是巨大的:例如P101 图4.
7、2.5,4.2.3 DIT-FFT算法运算量,1、原位计算（就地算法）,4.2.4 DIT-FFT的运算规律及编程思想,3、蝶形运算规律及编程思想,2、旋转因子的变化规律,4、倒位序规律,5、倒位序实现,1.原位计算（就地算法）,用同一地址既存输入序列又存输出序列的算法。,如图4.2.4，每级运算由N/2个蝶形构成，每个蝶形完成下述基本运算：,式中L代表第L级蝶形运算。J、J+B代表数据所在行。B表示蝶形运算的两个输入相距B个点。,运算规律,每个蝶形运算的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又在同一水平线上。,这样，蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中
8、。每列的N/2个蝶形运算全部完成后，再开始下一列的蝶形运算。下一列仍采用原位运算，只是进入蝶形的组合关系有所不同。,2.旋转因子 的变化规律,观察图4.2.4，第L级共有2L-1个不同的旋转因子。,称为旋转因子，p称为旋转因子的指数。级(L):从左到右的运算级数。(L=1,2,M),旋转因子与级数（L）的关系,更一般地,第 L 级的旋转因子为,蝶形运算两输入点间距离为：,第1级：1,第2级：2,第3级：4,第L级：2L-1,每一级的两个输入节点进行蝶形运算后，得到下一级的相同序号的两个输出节点。,3.蝶形运算规律(1.端点间距 2.相邻间距),对于每个旋转因子，有2M-L个蝶形运算。第一个蝶形
9、的第一个输入所在行为J，第二个蝶形的第一个输入所在行为J+2L，相邻两个蝶形运算第一个输入相距2L。,编程思想,先从输入端开始，逐级进行计算，共进行M级运算。在进行第L级运算时，依次求出2L-1个不同的旋转因子，每求一个旋转因子，就计算完它对应的所有2M-L个蝶形。(结合编程说明:三层循环,最内层计算为:一个蝶形的计算,结合图4.2.4),L表示运算级数,旋转因子个数,对旋转因子计数,计算旋转因子指数,每个旋转因子对应2M-L个蝶形运算。,两个蝶形运算第一个输入点距离是2L,此流程图是针对C写的,MATLAB时要相应修改,4.倒位序规律,若,是三位二进制数，,则,就是它的倒位序。,按原位计算时
10、，FFT的输出X(k)是按自然顺序存储的，但这时输入序列却不是按自然顺序存储的。,输入序列初看起来，好象没有规律，实际是按倒位序存储的。,倒位序的形成,x(111)=x(7),x(000)=x(0),x(010)=x(2),x(110)=x(6),x(001)=x(1),x(101)=x(5),x(100)=x(4),造成倒位序的原因是输入序列x(n)，按标号(序号)n的奇偶不断地分组造成的。,x(011)=x(3),5.倒位序的实现,（1）只要将顺序二进制数（n2n1n0）的二进制位倒置，得（n0n1n2）。根据这种规律，容易用硬件电路和汇编语言产生倒位序数。,（2）用高级语言程序实现时，必
11、须找出产生倒序数的十进制运算规律。,0 000 0 0001 001 4 1002 010 2 0103 011 6 1104 100 1 0015 101 5 1016 110 3 0117 111 7 111,左边为按自然顺序排列的二进制数，下面的一个数是上面一个数的最低位上加上1，且向高位进位。,右边为倒位序数，下面的一个数是上面一个数的最高位上加上1，且由高位向低位进位。称为反向进位加法,顺序与倒序二进制对照表,可由当前任一倒序值求得下一个倒序值,反向进位加法的实现(十进制情况),若已知某个倒位序数J，求下一个倒位序数，,判 断 J 的最高位是否为“0”,让J与N/2比较，因为N/2总
12、是100,如果 JN/2,则 J 的最高位为零,只需把该位变为 1(J=J+N/2),就得到下一个倒位序数,否则,把最高位变为 0(J=J-N/2),判 断 J 的次高位是否为“0”,让J与N/4比较，,如果 J 的次高位为零,只需把该位变为 1(J=J+N/4),其它位不变,就得到下一个倒位序数,否则,还需判断下一位(与 N/8比较),如此依次进行下去,总会碰到某位为 0,将此位改为1即可.,JK,No,实现倒位序的流程图,上一个倒序数,下一个倒序数,形成倒序数后，把原来按自然顺序存放在存储单元的输入序列x(n)重新按倒序排列。,通过变址运算完成倒位序,时，不必调换。而当 时，需调换。,变址
13、,4.2.5 频域抽取法FFT（DIF-FFT),与DIT相对应，DIF算法是将频域X(k)的序号k按奇偶分开。,推导过程,设,M为自然数,则x(n)的DFT为,式中,分别令k=2r,k=2r+1,r=0.1,N/2-1,4.2.5 频域抽取法FFT（DIF-FFT),令,则,由于N=2M，N/2仍然是偶数，继续将N/2点的DFT分成偶数组和奇数组。这样每个N/2点DFT可由两个N/4点DFT形成。其输入序列分别是x1(n)和x2(n)按上下对半分开形成的四个子序列。,DIF与DIT算法的比较,基本蝶形不同,都有M级运算,每级有N/2个蝶形,都可进行原位计算,运算次数相同,输入为自然顺序,输出
14、为倒位序,这样将X(k)按k的奇偶把一个N点的DFT分成为两个N/2点的DFT,且可一直分解为直到两点的DFT.,4.2.6 IDFT的高效算法,比较两个公式可以看出，只要改变DFT运算中的每个系数符号，最后乘以 1/N，就是IDFT的运算公式了。,实际中，为了避免发生溢出，将1/N分配到每一级蝶形运算中，因为 所以每一级的每个蝶形输出到乘以1/2.,4.2.6 IDFT的高效算法,DIT-FFT用于计算IFFT时，称为DIF-IFFT,DIF-FFT用于计算IFFT时，称为DIT-IFFT,对IDFT公式两边取共轭,所以,先将X(k)取共轭，就可以直接利用FFT子程序，最后将结果再取一次共轭，并乘以1/N，即得到x(n),作业：一、P127：1，3，4,下次课内容:,1.Matlab 语言简介2.实验3.期中考试.,学校书库只有少量数字信号处理实习指导书，为此，同学们可不必购买，而直接在网上下载电子版的该书。我已经放在学院教案下载处,说明:,学校书库只有少量数字信号处理实习指导书，为此，同学们可不必购买，而直接在网上下载电子版的该书。我已经放在学院教案下载处。,
