數(shù)字信號(hào)處理第5章-信號(hào)處理的效率課件

1、第5章 信號(hào)處理的效率 數(shù)學(xué)公式的DFT還有經(jīng)過計(jì)算才能吃完現(xiàn)實(shí)。DFT的計(jì)算方法優(yōu)劣直接影響信號(hào)處理的速度。15.1 直接計(jì)算離散傅里葉變換簡(jiǎn)寫為當(dāng)n和k從0N-1變化時(shí)，旋轉(zhuǎn)因子WNkn 都在極坐標(biāo)上繞單位圓旋轉(zhuǎn)。X(k)和x(n)的計(jì)算形式相同。 25.1 直接計(jì)算5.1.1 直接計(jì)算頻譜（1）不考慮旋轉(zhuǎn)因子設(shè)旋轉(zhuǎn)因子事先算好，并存在計(jì)算機(jī)存儲(chǔ)器中。信號(hào)x(n)是N個(gè)復(fù)數(shù)的數(shù)組。計(jì)算全部頻譜需復(fù)數(shù)乘N2次。計(jì)算全部頻譜需復(fù)數(shù)加N(N-1)次。還有，每個(gè)k的X(k)都要用到全部x(n)；在算出全部X(k)前，x(n)要用2N個(gè)存儲(chǔ)單元；X(k)要用2N個(gè)存儲(chǔ)單元；整個(gè)計(jì)算過程至少需要4N個(gè)

2、存儲(chǔ)單元。35.1 直接計(jì)算（2）考慮旋轉(zhuǎn)因子計(jì)算離散傅里葉變換需要旋轉(zhuǎn)因子計(jì)算全部頻譜需計(jì)算NN個(gè)旋轉(zhuǎn)因子。旋轉(zhuǎn)因子要計(jì)算余弦和正弦。 從極坐標(biāo)看，旋轉(zhuǎn)因子是周期序列。利用周期性，計(jì)算離散傅里葉變換時(shí)，只需計(jì)算旋轉(zhuǎn)因子的N個(gè)獨(dú)立值。45.1 直接計(jì)算5.1.2 直接計(jì)算卷積設(shè)信號(hào)x(n)和系統(tǒng)h(n)的長(zhǎng)等于N，則系統(tǒng)的輸出它的長(zhǎng)度2N-1。直接計(jì)算卷積需乘N(2N-1)次，加(N-1)(2N-1)次。 55.1 直接計(jì)算利用卷積定理也能計(jì)算y(n)，條件是循環(huán)卷積的長(zhǎng)2N-1。當(dāng)循環(huán)卷積的長(zhǎng)=2N-1時(shí)，y(n)的頻譜若先算好H(k)，用卷積定理求解y(n)的運(yùn)算量是：65.1 直接計(jì)算復(fù)

3、數(shù)乘4N(2N-1)次，復(fù)數(shù)加2(2N-1)(2N-2)次。 相比之下，直接卷積優(yōu)于卷積定理。例5.1 設(shè)語音信號(hào)的采樣率為6kHz，記錄時(shí)間為1s，計(jì)算機(jī)復(fù)數(shù)乘1次需3s，復(fù)數(shù)加1次需1s。請(qǐng)問：該信號(hào)均分為6段，直接計(jì)算其頻譜要多少時(shí)間？若分為3段，要多少時(shí)間？75.1 直接計(jì)算解 總樣本為6000，信號(hào)分為6段，直接計(jì)算頻譜的時(shí)間為若把信號(hào)分為3段，則直接計(jì)算頻譜的時(shí)間為若信號(hào)樣本逐秒連續(xù)輸入，這兩種算法不能實(shí)時(shí)分析。85.2 間接計(jì)算直接按定義計(jì)算離散傅里葉變換，工作量與N2成正比，還與旋轉(zhuǎn)因子的獨(dú)立值有關(guān)。這是一種啟示：縮短DFT長(zhǎng)度和減少旋轉(zhuǎn)因子獨(dú)立值，可以降低DFT的計(jì)算量。如果

4、把N點(diǎn)DFT的長(zhǎng)度縮短一半，變成兩個(gè)N/2點(diǎn)DFT的組合，那么，DFT的復(fù)乘可從N2變成N2/2，復(fù)加可從N(N-1)N2變成約N2/2次。常用的分解有：1、按時(shí)序的奇偶數(shù)將序列分成兩段，2、按時(shí)序的前后將序列分為兩段。95.3 時(shí)域抽取的快速算法時(shí)域抽取的基本做法是，按時(shí)序的奇數(shù)和偶數(shù)分解序列成兩段長(zhǎng)度相同的子序列。這種算法要求序列的長(zhǎng)度N滿足5.3.1 時(shí)域抽取的原理基本時(shí)域抽取法分兩步：第一，將序列分成兩段；第二，整理頻譜表達(dá)式。（1）分解序列 按時(shí)序n的偶奇數(shù)將N點(diǎn)序列x(n)分解成兩個(gè)子序列，105.3 時(shí)域抽取的快速算法用x0(m)和x1(m)組成x(n)的N點(diǎn)DFT，115.3

