數(shù)字信號(hào)處理dsp教程-ch2課件

1、第 2 章 離散變換及其快速算法本章內(nèi)容：離散傅里葉級(jí)數(shù)（DFS）離散傅立葉變換（DFT）基2快速傅立葉變換（FFT）利用DFT做連續(xù)信號(hào)的頻譜分析 FFT在分段卷積等中的應(yīng)用2.1 DFT對(duì)于有限長(zhǎng)序列，可以用離散傅里葉變換（Discrete Fourier Transform，DFT）來(lái)分析，DFT能反映信號(hào)的頻域特征且更便于用計(jì)算機(jī)處理。傅里葉變換的幾種可能形式四種傅里葉變換形式的歸納時(shí)間函數(shù) 頻率函數(shù) 連續(xù)和非周期 非周期和連續(xù) 連續(xù)和周期 非周期和離散 離散和非周期 周期和連續(xù) 離散和周期 周期和離散 一個(gè)域的離散對(duì)應(yīng)另一個(gè)域的周期延拓， 一個(gè)域的連續(xù)必定對(duì)應(yīng)另一個(gè)域的非周期。2.1

2、.1 周期序列的離散傅里葉級(jí)數(shù)(DFS)設(shè) 是一個(gè)周期為N的周期序列， 即 k次諧波周期序列 基頻（2/N）離散傅里葉級(jí)數(shù)取k=0 到N-1的N個(gè)獨(dú)立諧波分量諧波系數(shù)是以N為周期的周期序列即呈周期性，其周期為N， 推導(dǎo) 離散傅里葉級(jí)數(shù)（DFS）只要知道周期序列一個(gè)周期的內(nèi)容，其他的內(nèi)容也都知道了。所以，這種無(wú)限長(zhǎng)序列實(shí)際上只有一個(gè)周期中的N個(gè)序列值有信息。 因而周期序列和有限長(zhǎng)序列有著本質(zhì)的聯(lián)系。 例求所示周期序列的離散傅里葉級(jí)數(shù)表示式。解：離散傅里葉級(jí)數(shù)（DFS）的性質(zhì)1 線性2 序列的移位證：由于都是以N為周期的，即因此 離散傅里葉級(jí)數(shù)（DFS）的性質(zhì)3 共軛對(duì)稱性復(fù)序列 共軛偶對(duì)稱分量

3、共軛奇對(duì)稱分量 離散傅里葉級(jí)數(shù)（DFS）的性質(zhì)4 周期卷積證 例N=7，計(jì)算解：兩個(gè)周期序列的周期N=7，周期卷積過(guò)程用圖示。周期卷積過(guò)程用圖解表示m012345622220000022100000122020000122020000124220000181220000100122000100012200600012202周期卷積過(guò)程列表表示周期卷積結(jié)果2.1.2 有限長(zhǎng)序列離散傅里葉變換(DFT)周期序列實(shí)際上只有有限個(gè)序列值有意義設(shè)x(n)為有限長(zhǎng)序列，長(zhǎng)度為N，x(n)在n=0到N-1點(diǎn)上有值。把 的第一個(gè)周期n=0 到n=N-1 定義為“主值區(qū)間”， 故x(n)是 的“主值序列”，即主

