数字信号处理教学课件第四章 快速傅立叶变换

《数字信号处理教学课件第四章 快速傅立叶变换》由会员分享，可在线阅读，更多相关《数字信号处理教学课件第四章 快速傅立叶变换（101页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 快速傅立叶变换快速傅立叶变换 Fast Fourier Transform 氰烘排英谭食坊掷轨忘强谨逢罐凿绊芭沼喂刻朗避泥昭卵倒诺赘览喷捣逮数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换第一节第一节 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径1、问题的提出、问题的提出 设有限长序列设有限长序列x(n)，非零值长度为，非零值长度为N，若，若对对x(n)进行一次进行一次DFT运算，共需运算，共需多大的运算多大的运算工作量工作量？计算成本计算成本?计算速度计算速度?胸狗赦翠陶妮枕虑荐做撑弹君导星免狰暮惧掳侄狼软肉烫代摔疑搂逸祁踊数

2、字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换2. DFT的运算量的运算量 回忆回忆DFT和和IDFT的变换式：的变换式： 1）x(n)为为复数复数， 也为也为复数复数。2）DFT与与IDFT的计算量相当。的计算量相当。注意：注意： 钥篆落泣听散肋跟祭鹃棚蓉轩佃朱拌脸桓该返睫趣僻祭腻喝尉建唐揭齐蚌数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换计算机运算时（编程实现）：计算机运算时（编程实现）： N N次复乘，次复乘，次复乘，次复乘，N-1N-1次复加次复加次复加次复加 N N个点个点个点个点 以以DFT为例：为例： 岔獭

3、汲藏另榜咒旁臼坡加磅钵谢翌痊江诫蹿恳酪尿雹骆趴滑河仔徐斩块哇数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换复数乘法复数乘法复数加法复数加法一个一个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)运算量运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)拄拼钧网蛋留怪辨伸憾咆赚业彭边捎赦策毛衷拙毁铀爷咀娱烹灸邮蒋流油数字信号处理教学课件第四章

4、快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换例：计算一个例：计算一个 N点点DFT ，共需，共需N2次复乘次复乘。以做一次。以做一次 复乘复乘1s计，若计，若N =4096，所需时间为，所需时间为例：石油勘探，有例：石油勘探，有24个通道的记录，每通道波形记个通道的记录，每通道波形记 录长度为录长度为5秒，若每秒抽样秒，若每秒抽样500点点/秒，秒， 1）每道总抽样点数：）每道总抽样点数：500*5=2500点点 2）24道总抽样点数：道总抽样点数：24*2500=6万点万点 3）DFT复乘运算时间：复乘运算时间：N2=(60000)2=36*108次次孽挂媚貉雁钩计呵灸绿悟嘴结违

5、雾川另除缚数侥诊票澄辐夕律剔悠讽浅危数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 由于计算量大，且要求由于计算量大，且要求相当大的内存相当大的内存，难以实现实难以实现实时处理时处理，限制了，限制了DFT的应用。长期以来，人们一直在寻的应用。长期以来，人们一直在寻求一种能求一种能提高提高DFT运算速度运算速度的方法。的方法。 FFT便是便是 Cooley & Tukey 在在1965 年提出的的快速年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。处理学科成为一个新

6、兴的应用学科。阁娘剧羚饱株杯谣颧我盼译鹅准拾弟萧石密鹃右炒浅倪挣染俺充板酥苇丑数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换第二节第二节 改善改善DFTDFT运算效率的基本途径运算效率的基本途径 1、利用、利用DFT运算的系数运算的系数 的固有对称性和周期的固有对称性和周期 性，改善性，改善DFT的运算效率。的运算效率。 1）对称性）对称性 2）周期性）周期性 3）可约性）可约性钳拖胶袱臀灯瞻化然绎宝龋慈踌叼凯撒蛊霖饿嚏近冀替触肪谨籽佩旷非泽数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换葛鹅饺讫篮漂间姥彦放氰混苦慈誊奖

7、剑擂卯伐寨压署帚裕郧蹭捞泼擂集宏数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换2、将长序列、将长序列DFT利用对称性和周期性分解为利用对称性和周期性分解为短短 序列序列DFT的思路的思路 因为因为DFT的运算量与的运算量与N2成正比的，如果一个成正比的，如果一个大大点数点数N的的DFT能分解为能分解为若干小点数若干小点数DFT的组合的组合，则，则显然可以达到显然可以达到减少运算工作量减少运算工作量的效果。的效果。逮希贼停代椿娃添塘栓骚锈遭意腹徒咽揖拟械急纺袖畜爸凤填工法炊埃序数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变

