函數(shù)正交變換與離散傅里葉變換

第二章

函數(shù)正交變換與離散傅里葉變換2.1函數(shù)的正交展開2.2離散系統(tǒng)與連續(xù)系統(tǒng)的等效性2.3離散傅里葉變換及性質(zhì)2.4圓周卷積與線性卷積2.5快速傅里葉變換2.6其他離散變換及特點(diǎn)2.1函數(shù)的正交展開拉普拉斯變換，傅里葉變換，離散傅里葉變換，z變換的理論基礎(chǔ)：正交變換函數(shù)空間空間的正交基函數(shù)的正交展開1、函數(shù)空間定義：集合X={f(t),f(t)是具有某種性質(zhì)的連續(xù)函數(shù)或可導(dǎo)函數(shù)}若任意f1屬于X，f2屬于X，有則稱X是一個(gè)線性函數(shù)空間2.1函數(shù)的正交展開2、函數(shù)內(nèi)積定義：對(duì)內(nèi)積和范數(shù)是收斂的無窮多維向量所構(gòu)成的空間是函數(shù)空間中的兩個(gè)元f,g所決定的一個(gè)標(biāo)量<f,g>則稱為f和g的內(nèi)積滿足非負(fù)性，對(duì)稱性，齊次可加性3、范數(shù)定義：4、希爾伯特空間定義：每個(gè)元和自己的內(nèi)積正平方根2.1函數(shù)的正交展開5、空間的正交基定義：若函數(shù)集合則稱為X的一個(gè)正交基底若此函數(shù)集合的各元之間都彼此正交，且線性張成X，即=1，函數(shù)序列稱為規(guī)范（標(biāo)準(zhǔn)）正交2.1函數(shù)的正交展開5、函數(shù)的正交展開：則對(duì)于任意M可以是有限值也可以是無窮大都可以用唯一地表示出來2.1函數(shù)的正交展開？1：如何確定各系數(shù)fm？2：確定出的各系數(shù)能否保證級(jí)數(shù)確實(shí)收斂為函數(shù)f（t）？1解決方案：取和內(nèi)積m=n內(nèi)積為非零2.1函數(shù)的正交展開？1解決方案：取和內(nèi)積注意：由于正交展開的唯一性，f與fn一一對(duì)應(yīng)2.1函數(shù)的正交展開？2：確定出的各系數(shù)能否保證級(jí)數(shù)確實(shí)收斂為函數(shù)f（t）答案：f(t)對(duì)規(guī)范正交逼近基底的正交展開收斂于原f(t)2.1函數(shù)的正交展開引入：逼近基底概念定義：如果無窮維的希爾伯特函數(shù)空間中的任一元f(t)均可用一個(gè)有無窮多個(gè)元的基底函數(shù)集合的各元作任意準(zhǔn)確逼近，即：對(duì)任ε>0總存在有基底序列的局部線性組合，使得：則稱是空間的一組逼近基底，或稱完備集合與極限不同，因?yàn)閒k在不斷變化2.1函數(shù)的正交展開但若逼近基底彼此正交，則fk是不變的，從而極限f(t)對(duì)規(guī)范正交逼近基底的正交展開收斂于原f(t)2.1函數(shù)的正交展開6:正交展開實(shí)例例1：時(shí)限函數(shù)對(duì)（伸縮）復(fù)指數(shù)的可列集合的正交展開2.1函數(shù)的正交展開6:正交展開實(shí)例例1：時(shí)限函數(shù)對(duì)（伸縮）復(fù)指數(shù)的可列集合的正交展開即傅里葉級(jí)數(shù)及系數(shù)展開2.1函數(shù)的正交展開6:正交展開實(shí)例同理：對(duì)于伸縮單位為實(shí)數(shù)，伸縮單位為復(fù)數(shù)s=a+j

的正交展開，分別為傅里葉積分和拉普拉斯變換同理：對(duì)于序列伸縮單位為實(shí)數(shù)的變換為序列的傅里葉變換，伸縮單位為復(fù)數(shù)z的變換為z變換