4、值區(qū)間上的序列。主值序列把 的第一個(gè)周期n=0 到n=N-1 定義為“主值區(qū)間”， 故x(n)是 的“主值序列”，即主值區(qū)間上的序列。0n1N-1，n2為整數(shù) 例例離散傅里葉變換(DFT)0kN-1 0nN-1 離散傅里葉變換隱含著周期性x(n)和X(k)是一個(gè)有限長(zhǎng)序列的離散傅里葉變換對(duì)。已知其中的一個(gè)序列，就能惟一地確定另一個(gè)序列。這是因?yàn)閤(n)與X(k)都是點(diǎn)數(shù)為N的序列，都有N個(gè)獨(dú)立值（可以是復(fù)數(shù)），所以信息等量。 此外，值得強(qiáng)調(diào)得是，在使用離散傅里葉變換時(shí)，必須注意所處理的有限長(zhǎng)序列都是作為周期序列的一個(gè)周期來(lái)表示的。 離散傅里葉變換隱含著周期性。簡(jiǎn)記為簡(jiǎn)記為矩陣方程來(lái)表示 例x(

5、n)=(n)，求它的N點(diǎn)DFT不論對(duì)它進(jìn)行多少點(diǎn)的DFT，結(jié)果都是一個(gè)離散矩形序列解例矩形序列x(n)=RN(n)，求它的N點(diǎn)DFT結(jié)果只有一個(gè)非零值N解例求復(fù)數(shù)序列x(n)=1+j， 1-j，j，1的DFT。求得 解 例x(n)=cos(n/6) ，N=12， 求它的N點(diǎn)DFT解離散傅里葉變換的性質(zhì)（1） 線性（2） 循環(huán)移位，圓周移位一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列x(n)的圓周移位定義為f(n)=x(n+m)NRN(n) 圓周移位過(guò)程示意圖x(n)向左循環(huán)移位（圓周移位）時(shí)，此圓是順時(shí)針旋轉(zhuǎn); x(n)向右循環(huán)移位（圓周移位）時(shí)，此圓是逆時(shí)針旋轉(zhuǎn)。如果圍繞圓周觀察幾圈， 那么看到的就是周期序列循

6、環(huán)移位時(shí)域循環(huán)移位定理表明，有限長(zhǎng)序列的圓周移位在離散頻域中引入一個(gè)和頻率成正比的線性相移 ，而對(duì)頻譜的幅度沒(méi)有影響。 頻域循環(huán)移位定理調(diào)制特性：說(shuō)明時(shí)域序列的調(diào)制等效于頻域的圓周移位（3） 循環(huán)卷積 (圓周卷積)它和周期卷積過(guò)程是一樣的，只不過(guò)這里要取主值序列。時(shí)域循環(huán)卷積定理推導(dǎo) 頻域循環(huán)卷積定理例計(jì)算解（1） 循環(huán)卷積圖示法 N=7N=7解（2） m0123456f(n)x(m)2222000y(m)0022100y(0-m)NRN(n)00012202y(1-m)NRN(n)00001220y(2-m)NRN(n)20000124y(3-m)NRN(n)22000018y(4-m)NR

7、N(n)122000010y(5-m)NRN(n)012200010y(6-m)NRN(n)00122006y(7-m)NRN(n)00012202循環(huán)卷積列表法 例：循環(huán)卷積（圓周卷積）過(guò)程示意圖求這兩個(gè)矩形序列的循環(huán)卷積。 例 設(shè)兩個(gè)有限長(zhǎng)序列相等，各為N點(diǎn)，同為矩形序列解：矩形序列的DFT等于N點(diǎn)的循環(huán)卷積5點(diǎn)的循環(huán)卷積9點(diǎn)的循環(huán)卷積兩個(gè)序列各增加5個(gè)零點(diǎn)，為10點(diǎn)的序列進(jìn)行循環(huán)卷積9點(diǎn)的循環(huán)卷積與線性卷積比較9點(diǎn)的循環(huán)卷積=線性卷積一定條件下，循環(huán)卷積可以等于線性卷積研究循環(huán)卷積與線性卷積的關(guān)系 設(shè)x1(n)是N1點(diǎn)的有限長(zhǎng)序列（0nN1-1）， x2(n)是N2點(diǎn)的有限長(zhǎng)序列（0nN

