Chap4快速傅立叶变换(FFT).ppt

《Chap4快速傅立叶变换(FFT).ppt》由会员分享，可在线阅读，更多相关《Chap4快速傅立叶变换(FFT).ppt（69页珍藏版）》请在三一办公上搜索。

1、Chap4快速傅立叶变换（FFT）,本章主要内容按时间抽取（DIT）的FFT算法按频率抽取（DIF）的FFT算法线性调频z变换实序列FFT算法FFT应用,4.1 引言,一、DFT的计算工作量,两者的差别仅在指数的符号和因子1/N,4.1 引言（续）,分析计算一个X(k)的值的工作量:如X(1)考虑一般情况：都是复数一个X(k)：N次复数乘法，（N-1）次复数加法所有X(k)：N2次复数乘法，N（N-1）次复数加法运算量与N2（序列长度）成正比！当N很大时，如N=1024,则要完成1048576次（一百多万次）运算，这样，难以做到实时处理。,4.1 引言（续）,二、算法改进1.的对称性和周期性

2、对称性：周期性：,得到：,4.1 引言（续）,利用上述特性，可以将有些项合并，并将DFT分解为短序列，从而降低运算次数，提高运算速度。1965年，库利（cooley）和图基（Tukey）首先提出FFT算法，对于N点DFT，仅需 次复数乘法运算。例如：,4.1 引言（续）,例如：,将第n项和第N-n项合并，其中实部部分得：,乘法次数减少一半！其它项同样。,4.2按时间抽取的FFT算法 库利图基算法,一、算法原理（基-2FFT）1.先将x(n)按n的奇偶分为两组做DFT，设不足时可在序列末尾补零，这样有：n为偶数时：n为奇数时：因此：,4.2按时间抽取的FFT算法（续）,其中：,4.2按时间抽取的

3、FFT算法（续）,均为N/2点DFT 只能确定出 的前N/2，即：的后N/2点的确定,4.2按时间抽取的FFT算法（续）,的后一半也完全由 的前一半所确定。结论：一个N点序列的DFT可由两个N/2点的DFT来确定。,4.2按时间抽取的FFT算法（续）,2.蝶形运算由 表示 的运算是一种特殊的运算,实现上式运算的流图称作蝶形运算（N/2个蝶形）,1,1,-1,4.2按时间抽取的FFT算法（续）,3.计算量分析：按奇偶分组后的计算量一个N/2点的DFT运算量：复乘次数：复加次数：两个N/2点的DFT运算量：复乘次数：复加次数：一个蝶形运算量：复乘次数：1 复加次数：2N/2个蝶形运算量：复乘次数：

4、N/2 复加次数：N总运算量：复乘：复加：,直接运算量：,运算量减少近一半！,4.2按时间抽取的FFT算法（续）,例：N=8 可以分解为两个N/24点的DFT,N为偶数时，记,N为奇数时，记,分别计算N/24点的DFT，得,（k=0,1,2,3）,4.2按时间抽取的FFT算法（续）,得：,蝶形图如下：,4.2按时间抽取的FFT算法（续）,同理：仍为偶数，可进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4得子序列。,分别进行N/4点的DFT，得,4.2按时间抽取的FFT算法（续）,这样，,做相同的分解，并分别做傅立叶变换,4.2按时间抽取的FFT算法（续）,由 进行蝶形运算，得：,流图如

5、下：,4.2按时间抽取的FFT算法（续）,继续分解，直至两个一点为止。N8完整流图如下：,4.2按时间抽取的FFT算法（续）,二、DIT DFT算法小结：计算一个 的FFT时，需经过 级分解，最终得到N/2个两点DFT。由两点DFT逐级合成4点，8点，N点。每级中都有N/2个蝶形。每次分解都是根据序列序号的奇偶进行的，故称为按时间抽取的算法。DIT DFT 属于原位运算。流图中输入“乱序”，输出“顺序”。,4.2按时间抽取的FFT算法（续）,“乱序”原因,0,1,0,1,0,1,0,1,x(000),x(100),x(010),x(110),x(001),x(101),x(011),x(111

6、),0426,1537,4.2按时间抽取的FFT算法（续）,“整序”规律将输入序号按自然顺序排序后，用相应位数的二进制码表示，再进行反序，即可实现输入端的整序。,自然顺序n 二进制 反序二进制 倒位顺序n 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7,4.2按时间抽取的FFT算法（续）,蝶形图的规律第 级：蝶形运算有N/2个传输系数，为,共N/2个。,第三级：蝶形运算类型有四个,第二级：蝶形运算类型有二个,第一级：蝶形运算类型有一个,每向前一级，W因