2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性實(shí)際問題：如何用數(shù)字機(jī)對(duì)連續(xù)系統(tǒng)仿真，即用離散系統(tǒng)代替連續(xù)系統(tǒng)？連續(xù)系統(tǒng)空間離散系統(tǒng)空間L2（R）l2（Z）即能在空間找到一個(gè)同構(gòu)映射u,使上述兩個(gè)空間的元有一一對(duì)應(yīng)的關(guān)系離散到連續(xù)系統(tǒng)連續(xù)到離散系統(tǒng)連續(xù)系統(tǒng)L離散系統(tǒng)l2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性如果將系統(tǒng)限制在線性時(shí)不變范圍內(nèi)；映射是否能夠把卷積積分的三個(gè)函數(shù)映射成仍有卷積和關(guān)系的三個(gè)函數(shù)？這樣的映射條件稱為定常映射。對(duì)于連續(xù)系統(tǒng)，輸入輸出可表示為卷積積分的關(guān)系對(duì)于離散系統(tǒng)，輸入輸出可表示為卷積和的關(guān)系？什么樣的映射是可以的，即定常映射的條件是什么樣的？2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性由連續(xù)變到離散序列的映射，從數(shù)學(xué)上可由函數(shù)的正交展開來實(shí)現(xiàn)。由于基底是可列的，因此也是一個(gè)序列，即離散化的序列，這樣就構(gòu)成了從前面知道，對(duì)于函數(shù)空間V的一組可列的正交基底，任意均可利用此正交基底展開。連續(xù)到離散的映射。2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性正交展開后滿足定常映射的充分必要條件是：證明：基底的任意兩個(gè)元之間滿足：充分性：2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性正交展開后滿足定常映射的充分必要條件是：證明：基底的任意兩個(gè)元之間滿足：充分性：反推即得到必要性！2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性上面的定常映射條件為時(shí)域條件，下面可推得到頻域條件根據(jù)拉普拉斯變換或者傅立葉變換的卷積定理可以知道：也就是說條件變?yōu)椋夯缀瘮?shù)序列下標(biāo)為n的序列的積分變換需是下標(biāo)為1的元的n次方2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例1：帶限函數(shù)對(duì)偏移采樣函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用其他符合定常映射條件的展開方法。它在帶限函數(shù)（）空間中完備，其正交性為即是正交逼近基2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例1：帶限函數(shù)對(duì)偏移采樣函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用其他符合定常映射條件的展開方法。任意帶限函數(shù)可以展開為：由帕斯維爾定理：連續(xù)到離散的正映射2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例1：帶限函數(shù)對(duì)偏移采樣函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。其它為0恰好是反傅里葉變換，在t＝n?T處的采樣值2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例1：帶限函數(shù)對(duì)偏移采樣函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。其它為0其對(duì)應(yīng)的逆映射為因此采樣序列通過理想低通濾波器就可以恢復(fù)出原始信號(hào)滿足定常映射條件2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例2：時(shí)限函數(shù)對(duì)復(fù)指數(shù)函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。復(fù)指數(shù)序列：其連續(xù)到離散展開式是時(shí)限函數(shù)（－T/2,T/2）的一組正交逼近基底系數(shù)序列唯一地對(duì)應(yīng)了一個(gè)連續(xù)時(shí)間函數(shù)，這也是一種同構(gòu)映射離散到連續(xù)逆映射2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例2：時(shí)限函數(shù)對(duì)復(fù)指數(shù)函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。復(fù)指數(shù)序列：因此該映射不滿足定常映射條件傅立葉變換：2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例3：解析型函數(shù)對(duì)拉蓋爾函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。解析型函數(shù)是拉普拉斯變換存在的函數(shù)，在帶寬和持續(xù)期上都沒有限制正交性是對(duì)加權(quán)函數(shù)t的正交拉蓋爾函數(shù)序列的各元為2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性給出幾個(gè)正交展開的實(shí)例，并且判斷是否符合定常映射條件例3：解析型函數(shù)對(duì)拉蓋爾函數(shù)序列的展開即連續(xù)系統(tǒng)離散化時(shí)，通常利用的方法是采樣（也是正交展開的一種），還可以利用符合定常映射條件的展開方法。逆映射為模擬信號(hào)到離散序列實(shí)現(xiàn)復(fù)雜，連續(xù)系統(tǒng)設(shè)計(jì)等效的離散系統(tǒng)常用正映射為拉蓋爾函數(shù)序列顯然滿足定常映射條件2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性因此只要進(jìn)行滿足定常映射條件的同構(gòu)映射，就可以完成從連續(xù)系統(tǒng)到離散系統(tǒng)的轉(zhuǎn)換2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性數(shù)字信號(hào)處理中各種變換的總結(jié)TTDNNDSΩZWwFNF時(shí)域頻域連續(xù)信號(hào)離散信號(hào)K