8、2-1）。 線性卷積y (n)是N1+N2-1 點(diǎn)有限長(zhǎng)序列周期卷積循環(huán)卷積兩序列補(bǔ)充零值至L點(diǎn) 循環(huán)卷積等于線性卷積而不產(chǎn)生混疊的必要條件循環(huán)卷積等于線性卷積而不產(chǎn)生混疊的必要條件y (n)是N1+N2-1 點(diǎn)有限長(zhǎng)序列例：線性卷積與圓周卷積線性卷積圓周卷積（4） 共軛對(duì)稱性x*(n)為x(n)的共軛復(fù)序列DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0kN-1 X(N)=X(0) X*(N)=X*(0) 證X(k)的隱含周期性，故有X(N)=X(0)共軛對(duì)稱性同樣的方法可以證明對(duì)稱性是指關(guān)于坐標(biāo)原點(diǎn)的縱坐標(biāo)的對(duì)稱性。DTFT一些對(duì)稱性質(zhì)，定義了共

9、軛對(duì)稱序列與共軛反對(duì)稱序列的概念。 DFT有類(lèi)似的對(duì)稱性，但在DFT中，涉及的序列x(n)及其離散傅里葉變換X(k)均為有限長(zhǎng)序列，且定義區(qū)間為 0 到N-1，DFT的對(duì)稱性是指關(guān)于N/2 點(diǎn)的對(duì)稱性。 x(n) 的實(shí)部與虛部的DFT共軛（偶）對(duì)稱分量共軛奇（反）對(duì)稱分量x(n) 的實(shí)部與虛部的DFTx(n) 的 共軛對(duì)稱和共軛反對(duì)稱的DFT共軛（偶）對(duì)稱分量共軛奇（反）對(duì)稱分量x(n) 的 共軛對(duì)稱和共軛反對(duì)稱的DFTx(n) 為實(shí)序列的偶對(duì)稱和奇對(duì)稱偶對(duì)稱分量奇對(duì)稱分量（5） 選頻性例（6） DFT與zT、DTFTx(n)是一個(gè)有限長(zhǎng)序列，長(zhǎng)度為NDFT與序列傅里葉變換、Z變換的關(guān)系X(k

10、) 是X(z)在Z平面單位圓上N點(diǎn)等間隔采樣值， X(k)也可以看作x(n)的X(ej)在區(qū)間0， 2上的N點(diǎn)等間隔采樣，其采樣間隔為N=2/N， 這就是DFT的物理意義。顯而易見(jiàn)，DFT的變換區(qū)間長(zhǎng)度N不同， 表示對(duì)X(ej)在區(qū)間0， 2上的采樣間隔和采樣點(diǎn)數(shù)不同， 所以DFT的變換結(jié)果也不同。例0n4 求其N(xiāo)=5 點(diǎn)離散傅里葉變換X(k)k=0, N, 2N, 其他 DFS k=0, 1, 2, 3, 4 k=0 k=0, 1, 2, 3, 4 DFTDFT舉例說(shuō)明x(n)的5點(diǎn)DFT（a） 有限長(zhǎng)序列x(n)（b） 由x(n)形成的周期N=5的周期序列（c） 對(duì)應(yīng)于 的傅里葉級(jí)數(shù)和x(

11、n)的|X(ej)|（d） x(n)的5點(diǎn)DFTDFT舉例說(shuō)明x(n)的10點(diǎn)DFT（a） 有限長(zhǎng)序列x(n) （b） 由x(n)（補(bǔ)零）形成的周期N=10的周期序列（c） x(n)的10點(diǎn)DFT（7） DFT形式下的Parseval定理證進(jìn)一步例2.2 利用DFT做連續(xù)信號(hào)的頻譜分析由于DFT具有選頻特性，所以常用它對(duì)連續(xù)信號(hào)進(jìn)行頻譜分析。這一分析過(guò)程是一次次的近似過(guò)程。其步驟：（1）采樣連續(xù)信號(hào)用離散采樣信號(hào)的DTFT來(lái)近似連續(xù)信號(hào)的傅里葉變換 （2）將x(n)截短 用有限長(zhǎng)度序列的DTFT來(lái)近似無(wú)限長(zhǎng)度序列的DTFT（3）對(duì)截短的信號(hào)做DFT對(duì)有限長(zhǎng)度序列的DTFT采樣前置低通濾波器LP

