Chap4快速傅立叶变换(FFT)

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

1、Chap4快速傅立叶变换（快速傅立叶变换（FFT）本章主要内容本章主要内容v按时间抽取（按时间抽取（DIT）的）的FFT算法算法v按频率抽取（按频率抽取（DIF）的）的FFT算法算法v线性调频线性调频z变换变换v实序列实序列FFT算法算法vFFT应用应用4.1 引言引言一、一、DFT的计算工作量的计算工作量 101001101NknNnNknNnX kDFT x nx n WkNx nIDFT X kX k WnNN两者的差别仅在指数的符号和因子两者的差别仅在指数的符号和因子1/N4.1 引言（续）引言（续）分析计算一个分析计算一个X(k)的值的工作量的值的工作量:如如X(1)考虑一般情况：考

2、虑一般情况： 都是复数都是复数一个一个X(k)：N次复数乘法，（次复数乘法，（N-1）次复数加法）次复数加法所有所有X(k)：N2次复数乘法，次复数乘法，N（N-1）次复数加）次复数加法法运算量与运算量与N2（序列长度）成正比！（序列长度）成正比！当当N很大时，如很大时，如N=1024,则要完成则要完成1048576次次（一百多万次）运算，这样，难以做到实时处理。（一百多万次）运算，这样，难以做到实时处理。 012110121NNNNNXxWxWxWx NW ,nkNx nW4.1 引言（续）引言（续）二、算法改进二、算法改进1. 的对称性和周期性的对称性和周期性 对称性：对称性： 周期性：周

3、期性：nkNWN n kN k nnknkNNNNWWWWN n kN k nnkNNNWWW得到：22211NNjNNk NkNNWWeWW 4.1 引言（续）引言（续） 利用上述特性，可以将有些项合并，并将利用上述特性，可以将有些项合并，并将DFT分分解为短序列，从而降低运算次数，提高运算速度。解为短序列，从而降低运算次数，提高运算速度。1965年，库利（年，库利（cooley）和图基（）和图基（Tukey）首）首先提出先提出FFT算法，对于算法，对于N点点DFT，仅需，仅需 次复次复数乘法运算。例如数乘法运算。例如 ： 22 logNN101022102421024 2 log512*1

4、052105210 1048576N 时，需要次4.88，速度提高20倍4.1 引言（续）引言（续）例如：例如： 101010ReImReImReReImImReImImReNnkNnNnknkNNnNnknknknkNNNNnX kx n Wx njx nWjWx nWx nWjx nWx nW将第n项和第N-n项合并，其中实部部分得： ReReReReReReReN n knkNNnkNx nWx NnWx nx NnW乘法次数减少一半！其它项同样。4.2按时间抽取的按时间抽取的FFT算法算法 库利图基算法库利图基算法一、算法原理（基一、算法原理（基-2FFT）1.先将先将x(n)按按n的

5、奇偶分为两组做的奇偶分为两组做DFT，设，设不足时可在序列末尾补零，这样有：不足时可在序列末尾补零，这样有：n为偶数时：为偶数时：n为奇数时：为奇数时：因此：因此：2rN 122,0,1,1221,0,1,12Nxrx rrNxrxrr 10NnkNnX kDFT x nx n W4.2按时间抽取的按时间抽取的FFT算法（续）算法（续） 2 12 1212002 12 12212002222222 12 112122200221NNrkrkNNrnrkrkNNkNNNrrjjNNNNNNrkkrkkNNNNrrX kxr WxrWx rWWxrWWeeWX kx r WWxr WXkW Xk其

6、中： 2 12 11122002 12 1222200221NNrkrkNNrrNNrkrkNNrrXkx r Wxr WXkxr WxrW4.2按时间抽取的按时间抽取的FFT算法（续）算法（续） 均为均为N/2点点DFT 只能确定出只能确定出 的前的前N/2，即：，即： 的后的后N/2点的确定点的确定 12,X k X k 12kNXkW Xk X k0,1,2,12Nk X k 21222211211110022222212222()22,0,1,22NkNNr krkNNNr krkNNNNkkkNNNNkNNNNX kXkWXkWWNXkx r Wx r WXkNXkXkWW WWNX