L

F

Z

FT

DFT2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性數(shù)字信號(hào)處理中各種變換的總結(jié)定義的各種空間：T：在連續(xù)域上拉普拉斯（L）存在的希爾伯特空間N：希爾伯特空間T定常映射后的離散希爾伯特序列空間Ω：S定義在虛軸上的子空間S：希爾伯特空間T拉普拉斯變換后的復(fù)數(shù)空間W：空間Z的虛部子空間Z：將s中的各元作定常映射變換后的復(fù)數(shù)空間K：空間W中的元定常映射后的離散序列空間2.3離散傅里葉變換及性質(zhì)由“序列的傅立葉變換”我們知道：

序列的傅立葉變換就是序列的頻譜，它是數(shù)字頻率的連續(xù)變量函數(shù)，且序列的長(zhǎng)度不受限制。但在實(shí)際利用計(jì)算機(jī)或數(shù)字設(shè)備進(jìn)行頻譜分析時(shí)，只能處理有限長(zhǎng)數(shù)據(jù)且必須將其離散化。有限長(zhǎng)序列的傅立葉變換及頻率離散化問題——離散傅立葉變換（DFT）2.3離散傅里葉變換及性質(zhì)

DFT與z變換oooooooooooX（ejω）X（k）oRe[z]jIm[z]o2.3離散傅里葉變換及性質(zhì)序列傅里葉變換離散傅里葉變換離散化后時(shí)域序列以N為周期進(jìn)行重復(fù)，原序列長(zhǎng)度大于N會(huì)混疊2.3離散傅里葉變換及性質(zhì)有限長(zhǎng)離散時(shí)間信號(hào)的頻域離散表示可對(duì)傅立葉變換取樣得到若對(duì)傅立葉變換頻域0～2π取樣，點(diǎn)數(shù)N>信號(hào)長(zhǎng)度L，信號(hào)才能恢復(fù)結(jié)論：2.3離散傅里葉變換及性質(zhì)DFT的定義在上從0開始等間隔的取N個(gè)點(diǎn)，相應(yīng)的（k=0,…,N-1),則上式變?yōu)椋憾x式其中為序列在離散頻率點(diǎn)上的頻譜值。2.3離散傅里葉變換及性質(zhì)DFT的意義有限長(zhǎng)序列的離散傅立葉變換（簡(jiǎn)稱DFT）的意義：1、為序列在離散頻率點(diǎn)上的頻譜值。2、相當(dāng)于頻譜在范圍內(nèi)實(shí)施了等間隔采樣，采樣間隔為離散傅立葉反變換(IDFT)2.3離散傅里葉變換及性質(zhì)據(jù)DFT和IDFT的定義知：∴有限長(zhǎng)序列的DFT是的周期序列，周期為N；IDFT所求得的也變成了一個(gè)周期為N的周期序列，即通過IDFT將原進(jìn)行了周期延拓。DFT與Z變換的關(guān)系與離散傅立葉變換（DFT）相比較有：

可見序列的N點(diǎn)DFT是x(n)的Z變換在單位圓上N點(diǎn)的等間隔采樣。顯然，對(duì)于同一序列當(dāng)頻率采樣點(diǎn)數(shù)不同時(shí)，其DFT的值也不同。2.3離散傅里葉變換及性質(zhì)高密度譜和高分辨率譜的區(qū)別

1）信號(hào)長(zhǎng)度L<N時(shí)，對(duì)x(n)補(bǔ)零構(gòu)成N點(diǎn)序列，補(bǔ)零的個(gè)數(shù)越多，頻譜的密度越高，與實(shí)際頻譜更接近，計(jì)算復(fù)雜度越高。