12、F，是為了消除或減少時(shí)域連續(xù)信號(hào)轉(zhuǎn)換成序列時(shí)可能出現(xiàn)的頻譜混疊的影響。 在實(shí)際工作中，時(shí)域離散信號(hào)x(n)的時(shí)寬是很長(zhǎng)的， 甚至是無(wú)限長(zhǎng)的（例如語(yǔ)音或音樂(lè)信號(hào)）。由于DFT的需要(實(shí)際應(yīng)用FFT計(jì)算)，必須把x(n)限制在一定的時(shí)間區(qū)間之內(nèi)，即進(jìn)行數(shù)據(jù)截?cái)唷?數(shù)據(jù)的截?cái)嘞喈?dāng)于加窗處理。 因此， 在計(jì)算FFT之前，用一個(gè)時(shí)域有限的窗函數(shù)w(n)加到x(n)上是非常必要的。可能出現(xiàn)的問(wèn)題及其解決方法 （1）混疊采樣序列的頻譜是被采樣模擬信號(hào)頻譜的周期延拓，當(dāng)采樣頻率不滿足奈奎斯特采樣定理時(shí)，就會(huì)發(fā)生頻譜的混疊，不能真實(shí)地反映原信號(hào)的頻譜。解決混疊問(wèn)題的惟一方法是保證采樣頻率足夠高，以防止頻譜混疊，

13、這意味著通常需要知道原信號(hào)的頻譜范圍，以確定采樣頻率。但很多情況下可能無(wú)法預(yù)計(jì)信號(hào)頻率，為確保無(wú)混疊現(xiàn)象，可在采樣前利用一模擬低通濾波器（抗混疊濾波器） 。（2）泄漏一個(gè)時(shí)間有限的信號(hào)其頻帶寬度為無(wú)限，一個(gè)時(shí)間無(wú)限的信號(hào)其頻帶寬度則為有限。在實(shí)際DFT運(yùn)算中，時(shí)間長(zhǎng)度總是取有限值，在將信號(hào)截短的過(guò)程中，出現(xiàn)了分散的擴(kuò)展譜線的現(xiàn)象，稱為頻譜泄漏或功率泄漏。由于泄漏使信號(hào)的頻譜展寬，泄漏也會(huì)引起混疊。 （3）柵欄效應(yīng)DFT是對(duì)單位圓上z變換的均勻采樣，頻譜是一組離散譜線。有限長(zhǎng)序列的頻譜是連續(xù)狀的。用DFT來(lái)觀察頻譜就如同通過(guò)一個(gè)柵欄來(lái)觀看景象一樣，只能在離散點(diǎn)上看到真實(shí)的頻譜，這樣一些頻譜的峰點(diǎn)

14、或谷點(diǎn)就有可能被“尖樁的柵欄”擋住，也就是正好落在兩個(gè)離散采樣點(diǎn)之間，不能被觀察到。減小柵欄效應(yīng)的一個(gè)方法是在原序列的末端填補(bǔ)一些零值，增加了DFT的點(diǎn)數(shù)，從而離散譜線（柵）目加大，相當(dāng)于搬動(dòng)了“尖樁柵欄”的位置，從而使得頻譜的峰點(diǎn)或谷點(diǎn)暴露出來(lái)。柵欄效應(yīng)舉例（4）DFT的分辨率DFT的頻率分辨率通常規(guī)定為fs/N，這里的N是指信號(hào)x (n)的有效長(zhǎng)度，而不是補(bǔ)零的長(zhǎng)度。填補(bǔ)零值可以改變對(duì)DTFT的采樣密度，不能提高DFT的頻率分辨率。不同長(zhǎng)度的x(n)，其DTFT的結(jié)果是不同的；而相同長(zhǎng)度的x(n)只是反映了對(duì)相同的DTFT采用了不同的采樣密度。要提高DFT分辨率只有增加信號(hào)x/(n)的截取