7、 kXkW XkkNN22rr周期性同理，又,12N4.2按时间抽取的按时间抽取的FFT算法（续）算法（续） 的后一半也完全由的后一半也完全由 的前一半所确定。的前一半所确定。结论：结论： 一个一个N点序列的点序列的DFT可由两个可由两个N/2点的点的DFT来来确定。确定。 X k 12,X k X k4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）2.蝶形运算蝶形运算由由 表示表示 的运算是一种特殊的运算的运算是一种特殊的运算 12,X k X k X k 12120,1,2,12,12kNkNNX kXkW XkkNX kXkW XkkN实现上式运算的流图称作蝶形运算（N/2个蝶形

8、） 1X k 2X k1kNW1-1 122kNX kXkW XkN前点 1222kNX kNXkW XkN后点 1122,0,.,2 122NNXkXkXkXk kN4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）3.计算量分析：按奇偶分组后的计算量计算量分析：按奇偶分组后的计算量一个一个N/2点的点的DFT运算量运算量 ： 复乘次数：复乘次数： 复加次数：复加次数：两个两个N/2点的点的DFT运算量：运算量： 复乘次数：复乘次数： 复加次数：复加次数：一个蝶形运算量：一个蝶形运算量： 复乘次数：复乘次数：1 复加次数：复加次数：2N/2个蝶形运算量：个蝶形运算量： 复乘次数：复乘次

9、数： N/2 复加次数：复加次数：N总运算量：总运算量： 复乘：复乘： 复加：复加： 12X kX k或 直接运算量：运算量减少近一半！2224NN22 1NN22N2 1N N22222NNN22 12N NNN2N1N N 4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）例：例：N=8 可以分解为两个可以分解为两个N/24点的点的DFTN为偶数时，记N为奇数时，记 111100122436xxxxxxxx 222201132537xxxxxxxx分别计算N/24点的DFT，得 12,XkXk 3311440033224400221rkrkrrrkrkrrXkx r Wxr WXkx

10、r WxrW（k=0,1,2,3）4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）得：得： 12120,1,2,34,5,6,7kNkNX kXkW XkkX kXkW Xkk蝶形图如下：4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）同理：同理： 仍为偶数，可进一步把每个仍为偶数，可进一步把每个N/2点的序点的序列再按其奇偶部分分解为两个列再按其奇偶部分分解为两个N/4得子序列。得子序列。2 ,2rNN 1311420,1,2,14210,1,2,14Nxlxllx rNxlxll分解为分别进行N/4点的DFT，得 4 14 1233412004 14 12144412002

11、21NNlklkNNrrNNlklkNNrrXkxl Wxl WXkxl WxlW偶中偶（偶中奇）4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）这样，这样， 13241324kNkNXkXkWXkXkXkWXkN40,1,14Nk 2xr做相同的分解，并分别做傅立叶变换 252620,1,2,14210,1,2,14NxlxllNxlxll 4 155404 16640NlkNrNlkNrXkxl WXkxl W4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）由由 进行蝶形运算，得：进行蝶形运算，得： 56,XkXk 25262526kNkNXkXkWXkXkXkWXkN40

12、,1,14Nk 流图如下：4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）继续分解，直至两个一点为止。继续分解，直至两个一点为止。N8完整流图如下：完整流图如下：4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）二、二、DIT DFT算法小结：算法小结：计算一个计算一个 的的FFT时，需经过时，需经过 级分解，级分解，最终得到最终得到N/2个两点个两点DFT。由两点由两点DFT逐级合成逐级合成4点，点，8点，点， ，N点。点。每级中都有每级中都有N/2个蝶形。个蝶形。每次分解都是根据序列序号的奇偶进行的，故每次分解都是根据序列序号的奇偶进行的，故称为按时间抽取的算法。称为按时间抽

