讲座讲座: 快速离散傅立叶变换快速离散傅立叶变换 本本讲讲的教学内容的教学内容改进改进DFTDFT计算的方法计算的方法按时间抽取的按时间抽取的FFTFFT算法（算法（DIT FFT）按频率抽取的按频率抽取的FFTFFT算法（算法（DIF FFT）第第十章章 快速离散傅立叶变换快速离散傅立叶变换 （1） FFT:Fast Fourier Transform（2）傅立叶级数和傅立叶变换理论在19世纪就已经提出,时域离散傅立叶变换理论也在20世纪初发展完善.但由于其手工计算的复杂性,在工程实践中并没有得到广泛应用.相反,在应用中使用广泛的是其它一些手工计算相对简单的数学分析手段,如沃尔什变换.直到1965年, 库利-图基提出了针对N时复合数情况的快速离散傅立叶变换算法,与传统算法相比降低了1个数量级,由此引发了研究快速算法的热潮.这些算法统称为FFT. FFT算法的广泛应用，不仅奠定了离散傅立叶变换在数字信号处理中的经典地位,也极大推动了数字信号处理应用与发展.第一节第一节 改进改进DFT计算的方法计算的方法衡量算法的复杂性: 乘.加法运算次数,不考虑控制调度等操作;只考虑DFT的正变换,因为: K=0,1, ,N-1 DFT正变换DFT反变换反变换相对正变换:输入取共扼;输出取共轭并加权.直接计算直接计算DFT的运算量的运算量 n=0,1, ,N-1 k=0,N-1复数运算复数运算 对每一个对每一个k值值: 复乘复乘: N 复加: N-1第一节第一节 改进改进DFT计算的方法计算的方法 对所有对所有k: 复乘复乘: 复加复加: N(N-1)即复数运算量与即复数运算量与 近似成正比近似成正比(不考虑 情况) 1.实数运算 k=0,N-1第一节第一节 改进改进DFT计计算的方法算的方法对每一个固定对每一个固定k : 实乘实乘: 4N 实加实加: 对所有对所有k : 实乘实乘: 4N2实加实加: 2N(2N-1)= 4N2 -2N实数运算量与实数运算量与近似成正比近似成正比 结论结论:直接计算直接计算DFT的乘的乘.加运算量近似与加运算量近似与 成正比成正比.第一节第一节 改进改进DFT计算的方法计算的方法改善运算效率的途径改善运算效率的途径（1）利用）利用 的对称性和周期性等特性合并运算项的对称性和周期性等特性合并运算项复共轭对称性复共轭对称性: 对对n和和k的周期性的周期性: 可约性可约性 特殊值特殊值第一节第一节 改进改进DFT计算的方法计算的方法式中其它各对称项也可以找到类似归并办法式中其它各对称项也可以找到类似归并办法. .这样乘法这样乘法次数大约可减少一半次数大约可减少一半. .(2) (2) 大点数大点数DFTDFT逐次分解成小点数逐次分解成小点数DFT)DFT)分解分解 正是正是FFTFFT算法的基本原理算法的基本原理 第一节第一节 改进改进DFT计算的方法计算的方法例:利用对称性,可以合并对称项:FFT的基本原理： 为了提高DFT的运算效率, 把大点数DFT按倒位序逐次分解为更小点数DFT的合成.在分解过程中,要利用系数 的对称性和周期性. 如果算法是逐次分解时间序列得到的,那么这种分解算法称为按时间抽取算法.阐述按时间抽取原理最方便的方法是研究 这种特殊情况.由于N为2的整数幂,可以不断将x(n)一分为二. 这就是最常用的基-2FFT算法. 如果序列不满足这个条件,可以人为地加上若干零点得到.第一节第一节 改进改进DFT计算的方法计算的方法第二节第二节 按时间抽取按时间抽取FFTFFT算法算法算法原理：假设序列x(n)长为 (n=0,N-1), 由于N为 偶数,可以将x(n)按n为奇数和偶数分解为两个 N/2的长序列,并依此逐级分解来计算x(k).是x(n)按n为奇、偶数分为2个子序列，得:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法第一级分解定义偶序列与奇序列:上式可写为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法其中: k=0,N/2-1 第二节第二节 按时间抽取按时间抽取FFT算法算法上式表明一个N点的DFT可以分解成两个 点的DFT. 这两个 点的DFT又可按式合成一个N点DFT一个问题: 和 的长度为 , 它们的DFT 和 的点数也为 , 而x(k)却有N个点。 利用 的周期性解决这一问题，即：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法表达为前后两个部分:前半部分 后半部分 k=0, k=0, 和的周期为同样可得把即：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法这样只要求出0 -1 区间所有 和 ,就可以求出0N-1 区间内全部X(k)的值.这就是FFT运算的关键所在。用以下信号流图表示为：根据流图的形状，上述运算称为碟形运算。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法复乘: 1 复加: 2一次蝶形运算: 运算分析:当一次分解后DFT运算的信号流图为：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 仍为偶数,可以 直接计算N点DFT所需复乘 ,复加N(N-1),可见当 N较大时,一次分解后运算量减少近一半. 由于 N= (M1), 经一次分解后 点DFT再分别分解为两个 点DFT的组合.进一步把每个复乘: 一次分解: 2个 点DFT+ 个蝶形运算 复加: 第二节第二节 按时间抽取按时间抽取FFT算法算法第二级分解可得:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 与第一级分解一样,利用 和 隐含的周期性, 为 改写为前，后两部分: 其中:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法由此一个 点DFT分解成两个 点的DFT.其流图为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法也可以进行同样分解:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法奇序列中的偶序列,奇序列中的奇序列第二节第二节 按时间抽取按时间抽取FFTFFT算法算法为 改写为前,后两部分: 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法其中:系数统一为 (今后都使用统一的系数),这样,一个N点DFT就分解成4个N/4点的DFT,其信号流图为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法根据前面的分析,第二级分解组合比第一级分解后的运算量又降低了一半.对于N=8点的DFT,经过两次分解后,最后剩下四个N/4=2 的DFT,即 (k =0,1).尽管2点长的DFT只有加减法,仍然可用蝶式运算单元来统一表示.第二节第二节 按时间抽取按时间抽取FFTFFT算法算法例如 组成的2点DFT 可用公式计算: 类似,其它3个2点长DFT都可以用一个蝶式运算单元求得,综合这三级分解过程,可得到一个完整的8点DFT信号流图.第二节第二节 按时间抽取按时间抽取FFTFFT算法算法第二节第二节 按时间抽取按时间抽取FFTFFT算法算法这种方法每次分解都是按输入序列在时域上的次序是偶数还是奇数来抽取的，故称之为按时间抽取法.运算量分析由DIT FFT信号流图可见,对于任何一个 点DFT运算,都可以通过M次分解,最后分解成2点DFT运算的组合.这样的M级分解,就构成了M级运算过程.每级N/2个蝶形运算.每一级: 复乘: 复加: 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法结论: DIF FFT运算量与 近似成正比.全部M级:复乘 复加 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法第二节第二节 按时间抽取按时间抽取FFTFFT算法算法三. 按时间抽取的FFT算法特点.1. 蝶式运算 系统由大量蝶式运算单元组成,每个蝶式运算的迭代任务是: 为节点，m：表示第m列叠代。p,q：为数据所在行数，对应信号流图下图所示：第二节第二节 按时间抽取按时间抽取FFT算法算法是输入数据注：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法（1）蝶式运算的节点距离 (p,q间的距离)以N=8为例m 1 2 3q-p 1 2 4推广:基-2 DIF FFT中,第m级蝶式运算节点间距离为蝶式运算可写成:（2） 的确定每一级的旋转因子都不相同，但排列很有规律，下表所示。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法2. 原址运算第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 多级蝶式运算结构会产生大量中间结果.如果运算式要保存这些中间结果,则需要耗费大量资源(存贮器)观察FFT信号流图,可以发现任何两个节点(p与q)经过蝶式运算后,其结果即为下一列p,q两节点的变量.而每一级蝶式运算的输出,在该级运算结束之后无需保存.因此,任何一个蝶行运算的两个输出结果仍然可以存放两个输入值所在的存储单元中.这样,整个运算只需要N个寄存器,他们保存输入数据,并不断对每一级运算结果刷新,直到最后输出。其优点在于节省存储资源.第二节第二节 按时间抽取按时间抽取FFT算法算法3. 倒位序 观察同址运算结构,可以发现FFT输出端X(k)正好按07自然顺序排列的，而输出序列x(n)不是按07自然顺序排列。x(n)排列表面上混乱无序，而隐含着有规律的排列，即”倒位序”存贮,以N=8点FFT结构来说明。存储器号 数据结论: 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法倒位序排列是由于不断将DFT运算分解为较小点数DFT计算造成的。序列x(n)首先分成偶数标号和奇数标号两个子序列：偶数序列出现在流图上半部,奇数序列出现在流图下半部。从形式上说,这样的划分可通过分析标号n的二进制表示 的最低位 来实现。标号为偶数，则 =0，标号为奇数，则 =1。这样 =0的标号出现在流图上半部从中我们可以发现: 若 , 则: 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 =1的标号出现在下半部。下一次奇偶序列的分解又分别根据标号二进制表示的倒数第二位 开始,根据 分别将第一次分解生成的两个子序列再一次按奇偶性分开。持续该过程,直得到N个长度为1的子序列。最后的排列顺序呈”倒位序”第二节第二节 按时间抽取按时间抽取FFTFFT算法算法所以要实现FFT算法，首先必须把按自然顺序存放的数据变换成按倒序存放。这一过程称为整序，N=8时的整序过程下图所示。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法小结:1. 算法原理2. 计算量: 复乘:复加:3. 运算特点:蝶式运算.同址运算.倒位序第二节第二节 按时间抽取按时间抽取FFTFFT算法算法第三节第三节 按频率抽取按频率抽取FFTFFT算法算法DIT:将输入序列x(n)按其标号n为奇数或偶数分解成短序列DIF:将输出序列X(k)按其k值为奇数或偶数分解成短序列算法原理仍讨论基-2FFT,即 频域抽取法是将X(k)按标号k的自然顺序分成前后两半(注意:不再是奇偶顺序)第三节第三节 按频率抽取按频率抽取FFTFFT算法算法按k为偶数或是奇数将x(k)分解成两部分第三节第三节 按频率抽取按频率抽取FFTFFT算法算法输入序列前一半与后一半之差再与 乘积令输入序列前一半与后一半之和第三节第三节 按频率抽取按频率抽取FFTFFT算法算法与可通过一蝶式运算(结构)单元得到:第三节第三节 按频率抽取按频率抽取FFTFFT算法算法这样一个N点 DFT就分解为两个N/2点DFT。以N=8为例，上述分解过程如图所示:第三节第三节 按频率抽取按频率抽取FFTFFT算法算法一次分解的运算过程分为两步:（1）前后两半序列合成 与 （2）分别求 与 N/2点DFT，结果为x(k)偶奇部分特点：输入进行分解合成，输出不用合成，但顺序有变。和DIT-FFT一样，N一次分解后，N/2仍是偶数，因此可进一步按上述方式分解，直至最后N/2个2点DFT的全部N个输出就是x(n)的N点DFT 。第三节第三节 按频率抽取按频率抽取FFTFFT算法算法下图是N=8时完整的按频率抽取的FFT结构第三节第三节 按频率抽取按频率抽取FFTFFT算法算法运算特点 和DIT-FFT基本相同，都是通过蝶形运算完成，也是原位运算，但其输入是正常位序，输出为倒位序。按流图转置定理，即将流图的所有支路方向取反，交换输入输出，系数保持不变，可得到流图的转置形式。比较DIT-FFT流图可知它们互为转置。根据转置定理，两个流图的输入输出特性相同。因此频率抽取法和时间抽取法是两种等价的FFT运算。从上图可以看出,按频率抽取算法共有M级，每一级都有N/2个蝶形运算。因此N点FFT有NM/2个蝶形运算，每个蝶形运算需要一次复数乘法和二次复数加数，因此运算量与时域抽取相等。复乘：复加：第三节第三节 按频率抽取按频率抽取FFTFFT算法算法DIF FFT与DIF FFT的比较区别: 倒位序方式不同 蝶形运算的结构不同相似: 运算结构类似运算量相同同位运算 互为转置 等价第三节第三节 按频率抽取按频率抽取FFTFFT算法算法