15、長(zhǎng)度N。 例 設(shè)模擬信號(hào)xa(t)的最高頻率fmax=5Hz，試求最低采樣頻率fs，在這一采樣頻率下采得256點(diǎn)數(shù)據(jù)，對(duì)其做DFT，給出所能得到的最大頻率分辨率f 。解：由采樣定理得 fs=2fmax=10Hzf=10/256= 0.039Hz用FFT進(jìn)行頻譜分析時(shí)參數(shù)選擇的一般原則：（一）若已知信號(hào)的最高頻率fmax，選定采樣頻率（二）據(jù)實(shí)際需要，選定頻率分辨率f，再確定所需DFT長(zhǎng)度f(wàn)越小越好，但f越小，N越大，使計(jì)算量、存儲(chǔ)量也隨之增大。（三）根據(jù)fs和N確定模擬信號(hào)的時(shí)間長(zhǎng)度（）周期信號(hào)的譜分析圖 (c)和圖 (d)分別是N=16時(shí)的截取信號(hào)和DFT結(jié)果，由于截取了兩個(gè)整周期，得到單一

16、譜線的頻譜。上述頻譜的誤差主要是由于時(shí)域中對(duì)信號(hào)的非整周期截?cái)喈a(chǎn)生的頻譜泄漏。圖（a）和圖（b）分別是N=20時(shí)的截取信號(hào)和 DFT結(jié)果，由于截取了兩個(gè)半周期，頻譜出現(xiàn)泄漏；2.3 FFT DFT的運(yùn)算量每計(jì)算一個(gè)X(k)值，需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。X(k)一共有N個(gè)點(diǎn)（k從0取到N-1），所以完成整個(gè)DFT運(yùn)算總共需要N2次復(fù)數(shù)乘法及N(N-1)次復(fù)數(shù)加法。一次復(fù)數(shù)乘法需用四次實(shí)數(shù)乘法和二次實(shí)數(shù)加法；一次復(fù)數(shù)加法需二次實(shí)數(shù)加法。 每運(yùn)算一個(gè)X(k)需4N次實(shí)數(shù)乘法和2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法。 整個(gè)DFT運(yùn)算總共需要4N2次實(shí)數(shù)乘法和2N(2N-1)次實(shí)數(shù)加法。

17、 IDFT與DFT的差別只在于WN的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)1/N，所以IDFT與DFT具有相同的運(yùn)算工作量。 FFT的運(yùn)算量復(fù)數(shù)乘法復(fù)數(shù)加法例 對(duì)一幅NN點(diǎn)的二維圖像進(jìn)行DFT變換，如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問(wèn)需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？解 直接計(jì)算DFT所需復(fù)乘次數(shù)為（N2)21012次，因此用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，則需要近3000小時(shí)。 這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來(lái)說(shuō)，要么提高計(jì)算速度，而這樣，對(duì)計(jì)算速度的要求太高了。另外，只能通過(guò)改進(jìn)對(duì)DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。2.3.1 按時(shí)間抽?。―IT）的基 -2 FFT算法（1）

18、WNnk的對(duì)稱性Wnk的以下固有特性（2） WNnk的周期性（3） WNnk的可約性按時(shí)間抽取 (DIT）法序列x(n)長(zhǎng)度為N，且滿足N=2M，M為正整數(shù)。按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列：蝶形運(yùn)算結(jié)構(gòu) 利用G（k）、H（k）的周期特性，有 一個(gè)8點(diǎn)DFT由兩個(gè)4點(diǎn)DFT組成 由四個(gè)2點(diǎn)DFT組成8點(diǎn)DFT 按時(shí)間抽取的8點(diǎn)FFT 基2-DIT-FFT N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8)N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N=8)一個(gè)N=8點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較N=2M，共有M級(jí)蝶形， 每級(jí)都由N/2個(gè)蝶形運(yùn)算組成