13、取的算法。DIT DFT 属于原位运算。属于原位运算。流图中输入流图中输入“乱序乱序”，输出，输出“顺序顺序”。2rN 2logN4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）“乱序乱序”原因原因210,x n n n00n 偶01n 奇10n 11n 10n 11n 01010101x(000)x(100)x(010)x(110)x(001)x(101)x(011)x(111)042615374.2按时间抽取的按时间抽取的FFT算法（续）算法（续）“整序整序”规律规律将输入序号按自然顺序排序后，用相应位数的二将输入序号按自然顺序排序后，用相应位数的二进制码表示，再进行反序，即可实现

14、输入端的整进制码表示，再进行反序，即可实现输入端的整序。序。自然顺序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 210n n n012n n n4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）蝶形图的规律蝶形图的规律第第 级：蝶形运算有级：蝶形运算有N/2个传输系数，为个传输系数，为2rN 0122 1,NNNNNWWWW共N/2个。第三级：蝶形运算类型有四个第二级：蝶形运算类型有二个第一级：蝶形运算类型

15、有一个每向前一级，W因子取偶数序号。参加蝶形运算两点间的距离规律：最后一级的间距最大，每向前推一级，间距减小一半。4.2按时间抽取的按时间抽取的FFT算法（续）算法（续）DIT DFT算法与直接计算的算法与直接计算的DFT运算量的比较运算量的比较 因为在 级运算中，每一级都有N/2个蝶形，每一级运算中运算有都有N/2次复乘和N次复加（见前面） 因而， 级运算中，共需要 复加次数： 复乘次数：2logNFmNN2log22NFNNa只考虑乘法计算量时，直接计算与FFT方法运算量相比：22222loglogNNNNNN足够大时，FFT有明显优势。4.2按时间抽取的按时间抽取的FFT算法（续）算法（

16、续）直接计算与直接计算与FFT方法，乘法运算比较曲线方法，乘法运算比较曲线 4.3按频率抽取（按频率抽取（DIF）的）的FFT算法算法 桑德图基算法桑德图基算法一、算法原理一、算法原理设设 不足时，可在末尾补零。不足时，可在末尾补零。将将x(n)按按n的自然顺序分为前后两组，即的自然顺序分为前后两组，即 ,2rx nN 0120122Nx nnNNx nn则： 1112002NNNknknknNNNNnnnX kx n Wx n Wx n W4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续） 1122200122021200,1,122( 1)( 1)2NNNk nknNN

17、nnNNkknNNnNkkNNkknNnNx n Wx nWkNNx nx nWWWNX kx nx nW 4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）考虑两种情况：考虑两种情况：当取偶数时：当取偶数时：k2r r=0,1,N/2-1当取奇数时：当取奇数时：k2r1 r=0,1,N/2-1 11222200222NNrnrnNNnnNNX kXrx nx nWx nx nW 1122212002122NNrnnrnNNNnnNNX kXrx nx nWx nx nW W令： 1222nNNx nx nx nNxnx nx nW则： 2 11202 1220221Nnr

18、NnNnrNnXrx n WXrxn Wr=0,1,2,N/2-1可见，上两式均为N/2点DFT4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）用蝶形图描述用蝶形图描述 如下如下： 12,x nxn x n2Nx nnNW 0,1,2,122NNx nx nn 2nNNx nx nW14.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）上述过程小结如下：上述过程小结如下：首先形成首先形成计算计算分别计算分别计算 的的N/2点的点的DFT，得到，得到X（k）的偶数点和奇数点的输出。的偶数点和奇数点的输出。 12,x nxn ,2Nx nx n 12,x n

19、xn4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）以以N=8为例，为例，DIF FFT算法流图如下：算法流图如下：先蝶形运算，后先蝶形运算，后FFT：4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续） 2 ,2rNN仍是偶数即 可继续分组，使得每一个N/2点的DFT由两个N/4点的DFT来得到，以此类推，直至分解到两个一点序列。 12,x nxn4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）例如例如N=8时时DIF的的FFT流图如下：流图如下：4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）可见：可见：一