2）高分辨率譜：需要對(duì)x(n)取更長(zhǎng)長(zhǎng)度的真實(shí)值得到2.3離散傅里葉變換及性質(zhì)高密度譜和高分辨率譜的區(qū)別x(n)=cos(0.48*pi*n)+cos(0.52*pi*n)的DFT高密度譜2.3離散傅里葉變換及性質(zhì)高密度譜和高分辨率譜的區(qū)別x(n)=cos(0.48*pi*n)+cos(0.52*pi*n)的DFT高分辨率譜2.3離散傅里葉變換及性質(zhì)DFT變換長(zhǎng)度選擇的原則若已知信號(hào)的最高頻率，為防止混疊，選采樣頻率；根據(jù)頻率分辯率，確定所需DFT的長(zhǎng)度

(3)和N確定以后，即可確定相應(yīng)所需要的模擬信號(hào)的時(shí)間長(zhǎng)度，。2.3離散傅里葉變換及性質(zhì)DFT變換長(zhǎng)度選擇的原則在變換時(shí)盡量截取信號(hào)的完整周期，否則會(huì)引入新的頻率成分。并不是截取的信號(hào)越長(zhǎng)越好例如：對(duì)于單頻信號(hào)，不同的截取點(diǎn)頻譜不同2.3離散傅里葉變換及性質(zhì)DFT變換長(zhǎng)度選擇的原則信號(hào)最高頻率的估算選出波峰和波谷最小的一個(gè)。這里,t4可能就是由信號(hào)的最高頻率分量形成的。峰與谷之間的距離就是周期的一半2.3離散傅里葉變換及性質(zhì)DFT的矩陣形式DFT計(jì)算的特點(diǎn)：N點(diǎn)DFT的計(jì)算量次復(fù)數(shù)乘法DN具有對(duì)稱性次加法2.3離散傅里葉變換及性質(zhì)DFT的性質(zhì)1、線性（內(nèi)積的定義可知）2、循環(huán)移位性若x(n)是長(zhǎng)為n的有限長(zhǎng)序列，定義：為的循環(huán)移位序列。2.3離散傅里葉變換及性質(zhì)DFT的性質(zhì)3、頻域移位定理與序列傅立葉變換，Z變換性質(zhì)不同：移位特性包括了時(shí)域移位和頻域移位，而且移位是循環(huán)移位（或稱圓周移位）并非平移2.3離散傅里葉變換及性質(zhì)DFT的性質(zhì)4、共軛復(fù)序列的DFT特別地：若為實(shí)序列，則其DFT滿足共軛對(duì)稱特性若為純虛序列，則其DFT滿足共軛反對(duì)稱性2.3離散傅里葉變換及性質(zhì)DFT的性質(zhì)8、Parseval定理2.4圓周卷積與線性卷積頻域圓周卷積定理【附：循環(huán)卷積的計(jì)算】反褶循環(huán)移位乘積累加時(shí)域圓周卷積定理2.4圓周卷積與線性卷積例：已知作N=8的循環(huán)卷積解：①變量代換：將變成②將周期延拓為③反褶后得到④從n=0開始，對(duì)每一個(gè)n=0,1…,N-1,分別對(duì)進(jìn)行循環(huán)移位并取主值形成⑤分別將與對(duì)應(yīng)的m點(diǎn)從m=0,1…,N-1逐點(diǎn)相乘，并將乘積累加就得到了各個(gè)點(diǎn)n=0,1,…,N-1的y(n)。其計(jì)算過程見下圖：2.4圓周卷積與線性卷積2.4圓周卷積與線性卷積圓周卷積的矩陣表示形式圓周卷積結(jié)果的長(zhǎng)度不變2.4圓周卷積與線性卷積兩個(gè)有限長(zhǎng)序列的線性卷積

如果循環(huán)卷積的周期<N+M-1，那么周期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)混淆現(xiàn)象

線性卷積和循環(huán)卷積線性卷積2.4圓周卷積與線性卷積有限長(zhǎng)序列與無限長(zhǎng)序列的線性卷積

