讲座快速离散傅立叶变换.ppt

1、讲座: 快速离散傅立叶变换,本讲的教学内容 改进DFT计算的方法 按时间抽取的FFT算法（DIT FFT） 按频率抽取的FFT算法（DIF FFT）,第十章 快速离散傅立叶变换,（1） FFT:Fast Fourier Transform （2）傅立叶级数和傅立叶变换理论在19世纪就已经提出,时域离散傅立叶变换理论也在20世纪初发展完善.但由于其手工计算的复杂性,在工程实践中并没有得到广泛应用.相反,在应用中使用广泛的是其它一些手工计算相对简单的数学分析手段,如沃尔什变换.直到1965年, 库利-图基提出了针对N时复合数情况的快速离散傅立叶变换算法,与传统算法相比降低了1个数量级,由此引发了研

2、究快速算法的热潮.这些算法统称为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) 即复数运算量与 近似成正比 (不考

3、虑 情况),实数运算,k=0,N-1,第一节 改进DFT计算的方法,对每一个固定k :,实乘: 4N 实加:,对所有k :,实乘: 4N2,实加:,2N(2N-1)=,4N2,-2N,实数运算量与,近似成正比,结论:直接计算DFT的乘.加运算量近似与,成正比.,第一节 改进DFT计算的方法,改善运算效率的途径 （1）利用 的对称性和周期性等特性合并运算项 复共轭对称性: 对n和k的周期性: 可约性 特殊值,第一节 改进DFT计算的方法,式中其它各对称项也可以找到类似归并办法.这样乘法次数大约可减少一半. (2) 大点数DFT逐次分解成小点数DFT)分解 正是FFT算法的基本原理,第一节 改进D

4、FT计算的方法,例:利用对称性,可以合并对称项:,FFT的基本原理： 为了提高DFT的运算效率, 把大点数DFT按倒位序逐次分解为更小点数DFT的合成.在分解过程中,要利用系数 的对称性和周期性. 如果算法是逐次分解时间序列得到的,那么这种分解算法称为按时间抽取算法.阐述按时间抽取原理最方便的方法是研究 这种特殊情况.由于N为2的整数幂,可以不断将x(n)一分为二. 这就是最常用的基-2FFT算法. 如果序列不满足这个条件,可以人为地加上若干零点得到.,第一节 改进DFT计算的方法,第二节 按时间抽取FFT算法,算法原理： 假设序列x(n)长为 (n=0,N-1), 由于N为 偶数,可以将x(

5、n)按n为奇数和偶数分解为两个 N/2的长序列,并依此逐级分解来计算x(k).,是x(n)按n为奇、偶数分为2个子序列，得:,第二节 按时间抽取FFT算法,第一级分解 定义偶序列与奇序列:,上式可写为:,第二节 按时间抽取FFT算法,其中:,k=0,N/2-1,第二节 按时间抽取FFT算法,上式表明一个N点的DFT可以分解成两个 点的 DFT. 这两个 点的DFT又可按式合成一个N点 DFT 一个问题: 和 的长度为 , 它们的DFT 和 的点数也为 , 而x(k)却有N个点。 利用 的周 期性解决这一问题，即：,第二节 按时间抽取FFT算法,表达为前后两个部分:,前半部分,后半部分,k=0,

6、k=0,和,的周期为,同样可得,把,即：,第二节 按时间抽取FFT算法,这样只要求出0 -1 区间所有 和 ,就可以求出0N-1 区间内全部X(k)的值.这就是FFT运算的关键所在。用以下信号流图表示为：,根据流图的形状，上述运算称为碟形运算。,第二节 按时间抽取FFT算法,复乘: 1 复加: 2,一次蝶形运算:,运算分析:,当,一次分解后DFT运算的信号流图为：,第二节 按时间抽取FFT算法,仍为偶数,可以,直接计算N点DFT所需复乘,复加N(N-1),可见当,N较大时,一次分解后运算量减少近一半.,由于,N=,(M1), 经一次分解后,点DFT再分别分解为两个,点DFT的组合.,进一步把每

7、个,复乘:,一次分解: 2个,点DFT+,个蝶形运算,复加:,第二节 按时间抽取FFT算法,第二级分解,可得:,第二节 按时间抽取FFT算法,与第一级分解一样,利用 和 隐含的周期性, 为 改写为前，后两部分:,其中:,第二节 按时间抽取FFT算法,由此一个,点DFT分解成两个,点的DFT.,其流图为:,第二节 按时间抽取FFT算法,也可以进行同样分解:,第二节 按时间抽取FFT算法,奇序列中的偶序列,奇序列中的奇序列,第二节 按时间抽取FFT算法,为,改写为前,后两部分:,第二节 按时间抽取FFT算法,其中:,系数统一为 (今后都使用统一的系数),这样,一个N点DFT就分解成4个N/4点的D

8、FT,其信号流图为:,第二节 按时间抽取FFT算法,根据前面的分析,第二级分解组合比第一级分解后的 运算量又降低了一半.,对于N=8点的DFT,经过两次分解后,最后剩下四 个N/4=2 的DFT,即,(k =0,1).尽管2点长的DFT只有加减法,仍然可用蝶式运算单元来统一表示.,第二节 按时间抽取FFT算法,例如 组成的2点DFT 可用公式计算: 类似,其它3个2点长DFT都可以用一个蝶式运算单元求得,综合这三级分解过程,可得到一个完整的8点DFT信号流图.,第二节 按时间抽取FFT算法,第二节 按时间抽取FFT算法,这种方法每次分解都是按输入序列在时域上的次序是偶数还是奇数来抽取的，故称之