20、个一个N=8点的点的DFT经三级（经三级（N=23）分解后，变）分解后，变为为计算两点的计算两点的DFT，而这两点的，而这两点的DFT实际上只有加实际上只有加减运算，在每一级运算中，都有减运算，在每一级运算中，都有N/2个蝶形参加个蝶形参加运算，其运算量同运算，其运算量同DIT FFT。 因此，因此，DIF FFT算法从始至终都是在进行分解，算法从始至终都是在进行分解，而而DIT FFT算法从始至终都是在进行组合。算法从始至终都是在进行组合。4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）二、二、DIT FFT与与DIF FFT 算法的比较算法的比较区别：区别：输入输出顺

21、序相反，每一种输入输出顺序相反，每一种DIT FFT算法都存在一算法都存在一种种DIF FFT算法，二者互为倒置。算法，二者互为倒置。两种算法的蝶形运算存在差异，两种算法的蝶形运算存在差异，W因子相乘的位置因子相乘的位置不同。不同。相同点：相同点：都有都有 级运算，每级都有级运算，每级都有N/2个蝶形。个蝶形。运算量相同，即需要运算量相同，即需要 次复乘，次复乘， 次复加次复加都是原位运算。都是原位运算。2log2NN2logNN2rN 设4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）三、三、IDFT FFT算法算法IFFT 1101,NNknknNNkn ox nX

22、k WX kx n WN两式相比， 相差一个负号，系数相差 ，故：可用FFT流图计算IFFT。NW1 N方法：输入输出调换将FFT流图中的 同 代替。输出的每一个支路乘以nNWnNW1 N4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续）例：由例：由N=8按频率抽取的按频率抽取的FFT流图求流图求IFFT流图流图4.3按频率抽取（按频率抽取（DIF）的）的FFT算法（续）算法（续） 可见，一个按频率抽取地可见，一个按频率抽取地FFT流图能够实现按流图能够实现按时间抽取地时间抽取地IFFT流图，同理一个按时间抽取的流图，同理一个按时间抽取的FFT流图可以实现按频率抽取地流图可

23、以实现按频率抽取地IFFT流图。流图。 实际上机实现时，可直接用实际上机实现时，可直接用FFT程序计算程序计算IFFT 101011NknNkNknNkx nX k WNXk WNDIT FFT和DIF FFT都要求 ，故称为基2FFT.2rN 4.5 N为复合数的为复合数的FFT算法算法 对于对于 情况，可用下述方法提高计算情况，可用下述方法提高计算DFT速度速度将序列补最少的零至将序列补最少的零至 ，这种方法不是最简的。，这种方法不是最简的。若要求至计算若要求至计算N点的点的DFT，而，而N又不能分解成素又不能分解成素数的积，则直接计算数的积，则直接计算DFTCZT. 若若N是一个复合数，

24、则有快速算法计算是一个复合数，则有快速算法计算DFT。 利用利用FFT的基本思想：将大点数的基本思想：将大点数DFT的运算尽量的运算尽量分解为小点数的运算，提高运算效率。分解为小点数的运算，提高运算效率。2rN 2r4.5 N为复合数的为复合数的FFT算法（续）算法（续）一、算法原理一、算法原理设：设： 长长N=ML M：列：列 L：行：行则：则： x n 1010100,1,10,1,1,0,1,1,NknNnX kx n WkNNM LnMnnx nnLnM将序列的序号用矩阵表示表示行号表示列号例： 124 30,1,2,1143Nx nnML，则：列行4.5 N为复合数的为复合数的FFT

25、算法（续）算法（续）将将n排成矩阵形式如下：排成矩阵形式如下：0n1nn0 1 2 30120 1 2 34 5 6 78 9 10 11L行M列矩阵中的序号5表示如下：101054 1 10,1,2012 3nMnnnn 行 ， ， ， 列4.5 N为复合数的为复合数的FFT算法（续）算法（续） 同理：对于同理：对于X(k)，k也可以表示成矩阵形式也可以表示成矩阵形式 10100,1,1,0,1,1,kMkkx nkMkL将序列的序号用矩阵表示表示列号表示行号（与n表示相反）010124 3430,1,2,30,1,2NMLkkk1则：k=3k例：1k0kn0 1 2 30120 1 2 3

