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