9、为按时间抽取法.,运算量分析 由DIT FFT信号流图可见,对于任何一个 点DFT运算,都可以通过M次分解,最后分解成2点DFT运算的组合.这样的M级分解,就构成了M级运算过程.每级N/2个蝶形运算. 每一级: 复乘: 复加:,第二节 按时间抽取FFT算法,结论: DIF FFT运算量与 近似成正比.,全部M级: 复乘 复加,第二节 按时间抽取FFT算法,第二节 按时间抽取FFT算法,三. 按时间抽取的FFT算法特点. 1. 蝶式运算 系统由大量蝶式运算单元组成,每个蝶式运算的迭代任务是:,为节点，m：表示第m列叠代。p,q：为数据所在行数，对应信号流图下图所示：,第二节 按时间抽取FFT算法

10、,是输入数据,注：,第二节 按时间抽取FFT算法,（1）蝶式运算的节点距离 (p,q间的距离) 以N=8为例 m 1 2 3 q-p 1 2 4 推广:基-2 DIF FFT中,第m级蝶式运算节点间距离为,蝶式运算可写成:,（2） 的确定 每一级的旋转因子都不相同，但排列很有规律，下表所示。,第二节 按时间抽取FFT算法,2. 原址运算,第二节 按时间抽取FFT算法,多级蝶式运算结构会产生大量中间结果.如果运算式要保存这些中间结果,则需要耗费大量资源(存贮器)观察FFT信号流图,可以发现任何两个节点(p与q)经过蝶式运算后,其结果即为下一列p,q两节点的变量. 而每一级蝶式运算的输出,在该级运

11、算结束之后无需 保存.因此,任何一个蝶行运算的两个输出结果仍然可 以存放两个输入值所在的存储单元中.这样,整个运算 只需要N个寄存器,他们保存输入数据,并不断对每一 级运算结果刷新,直到最后输出。其优点在于节省存储资源.,第二节 按时间抽取FFT算法,3. 倒位序 观察同址运算结构,可以发现FFT输出端X(k)正好按07自然顺序排列的，而输出序列x(n)不是按07自然顺序排列。x(n)排列表面上混乱无序，而隐含着有规律的排列，即”倒位序”存贮,以N=8点FFT结构来说明。,存储器号 数据,结论:,第二节 按时间抽取FFT算法,倒位序排列是由于不断将DFT运算分解为较小点数DFT计算造成的。序列

12、x(n)首先分成偶数标号和奇数标号两个子序列：偶数序列出现在流图上半部,奇数序列出现在流图下半部。从形式上说,这样的划分可通过分析标号n的二进制表示 的最低位 来实现。标号为偶数，则 =0，标号为奇数，则 =1。这样 =0的标号出现在流图上半部,从中我们可以发现: 若, 则:,第二节 按时间抽取FFT算法,=1的标号出现在下半部。下一次奇偶序列的分解又分别根据标号二进制表示的倒数第二位 开始,根据 分别将第一次分解生成的两个子序列再一次按奇偶性分开。持续该过程,直得到N个长度为1的子序列。最后的排列顺序呈”倒位序”,第二节 按时间抽取FFT算法,所以要实现FFT算法，首先必须把按自然顺序存放的

13、数据变换成按倒序存放。这一过程称为整序，N=8时的整序过程下图所示。,第二节 按时间抽取FFT算法,小结: 1. 算法原理 2. 计算量: 复乘:复加: 3. 运算特点:蝶式运算.同址运算.倒位序,第二节 按时间抽取FFT算法,第三节 按频率抽取FFT算法,DIT:将输入序列x(n)按其标号n为奇数或偶数分解成短序列 DIF:将输出序列X(k)按其k值为奇数或偶数分解成短序列 算法原理 仍讨论基-2FFT,即 频域抽取法是将X(k)按标号k的自然顺序分成前后两半(注意:不再是奇偶顺序),第三节 按频率抽取FFT算法,按k为偶数或是奇数将x(k)分解成两部分,第三节 按频率抽取FFT算法,输入序

14、列前一半与后一半之差再与 乘积,令,输入序列前一半与后一半之和,第三节 按频率抽取FFT算法,与,可通过一蝶式运算(结构)单元得到:,第三节 按频率抽取FFT算法,这样一个N点 DFT就分解为两个N/2点DFT。以N=8为例，上述分解过程如图所示:,第三节 按频率抽取FFT算法,一次分解的运算过程分为两步: （1）前后两半序列合成 与 （2）分别求 与 N/2点DFT，结果为x(k)偶奇部分 特点：输入进行分解合成，输出不用合成，但顺序有变。 和DIT-FFT一样，N一次分解后，N/2仍是偶数，因此可进一步按上述方式分解，直至最后N/2个2点DFT的全部N个输出就是x(n)的N点DFT 。,第三节 按频率抽取FFT算法,下图是N=8时完整的按频率抽取的FFT结构,第三节 按频率抽取FFT算法,运算特点 和DIT-FFT基本相同，都是通过蝶形运算完成，也是原位运算，但其输入是正常位序，输出为倒位序。按流图转置定理，即将流图的所有支路方向取反，交换输入输出，系数保持不变，可得到流图的转置形式。比较DIT-FFT流图可知它们互为转置。根据转置定理，两个流图的