26、4 5 6 78 9 10 114.5 N为复合数的为复合数的FFT算法（续）算法（续） 1000101 00 010101 00 001010110100110001100011000,NknNnMLLkknNnnMLkLk nk nLkNNNNnnMLkLk nk nNNNnnn kLkkX kX kX LkkX k kx n Wxn Wxn WWWWxn WWW11111Mn1MnMn1Mn1将n=Mn代入得：Mnnn4.5 N为复合数的为复合数的FFT算法（续）算法（续） 01 00 00101 00 0010 01 001 001110000110001100011002010,ML

27、kLk nk nNNNnnMLkLk nk nLNNnnMk nLk nNMnMk nMnX k kxn WWWNMLxn WWWXk nWWXk nWXk k 11Mn1n1nn行DFT4.5 N为复合数的为复合数的FFT算法（续）算法（续）说明：说明：1.011100000,0,1,1LkLnXk nxn WkL1n1n表示将 作为参变量，对0n0,xn1n做 与 之间的L1n0k点DFT，共有M个（ ）即：对x(n)的每一列（ ）做L点DFT，最后得到M点DFT.01,2,1nM01,2,1nM2.1 0012011000,Mk nMnXk kXk nW表示以 作参变量，在 与 之间做的

28、M点DFT，共有L个（ ）即：将行号为 的行序列 做M点DFT，共得N点DFT 0k0n1k01,2,1KL0k100,Xk n4.5 N为复合数的为复合数的FFT算法（续）算法（续）二、二、N为复合数的为复合数的DFT算法的运算步骤算法的运算步骤1. 011010,0,1,2,1 ,0,1,2,1x nx n nx MnnnLnM即：将x(n)的数据排成矩阵形式。2.对列作M个L点的DFT011100000,0,1,1LkLnXk nxn WkL1n1n3.形成一个N点的新序列0 0100100,k nNXk nXk nW 4.对行作L个M点的DFT1 0012011000,Mk nMnXk

29、 kXk nW5.译序 201,Xk kX k4.5 N为复合数的为复合数的FFT算法（续）算法（续）例：例：124 3NML4.5 N为复合数的为复合数的FFT算法（续）算法（续） 01110000,3LkLnXk nxn WL1n1n其中，01011100010100000013330120133302401333,30,0,000,00,01,02,011,00,01,02,022,00,01,02,0LkLnLkLnXkxn WLnXkxWkXxWxWxWkXxWxWxWkXxWxWxW 11n1n1nn4.5 N为复合数的为复合数的FFT算法（续）算法（续）三、基数三、基数 若序列长

30、度为若序列长度为 时，可通过时，可通过m级级r点点DFT来实现来实现N点点FFT的运算，这种运算称为基的运算，这种运算称为基rFFT算法（常算法（常用）用）如：如：r=2,4,8分别称为基分别称为基2，基，基4，基，基8算法。算法。若序列长度为若序列长度为 时，但可分解成一些因子的乘积，时，但可分解成一些因子的乘积，如：如：N=60=3*4*5,则，可分别进行则，可分别进行3,4,5点的点的DFT来实现来实现N点点FFT，这种算法通常称为混合基算法。，这种算法通常称为混合基算法。 注：这种分解方法不唯一。注：这种分解方法不唯一。2rN 2rN 4.5 N为复合数的为复合数的FFT算法（续）算法