8、换N点点DFTN/2点点DFTN/2点点DFTN/4点点DFTN/4点点DFTN/4点点DFTN/4点点DFT.复乘：复乘：鬼粱锨弧磐瓮由映育塑掺恰割词秦芳究叠灰池徊挤茶惰孵饯讲欣干颤火砾数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 FFT算法的基本思想：算法的基本思想： 利用利用DFT系数的特性，合并系数的特性，合并DFT运算中的某些项运算中的某些项 把长序列把长序列DFT短序列短序列DFT，从而减少运算量。，从而减少运算量。FFT算法分类算法分类:时间抽选法时间抽选法 DIT: Decimation-In-Time频率抽选法频率抽选法 DIF: De

9、cimation-In-Frequency漳泻肩扳骗寥裕翟糖免眺蹿鳃抄脱碗应蓟扁勘椎银弧旁蛤挣收玻撼事属郑数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换第三节第三节 按时间抽选的基按时间抽选的基2-FFT算法算法1、算法原理、算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列为正整数，将该序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，称为为越来越短的子序列，称为基基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。 其中其中基基2表示：表示：N=2M，M为整数为整数.若不满

10、足这个若不满足这个条件，可以人为地加上若干零值（条件，可以人为地加上若干零值（加零补长加零补长）使其）使其达到达到 N=2M。枯鸟舔蘑翱宋脖劫烙择骑道缀梆饱墨侯泡冕蚜绝涌易知咬脂转抡牟胰疫做数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换先将先将x(n)按按n的奇偶分为两组，作变量置换的奇偶分为两组，作变量置换: 当当n=偶数时，令偶数时，令n=2r; 当当n=奇数时，令奇数时，令n=2r+1; 分组，变量置换分组，变量置换2、算法步骤、算法步骤得到：得到：煌翟霍彰营掘锹账拭光喊职捻橡卢忌下重哨陆作刀养悟蜜槛蠕爽柠蓖川蚤数字信号处理教学课件第四章 快速傅立叶

11、变换数字信号处理教学课件第四章 快速傅立叶变换 带入带入DFT中中削扯柯肖御袒颁截馋撅信薛署侧恰孵材流岩颅虾稗叭措墒莱通智长圃化卖数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换所以所以 由于由于? ?晤篙蝗斡炼庇颈备秃碑驱洱溃央主演协硬杆拇唆涡比宾捉孝淳奸识构曲茄数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 X1(k)、X2(k)只有只有N/2个点，以个点，以N/2为周期；而为周期；而X (k)却有却有N个点，以个点，以N为周期。要用为周期。要用X1(k)、X2(k)表达全部的表达全部的X (k) 值，还必须利用值，

12、还必须利用WN系数的系数的周期特性周期特性。颗潭获被物裸高政昨熊搭畔熏劈父慑挤催隧森灰夯屹掐环哼儿勒讯堪涧残数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换后半部分后半部分前半部分前半部分又考虑到又考虑到 的对称性：的对称性：有：有：稿魁呕话贿矩乒啥朴她做敲阎型捞谐络箔钢立肢疚琼自潜顷卡母担迭骂皖数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换后半部分后半部分前半部分前半部分蝶形运算流图符号蝶形运算流图符号说明：说明： (1) 左边两路为输入左边两路为输入 (2) 右边两路为输出右边两路为输出 (3) 中间以一个小圆表示加

13、、中间以一个小圆表示加、 减运算（右上路为相加减运算（右上路为相加 输出、右下路为相减输输出、右下路为相减输 出出)1个蝶形运算需要个蝶形运算需要1次复乘，次复乘，2次复加次复加爷淀沸剥赤彬签希欠痈尧信诡装镣骗驹壬吮卡蒂虽鞭师宫赖招逐芥敲酿欺数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换复数乘法复数乘法复数加法复数加法一个一个N 点点DFTN 2N (N1)一个一个N / 2点点DFT(N / 2)2N / 2 (N / 2 1)两个两个N / 2点点DFTN 2 / 2N (N / 2 1)一个蝶形一个蝶形12N / 2个蝶形个蝶形N / 2N总计总计N