5、時(shí)域抽取的快速算法（2）整理頻譜為使X0(k)和X1(k)滿足N/2點(diǎn)DFT的規(guī)定，同時(shí)又能反映X(k)的N個(gè)值，需對(duì)X(k)修改。當(dāng)k=0N/2-1時(shí)，當(dāng)k=N/2N-1時(shí)，r=0N/2-1。125.3 時(shí)域抽取的快速算法利用旋轉(zhuǎn)因子的周期和對(duì)稱性，并將符號(hào)r換為k，得到 修改后的DFT基本分解式該式的好處：k值減半，DFT的乘加法都減半，旋轉(zhuǎn)因子也減半。135.3 時(shí)域抽取的快速算法5.3.2 原理的推廣對(duì)N/2點(diǎn)X0(k)和X1(k)繼續(xù)分解。將X0(k)分解為兩個(gè)N/4點(diǎn)DFT，同理，X1(k)分解為兩個(gè)N/4點(diǎn)DFT，145.3 時(shí)域抽取的快速算法為了方便分解，將分解公式變?yōu)樾盘?hào)流圖

6、，稱蝶形圖。有更簡(jiǎn)潔的形式，一個(gè)碟形運(yùn)算需復(fù)乘1次復(fù)加2次。155.3 時(shí)域抽取的快速算法例5.2 有一個(gè)8點(diǎn)離散傅里葉變換，請(qǐng)用蝶形圖表示其時(shí)域抽取算法。解 遵循時(shí)域抽取法則，8點(diǎn)DFT可分解3次。165.3 時(shí)域抽取的快速算法蝶形運(yùn)算有兩個(gè)重要特點(diǎn)。（1）反序輸入序列的時(shí)序等于1點(diǎn)長(zhǎng)DFT的下標(biāo)，下標(biāo)用二進(jìn)制表示。它按從左到右遞增的二進(jìn)制順序，稱反序。（2）原位運(yùn)算蝶形的輸入數(shù)據(jù)在后面的蝶形都不再出現(xiàn)，蝶形運(yùn)算結(jié)果的位置和輸入的位置相同。稱為原位運(yùn)算，它能夠節(jié)省計(jì)算機(jī)的存儲(chǔ)器。175.3 時(shí)域抽取的快速算法運(yùn)用反序和原位運(yùn)算，蝶形運(yùn)算圖的中間過程符號(hào)可略，變?yōu)檫@種時(shí)序的奇偶分解DFT方法稱

7、時(shí)域抽取基2快速傅里葉變換，簡(jiǎn)稱時(shí)域抽取快速傅里葉變換185.3 時(shí)域抽取的快速算法5.3.3 時(shí)域抽取的計(jì)算量把每次分解DFT當(dāng)作一級(jí)，時(shí)域抽取的蝶形運(yùn)算共有M級(jí)，每級(jí)有N/2個(gè)蝶，每個(gè)蝶復(fù)數(shù)乘1次復(fù)數(shù)加2次。所以，時(shí)域抽取算法需復(fù)數(shù)乘MN/2次，復(fù)數(shù)加MN次。比直接計(jì)算法的N2 少許多。195.3 時(shí)域抽取的快速算法例5.3 設(shè)語音信號(hào)的采樣率為6kHz，記錄時(shí)間為1s，計(jì)算機(jī)復(fù)數(shù)乘1次需3s，復(fù)數(shù)加1次需1s。請(qǐng)問：該信號(hào)均分為6段，用時(shí)域抽取法計(jì)算頻譜要多少時(shí)間？若分為3段，要多少時(shí)間？解 因時(shí)域抽取法要求N=2M，當(dāng)信號(hào)分為6段時(shí)，每段有1000個(gè)樣本，故取N=210。這時(shí)計(jì)算機(jī)的耗