1、重疊相加（overlappedaddmethod)[][]為無限長(zhǎng)序列點(diǎn)有限長(zhǎng)序列，為設(shè)nxMlh[][][][][]10*=-=-=?nxnhlnxlhnyMl1）將無限長(zhǎng)序列分成N1長(zhǎng)度的段2.4圓周卷積與線性卷積有限長(zhǎng)序列與無限長(zhǎng)序列的線性卷積

1、重疊相加（overlappedaddmethod)[][]為無限長(zhǎng)序列點(diǎn)有限長(zhǎng)序列，為設(shè)nxMlh[][][][][]10*=-=-=?nxnhlnxlhnyMl1）將無限長(zhǎng)序列分成N1長(zhǎng)度的段2）兩個(gè)序列補(bǔ)零，成為長(zhǎng)度N1＋M－1長(zhǎng)度的序列3)利用N1＋M－1DFT計(jì)算每一段的圓周卷積，結(jié)果長(zhǎng)度為N1＋M－14）將結(jié)果相加，每段之間M-1個(gè)重疊部分相加2.4圓周卷積與線性卷積有限長(zhǎng)序列與無限長(zhǎng)序列的線性卷積

通常情況下，當(dāng)N>M時(shí)，長(zhǎng)度為M的序列h[n]與長(zhǎng)度為N的序列x[n]的N點(diǎn)循環(huán)卷積的前M-1個(gè)樣本與h[n]和x[n]的線性卷積不同，而后N-M+1個(gè)樣本則相同2、重疊保留（overlappedsavemethod)保留與線性卷積相同的部分2.4圓周卷積與線性卷積有限長(zhǎng)序列與無限長(zhǎng)序列的線性卷積

2、重疊保留（overlappedsavemethod)1）將無限長(zhǎng)序列分成N1長(zhǎng)度的段，其中有M－1個(gè)取樣與相鄰序列重疊2）h序列補(bǔ)零稱為長(zhǎng)度N1的序列3)利用N1點(diǎn)DFT計(jì)算每一段的圓周卷積4）將每段計(jì)算結(jié)果的前M－1個(gè)點(diǎn)丟棄DFT的運(yùn)算量減少DFT運(yùn)算量的方法①將長(zhǎng)度N變短。例如若將長(zhǎng)度變?yōu)镹/2，則運(yùn)算量變成：②利用的性質(zhì)

周期性：