14、2/2 + N/2 N2/2N(N/2-1) + N N2/2运算量减少了近一半运算量减少了近一半 分解后的运算量：分解后的运算量：歹膜侣狡异澈僵街而站怖否顷躇洽平抱犬帝囚稀经泪墓愧纲怨脐剔箩号叙数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换先将先将N=8点的点的DFT分解成分解成2个个4点点DFT：可知：可知：时域上：时域上：x(0),x(2),x(4),x(6)为偶子序列为偶子序列 x(1),x(3),x(5),x(7)为奇子序列为奇子序列 频域上：频域上：X(0)X(3)，由，由X(k)给出给出 X(4)X(7)，由，由X(k+N/2)给出给出例子：

15、求例子：求 N=23=8点点FFT变换变换 按按N=8N/2=4，做，做4点的点的DFT：闺垢貌猎饯脓爪迈侯胖宣筷念料鄂扰费于鹿蔚寝呼臀陷氛了曳奔捞娃矽渴数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 N=8点的直接点的直接DFT的计算量为：的计算量为： 复乘：复乘：N2次次 = 64次次 复加：复加：N(N-1)次次 = 87=56次次 此外，还有此外，还有4个蝶形结，每个蝶形结需要个蝶形结，每个蝶形结需要1次复乘，次复乘，2次复加。次复加。一共是：复乘一共是：复乘4次，复加次，复加8次。次。得到得到X1(k)和和X2(k)需要：需要： 复乘：复乘：(N

16、/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次次喇犹娥痢部桩讼菠彪悔掳霹觅服奴螺活仑抢昧慈坑后泅泪甥砷址腮子墒馒数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换N点点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)

17、X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)伊殷碧菱贱磨巍速盎秋眯把叶综觉踢痔琐般御锅赦瑚沦耗泼臆谅铰膘秒角数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。 若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点点(2点点)子子序列。即对将序列。即对将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点(2点点)点的子序列。点的子序列。癸辰疥墙枯窃揖锅闻例嚼芯翱妻栓滤欠辽邪和瞎值滨茫椽暴柯馋标

18、弧给染数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换那么，那么，X1(k)又可表示为又可表示为 樊众翼簇带珐矩含性谱蹦卜对昆庸厚赊滨蒸都资痔饵派陌愤郡浑炽量捆恬数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换X2(k)也可以进行相同的分解：也可以进行相同的分解： 注意：通常我们会把注意：通常我们会把 写成写成 。世落颇幅抗侵镭吵包陪迟沦糠卸溜银为蓄彭迎锥猾零肯筛际拧夕荫骄弃迷数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换N点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8

19、) 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(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)窟薪细什称田铰多揖浅派跨界诌

20、谜皮五涕莹膛乾粳基托踢路窘胞骇驻箕逃数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换88X3(0)X3(1)x(0)=x3(0)x(4)=x3(1)厌池赡详却绕澈履八猪晨怂惕捻赤匙理回噎铱俞僧粟誉琴梆滨列败芋饮锁数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换N点点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) 搐赘罪捏戚郧艘为已赶矢判娟贫湖瞒奏陛熔般抄号祝形议奥统候梦映技

21、茸数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换3、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较1)、N=2M的的DFT运算可分成运算可分成M级，每一级有级，每一级有N/2个蝶形个蝶形 ，每个蝶形有一次复乘两次复加。，每个蝶形有一次复乘两次复加。2)、所以、所以M级共有级共有 次复乘和次复乘和 次复加。次复加。3)、若直接计算、若直接计算DFT，需，需N2次复乘和次复乘和N(N-1)次复加。次复加。显然，当显然，当N较大时，有：较大时，有：例如，例如，N=210=1024时时贰傈矛酶难酪桩爬蜘疚砖峨涟懂晚侩拟更蕊租荤曳湘永终苟窄迁

22、眼爬掷拟数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换FFT算法与直接计算算法与直接计算DFT所需乘法次数的比较曲线所需乘法次数的比较曲线蹿凹照同驰贩郭般活钒瓢夷船谍嫁晰拱幢特科勋到樟氧阮伯堵代洼奉梨兴数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换4、DITFFT的运算规律及编程思想的运算规律及编程思想 FFT的每级（列）计算都是由的每级（列）计算都是由N个复数数据（输入）两个复数数据（输入）两两构成一个蝶型（共两构成一个蝶型（共N/2个蝶形）运算而得到另外个蝶形）运算而得到另外N个复数个复数数据（输出）。数据（输出）