19、，每個(gè)蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級(jí)運(yùn)算都需N/2次復(fù)乘和N次復(fù)加，這樣M級(jí)運(yùn)算總共需要 復(fù)乘復(fù)加直接計(jì)算DFT與FFT算法的計(jì)算量之比N=2048時(shí)，這一比值為372.4，即直接計(jì)算DFT的運(yùn)算量是FFT運(yùn)算量的372.4倍例 用FFT算法處理一幅NN點(diǎn)的二維圖像，如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問(wèn)需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？解 當(dāng)N=1024點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為107次，僅為直接計(jì)算DFT所需時(shí)間的10萬(wàn)分之一。 即原需要3000小時(shí)，現(xiàn)在只需要2 分鐘。FFT算法DFT按時(shí)間抽取的FFT算法的特點(diǎn)（1） 蝶形運(yùn)算N=2M

20、，共有M級(jí)蝶形， 每級(jí)都由N/2個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級(jí)運(yùn)算都需N/2次復(fù)乘和N次復(fù)加。（2） 原位運(yùn)算（同址運(yùn)算）原位運(yùn)算， 即某一列的N個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間無(wú)需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。 每列的N/2 個(gè)蝶形運(yùn)算全部完成后， 再開(kāi)始下一列的蝶形運(yùn)算。 這樣存儲(chǔ)器數(shù)據(jù)只需N個(gè)存儲(chǔ)單元。下一級(jí)運(yùn)算仍采用這種原位方式，只是進(jìn)入蝶形結(jié)的組合關(guān)系有所不同。 這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元， 降低設(shè)備成本。N點(diǎn)DITFFT運(yùn)算流圖(

21、N=8) 輸入倒序輸出順序（3） 蝶形類(lèi)型隨迭代次數(shù)成倍增加（4） 序數(shù)重排（倒位序規(guī)律）X(k)按正常順序，即按X(0)，X(1)，X(7)的順序排列，x(n)不是按自然順序存儲(chǔ)的，而是按x(0)，x(4)， ， x(7)的順序存入存儲(chǔ)單元，稱之為倒位序。倒位序的形成如輸入序列的自然順序號(hào)為n2n1n0，則其倒位序就是n0n1n2N=8序數(shù)重排過(guò)程 十進(jìn)制二進(jìn)制第一次分偶、奇第二次分偶、奇第三次分偶、奇十進(jìn)制0000n0=0000n1=0000n2=000001001010100n2=110042010100n1=1010n2=001023011110110n2=111064100n0=10

22、01n1=0001n2=000115101101101n2=110136110011n1=1011n2=001157111111111n2=11117N=8時(shí)的自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù)自然順序（I） 二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù) 倒位序（J） 0123456700000101001110010111011100010001011000110101111104261537N=8 倒位序的變址處理DIT-FFT程序框圖倒序程序框圖DIT-FFT運(yùn)算程序框圖按時(shí)間抽取的FFT算法的其他形式流圖時(shí)間抽取、 輸入自然順序、 輸出倒位序的FFT流圖 基2-DIT-FFT 輸入順序輸出倒序基2-D

23、IT-FFT 輸入順序輸出順序2.3.2 按頻率抽?。―IF）的基 -2 FFT算法設(shè)序列點(diǎn)數(shù)為N=2M，M為正整數(shù)。把輸入序列按前一半、后一半分開(kāi)（不是按偶數(shù)、 奇數(shù)分開(kāi)）， 把N點(diǎn)DFT寫(xiě)成兩部分。輸出X(k)按k的奇偶分組。 按頻率抽?。―IF）法按頻率抽取的第一次分解按頻率抽取的第二次分解按頻率抽取的FFT（N=8）信號(hào)流圖按頻率抽取法的運(yùn)算特點(diǎn)（）蝶形運(yùn)算（）原位計(jì)算（）蝶形類(lèi)型隨迭代次數(shù)成減少盡管蝶形結(jié)構(gòu)不同于按時(shí)間抽取FFT，但總的計(jì)算量與按時(shí)間抽取算法相同。 （）序數(shù)重排 與時(shí)間抽取法不同，按頻率抽取法的輸入是自然順序，而輸出是以按位反轉(zhuǎn)的規(guī)律重排。將頻率抽取法的流圖反轉(zhuǎn)，并且