8、時(shí)205.3 時(shí)域抽取的快速算法若將信號(hào)分為3段，每段有2000個(gè)樣本，故取N=211。這時(shí)計(jì)算機(jī)的耗時(shí)兩種算法都能實(shí)時(shí)分析頻譜。215.3 時(shí)域抽取的快速算法例5.4 設(shè)計(jì)算機(jī)1次乘需3s，1次加需1s；用它計(jì)算1000點(diǎn)序列的頻譜。請(qǐng)比較直接計(jì)算和時(shí)域抽取計(jì)算頻譜的時(shí)間。解 若按DFT的定義直接計(jì)算頻譜，取N=1000，這時(shí)計(jì)算機(jī)耗時(shí)225.3 時(shí)域抽取的快速算法若用時(shí)域抽取法計(jì)算頻譜，取N=210，這時(shí)計(jì)算機(jī)的耗時(shí)兩種結(jié)果相比，16/0.092174，時(shí)域抽取比直接計(jì)算快173倍。235.4 頻域抽取的快速算法頻域抽取的基本做法是：將離散傅里葉變換的序列從中間分解為等長(zhǎng)的兩段序列。這種算

9、法要求序列的長(zhǎng)5.4.1 頻域抽取的原理頻域抽取分兩步：1、將序列按時(shí)序分兩段，2、是整理短序列的頻譜。（1）分解序列245.4 頻域抽取的快速算法（2）整理頻譜為了得到N/2點(diǎn)DFT，根據(jù)k的偶奇數(shù)將X(k)分解為兩部分。偶數(shù)k的頻譜 這時(shí)n和k都是N/2點(diǎn)，故X(2k)是真正的N/2點(diǎn)DFT。 255.4 頻域抽取的快速算法它們都是N/2點(diǎn)DFT，運(yùn)算量比X(k)的運(yùn)算量少近一半。5.4.2 原理的推廣對(duì)N/2點(diǎn)的X0(k)和X1(k)繼續(xù)分解，可得N/4點(diǎn)離散傅里葉變換。不過用圖來表示比較簡(jiǎn)潔直觀。265.4 頻域抽取的快速算法例5.5 有個(gè)8點(diǎn)離散傅里葉變換，請(qǐng)用頻域抽取法的蝶形圖描述

10、計(jì)算過程。解 根據(jù)頻域抽取法則，8點(diǎn)DFT可分解3次。 275.4 頻域抽取的快速算法根據(jù)蝶形圖的原位運(yùn)算，分解過程的序列符號(hào)可省略，頻域抽取法的蝶形運(yùn)算圖可簡(jiǎn)化為285.4 頻域抽取的快速算法5.4.3 頻域抽取的計(jì)算量 頻域抽取法的運(yùn)算量和時(shí)域抽取法的運(yùn)算量相同。它全部蝶形運(yùn)算需復(fù)數(shù)乘和復(fù)數(shù)加次數(shù)是5.4.4 兩種算法的異同時(shí)域抽取法的輸入倒序，頻域抽取法的輸出倒序；前者的蝶形先乘后加，后者的蝶形先加后乘；前者的蝶由小到大，后者的蝶由大到小。295.5 反變換的快速算法離散傅里葉變換的用途很多，例如頻譜分析，信息提取、快速卷積、信號(hào)壓縮等；應(yīng)用離散傅里葉變換時(shí)，往往還要離散傅里葉變換反變換

11、。在設(shè)計(jì)產(chǎn)品時(shí)，該如何給離散傅里葉反變換編寫有效的計(jì)算程序呢？ 5.5.1 仿效正變換因離散傅里葉變換的正變換為305.5 反變換的快速算法反變換為兩者的計(jì)算方式除了系數(shù)1/N，其它相同。5.5.2 旋轉(zhuǎn)因子共軛抽去x(n)和X(k)的具體內(nèi)容，剩下都是數(shù)字，它們的乘法相同，只是兩種旋轉(zhuǎn)因子的正負(fù)相反。它們不影響旋轉(zhuǎn)因子的周期和反向?qū)ΨQ。315.5 反變換的快速算法只要我們?cè)谠瓉砜焖龠\(yùn)算的基礎(chǔ)上增加一個(gè)取WNkn的復(fù)共軛子程序，并乘1/N，就可以利用原有快速傅里葉變換程序，對(duì)數(shù)據(jù)X(k)進(jìn)行反變換。5.5.3 頻譜共軛對(duì)反變換公式取兩次共軛，即325.6 實(shí)數(shù)序列的快速算法為了程序的通用性，快