共軛對(duì)稱性：可約性：2.5快速傅里葉變換FFT盡量減少重復(fù)性運(yùn)算FFT算法分類FFT算法首先由Cooly-Tuky提出了基－2FFT算法，它對(duì)DFT的發(fā)展起到了極大推進(jìn)作用。隨后又出現(xiàn)了混合基算法?；?2FFT算法（DIT-FFT）指要求長(zhǎng)度N滿足（M為整數(shù)），若不滿足可將序列補(bǔ)零延長(zhǎng)，使其滿足長(zhǎng)度要求。時(shí)域與頻域抽取2.5快速傅里葉變換FFT時(shí)域抽取基－2FFT算法（DIT-FFT）時(shí)域抽取算法是按的奇偶把時(shí)間序列分解為兩個(gè)長(zhǎng)為N/2點(diǎn)的序列，即：上式中分別為的N/2點(diǎn)DFT，即：DFT可以分解成偶數(shù)序列的N/2的DFT和奇數(shù)序列的N/2點(diǎn)的DFT時(shí)域抽取基－2FFT算法（DIT-FFT）對(duì)于后N/2點(diǎn)的DFT顯然，可采用蝶式運(yùn)算圖來表示上述前N/2和后N/2兩式，如下圖所示：時(shí)域抽取基－2FFT算法（DIT-FFT）時(shí)域抽取基－2FFT算法（DIT-FFT）例如N=8時(shí)的DFT,可以分解為兩個(gè)N/2=4點(diǎn)DFT,如下圖：時(shí)域抽取基－2FFT算法（DIT-FFT）同理：,∴N/2仍可能是偶數(shù),可以進(jìn)一步把每個(gè)N/2點(diǎn)的序列再按其奇偶部分分解為兩個(gè)N/4的子序列。時(shí)域抽取基－2FFT算法（DIT-FFT）其中對(duì)也可進(jìn)行同樣的分解：時(shí)域抽取基－2FFT算法（DIT-FFT）依次類推：經(jīng)過M-1次分解后，可將N點(diǎn)DFT分解成N/2個(gè)兩點(diǎn)DFT。這樣又一次的分解得到4個(gè)N/4點(diǎn)DFT，見下圖。典型例題例：試畫出N=8時(shí)的完整的基-2DIT-FFT運(yùn)算流圖。運(yùn)算量時(shí)域抽取基－2FFT算法（DIT-FFT）由有關(guān)算法的討論知：當(dāng)時(shí)，總共應(yīng)有M級(jí)分解，每級(jí)有N/2個(gè)“蝶式運(yùn)算”。每個(gè)“蝶式運(yùn)算”需一次復(fù)數(shù)乘、兩次復(fù)數(shù)加運(yùn)算，這樣M級(jí)總共需要的運(yùn)算量為：如：若N＝1024，直接計(jì)算DFT與采用FFT運(yùn)算量之比約為205，“快速”得以充分體現(xiàn)。若N足夠大，通過直接計(jì)算DFT與采用FFT計(jì)算其運(yùn)算量之比為：FFT算法的特點(diǎn)時(shí)域抽取基－2FFT算法（DIT-FFT）①倒碼觀察完整的FFT流圖能發(fā)現(xiàn)有兩個(gè)特點(diǎn)：倒碼和原位運(yùn)算倒碼即碼位倒置：是指將原二進(jìn)制數(shù)的碼位倒過來按從低位到高位排列。順序與倒碼順序?qū)φ毡眄樞蚨M(jìn)制數(shù)倒碼倒碼順序

01234567

000001010011100101110111

000100010110001101011000

04261537如：N=8時(shí)，序號(hào)“4”

用三位二進(jìn)制表示正常碼為“100”，而其倒碼為“001”

，變成了序號(hào)

“1”

。時(shí)域抽取基－2FFT算法（DIT-FFT）②原位運(yùn)算由完整的FFT流圖可見：從左到右計(jì)算下一級(jí)蝶式運(yùn)算時(shí)，僅需要用到本級(jí)的數(shù)據(jù)而不需要前一級(jí)的數(shù)據(jù)。例如在實(shí)施第二級(jí)蝶式運(yùn)算時(shí)，僅需要第一級(jí)蝶式運(yùn)算的結(jié)果，而不需要用到原來的輸入數(shù)據(jù)。據(jù)此就可在數(shù)據(jù)輸入到存儲(chǔ)器以后，每一級(jí)運(yùn)算的結(jié)果存儲(chǔ)在同一組存儲(chǔ)單元中。直到最后輸出，中間無需其他存儲(chǔ)器。利用同一存儲(chǔ)單元存放蝶式運(yùn)算輸入和輸出數(shù)據(jù)的方法稱為原位運(yùn)算。原位運(yùn)算可節(jié)省存儲(chǔ)單元，降低FFT硬件實(shí)現(xiàn)的設(shè)備成本，從而使得FFT算法簡(jiǎn)單、快速、高效。DIT-FFT算法其他形式的流圖由信號(hào)流圖理論知道：只要保證各節(jié)點(diǎn)所連接的支路及其傳輸系數(shù)不變，無論各節(jié)點(diǎn)相對(duì)位置如何排列，所得到的流圖等效，DFT的結(jié)果相同。時(shí)域抽取基－2FFT算法（DIT-FFT）N=8時(shí)輸入是正序、輸出是倒碼的DIT-FFT運(yùn)算流圖例如將N=8時(shí)基－2DIT-FFT信號(hào)流圖中與、水平相連的所有節(jié)點(diǎn)分別同與、水平相連的所有節(jié)點(diǎn)對(duì)調(diào)，保持其余節(jié)點(diǎn)位置不變，得到新形式的信號(hào)流圖。頻域抽取基－2FFT算法（DIF-FFT）算法的推導(dǎo)頻域抽取算法是把時(shí)間序列前后對(duì)半分解為兩個(gè)長(zhǎng)為N/2點(diǎn)的序列，則：頻域抽取基－2FFT算法（DIF-FFT）當(dāng)k取偶數(shù)時(shí)（k=2r，r=0,1,...,N/2－1）∴的N點(diǎn)DFT按k的奇偶分組可分為兩個(gè)N/2的DFT當(dāng)k取奇數(shù)時(shí)（k=2r＋1，r=0,1,...,N/2－1）頻域抽取基－2FFT算法（DIF-FFT）這一結(jié)論表明：求的N點(diǎn)DFT再次分解成