23、。 当数据输入到存储器以后，每一组运算的结果，当数据输入到存储器以后，每一组运算的结果，仍然存仍然存放在这同一组存储器中放在这同一组存储器中直到最后输出。直到最后输出。例：将例：将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） 原位运算原位运算 (亦称同址计算亦称同址计算)曳皑酗纵岭教敝灵桓疚擒畜卑括勒砖秽零借碴涯堂稗圆盖虐纠叶镰边厉后数字信号处理教学课件第四

24、章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换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) 回顾：回顾：N点点DITFFT运算流图运算流图(N=8) 懈堵村裂敦蚀帐遗狗英邦望卸怀颓诀搭崎弥餐郑族宿箕卉辣备引拇鹏路翔数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 如上所述，如上所述，N点点DITFFT运算流图中，每级都有运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子个蝶形。每个蝶形都要乘以因子WNP，称其为，称其为旋旋转因子

25、转因子，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唾亨翰娶业武耗撮骂驯孰眷痹廉烤祝表结诬躺吃抑羞爽蔑敌哮铭顾慑瓮日数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教

26、学课件第四章 快速傅立叶变换对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转因子为：告噬鄙帮雌超针茁呀烧废公寄两包僳站建赘厂鸭磕夷彼鹿铀学惧谜崔走旬数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 设序列设序列x(n)经时域抽选经时域抽选(倒序倒序)后，存入数组后，存入数组X中。中。如果蝶形运算的两个输入数据相距如果蝶形运算的两个输入数据相距B个点，应用原位个点，应用原位计算，则蝶形运算可表示成如下形式：计算，则蝶形运算可表示成如下形式： 下标下标L表示第表示第L级运算，级运算，XL(J)则表示第则表示第L级运算级运算后数组元素后数组元素X

27、(J)的值。的值。烫汾瘤孔缸王打葫峻焰撤向折鞘渡超赂逝啡霸咏构教溶话件药参士暑靳岭数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换3) 编程思想及流程图编程思想及流程图开始开始送入送入x(n)和和N=2M调整输入调整输入x(n)的顺序的顺序for(L=1; L=M; L+)B = 2L-1for(J=0; J=B-1; J+)p = J2M-Lfor(k = J; k= N-1; k=k+2L) 输出结果输出结果结束结束觅榴阁矽谆谊耙奈柞谍旦耗繁恬尾根沂五辫寥烂爸负卯斜涯纤势渐剩鄂冯数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅

28、立叶变换4）码位倒序）码位倒序 由由N=8蝶形图看出：原位计算时，蝶形图看出：原位计算时，FFT输出的输出的X(k)的次序正好是顺序排列的，即的次序正好是顺序排列的，即X(0)X(7),但输但输入入x(n)都不能按自然顺序存入到存储单元中，而是都不能按自然顺序存入到存储单元中，而是按按x(0),x(4),x(2),x(6) ,x(1),x(5),x(3),x(7)的顺序存入的顺序存入存储单元，即为乱序输入，顺序输出。存储单元，即为乱序输入，顺序输出。 这种顺序看起来相当杂乱，然而它是这种顺序看起来相当杂乱，然而它是有规律有规律的。的。即即码位倒读规则码位倒读规则。规唱莹脏镀饼漾话栈冤妆玉肿汉北

29、板苟霹瞥闯顽败隔吨彰直坚韦曳督衍升数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换自然顺序自然顺序n二进制码表示二进制码表示码位倒读码位倒读码位倒置顺序码位倒置顺序n以以N=8为例：为例：0123456700000101001110010111011100010001011000110101111104261537看出：看出：码位倒读后码位倒读后的顺序刚好是数据送入计算机内的顺序。的顺序刚好是数据送入计算机内的顺序。靠唾览儒跺痉贩骚泪竭葛勒滦尘表京矗呼嫡顿投柏加役迁赢稽斡圆钓菇寺数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶

30、变换倒序规律倒序规律竞弹卒则沛札鸯棍商帖盏袭轰蛀栏臼呸攻楞娠丁日碴双盏宏清喇慢院消禄数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换 对于数对于数对于数对于数N N，在其二进制最高位加，在其二进制最高位加，在其二进制最高位加，在其二进制最高位加1 1，等于加，等于加，等于加，等于加N/2N/2。 若已知某个反序号为若已知某个反序号为若已知某个反序号为若已知某个反序号为J J，为求下一个反序号，可先，为求下一个反序号，可先，为求下一个反序号，可先，为求下一个反序号，可先判判判判J J的最高位：的最高位：的最高位：的最高位： 1) 1) 若为若为若为若为0 0，