12、速傅里葉變換大多按復(fù)數(shù)序列編寫。怎樣快速計(jì)算實(shí)數(shù)序列的頻譜？5.6.1 直接運(yùn)用把實(shí)數(shù)序列當(dāng)作是虛部為0的復(fù)數(shù)序列，用現(xiàn)成的快速傅里葉變換程序?qū)@個(gè)復(fù)數(shù)序列進(jìn)行計(jì)算。但計(jì)算機(jī)不是人，它不知道實(shí)數(shù)序列的虛部為0，0是不用算的。如果考慮計(jì)算機(jī)對(duì)這種復(fù)數(shù)序列的虛部運(yùn)算量和存儲(chǔ)器的需要，這種開銷很大。335.6 實(shí)數(shù)序列的快速算法5.6.2 合二為一先用兩個(gè)同長(zhǎng)實(shí)數(shù)序列x1(n)和x2(n)構(gòu)建新序列， 然后，運(yùn)用快速傅里葉變換程序計(jì)算X(k)；最后，根據(jù)DFT的共軛對(duì)稱性，這種分離只需復(fù)數(shù)加N次。345.6 實(shí)數(shù)序列的快速算法5.6.3 一分為二先將N點(diǎn)實(shí)數(shù)x(n)按n的奇偶分成x0(r)=x(2r

13、)和x1(r)=x(2r+1)，r=0N/2-1，并組成y(r)=x0 (r)+jx1(r)；然后，將y(n)送入快速傅里葉變換程序，得Y(k)，k=0N/2-1，并用DFT的共軛對(duì)稱性獲取355.6 實(shí)數(shù)序列的快速算法最后，根據(jù)時(shí)域抽取分解式，得x(n)的頻譜因y(n)比x(n)長(zhǎng)度減半，故這種算法的運(yùn)算量比直接快速計(jì)算X(k)的運(yùn)算量減少近一半。365.7 快速傅里葉變換的應(yīng)用離散傅里葉變換是分析和綜合序列的理論，快速傅里葉變換是計(jì)算離散傅里葉變換的策略。5.7.1 信號(hào)分析例5.6 設(shè)導(dǎo)彈的最高時(shí)速v=2000km/h，雷達(dá)發(fā)射的微波x(t)=cos(2f0t)，目標(biāo)的反射波y(t)=c

14、os2f0(t-r)。求y(t)的采樣頻率。若每3s發(fā)射一次0.1ms寬的微波脈沖x(t)，每3ms記錄一段2ms長(zhǎng)的y(t)，計(jì)算機(jī)復(fù)乘1次需20ns，復(fù)加1次需10ns。求直接計(jì)算和快速計(jì)算能否實(shí)時(shí)頻譜分析。 375.7 快速傅里葉變換的應(yīng)用解 （1）采樣頻率確定采樣頻率前要知道x(t)的帶寬。設(shè)雷達(dá)和目標(biāo)的距離為d(t)，用泰勒級(jí)數(shù)表示為 385.7 快速傅里葉變換的應(yīng)用d(0)和d(0)為導(dǎo)彈t=0時(shí)的距離和速度。信號(hào)往返的時(shí)間r=2d(t)/c，c=3108m/s為電磁波傳播速度，所以， 根據(jù)v=2000km/h，最大頻偏f=2d(0)f0/c 111.2kHz?？紤]fH=f0+f和

15、f0=30000.2MHz，為滿足帶通采樣定理fH=2nf，取f=200kHz可讓n為整數(shù)，故采樣頻率fs=800kHz。395.7 快速傅里葉變換的應(yīng)用（2）頻譜分析因2ms的信號(hào)樣本有1600個(gè)，根據(jù)頻域采樣定理，取N=1600，得按定義直接計(jì)算頻譜的時(shí)間約76.8ms，它大于3ms間隔，故不能實(shí)時(shí)分析反射信號(hào)。按快速傅里葉變換計(jì)算頻譜時(shí)，取N=211，其頻譜計(jì)算的時(shí)間約0.45ms，小于3ms間隔，故可實(shí)時(shí)分析頻譜。405.7 快速傅里葉變換的應(yīng)用5.7.2 線性卷積線性卷積是系統(tǒng)加工信號(hào)的工具，若信號(hào)x(n)和系統(tǒng)h(n)長(zhǎng)2M ，則它們卷積y(n)的長(zhǎng)為2M+1-1，需實(shí)數(shù)乘加各需約22M+1次。例5.7 設(shè)信號(hào)x(n)和系統(tǒng)h(n)的長(zhǎng)度N=1024=210，計(jì)算機(jī)乘1次要10ns，加1次要5ns。求計(jì)算機(jī)直接卷積和用快速卷積的時(shí)間。解 （1）直接卷積因線性卷積的非0值長(zhǎng)為2210-1，故計(jì)算卷積需乘約2220次，加約2220次，共耗時(shí)31.5ms。415.7 快速傅里葉變換的應(yīng)用（2）快速卷積先給序列x(n)和h(n)尾部添加零，延長(zhǎng)它們到2N=211。h(n)的頻譜可事先