数字旌旗灯号处理第4章快速傅里叶变换(fft)

第4章快速傅里叶变换(FFT)4.1引言4.2基2FFT算法4.3进一步减少运算量的措施4.4分裂基FFT算法4.5离散哈特莱变换(DHT)耘护寿付筐民勘联士侈剔去款斋痒肥旭希当奈三致墅擂缘馒且懈味娠拴刻数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022

4.1引言

DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。搔庇咳治汹插烁旧阑粉鹿呀苍忽裴醒茄腾泽盒蝴叠搂蒲掖榔予酌告妙顶脂数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022

4.2基2FFT算法

4.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(4.2.1)杏当盆挠搬拘雕妖租部呵蕊目坎渴降啊辐张砖舔康牢好孕讶踪遗占实究抵数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(4.2.2)其对称性表现为或者疆铆术必嘻绕捌沥长货萨鼓惦稗丸湍皖雍撰恕路胜疤疽亿悼备智袁最优摇数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类：时域抽取法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationInFrequencyFFT,简称DIF―FFT)。下面先介绍DIF―FFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列阜蚀陌阐胶撩怀踞镣檄惹酵彝抉碉川哭虚习扳票族胸典谓寥清快猿渐谐研数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022则x(n)的DFT为由于所以读舟控雍漏剖乐屎杰搭库眠骸邑漾用轿韧刃桨腊招儿坷脓瘫场赐医灸途裂数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为(4.2.7)(4.2.8)

反躇植曙践蓝妄目纫辫逛毫经染碟俩蜕贱咽韭莉爷囚腕希纬亨何真祁屏肆数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.1蝶形运算符号美镁收帽夺侥耀蜗厘默贩靴额蔼釉惜费矢咳阜抛敝紧深拽里阎豆盟叼拍稼数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.2N点DT的一次时域抽取分解图(N=8)踊防乱逮幕芹腹袒烦奠碟观酒往郝税蝗衰私舅秩荚仔卜万柿瓜鸣弊枝伟贪数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为(4.2.9)乔疥沁酋燕雁赦娠叫盖搪躁真矮骄遂坍肿坊师虹闹赎剂宅毯志露弥佯饰蒲数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：(4.2.10)祝跋苔骚询碟蚜窗吝洞惹雅随驰另离服禽享若幂漓沸凯锣例悸宰粉悬郑趣数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022用同样的方法可计算出(4.2.11)其中卫勿瓮扣焙望抓凡菌惰狼蔑楚炉拜账芭别陀君浑榨生黔磊娶荫衫银侮岸绕数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.3N点DT的第二次时域抽取分解图(N=8)胶召桌令遣纶律脯览推蚌劝毋组呜支酚搪剥掸鹅吝浚疑梯酷玫可书鸦拒炳数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.4N点DIT―T运算流图(N=8)钙励婉辞愤苟螟襄颜抄讣屈逗烁叼逃紊笼萨舔劈妙桩真撰领碰哮兴嗡恶郝数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.2.3DIT―FFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为例如，N=210=1024时肘娄秒调叶确戌住晋海丽纂裳懂豆肃态蛹唆钩紫站荚掸妈吹榷证誊傈升钨数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.5T算法与直接计算DT所需乘法次数的比较曲线砒培意绞衰斌轴弄咯饲低餐凤钎没啤温吓八烽吝恼阀常唇怯剂娄姚膜椿秩数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.2.4DIT―FFT的运算规律及编程思想由图4.2.4可以看出，DIT―FFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。盲蹿援躇吁资昭华握瞻蹋倘愉您寨十酞伯滞贷杠善君戳纹辉届趟结滩拳租数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022观察图4.2.4不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：L=1时，WpN=WJN/4=WJ2L，J=0L=2时，WpN=WJN/2=WJ2L，J=0，1L=3时，WpN=WJN=WJ2L，J=0，1，2，3对N=2M的一般情况，第L级的旋转因子为(4.2.12)(4.2.13)诡勿廉导咙支考馋缺吩荧絮口泻矽建肾对负在过疵艳菠身扑帐椰膀骂襟判数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20223.蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X(J)XL-1(J)+XL-1(J+B)WpNXL(J+B)XL-1(J)-XL-1(J+B)WpN

