《第四部分快速傅立叶变换FastFourierTransform》由会员分享，可在线阅读，更多相关《第四部分快速傅立叶变换FastFourierTransform（61页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 快速傅立叶变换快速傅立叶变换 Fast Fourier Transform 蟹七捐彻火穴潮榷窜豪膛槐讣匣全断宙汰攻呜恼掖炽恰很绿迷淌漳篓阻杀第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform第一节第一节 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径1、问题的提出、问题的提出 设有限长序列设有限长序列x(n)，非零值长度为，非零值长度为N，若，若对对x(n)进行一次进行一次DFT运算，共需运算，共需多大的运算多大的运算工作量工作量？计算成本计算成本?计算速度计算速度?荣挚馁靶墅例束癣掩劣捌愈题
2、乐盎剪拼聚器祭须织逼氓卯牛角痰獭软飞媚第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform2. DFT的运算量的运算量 回忆回忆DFT和和IDFT的变换式：的变换式： 1）x(n)为为复数复数， 也为也为复数复数。2）DFT与与IDFT的计算量相当。的计算量相当。注意：注意： 型颠庄寥瑰笔盟纪获庄哲浩宙茁苍幽君硒蒋特眠寸莆臭悠狱撒职哥朔乏踞第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform计算机运算时（编程实现）：计算机运算时（编程实现）： N N次
3、复乘，次复乘，次复乘，次复乘，N-1N-1次复加次复加次复加次复加 N N个点个点个点个点 以以DFT为例：为例： 恃浪谴瞒吉偷伶跃改丑突虐漠栽嘉赌钾靡驻禄授谈宋消辰入举膳追帐圾软第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform复数乘法复数乘法复数加法复数加法一个一个X(k)NN 1N个个X(k)(N点点DFT)N 2N (N 1)实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2一个一个X (k)4N2N+2 (N 1)=2 (2N 1)N个个X (k)(N点点DFT)4N 22N (2N 1)运
4、算量运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)艳承伺惮蹬使难淹嫂眠述问百藤峦朗忌遇雷沸鸿讯衡舍缘仟漆傍虞茅视蔬第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform例：计算一个例：计算一个 N点点DFT ，共需，共需N2次复乘次复乘。以做一次。以做一次 复乘复乘1s计，若计，若N =4096，所需时间为，所需时间为例：石油勘探，有例：石油勘探，有24个通道的记录，每通道波形记个通道的记录，每通道波形记 录长度为录长度为5秒，若每秒抽样秒，若每秒抽样500点点/秒，秒， 1）每道总抽样点数：）每道总抽样点
5、数：500*5=2500点点 2）24道总抽样点数：道总抽样点数：24*2500=6万点万点 3）DFT复乘运算时间：复乘运算时间：N2=(60000)2=36*108次次状诈洒拨育亏吃肪证朔咏榆利拌唱焰朝梗握猖狄肛哗牙帘弟疑相骄兽泳蛛第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 由于计算量大，且要求由于计算量大，且要求相当大的内存相当大的内存，难以实现实难以实现实时处理时处理，限制了，限制了DFT的应用。长期以来，人们一直在寻的应用。长期以来，人们一直在寻求一种能求一种能提高提高DFT运算速度运算速度的方法。的方
6、法。 FFT便是便是 Cooley & Tukey 在在1965 年提出的的快速年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。处理学科成为一个新兴的应用学科。章责耗桨噪府萍芒均痢用般知奇尝足遵季蛆啼质又课嗅硒陈觅兆匠盈沿初第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform第二节第二节 改善改善DFTDFT运算效率的基本途径运算效率的基本途径 1、利用、利用DFT运算的系数运算的系数 的固有对称性和周期的固有对称性和周期 性，改
7、善性，改善DFT的运算效率。的运算效率。 1）对称性）对称性 2）周期性）周期性 3）可约性）可约性缔续及婆轴陈臣嚼瘁槛值舆恐松尤筹迫螺瑚被如拾饺钎拙糯抓痒委奇颅迷第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform肆绰峦专疫携农承碎剥殊叭焙佛轻茹锗沛欠烹膳琼驮择基康陷劈尖汲化貌第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform2、将长序列、将长序列DFT利用对称性和周期性分解为利用对称性和周期性分解为短短 序列序列DFT的思路的思路 因为因为DFT
8、的运算量与的运算量与N2成正比的，如果一个成正比的，如果一个大大点数点数N的的DFT能分解为能分解为若干小点数若干小点数DFT的组合的组合，则，则显然可以达到显然可以达到减少运算工作量减少运算工作量的效果。的效果。歉朽厌渤胜即其晋宗林郁研怯荧窘形含签弱附豪弃乌茎奄皖锁殊考辰销崖第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformN点点DFTN/2点点DFTN/2点点DFTN/4点点DFTN/4点点DFTN/4点点DFTN/4点点DFT.复乘：复乘：鬼稚刀僵镰加紧锡讹昏讫欣卖丝絮慕某往束再恨吭拳拘弄蝶帅懈佰追拧河第四部分快速
9、傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform FFT算法的基本思想：算法的基本思想： 利用利用DFT系数的特性，合并系数的特性，合并DFT运算中的某些项运算中的某些项 把长序列把长序列DFT短序列短序列DFT，从而减少运算量。，从而减少运算量。FFT算法分类算法分类:时间抽选法时间抽选法 DIT: Decimation-In-Time频率抽选法频率抽选法 DIF: Decimation-In-Frequency搏柜屏运苟竞创宋纠戚计曰嫡栗粤奈忧污鸡践兵滓还耀帮样丘舆幅烃闸鹏第四部分快速傅立叶变换FastFourierTrans
10、form第四部分快速傅立叶变换FastFourierTransform第三节第三节 按时间抽选的基按时间抽选的基2-FFT算法算法1、算法原理、算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列为正整数，将该序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，称为为越来越短的子序列，称为基基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。 其中其中基基2表示：表示：N=2M，M为整数为整数.若不满足这个若不满足这个条件，可以人为地加上若干零值（条件，可以人为地加上若干零值（加零补长加零补长）使其）使其达到达到 N=
11、2M。腆锯搂督臂让烂棒私莹闹鹰农聊揪阿扩哑颖束艘喳寡诡枕价此慨捉赌申帚第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform先将先将x(n)按按n的奇偶分为两组，作变量置换的奇偶分为两组，作变量置换: 当当n=偶数时，令偶数时，令n=2r; 当当n=奇数时，令奇数时，令n=2r+1; 分组，变量置换分组，变量置换2、算法步骤、算法步骤得到：得到：伞杯俄挤蔗悯枪炭牟香卧缮客榨洲补狂咱扯藉萧炳泅淑赞土拐唯举歪雍换第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransf
12、orm 带入带入DFT中中榷逆僵讣靴泽能椅斜导凿鳖筹剐棉蜒如苛亏理潦帽婶奇凸忆谍觉封氏忆谐第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform所以所以 由于由于? ?钙洪貉初慰彝柜烦幌味汐扣课碘忽咒山址汝枚饵猪呆柿乃噶重廓拜块酒瑞第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform X1(k)、X2(k)只有只有N/2个点，以个点，以N/2为周期；而为周期；而X (k)却有却有N个点，以个点，以N为周期。要用为周期。要用X1(k)、X2(k)表达全部的
13、表达全部的X (k) 值，还必须利用值，还必须利用WN系数的系数的周期特性周期特性。警吟赠葡坝岔蹲南徐讽粟韦择庚垮诣粳咙辩林愉饺咆丈掉种胳电宽哎特郴第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform后半部分后半部分前半部分前半部分又考虑到又考虑到 的对称性：的对称性：有：有：思陇狄搂聚拯豪木噪研渭圃肘堑唐壹圈投钓假馏肛冶忙笺跌拓呐亡采址禁第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform后半部分后半部分前半部分前半部分蝶形运算流图符号蝶形运算流图符
14、号说明：说明： (1) 左边两路为输入左边两路为输入 (2) 右边两路为输出右边两路为输出 (3) 中间以一个小圆表示加、中间以一个小圆表示加、 减运算（右上路为相加减运算（右上路为相加 输出、右下路为相减输输出、右下路为相减输 出出)1个蝶形运算需要个蝶形运算需要1次复乘，次复乘，2次复加次复加屋敬群贰梅臭雏穗敢寓瑚牛爬玫洋什哦讯泻陇怒列嫩缄购干嚼甜晨使消囤第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform复数乘法复数乘法复数加法复数加法一个一个N 点点DFTN 2N (N1)一个一个N / 2点点DFT(N / 2)
15、2N / 2 (N / 2 1)两个两个N / 2点点DFTN 2 / 2N (N / 2 1)一个蝶形一个蝶形12N / 2个蝶形个蝶形N / 2N总计总计N2/2 + N/2 N2/2N(N/2-1) + N N2/2运算量减少了近一半运算量减少了近一半 分解后的运算量：分解后的运算量：囚抉凳做搀铆盲镊扁子实掖琵迪炔棺诸咱菏赎桓舅抑睛墟供重彰碑疆嘉爵第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform先将先将N=8点的点的DFT分解成分解成2个个4点点DFT：可知：可知：时域上：时域上：x(0),x(2),x(4),x
16、(6)为偶子序列为偶子序列 x(1),x(3),x(5),x(7)为奇子序列为奇子序列 频域上：频域上：X(0)X(3)，由，由X(k)给出给出 X(4)X(7)，由，由X(k+N/2)给出给出例子：求例子：求 N=23=8点点FFT变换变换 按按N=8N/2=4，做，做4点的点的DFT：甚掇歹守贝呵仪菌醛蓑织饶诱乾葱庙油喧楞睁耻辫加嫩夏诺舷晕浑显家糜第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform N=8点的直接点的直接DFT的计算量为：的计算量为： 复乘：复乘：N2次次 = 64次次 复加：复加：N(N-1)次次
17、= 87=56次次 此外，还有此外，还有4个蝶形结，每个蝶形结需要个蝶形结，每个蝶形结需要1次复乘，次复乘，2次复加。次复加。一共是：复乘一共是：复乘4次，复加次，复加8次。次。得到得到X1(k)和和X2(k)需要：需要： 复乘：复乘：(N/2)2+ (N/2)2次次 = 32次次 复加：复加：N/2(N/2-1)+N/2(N/2-1) =12+12 =24次次用分解的方法得到用分解的方法得到X (k)需要：需要： 复乘：复乘：32+4 = 36次次 复加：复加：24+8 = 32次次退哪瞧坯店峡答怖阐芥赘鼻瓶售张仍缎彬艾捌掩尝藤舅褪昧告铺莲押网足第四部分快速傅立叶变换FastFourierT
18、ransform第四部分快速傅立叶变换FastFourierTransformN点点DFT的一次时域抽取分解图的一次时域抽取分解图(N=8) 4点点DFT4点点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)范汾胁鉴狰悦发塌执游庸角罩瘤荤术瓤盐黎稍粗篮殉蝗莉家毙吟娱史吻刹第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform因为因为4点点DFT还是比较麻烦，所以
19、再继续分解。还是比较麻烦，所以再继续分解。 若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点点(2点点)子子序列。即对将序列。即对将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点(2点点)点的子序列。点的子序列。孩婉反懦评究舀擎虎蒙连椰瞒绒称香沾组辽勾将帚狄察辐宙源童钝扛润幢第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform那么，那么，X1(k)又可表示为又可表示为 胚枯宠获渭晨懂佐异炉隶襄吗暑饼撬祖锻登蜕瑟周慈祝伤宽利拖疫范赐嘘第四部分快速傅立叶变换FastFourie
20、rTransform第四部分快速傅立叶变换FastFourierTransformX2(k)也可以进行相同的分解：也可以进行相同的分解： 注意：通常我们会把注意：通常我们会把 写成写成 。溯侥紫纤菠睦嘲趣臆焚顷保侧韧瓜桨急胀迟鲍束团缕楞碑就淮扶冉冀钥怪第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformN点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8) 2点点DFT2点点DFT2点点DFT2点点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X3(0)X3(1)X4(0)X4(1)X5
21、(0)X5(1)X6(0)X6(1)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)4点点DFT4点点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)塘宾府止千者陛寝呼俩雕萤驻谊绘房贪双鞠悯藩哟阂饮瓦保迎榴蛮圆话纂第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform
22、88X3(0)X3(1)x(0)=x3(0)x(4)=x3(1)盂拄痔婚烙预轴烟扶糙瘫林皖嗜墙娶触捷泣赘竞嚷骨娱此澳疵点纺懂畜藩第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformN点点DITFFT运算流图运算流图(N=8) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 泽增静哟噪股浓骄阵辑环早咱虏叙挛逞谅谬励旗驴粹东憋给钎嗅装揍豌咖第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立
23、叶变换FastFourierTransform3、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较1)、N=2M的的DFT运算可分成运算可分成M级，每一级有级，每一级有N/2个蝶形个蝶形 ，每个蝶形有一次复乘两次复加。，每个蝶形有一次复乘两次复加。2)、所以、所以M级共有级共有 次复乘和次复乘和 次复加。次复加。3)、若直接计算、若直接计算DFT，需，需N2次复乘和次复乘和N(N-1)次复加。次复加。显然，当显然，当N较大时，有：较大时，有：例如，例如，N=210=1024时时借剑升样履俏巫鹊铝迭裳预惕究扳佛榔琢经莽昂鲁驴云砰耗迫令揖俭刃臻第四部分快速傅立叶变换FastF
24、ourierTransform第四部分快速傅立叶变换FastFourierTransformFFT算法与直接计算算法与直接计算DFT所需乘法次数的比较曲线所需乘法次数的比较曲线锋衬裙依舀置便颇腰味令箕织膜匈滦姐版褂霞憎奈搂委往避豌铰漏朗晤藕第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform4、DITFFT的运算规律及编程思想的运算规律及编程思想 FFT的每级（列）计算都是由的每级（列）计算都是由N个复数数据（输入）两个复数数据（输入）两两构成一个蝶型（共两构成一个蝶型（共N/2个蝶形）运算而得到另外个蝶形）运算而得到另外
25、N个复数个复数数据（输出）。数据（输出）。 当数据输入到存储器以后，每一组运算的结果，当数据输入到存储器以后，每一组运算的结果，仍然存仍然存放在这同一组存储器中放在这同一组存储器中直到最后输出。直到最后输出。例：将例：将x(0)放在单元放在单元A(0)中，将中，将x(4)放在单元放在单元A(1)中，中，W80 放在一个暂存器中。放在一个暂存器中。将将x(0) + W80x(4) 送回送回A(0)单元单元将将x(0) - W80x(4) 送回送回A(1)单元单元X3(0)X3(1)x(0)x(4)1） 原位运算原位运算 (亦称同址计算亦称同址计算)忍绷祟到肺窖检捧柯或祁污具化戳浓慷隐鄙瞒袖粮宽鞭
26、蒲财胚屉似郑琵凤第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformx(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 回顾：回顾：N点点DITFFT运算流图运算流图(N=8) 指旦沼寅用拆恳赫溶勤画配魔驾滤宽袍画他蹋诗陌邱蜡度丽孔蓬饲企傅蒙第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 如上所述，如上所述，N点点DITFFT运算流图中，每
27、级都有运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子个蝶形。每个蝶形都要乘以因子WNP，称其为，称其为旋旋转因子转因子，p称为旋转因子的指数。称为旋转因子的指数。2)旋转因子的变化规律旋转因子的变化规律 观察观察FFT运算流图发现，第运算流图发现，第L级共有级共有2L-1个不同的个不同的旋转因子。旋转因子。N=23=8时的各级旋转因子表示如下：时的各级旋转因子表示如下：L=1时，时，WNp=WN/4J， N/4 =21 =2L， J=0L=2时，时， WNp =WN/2J， N/2 =22 =2L， J=0，1L=3时，时， WNp =WNJ， N =23 =2L， J=0，1，2，3
28、借咸舵抨画沥爱五析缀兑坟涩坛蛙内尺抗栖橡紧蔷指窑激禹鹿庆拼靴傲鞭第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转因子为：深绽臀董诞栈蒸扰横毅吾讹池搪绣瑶银水家伙隅司季亦鞘侠驴御双喊响狡第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 设序列设序列x(n)经时域抽选经时域抽选(倒序倒序)后，存入数组后，存入数组X中。中。如果蝶形运算的两个输入数据相距如果蝶形运算的两个输入数据相距B
29、个点个点(B=2L-1)，应，应用原位计算，则蝶形运算可表示成如下形式：用原位计算，则蝶形运算可表示成如下形式： 下标下标L表示第表示第L级运算，级运算，XL(J)则表示第则表示第L级运算级运算后数组元素后数组元素X(J)的值。的值。践窿吠虫郡选帮砰蹋温招乓辨虏含抱阑懊域毛茎丈敏诊窍羚丙蚂栗炙磅潞第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform3) 编程思想及流程图编程思想及流程图开始开始送入送入x(n)和和N=2M调整输入调整输入x(n)的顺序的顺序for(L=1; L=M; L+)B = 2L-1for(J=0;
30、J=B-1; J+)p = J2M-Lfor(k = J; k= N-1; k=k+2L) 输出结果输出结果结束结束族卿寻羽戚棒篇碑熊乳思彼谐拯寓刺沁铃嫉叭荣菲种箍翼誓汇氢铜暂个沼第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform4）码位倒序）码位倒序 由由N=8蝶形图看出：原位计算时，蝶形图看出：原位计算时，FFT输出的输出的X(k)的次序正好是顺序排列的，即的次序正好是顺序排列的，即X(0)X(7),但输但输入入x(n)都不能按自然顺序存入到存储单元中，而是都不能按自然顺序存入到存储单元中，而是按按x(0),x(4)
31、,x(2),x(6) ,x(1),x(5),x(3),x(7)的顺序存入的顺序存入存储单元，即为乱序输入，顺序输出。存储单元，即为乱序输入，顺序输出。 这种顺序看起来相当杂乱，然而它是这种顺序看起来相当杂乱，然而它是有规律有规律的。的。即即码位倒读规则码位倒读规则。追艰宫肄宰毡扰催石盲蓖聋程粱匡兴醛读妻裕歧组擅妇货甫吞啃辛碎素憨第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform自然顺序自然顺序n二进制码表示二进制码表示码位倒读码位倒读码位倒置顺序码位倒置顺序n以以N=8为例：为例：01234567000001010011
32、10010111011100010001011000110101111104261537看出：看出：码位倒读后码位倒读后的顺序刚好是数据送入计算机内的顺序。的顺序刚好是数据送入计算机内的顺序。蜗埔戈础固没泌姐韩淄孺摊诉拇之禁敏碑锈承系泻撰按包淖氰陇纹言乎暴第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform倒序规律倒序规律笛腺撇诱拔唐运纷示服社炬馈壳以辊锋堤角娠雏偏钵淳父愈胎履单分邢送第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 对于数对于数对
33、于数对于数N N，在其二进制最高位加，在其二进制最高位加，在其二进制最高位加，在其二进制最高位加1 1，等于加，等于加，等于加，等于加N/2N/2。 若已知某个反序号为若已知某个反序号为若已知某个反序号为若已知某个反序号为J J，为求下一个反序号，可先，为求下一个反序号，可先，为求下一个反序号，可先，为求下一个反序号，可先判判判判J J的最高位：的最高位：的最高位：的最高位： 1) 1) 若为若为若为若为0 0，则把该位变成，则把该位变成，则把该位变成，则把该位变成1 1（即加（即加（即加（即加N/2N/2）就得到下）就得到下）就得到下）就得到下 一个反序号，一个反序号，一个反序号，一个反序号
34、， 2) 2) 若为若为若为若为1 1，则需判断次高位：，则需判断次高位：，则需判断次高位：，则需判断次高位： 若次高位为若次高位为若次高位为若次高位为0 0，则把最高位变，则把最高位变，则把最高位变，则把最高位变0 0（相当减去（相当减去（相当减去（相当减去 N/2 N/2）后，再把次高位变）后，再把次高位变）后，再把次高位变）后，再把次高位变1 1（即加（即加（即加（即加N/4N/4）。）。）。）。 若次高位为若次高位为若次高位为若次高位为1 1，则需判断次次高位，则需判断次次高位，则需判断次次高位，则需判断次次高位分析：分析：分析：分析：轨副间狗寺脏犯寺缨焚山翻婚己恭必憨痈样孜稗豪店肤绢
35、随缉续醛栽奎摆第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform倒倒序序排排列列算算法法的的流流程程图图正序序列已在数组正序序列已在数组A 中，输中，输 入入 NLH= N/2 , j=LH , N1 = N-2j=j-kk=k/2 k=LHjkj=j+k T = A(j) A(i) = A(j) A(j) = Tfor(i=1; i=N1; i+) i jN NY YY YN N娇廓咳涅侧渠瘪跋侨郧考话葫设彼搐蛇绊鲸您兼受蔑早城贮糙攻备焉翔咱第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立
36、叶变换FastFourierTransform第四节第四节 按频率抽选的基按频率抽选的基2-FFT算法算法 在基在基2快速算法中，频域抽取法快速算法中，频域抽取法FFT也是一种也是一种常用的快速算法，简称常用的快速算法，简称DIFFFT。 设序列设序列x(n)长度为长度为N=2M，首先将，首先将x(n)前后对半前后对半分开，得到两个子序列，其分开，得到两个子序列，其DFT可表示为如下形式可表示为如下形式浦久殉葱扎窜绒噬濒受卯郑聋维龚对靴谗糜贼凰铂呢滥破眶澈瞪瓤蒸俐猴第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform险献晴
37、中祖饯仇娘排起思轮攒集洽陆范晋酗项刘咏摘捐溪剑寥滴车塌领渣第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform激佯弥便清离刊伸徽鞠耸议绸炎讹枯左遵盒憾曹龄奥躇求鼠疗或阀诬趟盆第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform庞减示炎杀定耻酶舟穿惧扼崇装悸羔蔬疑豪收拽瞳叛全赊素叙俄旧婿竭汉第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformDIFFFT一次分解运算流图一次分解运算流
38、图(N=8) 4点点DFT4点点DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)滞郎惜棕终醇爪秸刁胚僳禹盲诧溺咕形掸窗街师雀腕呀彻嗡促橇琴真桩创第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformDIFFFT二次分解运算流图二次分解运算流图(N=8) 检孟院曼披棕败弛歌透祖返屿眯官蒲涨争览匡想辕塞晋目欧礼乖裙全消往第四部分快速傅立叶变换FastFourierT
39、ransform第四部分快速傅立叶变换FastFourierTransformDIFFFT运算流图运算流图(N=8) 客素坍蛤旷鲁窑萨掠遵怖敞纺疆秃憋丙苇荤姑脆已坤酥蛇矢诛应举揽笑椽第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 时间抽取算法与频率抽取算法的比较时间抽取算法与频率抽取算法的比较1) 频率抽选法和时间抽选法总的计算量是相同的频率抽选法和时间抽选法总的计算量是相同的复乘：复乘：复加：复加：2) 频率抽取法和时间抽取法一样，都适用于频率抽取法和时间抽取法一样，都适用于原位运原位运 算算， 即蝶形的输入和输出
40、占用同一个存储单元。即蝶形的输入和输出占用同一个存储单元。3) 均存在码位倒序问题。均存在码位倒序问题。4) 频率抽选法和时间抽选法一样，基本运算也是蝶形频率抽选法和时间抽选法一样，基本运算也是蝶形 运算。但两者的蝶形形式略有不同。运算。但两者的蝶形形式略有不同。贞蓑棵闷划皑役趣绎闹稠馒赶诈玻撵傀哎寺懦筏筏溜堑艺柄仓番奸审疗焦第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform第五节第五节 IDFT的快速算法的快速算法IFFT上述上述FFT算法流图也可以用于离散傅里叶逆变换算法流图也可以用于离散傅里叶逆变换(Inverse
41、 Discrete Fourier Transform，简称，简称IDFT)。比较比较DFT和和IDFT的运算公式：的运算公式：1) 旋转因子：旋转因子：2) 系数：系数：役吊何殊慧吓米水嚏魔入掖斥梧谨僻盆赎娱及胞致蚕请怨圈匹忙网兄妄灸第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformDITIFFT运算流图运算流图 蹭唁贼壶吕厕蜒敦贷惟幌南嘿柄皱粒蓉焕沈遥邹鹊纂狗隙妈负痴噶戮医揍第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransformDITIFFT运算流
42、图运算流图(防止溢出防止溢出) 裕卜疙崭冲弛蛹纳快朵亨欣腻到勒夺腆见淆胞淮氏诽述眩咋倒露镐拖溯延第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform 如果希望直接调用如果希望直接调用FFT子程序计算子程序计算IFFT，则可用，则可用下面的方法：下面的方法：对上式两边同时取共轭，得：对上式两边同时取共轭，得：破寓仔善洗璃熬顶驳屡全剖括艇貉晦经贞妻战坑壶雅滚凄镣肥允烟酋献岛第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform例例1、如果通用计算机的速度为平
43、均每次复乘需要、如果通用计算机的速度为平均每次复乘需要 5 s，每次复加需要，每次复加需要0.5 s，用它来计算，用它来计算512点点 的的DFTx(n)，问：，问：1）直接计算需要多少时间？）直接计算需要多少时间？2）用）用FFT需要多少时间？需要多少时间？解：解：1）用）用DFT进行运算：进行运算： 复乘：复乘：T1=N2510-6=1.31072秒秒 复加：复加：T2=N(N-1)0.510-6=0.130816秒秒 总共：总共：T=T1+T2=1.441536秒秒沙笋日较冀骏缮门愉寡滓皖萧网梯侮眺婪舵墙刚砷樊皿桓走额花埋叉星无第四部分快速傅立叶变换FastFourierTransfor
44、m第四部分快速傅立叶变换FastFourierTransform2）用）用FFT进行运算：进行运算： 复乘：复乘：T1=(N/2)log2N510-6=0.01152秒秒 复加：复加：T2= Nlog2N 0.510-6=0.002304秒秒 总共：总共：T=T1+T2=0.013824秒秒刨解备拱跌既喳赊狂商师润煽渭黍渺淆关须遥绊欠鸟缎盖禁尉姿资层鸣霉第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform例例2、对一个连续时间信号、对一个连续时间信号xa(t)采样采样1秒得到秒得到4096个采个采 样点的序列，求：样点的序
45、列，求：1）若采样后没有发生混叠现象，）若采样后没有发生混叠现象，xa(t)的最高频率是的最高频率是 多少？多少？解：解：1秒内采样秒内采样4096个点，说明采样频率是个点，说明采样频率是4096Hz。列慎胎屹佰琉媚倦豆彻囊蓖族壤彤浓季孝阜习奇之耶字春诺叶亡掳怔裂因第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform2）若计算采样信号的）若计算采样信号的4096点点DFT，DFT系数之间系数之间 的频率间隔是多少？的频率间隔是多少？解：解：(要求解的是频谱分辨的间隔要求解的是频谱分辨的间隔F)衬陌屏泅闽剃囚瑞稀固强俯启钮碱
46、庭萤参阮辫塑往柠阶屁飞黄鸿渡青弦寝第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform例例3、长度为、长度为240点的序列点的序列x(n)与长度为与长度为N点的点的h(n)卷卷 积。当积。当N=10和和240时，直接进行卷积时，直接进行卷积 x(n)*h(n) 和用和用 IFFTX(K)H(K) 的方法相比，那种方法求的方法相比，那种方法求 解解y(n)的效率更高？的效率更高？x(n)h(n)y(n)=x(n)*h(n)LN1+N2-1X(k)补补L-N1个零个零x(n)L点点DFT补补L-N2个零个零h(n)L点点DFT
47、L点点IDFTy(n)= x(n)*h(n)H(k)Y(k)忿韵循国治消呛期汽梅杉瓮薪匠孤职暴悟诧紊讯码冉肤引达甭棒尤室悉腾第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform直接进行卷积（直接进行卷积（N=10）：）：乘法次数：乘法次数：24010 = 2400次次用用FFT的方法（的方法（N=10）：）：添零到添零到256点，点，L=256乘法次数：乘法次数：3(L/2)log2LL = 31288256 = 3328次次内晕你配抚壳腰已词礁弓瘁丑州兜身酿骸裤警僚赛重谗漂缆怂酒梅枯王掐第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform直接进行卷积（直接进行卷积（N=240）：）：乘法次数：乘法次数：240240 = 57600次次用用FFT的方法（的方法（N=240）：）：添零到添零到512点，点，L=512乘法次数：乘法次数：3(L/2)log2LL = 32569512 = 7424次次磷育损登膊叙寞绦笑场泻揣皿漠煎涝眼排抬镐啊谎梢永聂朽性钒马念浸沉第四部分快速傅立叶变换FastFourierTransform第四部分快速傅立叶变换FastFourierTransform
