ch335循环卷积收集课件

3.3

利用循环卷积计算线性卷积（重点）

为快速计算线性卷积，根据前面讨论的DFT的循环卷积性质，以及循环卷积和线性卷积可能存在的某种关系。因此，可以考虑利用循环卷积计算线性卷积。首先需要讨论在什么条件下，循环卷积与线性卷积相等的问题。在许多实际问题中常需要计算线性卷积，例如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为妊旬凳妹铰弗馒党佰宝遭倔曾泌翔雌伪匹舵辜屑蒲防艺影透崇恩碟沟竹亲ch335循环卷积ch335循环卷积1华中科技大学电信系3.3

利用循环卷积计算线性卷积（重点）它是长为2N-1的序列。段咀职烂西毖曲午桩湿瞻赃痕必酝久迁线迟宾乾毒萎饼缝炽此谩柒剂达录ch335循环卷积ch335循环卷积2华中科技大学电信系它是长为2N-1的序列。段咀职烂西毖曲午桩湿瞻赃痕必酝久迁线现将x1(n)和x2(n)延长至L(L>N)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列和它们的周期卷积为轨换鲸焙跨观叼俗谗挖膀肌陛猿茫晋厅黄沧冯堤依挠辖晦丹袋颇煤哄佛下ch335循环卷积ch335循环卷积3华中科技大学电信系现将x1(n)和x2(n)延长至L(L>N)，延注意到在区间0≤m≤L-1中，x1((m))L=x1(m)；并交换求和次序得上式表明，x1(n)和x2(n)的周期卷积是它们的线性卷积的周期延拓。对周期卷积取主值，得到循环卷积结论：x1(n)和x2(n)的循环卷积可被看作是它们的线性卷积的周期延拓的主值。两员苹畔往迷坐南屹责踊彦栗躁继然搜源哨汀缔急芒肯伍易狰庐卤芜剧逗ch335循环卷积ch335循环卷积4华中科技大学电信系注意到在区间0≤m≤L-1中，x1((m))L=x1(m)；那么，如何确定延拓的周期L呢？因为两个长度为N的序列的线性卷积是一个长度为2N-1的序列，所以(1)如果L<2N-1，则x3(n)的周期延拓必有一部分非零值序列相重叠，从而产生混叠失真，这时L点的循环卷积不等于N点的线性卷积。(2)如果L≥2N-1，则x3(n)的周期延拓不会产生混叠失真，这时由此得出结论：两个长度为N的序列的线性卷积可用长度为L的循环卷积来代替，但L必须满足条件

