數(shù)字信號處理(第三)課后答案及學(xué)習(xí)指導(dǎo)(高西全丁玉美)第四

1、3.6 教材第教材第4章習(xí)題與上機(jī)題解答章習(xí)題與上機(jī)題解答快速傅里葉變換（FFT）是DFT的快速算法， 沒有新的物理概念。 FFT的基本思想和方法教材中都有詳細(xì)的敘述， 所以只給出教材第4章的習(xí)題與上機(jī)題解答。 1 如果某通用單片計(jì)算機(jī)的速度為平均每次復(fù)數(shù)乘需要4 s， 每次復(fù)數(shù)加需要1 s， 用來計(jì)算N=1024點(diǎn)DFT， 問直接計(jì)算需要多少時(shí)間。 用FFT計(jì)算呢？照這樣計(jì)算， 用FFT進(jìn)行快速卷積對信號進(jìn)行處理時(shí)， 估計(jì)可實(shí)現(xiàn)實(shí)時(shí)處理的信號最高頻率。 解解: 當(dāng)N=1024=210時(shí)， 直接計(jì)算DFT的復(fù)數(shù)乘法運(yùn)算次數(shù)為N2=10241024=1 048 576次復(fù)數(shù)加法運(yùn)算次數(shù)為N（N1

2、）=10241023=1 047 552次直接計(jì)算所用計(jì)算時(shí)間TD為TD=410610242+1 047 552106=5.241 856 s用FFT計(jì)算1024點(diǎn)DFT所需計(jì)算時(shí)間TF為66F665 10lblb10210245 1010 1024 10 10230.72 msNTNN N 快速卷積時(shí)， 需要計(jì)算一次N點(diǎn)FFT（考慮到H(k)=DFTh(n)已計(jì)算好存入內(nèi)存）、 N次頻域復(fù)數(shù)乘法和一次N點(diǎn)IFFT。 所以， 計(jì)算1024點(diǎn)快速卷積的計(jì)算時(shí)間Tc約為cF2102471680 s4 1024 s65536 sTT 次復(fù)數(shù)乘計(jì)算時(shí)間所以， 每秒鐘處理的采樣點(diǎn)數(shù)（即采樣速率）s610

3、2415 625 /65536 10F次 秒由采樣定理知， 可實(shí)時(shí)處理的信號最高頻率為smax156257.8125 kHz22Ff應(yīng)當(dāng)說明， 實(shí)際實(shí)現(xiàn)時(shí)， fmax還要小一些。 這是由于實(shí)際中要求采樣頻率高于奈奎斯特速率， 而且在采用重疊相加法時(shí)， 重疊部分要計(jì)算兩次。 重疊部分長度與h(n)長度有關(guān)， 而且還有存取數(shù)據(jù)和指令周期等消耗的時(shí)間。 2 如果將通用單片機(jī)換成數(shù)字信號處理專用單片機(jī)TMS320系列， 計(jì)算復(fù)數(shù)乘和復(fù)數(shù)加各需要10 ns。 請重復(fù)做上題。 解解: 與第1題同理。 直接計(jì)算1024點(diǎn)DFT所需計(jì)算時(shí)間TD為TD=1010910242+101091 047 552=20.

4、961 28 ms用FFT計(jì)算1024點(diǎn)DFT所需計(jì)算時(shí)間TF為99F8810 10lb10 10lb210241010 101024 1020.1536 msNTNNN快速卷積計(jì)算時(shí)間Tc約為cF3921024 2 0.1536 1010 101024 0.317 44 msTT次復(fù)數(shù)乘計(jì)算時(shí)間可實(shí)時(shí)處理的信號最高頻率fmax為maxsc1110241 = 3.1158 MHz=1.6129 MHz222fFT由此可見， 用DSP專用單片機(jī)可大大提高信號處理速度。 所以， DSP在數(shù)字信號處理領(lǐng)域得到廣泛應(yīng)用。 機(jī)器周期小于1 ns的DSP產(chǎn)品已上市， 其處理速度更高。 3 已知X(k)和Y

5、(k)是兩個(gè)N點(diǎn)實(shí)序列x(n)和y(n)的DFT， 希望從X(k)和Y(k)求x(n)和y(n)， 為提高運(yùn)算效率， 試設(shè)計(jì)用一次N點(diǎn)IFFT來完成的算法。 解解: 因?yàn)閤(n)和y(n)均為實(shí)序列， 所以， X(k)和Y(n)為共軛對稱序列， jY(k)為共軛反對稱序列。 可令X(k)和jY(k)分別作為復(fù)序列F(k)的共軛對稱分量和共軛反對稱分量， 即F(k)=X(k)+jY(k)=Fep(k)+Fop(k)計(jì)算一次N點(diǎn)IFFT得到f(n)=IFFTF(k)=Ref(n)+j Imf(n)由DFT的共軛對稱性可知Ref(n)=IDFTFep(k)=IDFTX(k)=x(n)j Imf(n)

6、=IDFTFop(k)=IDFTjY(k)=jy(n)故1( ) ( )( )2x nf nfn1( ) ( )( )2jy nf nfn4 設(shè)x(n)是長度為2N的有限長實(shí)序列， X(k)為x(n)的2N點(diǎn)DFT。 (1) 試設(shè)計(jì)用一次N點(diǎn)FFT完成計(jì)算X(k)的高效算法。 (2) 若已知X(k) ，試設(shè)計(jì)用一次N點(diǎn)IFFT實(shí)現(xiàn)求X(k)的2N點(diǎn)IDFT運(yùn)算。解解: 本題的解題思路就是DIT-FFT思想。（1） 在時(shí)域分別抽取偶數(shù)和奇數(shù)點(diǎn)x(n)， 得到兩個(gè)N點(diǎn)實(shí)序列x1(n)和x2(n)： x1(n)=x(2n) n=0, 1, , N1x2(n)=x(2n+1) n=0, 1, , N1

