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

第二章

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

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

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

L

F

Z

FT

DFT2.2離散系統(tǒng)和連續(xù)系統(tǒng)的等效性數(shù)字信號處理中各種變換的總結(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ù)，且序列的長度不受限制。但在實際利用計算機或數(shù)字設(shè)備進行頻譜分析時，只能處理有限長數(shù)據(jù)且必須將其離散化。有限長序列的傅立葉變換及頻率離散化問題——離散傅立葉變換（DFT）2.3離散傅里葉變換及性質(zhì)

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

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

1）信號長度L<N時，對x(n)補零構(gòu)成N點序列，補零的個數(shù)越多，頻譜的密度越高，與實際頻譜更接近，計算復(fù)雜度越高。

2）高分辨率譜：需要對x(n)取更長長度的真實值得到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變換長度選擇的原則若已知信號的最高頻率，為防止混疊，選采樣頻率；根據(jù)頻率分辯率，確定所需DFT的長度

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

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

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

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

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

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

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

周期性：

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

01234567

000001010011100101110111

000100010110001101011000

04261537如：N=8時，序號“4”

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

，變成了序號

“1”

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

求兩個N/2

點DFT

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

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

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

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

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

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

②

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

1/N

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

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

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

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

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

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

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

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

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

③要求能有效地計算當(dāng)N是素數(shù)時序列的DFT。

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

，k=0，…，M-1，M：采樣點數(shù)，A、W：任意復(fù)數(shù)其中：A0表示起始取樣點的半徑長度，通常A0≤1θ0表示起始取樣點z0的相角;φ0表兩相鄰點之間的等分角;W0螺旋線的伸展率，W0<1則線外伸，W0>1則線內(nèi)縮（反時針），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變換計算出全部M點采樣值需要NM次復(fù)乘和（N-1）M次復(fù)加采用FFT進行，這樣可大大提高計算速度。3、Chirp-z變換FFT的應(yīng)用1、對信號