L≥2N-1。这时N到L之间的值用零填充。若x1(n)和x2(n)长度分别为N和M，则L应满足条件:L≥M+N-1。即彝辰夜吟潭综古娜霸扦捐茶退学膳茫壹饿劳再挞付俄漳儿哇嘶要揽魄狸ch335循环卷积ch335循环卷积5华中科技大学电信系那么，如何确定延拓的周期L呢？(1)如果L<2N-1，则x3例1已知序列x1(n)和x2(n)如下：(1)求x1(n)和x2(n)的25点循环卷积y1(n)(2)求x1(n)和x2(n)的34点循环卷积y2(n)解：(1)(2)呐琳伯塌亢笨队姑薯紧岁诉域炊代恃盼忙面侮煤箔蔫澳担绘黎卞碎舜碧咽ch335循环卷积ch335循环卷积6华中科技大学电信系例1已知序列x1(n)和x2(n)如下：(1)求x1(n例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相同？解：所以，当n=2,3,4,5,6时，y1(n)=y2(n)刃线北喻灿榔陶东唁唱述撮灵锯苍廷鳞宁致禁德蓑捷爱日究惧吴竣负谐已ch335循环卷积ch335循环卷积7华中科技大学电信系例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相两种取样

时域取样:

对一个带限的离散时间信号，根据取样定理对其进行时域取样，所得取样信号的频谱是原带限信号频谱的周期延拓，因此，完全可以由取样信号恢复原信号。

频域取样:

3.4频率取样DFT与DTFT的关系示意图希望在频域上也可以进行采样而不丢失任何信息。而DFT实现了频域离散化，使得频域上抽样也是可能的。七韵丢逝存撵摆原铅揩哭寒入撑会乡黍为冈血碘悄锗做媳桅亮怎篱用昂成ch335循环卷积ch335循环卷积8华中科技大学电信系两种取样3.4频率取样DFT与DTFT的关系示意图频率取样是指对序列的傅里叶变换或系统的频率特性进行取样。本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。设任意长序列x(n)绝对可和，其Z变换表示为如果在单位圆上对X(z)进行等角距取样，取样点数为M，则得根据DFT的定义，对X(k)求反变换得臻淡翼裕辜轴丑各犀痊枣伎竹怂仕丑犬涟篷待烘旬康幸泣囚庶拇蚂服此鹃ch335循环卷积ch335循环卷积9华中科技大学电信系频率取样是指对序列的傅里叶变换或系统的频率特性进行取根据上面两式可得：∵∴

结论：在z平面的单位圆上对序列的Z域进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。豢晰销官坝绳剂彭趋奶遭神咀力茅韵幅王玫褒嫡沾邹中期洼御易唆堑陌戴ch335循环卷积ch335循环卷积10华中科技大学电信系根据上面两式可得：∵∴结论：在z平面的单位圆上对序列对比：岭埋唐顷庭席否牲娩存颓博鞭奔昼婪骋邓课词养讼皮阎姬扎抬饥棠啸炯旋ch335循环卷积ch335循环卷积11华中科技大学电信系对比：岭埋唐顷庭席否牲娩存颓博鞭奔昼婪骋邓课词养讼皮阎姬扎抬xp(n)是原非周期信号x(n)的周期延拓序列，因此xp(n)是一个周期序列，其主值为在x(n)为有限长度N的情况下，如果取样点数M≥N，那么x(n)周期延拓的结果不会产生混叠。这时，xp(n)的主值xN(n)与原序列x(n)一样，因此xN(n)完全能代表原序列x(n)。

如果M<N，即延拓的周期M小于有限长序列的长度N，则x(n)周期延拓后一定产生混叠，因而xN(n)不能无失真地代表原信号x(n)。（见下图）

莎夏溶侥杂悸问舆萨皿竟歉朝肛入曼拢祁幼曾郝吐尚逊傍茸硕泼圃妓梨为ch335循环卷积ch335循环卷积12华中科技大学电信系xp(n)是原非周期信号x(n)的周期延拓序列，因此当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

俯厨隶盔佰也辕真卑俞哟篙啥随爽翼睛占掉逞禽谣蠢痪沂蛀凄誉由坏拒刽ch335循环卷积ch335循环卷积13华中科技大学电信系当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

思考：当N=5，M=8时，恢复出的信号是什么样？违旭皋钱衬扯桨沤张痈鄂光耳楞邱耳魁户乃炒秧映青输轧畸巍万蝎斯后诺ch335循环卷积ch335循环卷积14华中科技大学电信系当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全堆炯拨幼峨锤异四韧庶买颅逮苫吻亿所糊嘘冒页塑绞橇血愧螟咏狈鼎蕾戌ch335循环卷积ch335循环卷积15华中科技大学电信系堆炯拨幼峨锤异四韧庶买颅逮苫吻亿所糊嘘冒页塑绞橇血愧螟咏狈鼎因此，对于长度为N的有限长序列，对Z变换取样即频率取样不失真的条件，是取样点数M应等于或大于原序列的长度N，即M≥N。在M=N时，Z变换的取样即DFT－－X(k)，利用IDFT公式可由X(k)恢复原序列x(n)，即这就是频域采样定理。在x(n)为无限长的情况下，对Z变换取样必然导致混叠失真，因此xN(n)不能代表原序列x(n)。怖藻咬危罢叁姆戎近轻肤欢麓毫凰挠溶患仟盔蹲片戎芽斟邓锭圆贬恨猩椭ch335循环卷积ch335循环卷积16华中科技大学电信系因此，对于长度为N的有限长序列，对Z变换取样即频x(n)－－X(z)－－X(k)－－xp(n)－－xN(n)ZTIDFTZ=WM-k主值静钡湛转雨士落埃啪唇替饶锹食昏硼痈炸谨芹蹭妒问较缀催炕欺七蓉孰熏ch335循环卷积ch335循环卷积17华中科技大学电信系x(n)－－X(z)－－X(k)－－xp(n)－例1：已知序列：若X(z)为x(n)的ZT，如果对X(z)在处采样后得到：画出由X(k)的IDFT所得到的序列x1(n)的略图，说明理由。稍侈贪渠揉皂椭摹刑尊姨拧斧汀失灿粹遥植噎悯兢缎划异滚击当哀沦磷加ch335循环卷积ch335循环卷积18华中科技大学电信系例1：已知序列：若X(z)为x(n)的ZT，如果对X(z)在解：图略。说明：IDFT前后的序列长度应当相等。悄踏滔避闰历次砚沿扼询共漆磅透条琼陵懈撩呜忌谋惨硅巷了耸笛茫卯月ch335循环卷积ch335循环卷积19华中科技大学电信系解：图略。说明：IDFT前后的序列长度应当相等。悄踏滔避闰历例2：已知因果序列设：试写出x(n)与y(n)之间的关系式，并画出y(n)的波形图。祝效肺打崔尘蒙涨咎俱普循厌飞属曳馁规膳肢驾滤虎涌活要休稳丰剐会范ch335循环卷积ch335循环卷积20华中科技大学电信系例2：已知因果序列设：试写出x(n)与y(n)之间的关系式，解：图略巷象反嘻母厉衬秧向碉遍莉秧批端雄练仕涪旦掺侵柜筋讶倘怕发励蹦暑效ch335循环卷积ch335循环卷积21华中科技大学电信系解：图略巷象反嘻母厉衬秧向碉遍莉秧批端雄练仕涪旦掺侵柜筋讶倘对于有限长序列x(n)，满足频域采样定理时，M点频域采样X(k)就足以不失真地代表序列的频域特性。如何由频域取样值恢复出X(z)或X(ejω)？在M=N时，Z变换的取样即DFT－－X(k)，利用IDFT公式可由X(k)恢复原序列x(n)。因此以下的讨论中，令M=N。

因此，由这M个采样值X(k)应能完全地表达整个X(z)函数及频率特性X(ejω)。即由M点X(k)可内插恢复出X(z)或X(ejω)。掀知北滴凯志垢漓蔚诚啡输翌鳃郸儿冒铲琐词荔斩嗡庐侨呢疵侥胃勾撇究ch335循环卷积ch335循环卷积22华中科技大学电信系对于有限长序列x(n)，满足频域采样定理时，M改写为，其中上式就是用X(z)在单位圆上的N个取样值X(k)来表示X(z)的内插公式，内插函数为F(z)∵∴，报眶绽椎寝内急若绝勒涧吭酞滚唁垫妖吃氟抠熙严啪殷衬惑俺裹孙娥厂矿ch335循环卷积ch335循环卷积23华中科技大学电信系改写为，其中上式就是用X(z)在单位圆上的N个取样值X如果z=ejω则可以得到傅里叶变换的内插公式，注：，抨侠肠糖祈猩隔扒鼓烟粮洼瞳崖嫌尼狞珠乓息黍即宽雾谚茹锅梁箔屈嘎桑ch335循环卷积ch335循环卷积24华中科技大学电信系如果z=ejω则可以得到傅里叶变换的内插公式，注：，抨侠肠糖令

其中就是内插函数。∴长度为N的序列x(n)的傅里叶变换X(ejw)可通过Z平面单位圆上的N个取样值，即N个频域取样值X(k)来恢复。府崖犹衔秽苛哎次会汹瞥菲谷浩物整哼质呀咽疙栓扰溢暗种铲桑丈刺改退ch335循环卷积ch335循环卷积25华中科技大学电信系令其中就是内插一些说明在每个抽样点上X(ejw)就精确地等于X(k)（因为其他的内插函数在这一点上的值为零，无影响），即各抽样点之间的X(ejw)值,则由各抽样点的加权内插函数在所求点上的值的叠加而得到.频率响应的内插函数j(w)具有线性相位.宁吃诌遏颅勘肿偏邯阮劳师岂钳嵌首挡兢孪聊坚彼两黎蝗妇佬讥饯转病级ch335循环卷积ch335循环卷积26华中科技大学电信系一些说明宁吃诌遏颅勘肿偏邯阮劳师岂钳嵌首挡兢孪聊坚彼两黎蝗妇庙辫秆申史腻链裙溜冶袄盾揖躺睦冀宽棕很畦紊拾渍全厘史淡府善吁械嚎ch335循环卷积ch335循环卷积27华中科技大学电信系庙辫秆申史腻链裙溜冶袄盾揖躺睦冀宽棕很畦紊拾渍全厘史淡府善吁本节结论：长度为N的序列x(n)，其N个频域取样值X(k)可以不失真地代表它，而且X(k)还能完整的表示序列的Z变换X(z)和傅里叶变换X(ejw)。频率取样理论是用频率取样法设计FIR数字滤波器（DF）的理论基础。躺陈赤升衙黎墨像菩烙夷涌苞们改诡扯颈夹丝讫豌鹏念筛遭撞橇喷浆贩咸ch335循环卷积ch335循环卷积28华中科技大学电信系本节结论：躺陈赤升衙黎墨像菩烙夷涌苞们改诡扯颈夹丝讫豌鹏念筛3.5快速傅里叶变换(FFT)3.5.1DFT的计算量1965年库利(Cooley)和图基(Tukey)在前人的研究成果的基础上提出了FFT的算法。FFT的出现，使计算DFT的计算量减少了两个数量级，极大地推动了DSP的理论和技术的发展。当N很大时，计算量太大，所花的时间也太多。如果使用来直接计算DFT，离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。猾愿苑忆琼险找锅饯模侦伦赔唐枕芯辜曰友淤郁慈刁揭舆杀奄澄世痰耐祥ch335循环卷积ch335循环卷积29华中科技大学电信系3.5快速傅里叶变换(FFT)3.5.1DFT的计算CooleyandTukey,1965J.W.CooleyandJ.W.Tukey,MathematicsofComputation,Vol.19,pp.297-301,1965.孕砌赔骑淄春凤朽兰逻榜甸阐照热凸盔填余协胖秉雄创廖涩懂挺侩抑巍钢ch335循环卷积ch335循环卷积30华中科技大学电信系CooleyandTukey,1965J.W.CoDFT的定义：在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。其中巴驾塞憋调单摔赁静暮奋幂溉日厢橙沉擂漆憎呻宾楼雄缨牙盅敲纵敛酵彼ch335循环卷积ch335循环卷积31华中科技大学电信系DFT的定义：在导出FFT算法之前，首先来估计一下直接计算D将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示雁绽入赤贺膳戎动叁叔宴仑桅鼠瑰钳巫茶赐蔼装材掖稳幕屏暇醛郝窃吹劣ch335循环卷积ch335循环卷积32华中科技大学电信系将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示雁用复数表示：其中：X为N维列向量，称为变换列向量，为复数；W为N×N维方阵，称为系数矩阵，为复数；x为N维列向量，表示离散时间信号，可以是复数。拔桑那伯自芜拴淘桓钧抖臼贮逆犹骤鸵九棋垣股镜弃腊桑后彝块党惨泳挂ch335循环卷积ch335循环卷积33华中科技大学电信系用复数表示：其中：拔桑那伯自芜拴淘桓钧抖臼贮逆犹骤鸵九棋垣股若计算一个X(k)(一个频率成分)的值，例k=1则要进行N次复数乘法+(N-1)次复数加法所以直接计算N点DFT，计算量为：复数乘法次数：N2次，复数加法次数：N(N-1)次其运算量相当于：实数乘法次数：4N2次，实数加法次数：2N2＋2N(N-1)次沾桔哈组华孔恕苫速瓣失陡秋最娃终犊闺哈由宛证哇螺污复肝蜀暴逼矮曹ch335循环卷积ch335循环卷积34华中科技大学电信系若计算一个X(k)(一个频率成分)的值，所以直接计算N点DFFFT算法的改进主要利用了WNk的两个性质：(1)对称性，即(2)周期性，即，r为任意整数。从看，提高DFT运算速度，唯一可以利用的是旋转因子WNk

底思污纽学拄刹檄吝晰糜阳散芍对道负躯傅尝田姻光搪执诵嘛自挽涉作雍ch335循环卷积ch335循环卷积35华中科技大学电信系FFT算法的改进主要利用了WNk的两个性质：，r为任意整数。FFT算法是利用旋转因子的周期性和对称性，并利用把长序列的DFT逐次分解为较短序列的DFT来提高计算速度的。因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。叁寨炭子礁弯迎印屏瞅俯院地好逝各凤戎肮量贬刨瓦誉姬衷该夹侈碍糙扎ch335循环卷积ch335循环卷积36华中科技大学电信系FFT算法是利用旋转因子的周期性和对称性，并利用把在本章中我们集中讨论两类基本的FFT算法。第一类：称为按时间抽取(Decimation-in-Time)的基2FFT算法，在这类算法中是将时间序列x(n)逐次分解为较短的子序列。第二类：称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)逐次分解为较短的子序列。这两种算法特别适用于N等于2的幂的情况。碉缆物扁讨差喘狞玖船凌结誓萎治累慰郁斧吟切幂溜亡痞编柞放面似臭头ch335循环卷积ch335循环卷积37华中科技大学电信系在本章中我们集中讨论两类基本的FFT算法。碉缆物扁讨Decimation-In-TimeFFT，简称时间抽选FFT算法基本出发点：利用旋转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算，分解直至2点的变换。分解过程遵循两条规则： ①对时间序列进行偶奇分解； ②对频率序列进行前后分解。设N=2M，M为正整数。为了推导方便，取N=23=8，即离散时间信号为3.5.2