7、子取偶数序号。参加蝶形运算两点间的距离规律：最后一级的间距最大，每向前推一级，间距减小一半。,4.2按时间抽取的FFT算法（续）,DIT DFT算法与直接计算的DFT运算量的比较,因为在 级运算中，每一级都有N/2个蝶形，每一级运算中运算有都有N/2次复乘和N次复加（见前面）因而，级运算中，共需要 复加次数：复乘次数：,只考虑乘法计算量时，直接计算与FFT方法运算量相比：,N足够大时，FFT有明显优势。,4.2按时间抽取的FFT算法（续）,直接计算与FFT方法，乘法运算比较曲线,4.3按频率抽取（DIF）的FFT算法 桑德图基算法,一、算法原理设 不足时，可在末尾补零。将x(n)按n的自然顺序

8、分为前后两组，即,则：,4.3按频率抽取（DIF）的FFT算法（续）,4.3按频率抽取（DIF）的FFT算法（续）,考虑两种情况：当取偶数时：k2r r=0,1,N/2-1当取奇数时：k2r1 r=0,1,N/2-1,令：,则：,r=0,1,2,N/2-1,可见，上两式均为N/2点DFT,4.3按频率抽取（DIF）的FFT算法（续）,用蝶形图描述 如下：,1,4.3按频率抽取（DIF）的FFT算法（续）,上述过程小结如下：首先形成计算分别计算 的N/2点的DFT，得到X（k）的偶数点和奇数点的输出。,4.3按频率抽取（DIF）的FFT算法（续）,以N=8为例，DIF FFT算法流图如下：先蝶形

9、运算，后FFT：,4.3按频率抽取（DIF）的FFT算法（续）,仍是偶数,即 可继续分组，使得每一个N/2点的DFT由两个N/4点的DFT来得到，以此类推，直至分解到两个一点序列。,4.3按频率抽取（DIF）的FFT算法（续）,例如N=8时DIF的FFT流图如下：,4.3按频率抽取（DIF）的FFT算法（续）,可见：一个N=8点的DFT经三级（N=23）分解后，变为计算两点的DFT，而这两点的DFT实际上只有加减运算，在每一级运算中，都有N/2个蝶形参加运算，其运算量同DIT FFT。因此，DIF FFT算法从始至终都是在进行分解，而DIT FFT算法从始至终都是在进行组合。,4.3按频率抽取

10、（DIF）的FFT算法（续）,二、DIT FFT与DIF FFT 算法的比较区别：输入输出顺序相反，每一种DIT FFT算法都存在一种DIF FFT算法，二者互为倒置。两种算法的蝶形运算存在差异，W因子相乘的位置不同。相同点：都有 级运算，每级都有N/2个蝶形。运算量相同，即需要 次复乘，次复加都是原位运算。,4.3按频率抽取（DIF）的FFT算法（续）,三、IDFT FFT算法IFFT,两式相比，相差一个负号，系数相差，故：可用FFT流图计算IFFT。,方法：输入输出调换将FFT流图中的 同 代替。输出的每一个支路乘以,4.3按频率抽取（DIF）的FFT算法（续）,例：由N=8按频率抽取的F

11、FT流图求IFFT流图,4.3按频率抽取（DIF）的FFT算法（续）,可见，一个按频率抽取地FFT流图能够实现按时间抽取地IFFT流图，同理一个按时间抽取的FFT流图可以实现按频率抽取地IFFT流图。实际上机实现时，可直接用FFT程序计算IFFT,DIT FFT和DIF FFT都要求，故称为基2FFT.,4.5 N为复合数的FFT算法,对于 情况，可用下述方法提高计算DFT速度将序列补最少的零至，这种方法不是最简的。若要求至计算N点的DFT，而N又不能分解成素数的积，则直接计算DFTCZT.若N是一个复合数，则有快速算法计算DFT。利用FFT的基本思想：将大点数DFT的运算尽量分解为小点数的运

12、算，提高运算效率。,4.5 N为复合数的FFT算法（续）,一、算法原理设：长N=ML M：列 L：行则：,例：,4.5 N为复合数的FFT算法（续）,将n排成矩阵形式如下：,0 1 2 3,012,0 1 2 3 5 6 78 9 10 11,L行,M列,矩阵中的序号5表示如下：,4.5 N为复合数的FFT算法（续）,同理：对于X(k)，k也可以表示成矩阵形式,（与n表示相反）,例：,0 1 2 3,012,0 1 2 3 5 6 78 9 10 11,4.5 N为复合数的FFT算法（续）,4.5 N为复合数的FFT算法（续）,行DFT,4.5 N为复合数的FFT算法（续）,说明：1.,表示将