7、根據(jù)DIT-FFT的思想， 只要求得x1(n)和x2(n)的N點(diǎn)DFT， 再經(jīng)過簡單的一級蝶形運(yùn)算就可得到x(n)的2N點(diǎn)DFT。 因?yàn)閤1(n)和x2(n)均為實(shí)序列， 所以根據(jù)DFT的共軛對稱性， 可用一次N點(diǎn)FFT求得X1(k)和X2(k)。 具體方法如下：令 y(n)=x1(n)+jx2(n)Y(k)=DFTy(n) k=0, 1, , N1則*11ep*22ep1( )DFT( )( ) ( )()21j( )DFTj( )( ) ( )()2X kx nYkY kYNkXkx nYkY kYNk2N點(diǎn)DFTx（n）=X（k）可由X1(k)和X2(k)得到122122( )( )(

8、) 0,1,1()( )( )kNkNX kX kWXkkNX kNX kWXk這樣， 通過一次N點(diǎn)IFFT計(jì)算就完成了計(jì)算2N點(diǎn)DFT。 當(dāng)然還要進(jìn)行由Y(k)求X1(k)、 X2(k)和X(k)的運(yùn)算(運(yùn)算量相對很少)。 （2） 與（1）相同， 設(shè)x1(n)=x(2n) n=0, 1, , N1x2(n)=x(2n+1) n=0, 1, , N1X1(k)=DFTx1(n) k=0, 1, , N1X2(k)=DFTx2(n) k=0, 1, , N1則應(yīng)滿足關(guān)系式122122( )( )( ) 0,1,1()( )( )kNkNX kX kWXkkNX kNX kWXk由上式可解出122

9、1( )( )()2 0,1,2,11( )( )()2kNX kX kX kNkNXkX kX kN W由以上分析可得出運(yùn)算過程如下： 由X(k)計(jì)算出X1(k)和X2(k): 1221( )( )()21( )( )()2kNX kX kX kNXkX kX kN W 由X1(k)和X2(k)構(gòu)成N點(diǎn)頻域序列Y(k): Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)其中， Yep(k)=X1(k), Yop(k)=jX2(k)， 進(jìn)行N點(diǎn)IFFT， 得到y(tǒng)(n)=IFFTY(k)=Rey(n)+j Imy(n) n=0, 1, , N1由DFT的共軛對稱性知*ep1*op2

10、1Re ( ) ( )( )DFT( )( )21jIm ( ) ( )( )DFT( )j( )2y ny ny nYkx ny ny ny nYkx n 由x1(n)和x2(n)合成x(n):12 2( )1 2nxnx nnxn偶數(shù)奇數(shù)，0n2N1在編程序?qū)崿F(xiàn)時(shí)， 只要將存放x1(n)和x2(n)的兩個(gè)數(shù)組的元素分別依次放入存放x(n)的數(shù)組的偶數(shù)和奇數(shù)數(shù)組元素中即可。5 分別畫出16點(diǎn)基2DIT-FFT和DIF-FFT運(yùn)算流圖， 并計(jì)算其復(fù)數(shù)乘次數(shù)， 如果考慮三類碟形的乘法計(jì)算， 試計(jì)算復(fù)乘次數(shù)。 解解： 本題比較簡單， 仿照教材中的8點(diǎn)基2DIT-FFT和DIF-FFT運(yùn)算流圖很容易

11、畫出16點(diǎn)基2DIT-FFT和DIF-FFT運(yùn)算流圖。 但畫圖占篇幅較大， 這里省略本題解答， 請讀者自己完成。6* 按照下面的IDFT算法編寫MATLAB語言 IFFT程序， 其中的FFT部分不用寫出清單， 可調(diào)用fft函數(shù)。 并分別對單位脈沖序列、 矩形序列、 三角序列和正弦序列進(jìn)行FFT和IFFT變換， 驗(yàn)證所編程序。 *1( )IDFT( )DFT( )x nX kXkN解解： 為了使用靈活方便， 將本題所給算法公式作為函數(shù)編寫ifft46.m如下： %函數(shù)ifft46.m%按照所給算法公式計(jì)算IFETfunction xn=ifft46(Xk， N)Xk=conj(Xk)； %對Xk

12、取復(fù)共軛xn=conj(fft(Xk， N)/N； %按照所給算法公式計(jì)算IFFT分別對單位脈沖序列、 長度為8的矩形序列和三角序列進(jìn)行FFT， 并調(diào)用函數(shù)ifft46計(jì)算IFFT變換， 驗(yàn)證函數(shù)ifft46的程序ex406.m如下： %程序ex406.m%調(diào)用fft函數(shù)計(jì)算IDFTx1n=1； %輸入單位脈沖序列x1nx2n=1 1 1 1 1 1 1 1； %輸入矩形序列向量x2nx3n=1 2 3 4 4 3 2 1； %輸入三角序列序列向量x3nN=8； X1k=fft(x1n， N)； %計(jì)算x1n的N點(diǎn)DFTX2k=fft(x2n， N)； %計(jì)算x2n的N點(diǎn)DFTX3k=fft(x3n， N)； %計(jì)算x3n的N點(diǎn)DFTx1n=ifft46(X1k， N) %調(diào)用ifft4