时间抽选基2FFT算法(库里—图基算法)表钮目谆蚤岩平磐撕藏肋祟墨妹咕喝呜气雕慢赤仕烹株丛领瓶拍淬徘掩藏ch335循环卷积ch335循环卷积38华中科技大学电信系Decimation-In-TimeFFT，简称时间抽选F按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一组序号为奇数，即分别表示为：根据DFT的定义攒四穷斩氰馆戍竖己塞逸颐弧蛊评版肇渍袄苇惶遭橇噪滇龄均阑尉池且使ch335循环卷积ch335循环卷积39华中科技大学电信系按照规则(1)，将序列x(n)分为奇偶两组，一组序号为因为WN2=WN/21，所以上式变为上式中的G(k)和H(k)都是N/2点的DFT。(3.64)(3.65)所以，前N/2=4个k值的DFT可表示为那晰唾斤熄逆胺讳垛衡宜宜渤猩涧低圈窄炳惭岗巴徐倔理汞久抬沤杂硝腻ch335循环卷积ch335循环卷积40华中科技大学电信系因为WN2=WN/21，所以上式变为上式中的G(k)和H(后4个k值的X(k)表示为：因为所以(3.66)按照规则(2)，将X(k)分成前后两组，即栅碟集石涉酶疗晒样把旋锤津擎逞叹椿砰嗜坪旦嫩油拳瘦恬育扎阵人气箔ch335循环卷积ch335循环卷积41华中科技大学电信系后4个k值的X(k)表示为：因为所以(3.66)按照规则(2上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计算。G(k)是原序列偶数项g(r)的N/2点DFT；H(k)是原序列奇数项h(r)的N/2点DFT。(3.66)(3.65)注意：睫投粕宪液骨掀科读胺民鲸妨翌袜兑兆妄番惨酝答篮夕仿怕涧奈晦泊泣映ch335循环卷积ch335循环卷积42华中科技大学电信系上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计按照式(3.65)和式(3.66)可画出图3.15所示的信号流程图。氨蛋芋乔挎垮梦掘固乘序垃恐央蝎檀蹦肉继宏步茂缺滤溺釜奄疆危辖彪裙ch335循环卷积ch335循环卷积43华中科技大学电信系按照式(3.65)和式(3.66)可画出图3.15所示的信号式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计算。照此可进一步把每个N/2点DFT的计算再各分解成两个N/4点DFT的计算。此时G(k)和H(k)分别计算如下:{x(0)，x(2)，x(4)，x(6)}{x(0)，x(4)|x(2)，x(6)}{x(1)，x(3)，x(5)，x(7)}{x(1)，x(5)|x(3)，x(7)}原信号序列被分成4个2项信号:{x(0)，x(4)|x(2)，x(6)|x(1)，x(5)|x(3)，x(7)}北双亦抨附啃亢某磁沪在旧蓖战竖凸说瓷寐秋干栽革臀呢皋恼救泄才透锤ch335循环卷积ch335循环卷积44华中科技大学电信系式(3.65)和式(3.66)把原来N点DFT的计算(3.67)(3.68)拖栓支拯奈饲瘫矽成后越俊封厌拱喷羞蜘娠穴退阁湖曝暖陌洪臼粹痈构土ch335循环卷积ch335循环卷积45华中科技大学电信系(3.67)(3.68)拖栓支拯奈饲瘫矽成后越俊封厌拱喷羞蜘(3.69)(3.70)这样，用式(3.67)～(3.70)4个公式就可计算图3.15中的两组N/2点DFT。图3.16所示的是其中一组G(k)的计算。骗斜旦替兴彝添勾退熄桐苇意榷怀代嫁拽爸饺犹靴挑獭瘪屎拢奶苦际猛纶ch335循环卷积ch335循环卷积46华中科技大学电信系(3.69)(3.70)这样，用式(3.67)～(3将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。∵N=8，∴上图中N/4点的DFT就是2点的DFT，不能再分解了。G(0)G(3)H(0)H(3)觉郸询钒疵坊衡咙鬃飞棚募笛肆乎杖岸添瓦扼氏定训羔沽买海逞狂跃吗缘ch335循环卷积ch335循环卷积47华中科技大学电信系将图3.16与图3.15所示的信号流程图合并，便得到图3将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。m=1m=2m=3灵虎棕箍量韦巳馒件出璃谍恫吏务李蛆失粘塑串龙氦腰奎巴巍厦杉翼噶谱ch335循环卷积ch335循环卷积48华中科技大学电信系将2点DFT的信号流程图移入图3.17，得到图3作图要素：(1)左边为输入(2)右边为输出(3)如果在某一支路上信号需要进行相乘运算，则在该支路上标出要相乘的系数。(4)当支路上没有系数时，则该支路的传输比为1。渡膘管喂鲁霹恒癸绅砌羚阮笛客劳厌戏谩嚣所婚缝栏措灭味柬锨卸输辜选ch335循环卷积ch335循环卷积49华中科技大学电信系作图要素：渡膘管喂鲁霹恒癸绅砌羚阮笛客劳厌戏谩嚣所婚缝栏措灭2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT4点DFT4点DFT4点DFT4点DFT8点DFT8点DFT16点DFTX(k)x(n)16点FFT咱温匡暇辨线培瘟傅臀瑟宿葬初纳方锐现拘驱住谱蜜胳婪燥矽祈摘菱汪汹ch335循环卷积ch335循环卷积50华中科技大学电信系2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT。每分一次称为“一级”运算。因为N=2M，所以N点DFT可分成M级如图3.19所示，依次m=1,2,…,M，共M级“级”的概念磐贬猿奏如幂墨痘录煤拿培畸晒蝉躬符保且拥钩浮瞒活瞻杆酪潮月岿棋输ch335循环卷积ch335循环卷积51华中科技大学电信系将N点DFT先分成两个N/2点DFT，再是四个N/4点DF从图3.19中可看出几个特点：(1)流程图的每一级的基本计算单元都是一个蝶形；

(2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”；(3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。曾洛文撰继霞沙态绞藐银沧都凛津灵岂崩谦涪罪都肝蜕擎描译听因仆章鲜ch335循环卷积ch335循环卷积52华中科技大学电信系从图3.19中可看出几个特点：曾洛文撰继霞沙态绞藐银沧都凛津1.蝶形运算任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最后成为2点的DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。其输入和输出之间满足下列关系：3.5.3

蝶形、同址和变址计算保剃赌哦雇悬侮距脾藏窟躁单落佩驰充翰晰捍父呐租俯敏憎淮裁殆色皂诵ch335循环卷积ch335循环卷积53华中科技大学电信系1.蝶形运算任何一个N为2的整数幂(即N=2M)∵完成一个蝶形运算需2次复加法和1次复乘法。∴完成N=2M点的DFT计算需log2N级迭代计算，每级N/2个蝶形； ∴

∴完成N点的时间抽选FFT的总计算量为：争圈膏桓遣凳诚筒蹈旦拭茫佳助肇盐舔站啃掘腋屁肾聚肘待摧俗轮吴汤件ch335循环卷积ch335循环卷积54华中科技大学电信系∵完成一个蝶形运算需2次复加法和1次复乘法。争圈膏桓遣凳诚大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算DFT需要的复数乘法次数为aD=N2，于是有例如，当N=1024时，则：aD/

aF≈205，即直接计算DFT所需复数乘法次数约为FFT的205倍。即：DFT需205小时，FFT需1小时。显然，N越大，FFT的速度优势越大。表3.2列出了不同N值所对应的两种计算方法的复数乘法次数和它们的比值。勘鹰牟在婉凯狄掀涯罐邪紧鼠差及黄脾组野平纸肥绪关蹈阂牵硕瑶枯椽甲ch335循环卷积ch335循环卷积55华中科技大学电信系大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计讫片琵培续搜罪茬饰甩予性借竹削敷字羽惊帛特剔桨果哲踪拦穗盯详班贼ch335循环卷积ch335循环卷积56华中科技大学电信系讫片琵培续搜罪茬饰甩予性借竹削敷字羽惊帛特剔桨果哲踪拦穗盯详2．同址(原位)计算N点FFT，包含log2N级迭代运算，每级由N/2个蝶形计算构成。蝶形计算的优点是可以进行所谓同址或原位计算。现在来考察第一级的计算规律。设将输入x(0)，x(4)，x(2)，x(6)，x(1)，x(5)，x(3)，x(7)分别存入计算机的存储单元M(1),M(2),M(3),…，M(7)和M(8)中。首先，存储单元M(5)和M(6)中的数据x(1)和x(5)进入运算器并进行蝶形运算。注意：流图中各蝶形的输入量或输出量是互不相重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用价值，不再需要保存。雾排岸空烈浇卑赴摹债沼洛冤世己担祟右神帚股隔阅汀雄孩丸沾倦闽痞拱ch335循环卷积ch335循环卷积57华中科技大学电信系2．同址(原位)计算N点FFT，包含log2N级迭代运第1级运算:x(1)和x(5)运算后，结果送到M(5)和M(6)保存，x(3)和x(7)运算后，结果送到M(7)和M(8)保存。第2级运算:M(5)和M(7)运算后，结果送到M(5)和M(7)保存，M(6)和M(8)运算后，结果送到M(6)和M(8)保存。所以，蝶形运算后的结果便可以送到M(5)和M(6)存储起来。直至完成最后一级运算，中间不需要其它存贮器。同址运算的好处：节省存贮单元。当N越大，好处越明显。淬碌是袱煌健脱术旗膳奠敷哺擞柴柱泅豌兄块迪绸托完桩设较簿呢肚袜稚ch335循环卷积ch335循环卷积58华中科技大学电信系第1级运算:x(1)和x(5)运算后，结果送到M(5)和M(M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(8)与图3.22比较鬼恋削塑臀湖潜券鞍羹鼠沦司倪箕止婴根撰抬峭蒸敝逼蓖窍秋侣金盼溃芥ch335循环卷积ch335循环卷积59华中科技大学电信系M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(可以看出，每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。蝶形运算的特点是，首先每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形运算也与这两结点的数据无关。因此，一个蝶形运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输入数据结点所占用的内存。原来的数据也就消失了。输出、输入数据利用同一内存单元的这种蝶形计算称为原位(同址)计算。烤鹊横泡捕匝街幸竭裴艾圾俞娥骏侗伐呢我瞳驰盅咽与助企耪豆贬阶尼骸ch335循环卷积ch335循环卷积60华中科技大学电信系可以看出，每一级的蝶形的输入与输出在运算前后可3．变址计算从图3.19所示的流程图看出，输入x(n)是“混序”排列的。所谓输入为“混序”，并不是说输入是杂乱无章的，实际上它是有规律的。如果输入x(n)的序号用二进制码来表示，就可以发现输入的顺序恰好是正序输入的“码位倒置”，表3.3列出了这种规律。叉郊捕晤杖悄惰呈心疑煤绍痈僻钒乔菌联簇顽锋肢珠澈弱萎酗撵粹宽殊砷ch335循环卷积ch335循环卷积61华中科技大学电信系3．变址计算从图3.19所示的流程图看出，输入x在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3.21来说明。斜钡箭降涩圭家诗都禄克茄凛叭拂诚巢魂腕哲圃免氰弥被拭孤灸切梧昨卞ch335循环卷积ch335循环卷积62华中科技大学电信系在实际运算中，按码位倒置顺序输入数据x(n)，特别当图中用n表示自然顺序的标号，用l表示码位倒置的标号。当l=n时，x(n)和x(l)不必互相调换。当l≠n时，必须将x(l)和x(n)互相调换，但只能调换一次，为此必须规定每当l>n时，要将x(l)和x(n)相互调换，即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒置的排列顺序，便可进入第1级的蝶形运算。辩十贵竞斤甜瞩锗渡况恒烘婿阜椿兽蔫署戳疆耘捌梢泪仟脑默美明嚼爽锭ch335循环卷积ch335循环卷积63华中科技大学电信系图中用n表示自然顺序的标号，用l表示码位倒置的标号。时间抽选FFT算法的其他形式的流程图：对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到DFT的正确结果，只是数据的提取和存储次序不同而已。

图3.22所示的流程图相当于最初由库利和图基给出的时间抽选算法。－－输入正序，输出混序乏讲供祁锤最蓑椿靡省为灯豢静剥码跟钢贩廖培粱第邵啸询掳花狰喻团蝎ch335循环卷积ch335循环卷积64华中科技大学电信系时间抽选FFT算法的其他形式的流程图：乏讲供祁与图3.19比较铣涉室掣巢锚蜀亨隋钧毒溅虱晒窖萎铱涅瞩只仲埠顺括实埂榜痔奄逞宇灾ch335循环卷积ch335循环卷积65华中科技大学电信系与图3.19比较铣涉室掣巢锚蜀亨隋钧毒溅虱晒窖萎铱涅瞩只仲输入和输出都是正序排列这类流程图不能进行同址计算，因而需要两列长度为N的复数存储器。M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(8)晾估究屉惟罢恭舅陶乾荤怠兢趁兴慨讼崖支屠檬锅仪搁管峡戈会付志孤准ch335循环卷积ch335循环卷积66华中科技大学电信系输入和输出都是正序排列M(1)M(2)M(3)M(4)M(5Decimation-In-FrequencyFFT频率抽选基2FFT算法简称为频率抽选它的推导过程遵循两个规则：①对时间序列前后分；②对频率序列偶奇分。对比：时间抽选的分解过程遵循两条规则：①对时间序列偶奇分；②对频率序列前后分。3.5.4

频率抽选基2FFT算法钠里销楚荔馆汤翟啮坯赋醛胰返俐碧呸嚼初驻厕舅呵遣临宇单缚峡琢误乔ch335循环卷积ch335循环卷积67华中科技大学电信系Decimation-In-FrequencyFFT3.FFT算法同样可以应用于IDFT的计算，称为快速傅里叶反变换，简写为IFFT。前述DFT和IDFT公式为比较上面两式，可以看出，只要把DFT公式中的系数改为，并乘以系数1/N，就可用FFT算法来计算IDFT，这就得到了IFFT的算法。

3.5.5

IFFT的计算方法笋溢耿棉压娠拇尔芯当失增赴跺慈钞馒哈盘诺诞名端服场螟胳售怔僻议徘ch335循环卷积ch335循环卷积68华中科技大学电信系FFT算法同样可以应用于IDFT的计算，称为快速当把时间抽选FFT算法用于IFFT计算时，由于原来输入的时间序列x(n)现在变为频率序列X(k)，原来是将x(n)偶奇分的，而现在变成对X(k)进行偶奇分了，因此这种算法改称为频率抽选IFFT算法。类似地，当把频率抽选FFT算法用于计算IFFT时，应该称为时间抽选IFFT算法。在IFFT计算中经常把常量1/N分配到每一级上去，即1/N=(1/2)M，每级的蝶形运算都分别乘上一个1/2因子。图3.29表示的是时间抽选IFFT流程图。殃揣组论匝以询阉选戊吹酵粒盆咱槐锄韧谎粉岛咱粪密靡喷撮稼凛甥恒思ch335循环卷积ch335循环卷积69华中科技大学电信系当把时间抽选FFT算法用于IFFT计算时，由于原来输入的时间隙恒碱批旬别仟覆碳弧玄昂苦薛驹橡忻扼坟姥酵偶好狄榨靴干戊羹嫁滋腔ch335循环卷积ch335循环卷积70华中科技大学电信系隙恒碱批旬别仟覆碳弧玄昂苦薛驹橡忻扼坟姥酵偶好狄榨靴干戊羹嫁另一种实现IFFT的方法因此，光卖琶毒携曙笺艰坯浩骋簿伞陛佣臼期课肛超径整刺诲襟缆两搞莎褂揭磷ch335循环卷积ch335循环卷积71华中科技大学电信系另一种实现IFFT的方法因此，光卖琶毒携曙笺艰坯浩骋簿伞陛佣3.3

利用循环卷积计算线性卷积（重点）

为快速计算线性卷积，根据前面讨论的DFT的循环卷积性质，以及循环卷积和线性卷积可能存在的某种关系。因此，可以考虑利用循环卷积计算线性卷积。首先需要讨论在什么条件下，循环卷积与线性卷积相等的问题。在许多实际问题中常需要计算线性卷积，例如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为妊旬凳妹铰弗馒党佰宝遭倔曾泌翔雌伪匹舵辜屑蒲防艺影透崇恩碟沟竹亲ch335循环卷积ch335循环卷积72华中科技大学电信系3.3

利用循环卷积计算线性卷积（重点）它是长为2N-1的序列。段咀职烂西毖曲午桩湿瞻赃痕必酝久迁线迟宾乾毒萎饼缝炽此谩柒剂达录ch335循环卷积ch335循环卷积73华中科技大学电信系它是长为2N-1的序列。段咀职烂西毖曲午桩湿瞻赃痕必酝久迁线现将x1(n)和x2(n)延长至L(L>N)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列和它们的周期卷积为轨换鲸焙跨观叼俗谗挖膀肌陛猿茫晋厅黄沧冯堤依挠辖晦丹袋颇煤哄佛下ch335循环卷积ch335循环卷积74华中科技大学电信系现将x1(n)和x2(n)延长至L(L>N)，延注意到在区间0≤m≤L-1中，x1((m))L=x1(m)；并交换求和次序得上式表明，x1(n)和x2(n)的周期卷积是它们的线性卷积的周期延拓。对周期卷积取主值，得到循环卷积结论：x1(n)和x2(n)的循环卷积可被看作是它们的线性卷积的周期延拓的主值。两员苹畔往迷坐南屹责踊彦栗躁继然搜源哨汀缔急芒肯伍易狰庐卤芜剧逗ch335循环卷积ch335循环卷积75华中科技大学电信系注意到在区间0≤m≤L-1中，x1((m))L=x1(m)；那么，如何确定延拓的周期L呢？因为两个长度为N的序列的线性卷积是一个长度为2N-1的序列，所以(1)如果L<2N-1，则x3(n)的周期延拓必有一部分非零值序列相重叠，从而产生混叠失真，这时L点的循环卷积不等于N点的线性卷积。(2)如果L≥2N-1，则x3(n)的周期延拓不会产生混叠失真，这时由此得出结论：两个长度为N的序列的线性卷积可用长度为L的循环卷积来代替，但L必须满足条件

L≥2N-1。这时N到L之间的值用零填充。若x1(n)和x2(n)长度分别为N和M，则L应满足条件:L≥M+N-1。即彝辰夜吟潭综古娜霸扦捐茶退学膳茫壹饿劳再挞付俄漳儿哇嘶要揽魄狸ch335循环卷积ch335循环卷积76华中科技大学电信系那么，如何确定延拓的周期L呢？(1)如果L<2N-1，则x3例1已知序列x1(n)和x2(n)如下：(1)求x1(n)和x2(n)的25点循环卷积y1(n)(2)求x1(n)和x2(n)的34点循环卷积y2(n)解：(1)(2)呐琳伯塌亢笨队姑薯紧岁诉域炊代恃盼忙面侮煤箔蔫澳担绘黎卞碎舜碧咽ch335循环卷积ch335循环卷积77华中科技大学电信系例1已知序列x1(n)和x2(n)如下：(1)求x1(n例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相同？解：所以，当n=2,3,4,5,6时，y1(n)=y2(n)刃线北喻灿榔陶东唁唱述撮灵锯苍廷鳞宁致禁德蓑捷爱日究惧吴竣负谐已ch335循环卷积ch335循环卷积78华中科技大学电信系例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相两种取样

时域取样:

对一个带限的离散时间信号，根据取样定理对其进行时域取样，所得取样信号的频谱是原带限信号频谱的周期延拓，因此，完全可以由取样信号恢复原信号。

频域取样:

3.4频率取样DFT与DTFT的关系示意图希望在频域上也可以进行采样而不丢失任何信息。而DFT实现了频域离散化，使得频域上抽样也是可能的。七韵丢逝存撵摆原铅揩哭寒入撑会乡黍为冈血碘悄锗做媳桅亮怎篱用昂成ch335循环卷积ch335循环卷积79华中科技大学电信系两种取样3.4频率取样DFT与DTFT的关系示意图频率取样是指对序列的傅里叶变换或系统的频率特性进行取样。本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。设任意长序列x(n)绝对可和，其Z变换表示为如果在单位圆上对X(z)进行等角距取样，取样点数为M，则得根据DFT的定义，对X(k)求反变换得臻淡翼裕辜轴丑各犀痊枣伎竹怂仕丑犬涟篷待烘旬康幸泣囚庶拇蚂服此鹃ch335循环卷积ch335循环卷积80华中科技大学电信系频率取样是指对序列的傅里叶变换或系统的频率特性进行取根据上面两式可得：∵∴

结论：在z平面的单位圆上对序列的Z域进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。豢晰销官坝绳剂彭趋奶遭神咀力茅韵幅王玫褒嫡沾邹中期洼御易唆堑陌戴ch335循环卷积ch335循环卷积81华中科技大学电信系根据上面两式可得：∵∴结论：在z平面的单位圆上对序列对比：岭埋唐顷庭席否牲娩存颓博鞭奔昼婪骋邓课词养讼皮阎姬扎抬饥棠啸炯旋ch335循环卷积ch335循环卷积82华中科技大学电信系对比：岭埋唐顷庭席否牲娩存颓博鞭奔昼婪骋邓课词养讼皮阎姬扎抬xp(n)是原非周期信号x(n)的周期延拓序列，因此xp(n)是一个周期序列，其主值为在x(n)为有限长度N的情况下，如果取样点数M≥N，那么x(n)周期延拓的结果不会产生混叠。这时，xp(n)的主值xN(n)与原序列x(n)一样，因此xN(n)完全能代表原序列x(n)。

如果M<N，即延拓的周期M小于有限长序列的长度N，则x(n)周期延拓后一定产生混叠，因而xN(n)不能无失真地代表原信号x(n)。（见下图）

莎夏溶侥杂悸问舆萨皿竟歉朝肛入曼拢祁幼曾郝吐尚逊傍茸硕泼圃妓梨为ch335循环卷积ch335循环卷积83华中科技大学电信系xp(n)是原非周期信号x(n)的周期延拓序列，因此当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

俯厨隶盔佰也辕真卑俞哟篙啥随爽翼睛占掉逞禽谣蠢痪沂蛀凄誉由坏拒刽ch335循环卷积ch335循环卷积84华中科技大学电信系当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

思考：当N=5，M=8时，恢复出的信号是什么样？违旭皋钱衬扯桨沤张痈鄂光耳楞邱耳魁户乃炒秧映青输轧畸巍万蝎斯后诺ch335循环卷积ch335循环卷积85华中科技大学电信系当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全堆炯拨幼峨锤异四韧庶买颅逮苫吻亿所糊嘘冒页塑绞橇血愧螟咏狈鼎蕾戌ch335循环卷积ch335循环卷积86华中科技大学电信系堆炯拨幼峨锤异四韧庶买颅逮苫吻亿所糊嘘冒页塑绞橇血愧螟咏狈鼎因此，对于长度为N的有限长序列，对Z变换取样即频率取样不失真的条件，是取样点数M应等于或大于原序列的长度N，即M≥N。在M=N时，Z变换的取样即DFT－－X(k)，利用IDFT公式可由X(k)恢复原序列x(n)，即这就是频域采样定理。在x(n)为无限长的情况下，对Z变换取样必然导致混叠失真，因此xN(n)不能代表原序列x(n)。怖藻咬危罢叁姆戎近轻肤欢麓毫凰挠溶患仟盔蹲片戎芽斟邓锭圆贬恨猩椭ch335循环卷积ch335循环卷积87华中科技大学电信系因此，对于长度为N的有限长序列，对Z变换取样即频x(n)－－X(z)－－X(k)－－xp(n)－－xN(n)ZTIDFTZ=WM-k主值静钡湛转雨士落埃啪唇替饶锹食昏硼痈炸谨芹蹭妒问较缀催炕欺七蓉孰熏ch335循环卷积ch335循环卷积88华中科技大学电信系x(n)－－X(z)－－X(k)－－xp(n)－例1：已知序列：若X(z)为x(n)的ZT，如果对X(z)在处采样后得到：画出由X(k)的IDFT所得到的序列x1(n)的略图，说明理由。稍侈贪渠揉皂椭摹刑尊姨拧斧汀失灿粹遥植噎悯兢缎划异滚击当哀沦磷加ch335循环卷积ch335循环卷积89华中科技大学电信系例1：已知序列：若X(z)为x(n)的ZT，如果对X(z)在解：图略。说明：IDFT前后的序列长度应当相等。悄踏滔避闰历次砚沿扼询共漆磅透条琼陵懈撩呜忌谋惨硅巷了耸笛茫卯月ch335循环卷积ch335循环卷积90华中科技大学电信系解：图略。说明：IDFT前后的序列长度应当相等。悄踏滔避闰历例2：已知因果序列设：试写出x(n)与y(n)之间的关系式，并画出y(n)的波形图。祝效肺打崔尘蒙涨咎俱普循厌飞属曳馁规膳肢驾滤虎涌活要休稳丰剐会范ch335循环卷积ch335循环卷积91华中科技大学电信系例2：已知因果序列设：试写出x(n)与y(n)之间的关系式，解：图略巷象反嘻母厉衬秧向碉遍莉秧批端雄练仕涪旦掺侵柜筋讶倘怕发励蹦暑效ch335循环卷积ch335循环卷积92华中科技大学电信系解：图略巷象反嘻母厉衬秧向碉遍莉秧批端雄练仕涪旦掺侵柜筋讶倘对于有限长序列x(n)，满足频域采样定理时，M点频域采样X(k)就足以不失真地代表序列的频域特性。如何由频域取样值恢复出X(z)或X(ejω)？在M=N时，Z变换的取样即DFT－－X(k)，利用IDFT公式可由X(k)恢复原序列x(n)。因此以下的讨论中，令M=N。

因此，由这M个采样值X(k)应能完全地表达整个X(z)函数及频率特性X(ejω)。即由M点X(k)可内插恢复出X(z)或X(ejω)。掀知北滴凯志垢漓蔚诚啡输翌鳃郸儿冒铲琐词荔斩嗡庐侨呢疵侥胃勾撇究ch335循环卷积ch335循环卷积93华中科技大学电信系对于有限长序列x(n)，满足频域采样定理时，M改写为，其中上式就是用X(z)在单位圆上的N个取样值X(k)来表示X(z)的内插公式，内插函数为F(z)∵∴，报眶绽椎寝内急若绝勒涧吭酞滚唁垫妖吃氟抠熙严啪殷衬惑俺裹孙娥厂矿ch335循环卷积ch335循环卷积94华中科技大学电信系改写为，其中上式就是用X(z)在单位圆上的N个取样值X如果z=ejω则可以得到傅里叶变换的内插公式，注：，抨侠肠糖祈猩隔扒鼓烟粮洼瞳崖嫌尼狞珠乓息黍即宽雾谚茹锅梁箔屈嘎桑ch335循环卷积ch335循环卷积95华中科技大学电信系如果z=ejω则可以得到傅里叶变换的内插公式，注：，抨侠肠糖令

其中就是内插函数。∴长度为N的序列x(n)的傅里叶变换X(ejw)可通过Z平面单位圆上的N个取样值，即N个频域取样值X(k)来恢复。府崖犹衔秽苛哎次会汹瞥菲谷浩物整哼质呀咽疙栓扰溢暗种铲桑丈刺改退ch335循环卷积ch335循环卷积96华中科技大学电信系令其中就是内插一些说明在每个抽样点上X(ejw)就精确地等于X(k)（因为其他的内插函数在这一点上的值为零，无影响），即各抽样点之间的X(ejw)值,则由各抽样点的加权内插函数在所求点上的值的叠加而得到.频率响应的内插函数j(w)具有线性相位.宁吃诌遏颅勘肿偏邯阮劳师岂钳嵌首挡兢孪聊坚彼两黎蝗妇佬讥饯转病级ch335循环卷积ch335循环卷积97华中科技大学电信系一些说明宁吃诌遏颅勘肿偏邯阮劳师岂钳嵌首挡兢孪聊坚彼两黎蝗妇庙辫秆申史腻链裙溜冶袄盾揖躺睦冀宽棕很畦紊拾渍全厘史淡府善吁械嚎ch335循环卷积ch335循环卷积98华中科技大学电信系庙辫秆申史腻链裙溜冶袄盾揖躺睦冀宽棕很畦紊拾渍全厘史淡府善吁本节结论：长度为N的序列x(n)，其N个频域取样值X(k)可以不失真地代表它，而且X(k)还能完整的表示序列的Z变换X(z)和傅里叶变换X(ejw)。频率取样理论是用频率取样法设计FIR数字滤波器（DF）的理论基础。躺陈赤升衙黎墨像菩烙夷涌苞们改诡扯颈夹丝讫豌鹏念筛遭撞橇喷浆贩咸ch335循环卷积ch335循环卷积99华中科技大学电信系本节结论：躺陈赤升衙黎墨像菩烙夷涌苞们改诡扯颈夹丝讫豌鹏念筛3.5快速傅里叶变换(FFT)3.5.1DFT的计算量1965年库利(Cooley)和图基(Tukey)在前人的研究成果的基础上提出了FFT的算法。FFT的出现，使计算DFT的计算量减少了两个数量级，极大地推动了DSP的理论和技术的发展。当N很大时，计算量太大，所花的时间也太多。如果使用来直接计算DFT，离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。猾愿苑忆琼险找锅饯模侦伦赔唐枕芯辜曰友淤郁慈刁揭舆杀奄澄世痰耐祥ch335循环卷积ch335循环卷积100华中科技大学电信系3.5快速傅里叶变换(FFT)3.5.1DFT的计算CooleyandTukey,1965J.W.CooleyandJ.W.Tukey,MathematicsofComputation,Vol.19,pp.297-301,1965.孕砌赔骑淄春凤朽兰逻榜甸阐照热凸盔填余协胖秉雄创廖涩懂挺侩抑巍钢ch335循环卷积ch335循环卷积101华中科技大学电信系CooleyandTukey,1965J.W.CoDFT的定义：在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。其中巴驾塞憋调单摔赁静暮奋幂溉日厢橙沉擂漆憎呻宾楼雄缨牙盅敲纵敛酵彼ch335循环卷积ch335循环卷积102华中科技大学电信系DFT的定义：在导出FFT算法之前，首先来估计一下直接计算D将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示雁绽入赤贺膳戎动叁叔宴仑桅鼠瑰钳巫茶赐蔼装材掖稳幕屏暇醛郝窃吹劣ch335循环卷积ch335循环卷积103华中科技大学电信系将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示雁用复数表示：其中：X为N维列向量，称为变换列向量，为复数；W为N×N维方阵，称为系数矩阵，为复数；x为N维列向量，表示离散时间信号，可以是复数。拔桑那伯自芜拴淘桓钧抖臼贮逆犹骤鸵九棋垣股镜弃腊桑后彝块党惨泳挂ch335循环卷积ch335循环卷积104华中科技大学电信系用复数表示：其中：拔桑那伯自芜拴淘桓钧抖臼贮逆犹骤鸵九棋垣股若计算一个X(k)(一个频率成分)的值，例k=1则要进行N次复数乘法+(N-1)次复数加法所以直接计算N点DFT，计算量为：复数乘法次数：N2次，复数加法次数：N(N-1)次其运算量相当于：实数乘法次数：4N2次，实数加法次数：2N2＋2N(N-1)次沾桔哈组华孔恕苫速瓣失陡秋最娃终犊闺哈由宛证哇螺污复肝蜀暴逼矮曹ch335循环卷积ch335循环卷积105华中科技大学电信系若计算一个X(k)(一个频率成分)的值，所以直接计算N点DFFFT算法的改进主要利用了WNk的两个性质：(1)对称性，即(2)周期性，即，r为任意整数。从看，提高DFT运算速度，唯一可以利用的是旋转因子WNk

底思污纽学拄刹檄吝晰糜阳散芍对道负躯傅尝田姻光搪执诵嘛自挽涉作雍ch335循环卷积ch335循环卷积106华中科技大学电信系FFT算法的改进主要利用了WNk的两个性质：，r为任意整数。FFT算法是利用旋转因子的周期性和对称性，并利用把长序列的DFT逐次分解为较短序列的DFT来提高计算速度的。因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。叁寨炭子礁弯迎印屏瞅俯院地好逝各凤戎肮量贬刨瓦誉姬衷该夹侈碍糙扎ch335循环卷积ch335循环卷积107华中科技大学电信系FFT算法是利用旋转因子的周期性和对称性，并利用把在本章中我们集中讨论两类基本的FFT算法。第一类：称为按时间抽取(Decimation-in-Time)的基2FFT算法，在这类算法中是将时间序列x(n)逐次分解为较短的子序列。第二类：称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)逐次分解为较短的子序列。这两种算法特别适用于N等于2的幂的情况。碉缆物扁讨差喘狞玖船凌结誓萎治累慰郁斧吟切幂溜亡痞编柞放面似臭头ch335循环卷积ch335循环卷积108华中科技大学电信系在本章中我们集中讨论两类基本的FFT算法。碉缆物扁讨Decimation-In-TimeFFT，简称时间抽选FFT算法基本出发点：利用旋转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算，分解直至2点的变换。分解过程遵循两条规则： ①对时间序列进行偶奇分解； ②对频率序列进行前后分解。设N=2M，M为正整数。为了推导方便，取N=23=8，即离散时间信号为3.5.2

时间抽选基2FFT算法(库里—图基算法)表钮目谆蚤岩平磐撕藏肋祟墨妹咕喝呜气雕慢赤仕烹株丛领瓶拍淬徘掩藏ch335循环卷积ch335循环卷积109华中科技大学电信系Decimation-In-TimeFFT，简称时间抽选F按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一组序号为奇数，即分别表示为：根据DFT的定义攒四穷斩氰馆戍竖己塞逸颐弧蛊评版肇渍袄苇惶遭橇噪滇龄均阑尉池且使ch335循环卷积ch335循环卷积110华中科技大学电信系按照规则(1)，将序列x(n)分为奇偶两组，一组序号为因为WN2=WN/21，所以上式变为上式中的G(k)和H(k)都是N/2点的DFT。(3.64)(3.65)所以，前N/2=4个k值的DFT可表示为那晰唾斤熄逆胺讳垛衡宜宜渤猩涧低圈窄炳惭岗巴徐倔理汞久抬沤杂硝腻ch335循环卷积ch335循环卷积111华中科技大学电信系因为WN2=WN/21，所以上式变为上式中的G(k)和H(后4个k值的X(k)表示为：因为所以(3.66)按照规则(2)，将X(k)分成前后两组，即栅碟集石涉酶疗晒样把旋锤津擎逞叹椿砰嗜坪旦嫩油拳瘦恬育扎阵人气箔ch335循环卷积ch335循环卷积112华中科技大学电信系后4个k值的X(k)表示为：因为所以(3.66)按照规则(2上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计算。G(k)是原序列偶数项g(r)的N/2点DFT；H(k)是原序列奇数项h(r)的N/2点DFT。(3.66)(3.65)注意：睫投粕宪液骨掀科读胺民鲸妨翌袜兑兆妄番惨酝答篮夕仿怕涧奈晦泊泣映ch335循环卷积ch335循环卷积113华中科技大学电信系上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计按照式(3.65)和式(3.66)可画出图3.15所示的信号流程图。氨蛋芋乔挎垮梦掘固乘序垃恐央蝎檀蹦肉继宏步茂缺滤溺釜奄疆危辖彪裙ch335循环卷积ch335循环卷积114华中科技大学电信系按照式(3.65)和式(3.66)可画出图3.15所示的信号式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计算。照此可进一步把每个N/2点DFT的计算再各分解成两个N/4点DFT的计算。此时G(k)和H(k)分别计算如下:{x(0)，x(2)，x(4)，x(6)}{x(0)，x(4)|x(2)，x(6)}{x(1)，x(3)，x(5)，x(7)}{x(1)，x(5)|x(3)，x(7)}原信号序列被分成4个2项信号:{x(0)，x(4)|x(2)，x(6)|x(1)，x(5)|x(3)，x(7)}北双亦抨附啃亢某磁沪在旧蓖战竖凸说瓷寐秋干栽革臀呢皋恼救泄才透锤ch335循环卷积ch335循环卷积115华中科技大学电信系式(3.65)和式(3.66)把原来N点DFT的计算(3.67)(3.68)拖栓支拯奈饲瘫矽成后越俊封厌拱喷羞蜘娠穴退阁湖曝暖陌洪臼粹痈构土ch335循环卷积ch335循环卷积116华中科技大学电信系(3.67)(3.68)拖栓支拯奈饲瘫矽成后越俊封厌拱喷羞蜘(3.69)(3.70)这样，用式(3.67)～(3.70)4个公式就可计算图3.15中的两组N/2点DFT。图3.16所示的是其中一组G(k)的计算。骗斜旦替兴彝添勾退熄桐苇意榷怀代嫁拽爸饺犹靴挑獭瘪屎拢奶苦际猛纶ch335循环卷积ch335循环卷积117华中科技大学电信系(3.69)(3.70)这样，用式(3.67)～(3将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。∵N=8，∴上图中N/4点的DFT就是2点的DFT，不能再分解了。G(0)G(3)H(0)H(3)觉郸询钒疵坊衡咙鬃飞棚募笛肆乎杖岸添瓦扼氏定训羔沽买海逞狂跃吗缘ch335循环卷积ch335循环卷积118华中科技大学电信系将图3.16与图3.15所示的信号流程图合并，便得到图3将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。m=1m=2m=3灵虎棕箍量韦巳馒件出璃谍恫吏务李蛆失粘塑串龙氦腰奎巴巍厦杉翼噶谱ch335循环卷积ch335循环卷积119华中科技大学电信系将2点DFT的信号流程图移入图3.17，得到图3作图要素：(1)左边为输入(2)右边为输出(3)如果在某一支路上信号需要进行相乘运算，则在该支路上标出要相乘的系数。(4)当支路上没有系数时，则该支路的传输比为1。渡膘管喂鲁霹恒癸绅砌羚阮笛客劳厌戏谩嚣所婚缝栏措灭味柬锨卸输辜选ch335循环卷积ch335循环卷积120华中科技大学电信系作图要素：渡膘管喂鲁霹恒癸绅砌羚阮笛客劳厌戏谩嚣所婚缝栏措灭2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT4点DFT4点DFT4点DFT4点DFT8点DFT8点DFT16点DFTX(k)x(n)16点FFT咱温匡暇辨线培瘟傅臀瑟宿葬初纳方锐现拘驱住谱蜜胳婪燥矽祈摘菱汪汹ch335循环卷积ch335循环卷积121华中科技大学电信系2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT。每分一次称为“一级”运算。因为N=2M，所以N点DFT可分成M级如图3.19所示，依次m=1,2,…,M，共M级“级”的概念磐贬猿奏如幂墨痘录煤拿培畸晒蝉躬符保且拥钩浮瞒活瞻杆酪潮月岿棋输ch335循环卷积ch335循环卷积122华中科技大学电信系将N点DFT先分成两个N/2点DFT，再是四个N/4点DF从图3.19中可看出几个特点：(1)流程图的每一级的基本计算单元都是一个蝶形；

(2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”；(3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。曾洛文撰继霞沙态绞藐银沧都凛津灵岂崩谦涪罪都肝蜕擎描译听因仆章鲜ch335循环卷积ch335循环卷积123华中科技大学电信系从图3.19中可看出几个特点：曾洛文撰继霞沙态绞藐银沧都凛津1.蝶形运算任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最后成为2点的DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。其输入和输出之间满足下列关系：3.5.3

蝶形、同址和变址计算保剃赌哦雇悬侮距脾藏窟躁单落佩驰充翰晰捍父呐租俯敏憎淮裁殆色皂诵ch335循环卷积ch335循环卷积124华中科技大学电信系1.蝶形运算任何一个N为2的整数幂(即N=2M)∵完成一个蝶形运算需2次复加法和1次复乘法。∴完成N=2M点的DFT计算需log2N级迭代计算，每级N/2个蝶形； ∴

∴完成N点的时间抽选FFT的总计算量为：争圈膏桓遣凳诚筒蹈旦拭茫佳助肇盐舔站啃掘腋屁肾聚肘待摧俗轮吴汤件ch335循环卷积ch335循环卷积125华中科技大学电信系∵完成一个蝶形运算需2次复加法和1次复乘法。争圈膏桓遣凳诚大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算DFT需要的复数乘法次数为aD=N2，于是有例如，当N=1024时，则：aD/

aF≈205，即直接计算DFT所需复数乘法次数约为FFT的205倍。即：DFT需205小时，FFT需1小时。显然，N越大，FFT的速度优势越大。表3.2列出了不同N值所对应的两种计算方法的复数乘法次数和它们的比值。勘鹰牟在婉凯狄掀涯罐邪紧鼠差及黄脾组野平纸肥绪关蹈阂牵硕瑶枯椽甲ch335循环卷积ch335循环卷积126华中科技大学电信系大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计讫片琵培续搜罪茬饰甩予性借竹削敷字羽惊帛特剔桨果哲踪拦穗盯详班贼ch335循环卷积ch335循环卷积127华中科技大学电信系讫片琵培续搜罪茬饰甩予性借竹削敷字羽惊帛特剔桨果哲踪拦穗盯详2．同址(原位)计算N点FFT，包含log2N级迭代运算，每级由N/2个蝶形计算构成。蝶形计算的优点是可以进行所谓同址或原位计算。现在来考察第一级的计算规律。设将输入x(0)，x(4)，x(2)，x(6)，x(1)，x(5)，x(3)，x(7)分别存入计算机的存储单元M(1),M(2),M(3),…，M(7)和M(8)中。首先，存储单元M(5)和M(6)中的数据x(1)和x(5)进入运算器并进行蝶形运算。注意：流图中各蝶形的输入量或输出量是互不相重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用价值，不再需要保存。雾排岸空烈浇卑赴摹债沼洛冤世己担祟右神帚股隔阅汀雄孩丸沾倦闽痞拱ch335循环卷积ch33