31、（续）四、四、N为复合数的为复合数的FFT算法的运算量算法的运算量根据计算步骤：根据计算步骤：复数乘法复数乘法 复数加法复数加法M个个L点点DFT形成形成N点的新序点的新序列，乘列，乘N个个 N 0L个个M点点DFT总运算量总运算量直接计算直接计算N点的点的DFT0 0k nNW2ML1ML L 2LM1LM M 22(1)MLNLMN LM 112LM MML LN ML2N1N N 4.5 N为复合数的为复合数的FFT算法（续）算法（续）两种计算方法运算量比较两种计算方法运算量比较复数乘法比：复数乘法比：复数加法比：复数加法比：例：例：2(1)(1)N LMNLMN 2121N MLN N

32、MLN6012*5125 11860601559maNMLRR 结论：运算量明显减少！4.6 线性调频线性调频Z变换（变换（chirp z transform）一、算法原理一、算法原理已知：已知： ,01x nnN则： 10NnnX zx n z现在Z平面内对X(z)沿某一路径取样，取样点 ，点数为M个。kz令：,0,1,1kkzAWkM其中：0000,jjWW eAA e则：0000jjkkkzA eWe4.6 线性调频线性调频Z变换（变换（chirp z transform） 不同的不同的k，对应不同的取样点，对应不同的取样点000000000110022100111000121jjjjM

33、MMkzA ekzAW ekzAWekMzAWe：起始取样点 的半径：起始取样点 的相角，可正可负： 与 之间的角频率差，可正可负：0A000z0zkz1kz0W000111WWkW向外盘旋随向内盘旋单位圆的一部分4.6 线性调频线性调频Z变换变换(续续)若满足下列条件：若满足下列条件：1.2.3.MN001jAA e020jjNWW ee则： 就是单位圆上均匀分布的取样点。kz此时 就是 的DFTkX z x n4.6 线性调频线性调频Z变换变换(续续)将将 代入代入X(z)得：得：kkzAW 22222222210222122201222022120010,1,10,1,1Nnnkknn

34、knkNnknn kknNnnnnnkNknX zx n A WkMnknkX zx n AWWWWx n AWWf nx n AWnNh nWX zWf n h knkM1由布鲁斯坦公式：nk=2令：则：4.6 线性调频线性调频Z变换变换(续续) 22kkkzX zX zf kh kWFFT点的为：上述的卷积可通过实现，即 Lf nh nf nh nIDFT F r H rIDFT DFTf nDFT h n4.6 线性调频线性调频Z变换变换(续续) 22002220012nnjWh nWenddnn时，频率 频率与时间成线性关系，雷达系统中，通常称 为线性调频信号（chirp）。该方法对应

35、的变换称线性调频z变换。 h n4.6 线性调频线性调频Z变换变换(续续)CZT实现步骤实现步骤 x n h n22nnA W22kW0,1,2,1kX zkM1.根据A,W，求出 和f(n)22nnA W2. 利用FFT计算 与 L点（ ）圆周卷积 N： 的长度，M: 被截断的长度。 f n h n1LNM h n x n 22220111nk nWnMh nWLNnLMnLN 任意 nf4.6 线性调频线性调频Z变换变换(续续)3.取出卷积结果的前取出卷积结果的前M个值，并与个值，并与 相乘，即可。相乘，即可。解释解释 的选取方法：的选取方法：22kW h n4.6 线性调频线性调频Z变换

36、变换(续续)CZT运算量运算量计算计算 需要需要N次复乘次复乘计算计算计算计算 需要需要L次复乘次复乘计算计算 需要需要M次复乘次复乘共计：共计： 复乘。复乘。直接计算需要直接计算需要MN复乘。复乘。 f n 2log2LF rLH rg kG r各需复乘 G rF r L r 22kkX zg k W23log2LLNLM当M,N足够大时，CZT运算量将大大减少。4.6 线性调频线性调频Z变换变换(续续)CZT特点特点与标准与标准FFT算法相比：算法相比：输入与输出的序列长度不必相等。输入与输出的序列长度不必相等。N与与M均可为素数，而这不必是高度复合。均可为素数，而这不必是高度复合。 的角