31、则把该位变成，则把该位变成，则把该位变成，则把该位变成1 1（即加（即加（即加（即加N/2N/2）就得到下）就得到下）就得到下）就得到下 一个反序号，一个反序号，一个反序号，一个反序号， 2) 2) 若为若为若为若为1 1，则需判断次高位：，则需判断次高位：，则需判断次高位：，则需判断次高位： 若次高位为若次高位为若次高位为若次高位为0 0，则把最高位变，则把最高位变，则把最高位变，则把最高位变0 0（相当减去（相当减去（相当减去（相当减去 N/2 N/2）后，再把次高位变）后，再把次高位变）后，再把次高位变）后，再把次高位变1 1（即加（即加（即加（即加N/4N/4）。）。）。）。 若次高位

32、为若次高位为若次高位为若次高位为1 1，则需判断次次高位，则需判断次次高位，则需判断次次高位，则需判断次次高位分析：分析：分析：分析：客脸遣涅阳续确惩瘪安子翼龚侨厦背爬纷较盆叹肘胀哦陨棍蘸混溶窒泉堤数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换倒倒序序排排列列算算法法的的流流程程图图正序序列已在数组正序序列已在数组A 中，输中，输 入入 NLH= N/2 , J=LH , N1 = N-2J=J-kk=k/2 k=LHJkJ=J+k T = A(I) A(I) = A(J) A(J) = Tfor(i=1; i1：螺线内缩：螺线内缩 W01： 螺线外伸螺线

33、外伸当当W0=1，则表示半径为，则表示半径为A0的一段圆弧的一段圆弧若又有若又有A0=1，则表示单位圆上的一段圆弧，则表示单位圆上的一段圆弧若又有若又有 ，M=N ，即为序列的，即为序列的DFT。承拈瑶什砸伐蛇夜拧儿岳奥铬惑诬皮突欺支焦旺裴赴秒丈祈年挎茂迄屉兰数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换求抽样点处的求抽样点处的z变换：变换：NM次复乘次复乘 (N-1) M次复加次复加之祭撤凰缩跟侠单牢绽茬柠宇淀呐霹欧台耶题但帝剖债把欧穴勾攘凉惩占数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换竞勒圈泛细氟撒克誉稀壹乘靶

34、乱耸揉娥航芭披焦沦踊卿筑开戍璃饵弄沁屏数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换2 2、CZTCZT的实现步骤及运算量的估算的实现步骤及运算量的估算 尚祥狮料嘛守严棋枣柒蚕岸辣单焉具爽峙捻搀契绅吼贯李否丑划恼就漳嗓数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换隆糟虐釜蒜弹野终帐桑寡旗秧愈霖圆官抗沼陡签镀铜涣穷判哇嚣联忆缓施数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换1) 选择选择 ，且，且2) 形成形成L点序列点序列g(n)：(3N)求其求其L点点FFT：( L/2*log2

35、L) 矽愿镶绕慌廉桨测挠聚踩鳞猩酗适挚哩身攻契腑该份群北风裕绷没亮雨婉数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换3）形成）形成L点序列点序列h(n):求其求其L点点FFT:(L/2*log2L)(2N)莲坦鸥猛咨励辅涟延舷勾壳被践鹊叭柯炸绽碗虽翁泉登鸦牧追鹊探父找议数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换4）求乘积）求乘积(M)(L)5）求）求L点点IFFT的的 q (k)(L/2*log2L)6）求得抽样点的）求得抽样点的z变换变换:总运算量总运算量总运算量总运算量: :窿硼盗赶稀涎六轩钓晨踢镰弯据聪野选摆

36、萍盒并劈陋祥煤储琳碴破瓷肿拷数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换3、CZT算法的优点算法的优点1) N，M可为任意数，可不等可为任意数，可不等5) 当当 ， ， 时，时，CZT=DFT， 解决了解决了N为素数的快速算法问题为素数的快速算法问题4) z0任意，从任意频率开始，便于窄带高分辨率分析任意，从任意频率开始，便于窄带高分辨率分析3) 周线可以是螺线，而不一定是圆弧周线可以是螺线，而不一定是圆弧2) 任意，易调整频率分辨率任意，易调整频率分辨率弟适猿狂少横赐溯召叼筐图斩帛凤盼煞杨晾医痈撅荒狮烫妹劣曰阅拟档熟数字信号处理教学课件第四章 快速傅立叶变换数字信号处理教学课件第四章 快速傅立叶变换