求兩個(gè)N/2

點(diǎn)DFT

DIF-FFT的蝶式運(yùn)算流圖DIF-FFT的一次分解運(yùn)算流圖頻域抽取基－2FFT算法（DIF-FFT）先蝶式運(yùn)算，后DFT。例如：N=8時(shí)頻域抽取基－2FFT算法（DIF-FFT）DIF-FFT的二次分解運(yùn)算流圖通常N/2仍然為2的整數(shù)冪，繼續(xù)將N/2點(diǎn)DFT分成偶數(shù)組和奇數(shù)組，這樣每個(gè)N/2點(diǎn)DFT又可分解成兩個(gè)N/4點(diǎn)DFT，其輸入序列分別是和按上下對(duì)半分開后通過蝶式運(yùn)算構(gòu)成的4個(gè)子序列，如下圖所示：頻域抽取基－2FFT算法（DIF-FFT）按照以上方法繼續(xù)分解下去，經(jīng)過M-1

次分解，最后分解為N/2

個(gè)兩點(diǎn)DFT，這N/2個(gè)2點(diǎn)DFT的輸出就是N點(diǎn)DFT的結(jié)果X(k)

，如下圖所示：有關(guān)說明頻域抽取基－2FFT算法（DIF-FFT）以上給出了N=8時(shí)完整的DIF-FFT

的運(yùn)算流圖。由于這種方法是按在頻域進(jìn)行奇偶分解，因此稱之為頻域抽取基－2ＦＦＴ運(yùn)算。比較ＤＩＦ－ＦＦＴ與ＤＩＴ－ＦＦＴ相同點(diǎn)：運(yùn)算次數(shù)與存儲(chǔ)量相同不同點(diǎn)：①

ＤＩＦ－ＦＦＴ輸入序列為自然序列而輸出為碼位倒置序列

②

蝶式運(yùn)算過程不同ＤＩＴ－ＦＦＴ是序列先乘旋轉(zhuǎn)因子后相加減ＤＩＦ－ＦＦＴ是序列先相加減后乘旋轉(zhuǎn)因子逆DFT的快速算法（IFFT）IFFT算法的推導(dǎo)比較兩式可知：只要將FFT中的旋轉(zhuǎn)因子改為，再乘以

1/N

即可得到IDFT的快速算法IFFT。IFFT基本思想，∴還可將常數(shù)1/N分配到每級(jí)運(yùn)算中，也就是每級(jí)蝶形運(yùn)算均乘以?。這樣就實(shí)現(xiàn)了FFT與IFFT運(yùn)算的統(tǒng)一。1、純軟件實(shí)現(xiàn)2、硬件實(shí)現(xiàn)3、DSP（軟硬件結(jié)合）逆DFT的快速算法（IFFT）FFT（IFFT）算法的實(shí)現(xiàn)1、信號(hào)消噪

假設(shè)信號(hào)在傳輸過程中，受到噪聲的干擾，則在接收端得到的信號(hào)由于受到噪聲的干擾，信號(hào)將難以辨識(shí)。用FFT方法消噪：對(duì)含噪信號(hào)的頻譜進(jìn)行處理，將噪聲所在頻段的X(k)值全部置零后，再對(duì)處理后的X(k)進(jìn)行（IFFT）可得原信號(hào)的近似結(jié)果。這種方法要求噪聲與信號(hào)的頻譜不在同一頻段FFT的應(yīng)用