37、间隔的角间隔 是任意的，因此频率分辨率也是任意的。是任意的，因此频率分辨率也是任意的。取样轨迹不必是圆取样轨迹不必是圆起始点位置可任意选定，目的是可从任意频率上开始起始点位置可任意选定，目的是可从任意频率上开始对输入数据进行窄带的高分辨率的分析。对输入数据进行窄带的高分辨率的分析。CZT是是FFT的推广，是一般化的的推广，是一般化的DFT，FFT是是CZT的一的一个特例。个特例。kz04.7 实序列的实序列的FFT算法算法一、一个一、一个N点点FFT同时计算两个同时计算两个N点实序列的点实序列的DFT设设 长度为长度为N，均为实序列，均为实序列， 现将现将 组合乘一个复序列，得：组合乘一个复序

38、列，得： 12,x nxn 12,x nxn 12,?XkXk 121212121212epopx nx njxnX kDFT x nDFT x njDFT xnXkjXkXkXkX kXNkXkXkjX kXNk 则：其中：j4.7 实序列的实序列的FFT算法（续）算法（续）注意：注意： 1211212X kXkjXkXkX kXkXkXk虽然但：因为：，不是实函数！4.7 实序列的实序列的FFT算法（续）算法（续）三、一个三、一个N点点FFT计算一个计算一个2N点实序列的点实序列的DFT设：设： 长度为长度为2N现将现将 按序号的奇偶分为两个序列按序号的奇偶分为两个序列 x n x n 1

39、212121211222211212x nxnxnxny nx njxnY kDFT y nDFT x njDFT xnXkjXkXkDFT x nY kYNkXkDFT xnY kYNk令：则：其中：-j0,1,2,1nN4.7 实序列的实序列的FFT算法（续）算法（续）现在寻找现在寻找 与与 的关系的关系 X k 12,XkXk 11212001122200122122122222212121021NNnknkNNnnNNnknkNNnnkNkNkNXkDFT xnxn Wxn WXkDFT xnxnWxnWFFTX kXkWXkkNX kXkWXkX kNXkWXk根据按时间抽取的算法，

40、得：或0,1,1kN4.7 实序列的实序列的FFT算法（续）算法（续）运算量分析运算量分析复乘次数：复乘次数：复加次数：复加次数：直接计算直接计算2N点点DFT复乘次数：复乘次数：复加次数复加次数:N很大时，工作量节省近一倍！很大时，工作量节省近一倍！ 22log2log:222NNNNNY kX kN计算：， 2212log4log:4NNNNY kXkXkX kN计算：N，计算，222log(1 log )NNNN2222log(1 log )NNNN24.8 快速傅立叶变换应用快速傅立叶变换应用一、用一、用FFT求线性卷积求线性卷积快速卷积快速卷积用用FFT求两个长度相差很大得序列得线性

41、卷积求两个长度相差很大得序列得线性卷积利用利用DFT的圆周卷积定理：的圆周卷积定理：当其中一个序列很长时，可用重叠相加法或叠接保当其中一个序列很长时，可用重叠相加法或叠接保留法。留法。高效的高效的FFT卷积卷积用一次用一次FFT同时完成两个卷积同时完成两个卷积 Nx nh nx nh nIDFT X k H k 12yng nh nyns nh n4.8 快速傅立叶变换应用（续）快速傅立叶变换应用（续）方法：方法： 12ReImp ng njs nDFTp nP kG kjS kY kH k P kIFFT Y kp nh ng njs nh ng nh njs nh nyny ng nh nyny ns nh n令：则：y n4.8 快速傅立叶变换应用（续）快速傅立叶变换应用（续）对应的三种实际使用情况：对应的三种实际使用情况：一个系统同时通过两个输入信号一个系统同时通过两个输入信号一个信号同时通过两个系统一个信号同时通过两个系统一个系统同时处理长序列分段过程中的两个片一个系统同时处理长序列分段过程中的两个片断断二、用二、用FFT求线性相关求线性相关快速相关快速相关 利用利用DFT的圆周相关定理：的圆周相关定理： Nx n h nRRIFFT Xk H k点圆周本章内容结束