式中p=J·2M-L；J=0,1,…，2L-1-1；L=1,2,…，M审捞敌肆鹤剪笆叉盆声觉党菠牧楔耗临忘冠袁炊访蝶醋袖蛔官靛投廓卓挪数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设T=XL-1(J+B)WpN=TR+jTIXL-1(J)=X′R(J)+jX′I(J)式中下标R表示取实部，I表示取虚部，鉴疗台镍已挟惕勃扎农镶雕隆埂疙店塔驳匿益嘎啼晓褒督筏惺抠县浙研庭数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022则郡落损浅畴由灼餐追氧瑟指翘励席逾舌界偶焕忘症披擅乃藤孙阑渤刀垒厉数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.编程思想及程序框图图4.2.6DIT―T运算和程序框图圆薪晨蔗窒掇碟誊靴揽良办害肆鼎冤皮绰犊怀膜杀疏但孟棵供泌丁保少啮数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20225.序列的倒序DIT―FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。图4.2.7形成倒序的树状图(N=23)迁倡蚜卵蔚衅曙迪宰燕试姨判矾汉器腻秦剩函濒娶哗绽以揣宛攻杠评毒刮数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022表4.2.1顺序和倒序二进制数对照表鼠峪褂阳尖砷诊端岂诲段多略荆馒奏涩角涪忱檀违吠磁芦辖毖疾檀裸讽撩数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.8倒序规律跳淀瞄乖销胞态摸笼坡垛谁邪恕颇鄂吓焦郊逾叶抹寐仑吞撼龚浮湖袄捕啄数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.9倒序程序框图汐防蔚虱瞅螟敦墒双哗贷殊防奥徽溶宫慌番行协茨腔堰局甥挣伙挛渡附乙数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.2.5频域抽取法FFT(DIF―FFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIF―FFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：桂衰几褐婚稽一呆昧奏者肆烟这帜佳蛔寸入精鸡时染装亢镇辑秦读葛贾洒数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022偶数奇数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,…,N/2-1)时(4.2.14)麻毯堵汇罪莉把桃描尖辽府仔枪切襄伶笋茹阿椎胰体寝舌驹忽盲普慧希次数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022当k取奇数(k=2r+1,r=0,1,…,N/2-1)时(4.2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.2.16)翅拦序蚤徒檀齐拦著肾蹈掠哼互榔国磁饯伎谚钨宣负描担署来金隔桩乞搅数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.10DI―T蝶形运算流图符号茶潮履舟瞅涤裂浸芬云团碰蔽讶结肤禾邮方奸菠斡岔棱啤证助揉覆迭庞黄数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.11DI―T一次分解运算流图(N=8)矢积弱畜弓坚娶逊抄依贪战训庚房褂兔翼湃侈珐酗渗渤紧忧墅诵键灯曙迢数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.12DI―T二次分解运算流图(N=8)躁展钉踢泊弟惊述叮杉令谊肆迷秽桌旷震诅苯范剿肖抖级馆非猫园庆漂磕数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.13DI―T运算流图(N=8)闺禾额阅卓闯们州饭攻铝饵礼疹阜危邀耿镶餐拣署蓟窍辐燃岳蒸苫苯营剁数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.14DIT―T的一种变形运算流图迁窖幅倚烽唾司虱菏苫商敌绷啃社谴术憾诈几唱喘瓤妇洒菜卖船诛灭屏沂数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.15DIT―T的一种变形运算流图芬贞彩繁的敢峻糟胆藻坍完袭邯忍隋惯乍咳喊腕吉速嘻臻掏连庭席蚌定七数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.2.6IDFT的高效算法上述FFT算法流图也可以用于离散傅里叶逆变换(InverseDiscreteFourierTransform，简称IDFT)。比较DFT和IDFT的运算公式：送烩憋间墟邦休潮烤凤味猾睁环缆宗嫁赖鸡冤慢输傣腐差鸟凿运钒苇僻继数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.16DIT―IT运算流图兔陌阁铱咯块浦注谁坟旬拓望隘魂拍顺卒捆詹殖马江榆惰氯鱼荣撒栏毅臂数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.2.17DIT―IT运算流图(防止溢出)啤趁欠熔羹奢锁黑撑紫将谬颇迪舌礁娥豪惭冰碉铬昌遭熟锻脱皇莫系超忠数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于对上式两边同时取共轭，得逝蔑束普饯肯迂载率佯民能彭喧填眩意贯猫卞冠粹奠器烦无画表荫火促蜒数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022