例語(yǔ)音消噪。下圖是一個(gè)實(shí)際例子，語(yǔ)音信號(hào)受到了強(qiáng)烈的嘯叫噪聲干擾，無法聽清語(yǔ)音意思，信號(hào)淹沒在噪聲中（信噪比只有-10dB）。試用FFT方法消噪。1、先作FFT分析，得到其功率譜2、可見在頻率2.5kHz附近有一極強(qiáng)分量，嘯叫噪聲干擾3、中頻率在30～800Hz范圍是語(yǔ)音信號(hào)。對(duì)頻譜進(jìn)行修正，去除噪聲頻段，即將大于2.5kHz部分的X(k)值全部置為零，4、(c)是去噪后的功率譜。再由（IFFT）重構(gòu)信號(hào)得到原語(yǔ)音信號(hào)如圖

(d)。這時(shí)信噪比為14dB，提高了24dB。這是早期的數(shù)字式錄音音樂中所采用的消噪方法。FFT的應(yīng)用語(yǔ)音信號(hào)消噪過程信號(hào)淹沒在嘯叫噪聲中；(b)信號(hào)與噪聲的功率譜；(c)去噪后的功率譜；(d)重構(gòu)原語(yǔ)音信號(hào)FFT的應(yīng)用2、FFT在雙音多頻（DTMF）信號(hào)中的應(yīng)用

雙音多頻信號(hào)DTMF是按鍵式電話信令中的一般名稱DTMF信令系統(tǒng)中共有八個(gè)頻率，分為四個(gè)高頻音和四個(gè)低頻音一個(gè)高頻音和一個(gè)低頻音的組合來代表某一特定的數(shù)字FFT的應(yīng)用2、FFT在雙音多頻（DTMF）信號(hào)中的應(yīng)用

941Hz和1209Hz“*”還未被使用，用于將來附加按鈕FFT的應(yīng)用2、FFT在雙音多頻（DTMF）信號(hào)中的應(yīng)用

通帶截止頻率略高于1000Hz，高通濾波器通帶截止頻率略低于1200HzFFT的應(yīng)用2、FFT在雙音多頻（DTMF）信號(hào)中的應(yīng)用

FFT解決方案通過FFT計(jì)算DTMF信號(hào)的頻譜檢測(cè)八個(gè)對(duì)應(yīng)頻率點(diǎn)的幅值來確定輸入的信號(hào)3、Chirp-z變換問題的提出：①不需要計(jì)算整個(gè)單位圓上z變換的取樣，如對(duì)于窄帶信號(hào),希望頻譜的采樣集中在這一頻帶內(nèi)，較高的分辨率

②對(duì)其它圍線上的z變換取樣感興趣，如果采樣沿一條接近這些極點(diǎn)的弧線進(jìn)行，則在極點(diǎn)所在頻率上的將出現(xiàn)明顯的尖峰，由此可較準(zhǔn)確地測(cè)定極點(diǎn)頻率。

③要求能有效地計(jì)算當(dāng)N是素?cái)?shù)時(shí)序列的DFT。

FFT的應(yīng)用已知x(n)，0≤n≤N-1令zk=AW-k

，k=0，…，M-1，M：采樣點(diǎn)數(shù)，A、W：任意復(fù)數(shù)其中：A0表示起始取樣點(diǎn)的半徑長(zhǎng)度，通常A0≤1θ0表示起始取樣點(diǎn)z0的相角;φ0表兩相鄰點(diǎn)之間的等分角;W0螺旋線的伸展率，W0<1則線外伸，W0>1則線內(nèi)縮（反時(shí)針），W0=1則表示半徑為A0的一段圓弧，若A0=1，這段圓弧則是單位圓的一部分。FFT的應(yīng)用3、Chirp-z變換螺旋線采樣圖螺旋線采樣

FFT的應(yīng)用3、Chirp-z變換3、Chirp-z變換FFT的應(yīng)用Chirp-z變換z變換計(jì)算出全部M點(diǎn)采樣值需要NM次復(fù)乘和（N-1）M次復(fù)加采用FFT進(jìn)行，這樣可大大提高計(jì)算速度。3、Chirp-z變換FFT的應(yīng)用1、對(duì)信號(hào)