數(shù)字信號處理原理配套習(xí)題答案第5章快速傅利葉變換習(xí)題解答

5.1一臺通用計(jì)算機(jī)的速度為：平均每次復(fù)數(shù)乘法需要100μs，每次復(fù)數(shù)加法需要20μs，今用來計(jì)算N=1024點(diǎn)的DFT[x(n)]。問直接運(yùn)算需要多少時間？用FFT運(yùn)算需要多少時間？解直接計(jì)算DFT需要N2次復(fù)數(shù)乘法、N(N-1)次復(fù)數(shù)加法；當(dāng)N=1024=210復(fù)數(shù)乘法：N2=10242復(fù)數(shù)加法：N(N-1)=1024×(1024-1)≈10242=1048576所以直接運(yùn)算需要的時間為1048576×100μs+1048576×20μs=125829120μs≈125.829s而如果用DIT-FFT算法，需要的運(yùn)算量如下：復(fù)數(shù)乘法：mF復(fù)數(shù)加法：m所以采用DIT-FFT算法需要的時間為5120×100μs+10240×20μs=716800μs=0.7168s5.2一個線性非移變系統(tǒng)的單位取樣響應(yīng)為，已知輸入信號為，請用FFT方法求，要求畫出詳細(xì)的運(yùn)算流圖，并寫出計(jì)算步驟。解由題意y(n)=x(n)??(n)，根據(jù)圓周卷積定理可知Y(k)=X(k)H(k)，又因?yàn)楫?dāng)N≥N1+N2?1=時，可用圓周卷積替代線性卷積。若用基-2FFT，N取4，先計(jì)算x(n)和?(n)的FFT，再求X(k)和H(k)乘積得到Y(jié)(k)圖5.6圖5.7因此，Y(k)=X(k)H(k)={3,1求Y(k)的IFFT的方法有兩種：方法一：因?yàn)閥(n)=1NDFTY圖5.8所以y(n)=方法二：可利用4點(diǎn)的DIF-IFFT計(jì)算y(n)結(jié)果，如圖5.9所示。圖5.9所以y(n)=1,5.3試畫出為復(fù)合數(shù)時的FFT算法求的結(jié)果（采用基）。解依題意：，∴對于，有有，同樣，令對于頻率變量有，∴∴圖5.105.4已知是一個點(diǎn)實(shí)序列的DFT，現(xiàn)在要用為求，為提高運(yùn)算效率，試設(shè)計(jì)一個點(diǎn)IFFT運(yùn)算一次完成。解將x(n)奇偶分組得{x1因?yàn)閤(n)為實(shí)序列，因此構(gòu)造一個復(fù)序列wn設(shè){X{X(所以如果已知X(k)，可得令{WWk=也即wn5.5一個長度為的復(fù)序列與一個長度為的復(fù)序列卷積。(1)求直接進(jìn)行卷積所需(復(fù))乘法次數(shù)。(2)若用1024點(diǎn)基2按時間抽取FFT重疊相加法計(jì)算卷積，重做問題(1)。解(1)直接進(jìn)行卷積所需(復(fù))乘法次數(shù)為：K1=ML=512×8192=4194304。若用1024點(diǎn)按時間抽取的基-2FFT重疊相加法計(jì)算卷積，由于的長度為512點(diǎn)，可以將分段成16段長度為512的序列，這樣與1024點(diǎn)的圓周卷積與線性卷積相等。根據(jù)快速卷積原理，需計(jì)算17次1024點(diǎn)的FFT和16次1024點(diǎn)的IFFT。N點(diǎn)的FFT的(復(fù))乘法次數(shù)為mF=N2log2?NK5.6設(shè)是一個長度為的序列，且，，其中為偶數(shù)。(1)證明x(n)的N點(diǎn)DFT僅有奇次諧波，即X(k)=0，k為偶數(shù)(2)證明如何由一個經(jīng)過適當(dāng)調(diào)整的序列的N/2的DFT求得x(n)的N點(diǎn)DFT。證明(1)X=當(dāng)k為偶數(shù)時，由于xn=?xn+N2(2)Xk因?yàn)閃NXk=Xn/2(2k)表示序列的N2的DFT，從而得x5.7已知以1s為周期均勻采樣得到。(1)試求頻譜X(k)，并作出碟形圖。(2)試進(jìn)行譜分析，即求出振幅譜、相位譜和功率譜。解(1)采用圖示法，4點(diǎn)的DIT-FFT運(yùn)算蝶形圖如圖5.11所示。圖5.11所以X(k)={5,2+j,-5,2-j}振幅譜Ak相位譜φ功率譜S(k)=A5.8用微處理機(jī)對實(shí)序列進(jìn)行譜分析，要求譜分辨率F≤1Hz，信號的最高頻率為，試確定以下各參數(shù)：(1)最小記錄時間Tpmin；(2)最大的取樣間隔Tmax；(3)最少采樣點(diǎn)數(shù)Nmin解由F≤1Hz及Tp≥1F可得：而采樣頻率fsTN分辨率提高一倍，即，則5.9用重疊相加法計(jì)算一個長度為1000點(diǎn)的序列與長度為64點(diǎn)的序列的線性卷積時，共需要多少點(diǎn)DFT變換與DFT反變換？用重疊保留法呢？解由重疊相加法可知，需要把1000點(diǎn)的長序列分成每段分為L=128+1-64=65點(diǎn)共可得16段，這樣每段65點(diǎn)序列與64點(diǎn)短序列的線性卷積恰好可以由128點(diǎn)的圓周卷積計(jì)算。由此可得需通過DFT轉(zhuǎn)換16次，DFT轉(zhuǎn)換1次，總共17次DFT，并運(yùn)用DFT反變換16次就可以了。若采用重疊保留法，則分組的時候與重疊相加法有區(qū)別，第一段128點(diǎn)中包含64-1=63個零點(diǎn)，含有65個非零點(diǎn)，第二段中又重復(fù)第一段中最后63個點(diǎn)，然后依次排列后面的65個點(diǎn)，接著第三段依此類推，每段只有65個點(diǎn)是唯一的，因此100