24、將輸入變輸出，輸出變輸入，正好得到時(shí)間抽取法的流圖。按頻率抽取法與按時(shí)間抽取法是兩種等價(jià)的FFT運(yùn)算 2.3.3 N為組（復(fù)）合數(shù)的FFT算法 問(wèn)題: N為任意因子的組合數(shù)，N=P1P2 Pm，(Pi是正整數(shù))，如何提高計(jì)算效率?最簡(jiǎn)單的情況: N=PQ為兩個(gè)數(shù)的乘積。(1)將DFT的時(shí)間順序n和頻率順序k分別表示成二維的形式 n=n1Q+n0 k=k1P+k0 式中n0, k1分別為0,1,，Q-1;n1, k0分別為0,1,，P-12.3.4 線性調(diào)頻Z變換（Chirp-Z變換）算法螺線采樣Chirp-Z變換的線性系統(tǒng)表示Chirp-Z變換的圓周卷積圖2.4 關(guān)于FFT應(yīng)用中的幾個(gè)問(wèn)題2.

25、4.1 用FFT計(jì)算 IDFTIFFT計(jì)算分三步： 將X(k)取共軛(虛部乘以-1) 對(duì)X*(k)直接作FFT 對(duì)FFT的結(jié)果取共軛并乘以1/N，得x(n)2.4.2 實(shí)數(shù)序列的FFT大多數(shù)場(chǎng)合下,信號(hào)是實(shí)數(shù)序列,任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù)：x(n)+j0求某實(shí)信號(hào)y(n)的復(fù)譜,可認(rèn)為是將實(shí)信號(hào)加上數(shù)值為零的虛部變成復(fù)信號(hào),再用FFT求其離散付里葉變換。不經(jīng)濟(jì),存儲(chǔ)器要增加一倍,且計(jì)算機(jī)運(yùn)行時(shí),即使虛部為零,也要涉及虛部的運(yùn)算,浪費(fèi)了運(yùn)算量。合理的解決方法是利用復(fù)數(shù)據(jù)FFT對(duì)實(shí)數(shù)據(jù)進(jìn)行有效計(jì)算(1)用 一個(gè)N點(diǎn)FFT同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的DFT設(shè)x(n)、y(n)是彼此獨(dú)立的兩個(gè)N點(diǎn)實(shí)

26、序列,且 X(k)=DFTx(n) ，Y(k)=DFTy(n) 則X(k)、Y(k)可通過(guò)一次FFT運(yùn)算同時(shí)獲得。算法：將x(n)、y(n)構(gòu)成一復(fù)序列 g(n)=x(n)+jy(n)通過(guò)FFT運(yùn)算可獲得g(n)的DFT值 G(k)=DFTx(n)+jDFTy(n)=X(k)+jY(k) Gr(k)+jGi(k) =Xr (k)-Yi (k)+j Xi (k)+Yr (k)g(n)的FFT運(yùn)算結(jié)果G(k), 由上式可得到X(k)、Y(k)。(2)用N點(diǎn)的FFT運(yùn)算獲得2N點(diǎn)實(shí)序列的DFT設(shè)x(n)是2N點(diǎn)實(shí)序列,并分為偶數(shù)組x1(n)和奇數(shù)組x2(n) x1(n)=x(2n) x2(n)=x(

27、2n+1) n=0,1,N-1將x1(n)及x2(n)組成一復(fù)序列： y(n)=x1(n)+jx2(n)通過(guò)N點(diǎn)FFT運(yùn)算可得到： Y(k)=X1(k)+jX2(k) N點(diǎn)根據(jù)共軛對(duì)稱性，得X1(k)和X2(k) 。再按下式復(fù)合成X(k)2.4.3 線性卷積的FFT算法線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一許多重要應(yīng)用都建立在這一理論基礎(chǔ)上,如卷積濾波等。用圓周卷積計(jì)算線性卷積的方法：長(zhǎng)為N2的序列x(n)延長(zhǎng)到L,補(bǔ)L-N2個(gè)零長(zhǎng)為N1的序列h(n)延長(zhǎng)到L,補(bǔ)L-N1個(gè)零如果LN1+N2-1,則圓周卷積與線性卷積相等,此時(shí),可用FFT計(jì)算線性卷積可用FFT計(jì)算線性卷積方法a. 計(jì)算X(k)