13、 作为参变量，对,做 与 之间的L,点DFT，共有M个（）即：对x(n)的每一列（）做L点DFT，最后得到M点DFT.,2.,表示以 作参变量，在 与 之间做的M点DFT，共有L个（）即：将行号为 的行序列 做M点DFT，共得N点DFT,4.5 N为复合数的FFT算法（续）,二、N为复合数的DFT算法的运算步骤1.,即：将x(n)的数据排成矩阵形式。,2.对列作M个L点的DFT,3.形成一个N点的新序列,4.对行作L个M点的DFT,5.译序,4.5 N为复合数的FFT算法（续）,例：,4.5 N为复合数的FFT算法（续）,其中，,4.5 N为复合数的FFT算法（续）,三、基数 若序列长度为 时

14、，可通过m级r点DFT来实现N点FFT的运算，这种运算称为基rFFT算法（常用）如：r=2,4,8分别称为基2，基4，基8算法。若序列长度为 时，但可分解成一些因子的乘积，如：N=60=3*4*5,则，可分别进行3,4,5点的DFT来实现N点FFT，这种算法通常称为混合基算法。注：这种分解方法不唯一。,4.5 N为复合数的FFT算法（续）,四、N为复合数的FFT算法的运算量根据计算步骤：,4.5 N为复合数的FFT算法（续）,两种计算方法运算量比较复数乘法比：复数加法比：例：,结论：运算量明显减少！,4.6 线性调频Z变换（chirp z transform）,一、算法原理已知：,则：,现在Z

15、平面内对X(z)沿某一路径取样，取样点，点数为M个。,令：,其中：,则：,4.6 线性调频Z变换（chirp z transform）,不同的k，对应不同的取样点,：起始取样点 的半径：起始取样点 的相角，可正可负：与 之间的角频率差，可正可负：,4.6 线性调频Z变换(续),若满足下列条件：1.2.3.,则：就是单位圆上均匀分布的取样点。,此时 就是 的DFT,4.6 线性调频Z变换(续),将 代入X(z)得：,4.6 线性调频Z变换(续),4.6 线性调频Z变换(续),频率与时间成线性关系，雷达系统中，通常称 为线性调频信号（chirp）。该方法对应的变换称线性调频z变换。,4.6 线性调

16、频Z变换(续),CZT实现步骤,1.根据A,W，求出 和f(n),2.利用FFT计算 与 L点（）圆周卷积 N：的长度，M:被截断的长度。,4.6 线性调频Z变换(续),3.取出卷积结果的前M个值，并与 相乘，即可。解释 的选取方法：,4.6 线性调频Z变换(续),CZT运算量计算 需要N次复乘计算计算 需要L次复乘计算 需要M次复乘共计：复乘。直接计算需要MN复乘。,当M,N足够大时，CZT运算量将大大减少。,4.6 线性调频Z变换(续),CZT特点与标准FFT算法相比：输入与输出的序列长度不必相等。N与M均可为素数，而这不必是高度复合。的角间隔 是任意的，因此频率分辨率也是任意的。取样轨迹

17、不必是圆起始点位置可任意选定，目的是可从任意频率上开始对输入数据进行窄带的高分辨率的分析。CZT是FFT的推广，是一般化的DFT，FFT是CZT的一个特例。,4.7 实序列的FFT算法,一、一个N点FFT同时计算两个N点实序列的DFT设 长度为N，均为实序列，现将 组合乘一个复序列，得：,4.7 实序列的FFT算法（续）,注意：,4.7 实序列的FFT算法（续）,三、一个N点FFT计算一个2N点实序列的DFT设：长度为2N现将 按序号的奇偶分为两个序列,4.7 实序列的FFT算法（续）,现在寻找 与 的关系,4.7 实序列的FFT算法（续）,运算量分析复乘次数：复加次数：直接计算2N点DFT复乘次数：复加次数:N很大时，工作量节省近一倍！,4.8 快速傅立叶变换应用,一、用FFT求线性卷积快速卷积用FFT求两个长度相差很大得序列得线性卷积利用DFT的圆周卷积定理：当其中一个序列很长时，可用重叠相加法或叠接保留法。高效的FFT卷积用一次FFT同时完成两个卷积,4.8 快速傅立叶变换应用（续）,方法：,4.8 快速傅立叶变换应用（续）,对应的三种实际使用情况：一个系统同时通过两个输入信号一个信号同时通过两个系统一个系统同时处理长序列分段过程中的两个片断二、用FFT求线性相关快速相关 利用DFT的圆周相关定理：,本章内容结束,