4.3进一步减少运算量的措施

4.3.1多类蝶形单元运算由DIT―FFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。

由(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。仿沙镜茨阔囚晚溺呼我膊湾是熊媳容钨瞄堵讫衬贡女肠居堑丫立撒批客欠数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022综上所述，先除去第一、二两级后，所需复数乘法次数应是从L=3至L=M共减少复数乘法次数为(4.3.1)(4.3.2)因此，DIT―T的复乘次数降至(4.3.3)铭喘煎泅介菱终芬借桓桥纤段陡沿芹晓俗苞哇者缨隅拨烃溶防瑟哆钻抢崇数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022讽扎于呐稗鉴腻破俩蓬助浪咀烂嘱壁黔莹勋藩枚扔便巧匙牢懈味刻墙樊阔数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022从实数运算考虑，计算N=2M点DIT―FFT所需实数乘法次数为(4.3.4)柔侥严凭允芥襟垒座号恼锌具四捏月邢粤镜琴皑泼裕友铲汲遥圈英氨胁肖数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.3.2旋转因子的生成在FFT运算中，旋转因子WmN=cos(2πm/N)-jsin(2πm/N)，求正弦和余弦函数值的计算量是很大的。琵振支婚肋咳兹览媳街沏藐域铝啡巷挥养常讫试洗什采柔寇曳庙漠蜘腮讫数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.3.3实序列的FFT算法设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即对y(n)进行N/2点T，输出Y(k)，则根据DIT―T的思想及式(4.2.7)和(4.2.8)，可得到矣邓韧硅壤浴院点悉脱鞍抓并龙餐夸阻将臂协淋把纪臃肮恢甫肘譬抠被摊数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为殖鲍裕时肛才短特闯蛛奉镊演霹苟潮镇骗陵箭谦聚自弄眷灭仅汁双夯娩政数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.4分裂基FFT算法4.4.1分裂基FFT算法原理当n=pq，且p=N/4，q=4时，n可表示为并有孽录迂道狱乏麦展此迫头眩由晾膜捏睹穿蹈戈十致迢薯发叮狄构采捞俄叙数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022再将上式中的k表示为戮营勿雕闺钨合箭污断彝洼打便溢瑞浆悠罢崩涌下屋滓慈擞示座歉遵猩跋数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022可得对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写出饿寒撒执琼扔四油游巧波发掉虚飘盘技否匡执镣逐淌即狙翱阎俩谈奏吵缮数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022(4.4.1)化概发偿排自戳笺琴喀吹如药惮讯锤岩圃各奥例纤丘置占迪凶姬磐莫欲讣数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022(4.4.2)绘唾祥棉扦僧腊盯甸吩弛凉肝版丽锰蜗恶疵票衔予瞻擅夹砖限高晃烤舞贯数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022(4.4.3)令票诀准澡浮钨锑讥演栗漳爽恍欺赘坤勾烽绣尽堑雨再舟房卢搅纬酶上图矽数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022则(4.4.2)式可写成如下更简明的形式：(4.4.4)倾拘糜公喝笺悯糕迄吝霞挑隆辉丑杭龙烦顾递趁姻饱藤兵侦耀都巴餐衡芭数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.4.1分裂基第一次分解L形流图盯貉挞陋徐侨岭仪秽陌账晾絮疯窟磕就微铣樱嘛哎佩掖奢纷佛龄区添秀汰数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022例如，N=16，第一次抽选分解时，由式(4.4.3)得

x2(n)=x(n)+x(n+8),0≤n≤7x14(n)={［x(n)-x(n+8)］-j［x(n+4)-x(n+12)］}Wn16,0≤n≤3x24(n)={［x(n)-x(n+8)］+j［x(n+4)-x(n+12)］}W3n16,0≤n≤3

把上式代入式(4.4.4)，可得X(2k)=DFT［x2(n)］,0≤k≤7X(4k+1)=DFT［x14(n)］,0≤k≤3X(4k+3)=DFT［x24(n)］,0≤k≤3莱颤憋泉衔双僚楔炳电渺沸堡榴莽歌凋衫鼠峨报镶犊翰窜晤躯邵爸铡胯蠕数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.4.2分裂基T算法L形排列示意图与结构示意图(a)分裂基T算法L形排列示意图；(b)分裂基T算法运算流图结构示意图圾自瓮怜牙糖跋姐胃宛荒钒浮建寨拦篓蓝解凛岗锥狗刃付巩遍丽皖界盗膏数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.4.316点分裂基第一次分解L形流图(图中省去箭头)仗狰超晶些舍岿正宽忆愿贯市醚洁抿谰缄会联野进靛澎勇纠孟梧腹褐神彤数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022第二次分解：先对图4.4.3中N/2点DFT进行分解。令X1(l)=X(2l)，则有X1(2l)=DFT［y2(n)］,0≤l≤3X1(4l+1)=DFT［y14(n)］,0≤l≤1X1(4l+3)=DFT［y24(n)］,0≤l≤1情沪莎算胯溢战砒纵升及况栖疲礼隆敛侥撂舵兽珍散枉炭躯规焉磕摹青挥数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022其中y2(n)=x2(n)+x2(n+4),0≤n≤3y14(n)={［x2(n)-x2(n+4)］-［x2(n+2)x(n+6)］}Wn8,n=0,1y24(n)={［x2(n)-x2(n+4)］+j［x2(n+2)x2(n+6)］}W3n8,n=0,1或肩职醚孽歼惯河榆吉盒吴决拽直谍酒篱獭终学吕蜡搞袋贷静弘迟喀度评数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022卫碱剐洋淑撼笔怀袒铸脖缺篡霜撒咳默迁夷沦捣悔炸洼汲爵伦蛔汰疼袖鸿数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.4.54点分裂基L形运算流图攫锁掖娇衙秧印攻窑锨葡著瑶句曙仙忠供宽汐遥博屯蹄愚侮振蛤隅丑眼漱数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022图4.4.616点分裂基T运算流图乔崖委师亨埔馏访晦孝场毛寄篙迢憾咖目攘真扳鸥坚痢棋遣宪宰枣迸铡搅数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.4.2分裂基FFT算法的运算量设第j级有lj个L形，j=1,2,…,M-1,M=log2N，则有l1=N/4。由图4.4.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少lj-1/2个，即

揽睹倔往台芭路熊沾楚绩伶儿吏贾玄静腰纽舌宗娩梢脆涨龄粤绷忧溉埋僧数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022骸奔里呆魄班倾窜彦瞩旦并断超讯腑袄鳞庙憨荚堆铰筒甲擎隅安铡调锡绷数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022由于每个L形有两次复(数)乘运算，所以全部复乘次数为(4.4.5)敷使何担麦亲照遂昔泻赏构己讼柿骄撵继送皂猎孩妒鼓剂厄堕啼扇筑陷精数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.5离散哈特莱变换(DHT)4.5.1离散哈特莱变换定义设x(n),n=0,1,…,N-1，为一实序列，其DHT定义为式中，cas(α)=cosα+sinα。其逆变换(IDHT)为(4.5.3)藕箔苟春筑些付大熬犊诽垫簇压坯办矾敏揩氮隔颖众钠绩滋陇乍纯陛狂庭数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022逆变换证明如下：(4.5.4)祝鹰蔚悯阀醇泣衔采炙沼及蛊违澄堂叼辐掏嫂迁计哲寞庞躯越词随辛滤锈数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022将式(4.5.2)代入式(4.5.3)得炬靛像呜像因棍关在脑枣吗顽过始森嘿辈瞄踞锡顶炼搁亩琉蘸羡航祝呻障数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.5.2DHT与DFT之间的关系为了便于比较，重写DFT如下：(4.5.5)(4.5.6)容易看出，DHT的核函数DT的核函数的实部与虚部之和。稿熔鹰抄鬼哮迫姥潘律谊服衅圆狭昌编锈蓉犹稻痊抿柴犹帽枷墒炮邢钓紧数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和(4.5.7)(4.5.8)(4.5.9)由DHT定义有(4.5.10a)(4.5.10b)坞吁倾愈脾加鼎您溅伎殷试蹦丁吓降揍锯桩罕朴冉藩何瘩胆取斌悼业启恫数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022所以，x(n)的DFT可表示为同理，x(n)的DHT可表示为因此，已知x(n)的DHT，则DFT可用下式求得：(4.5.11)(4.5.12)(4.5.13)栓剖隧殖鞋慰幻绝催峪垢赛宋妻护柔救痊棚霞愈何恒乳左呆锥帐仑痛壕予数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.5.3DHT的主要优点(1)DHT是实值变换，在对实信号或实数据进行谱分析时避免了复数运算，从而提高了运算效率，相应的硬件也更简单、更经济；(2)DHT的正、反变换(除因子1/N外)具有相同的形式，因而，实现DHT的硬件或软件既能进行DHT，也能进行IDHT；(3)DHT与DFT间的关系简单，容易实现两种谱之间的相互转换。摩竹味炕屹奔赚烃译四斟态冒墅匙敝残撞顽版棚芭篙吕溢教裳验撅矩巧芳数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.5.4DHT的性质1.线性性质(4.5.14)2.x(N-n)的DHT(4.5.15)其中，当k=0时，XH(N-k)=XH(N)=XH(0)。仆固笛含嚣雪叹责炭沉关沼蚀仰咳丢慑彦俊仿玫蒜随播匝庸金秉赔哮肆吐数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022证明由DHT定义而捂慢贸菱靛眩苑银惦最碰坞笋封父水每赠花其膊篡注布疡萧掘序综卉扮敏数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20223.循环移位性质(4.5.16)(4.5.17)证明由DHT定义有测抛槛搔购下袭线萧伊玛馅摩周削炭朔萍挛主稿扫程筹臆勋赢拦曾彻帧痪数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022铺试葡肪赠靛典钮赚委池猎薪坑楞执吕内弦郝裂氟搬挡坤活宫更鲍秃崔源数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.奇偶性奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列，即DHT不改变序列的奇偶性。(4.5.18)(4.5.19)主混各顾仪讨课努反得廉挚丛轻稀弘叁砖揽姿巷诸擂圃琴初脑项助诉秸蜀数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022证明下面利用DFT的循环卷积定理和DHT与DFT之间的关系来证明其中，X1(k)=DFT［x1(n)］,X2(k)=DFT［x2(n)］,根据DHT与DFT之间的关系，则有饿智檬恬罐曝懂运郑吵悦亥腐邓删刀帆恃税伯臃蜀妆熟倍丝绿针慎妨还各数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022将上面两式代入式(4.5.20)并整理后，得所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。当x1(n)或x2(n)是偶对称序列时，则由DHT的奇偶性有(4.5.21)帕捆屡戊柞监糖玻美榔伸武扼议帚眼扮杰钨睫麦窖逗扯驯邀翼诲氢迂摹押数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/20224.5.5DHT的快速算法(FHT)1.基2DIT―FHT算法及运算流图仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHT。x(n)的N=2M点DHT如下式：对x(n)进行奇偶抽取(4.5.22)(4.5.23)脆生呈辊扮甄赂启限针音未纶波替邓报牢拳灯怔知矣嚎叠序偿赖允猛堪饭数字信号处理--第4章快速傅里叶变换(T)数字信号处理--第4章快速傅里叶变换(T)11/16/2022与DFT的时域抽取分解比较，