28、=FFTx(n)b. 求 H(k)=FFTh(n)c. 求 Y(k)=H(k)X(k) k=0L-1d. 求 y(n)=IFFTY(k) n=0L-1進(jìn)行二次FFT,一次IFFT就可完成線性卷積計(jì)算L32時(shí),上述計(jì)算線性卷積的方法比直接計(jì)算線卷積有明顯的優(yōu)越性圓周卷積方法為快速卷積法將 x(n) 分為許多段,每段的長(zhǎng)度與 h(n) 接近上述結(jié)論適用于 x(n)、h(n) 兩序列長(zhǎng)度比較接近或相等的情況如果x(n)、h(n) 長(zhǎng)度相差較多如, h(n) 為某濾波器的單位脈沖響應(yīng),長(zhǎng)度有限,用來(lái)處理一個(gè)很長(zhǎng)的輸入信號(hào) x(n),或者處理一個(gè)連續(xù)不斷的信號(hào)，按上述方法, h(n) 要補(bǔ)許多零再進(jìn)行計(jì)

29、算,計(jì)算量有很大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。為了保持快速卷積法的優(yōu)越性,可將 x(n) 分為許多段,每段的長(zhǎng)度與 h(n) 接近處理方法有兩種(1)重疊相加法由分段卷積的各段相加構(gòu)成總的卷積輸出N=N1+N2-1重疊相加法xi(n) 表示 x(n)的第i段只要將x(n)的每一段分別與h(n)卷積，再將這些卷積結(jié)果相加就可得到輸出序列。每一段的卷積都可用快速卷積來(lái)計(jì)算： 1)先對(duì)h(n)及xi(n)補(bǔ)零，補(bǔ)到具有N點(diǎn)長(zhǎng)度，N=N1+N2-1。 一般選 N=2M。 2)用基2 FFT計(jì)算 yi(n)=xi(n)*h(n) 3)重疊部分相加構(gòu)成最后的輸出序列。由于yi(n)的長(zhǎng)度為N，而xi(n)的長(zhǎng)

30、度為N2，因此相鄰兩段yi(n)序列必然有N-N2=N1-1點(diǎn)發(fā)生重疊重疊相加法L=N=N1+N2-1重疊相加法N=N1+N2-1計(jì)算步驟a. 準(zhǔn)備好濾波器N點(diǎn)參數(shù) H(k)=DFTh(n)b. N點(diǎn)FFT計(jì)算Xi(k)=DFTxi(n)c. Yi(k)=Xi(k)H(k)d. N點(diǎn)IFFT求yi(n)=IDFTYi(k)e. 將重疊部分相加N=N1+N2-1重疊相加法例 n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16h (n) 1 1 1x (n)15 14 13 12 1110 9 8 7 6 5 4 3 2 1x0(n)15 14 13 12 11x1(n)10 9 8 7 6x2(n) 5 4 3 2 1y0(n)15 29 42 39 3623 11y1(n) 10 19 27 24 2113 6y2(n) 5 9 12 9 6 3 1y(n)15 29 42 39 3633 30 27 24 2118 15 12 9 6 3 1 n N1-1 N2-1 N-1 N2+N-1 2N2+N-1N1=3 N2=5 N= N1+ N2-