1、第第4章習題解答章習題解答1.如果一臺通用計算機的速度為平均每次復乘 ，每次復加 ，用它來計算512點的 ，問直接計算需要多少時間，用 運算需要多少時間。 5 s0.5 s DFT x nFFT解：(1)直接利用 計算： 復乘次數為 ，復加次數為 。 DFT2N1N N 復乘所需時間 626215 105 105121.31072TNs復加所需時間 6260.5 1010.5 1051251210.130816TNNs所以直接利用DFT 計算所需時間： 121.441536TTTs復乘所需時間 612625 10log25125 10log 5120.011522NTNs622620.5 10

2、log0.5 10512log 5120.002304TNNs復加所需時間 所以用 FFT 計算所需時間 120.013824TTTs(2) 利用 計算： 復乘次數為 ，復加次數為 。 FFT2log2NN2logNN2.已知 ， 是兩個N點實序列 ， 的 值，今需要從 ， 求 ， 的值，為了提高運算效率，試用一個N點 運算一次完成。 X k Y k x n y nDFT X k Y k x n y nIFFT解： 由題意 X kDFT x nY kDFT y n，構造序列 Z kX kjY k對 作一次N點IFFT可得序列 Z k z n又根據DFT的線性性質 IDFT X kjIDFT Y

3、 k而 ， 都是實序列 x n y n ReImx nz ny nz n ( )z nIDFT Z k ( )z nIDFT Z kIDFT X kjY k x njy nB 設x1(n)和x2(n)都是N點的實數序列，試用一次N點DFT運算來計算它們各自的DFT: 11( )( )DFT x nX k22( )( )DFT x nXk解：利用兩序列構成一個復序列12( )( )( )w nx njxn12( ) ( )( )( )W kDFT w nDFT x njx n則12( )( )DFT x njDFT x n12( )( )X kjXkRe ( )( )epw nWkIm ( )(

4、 )opjw nWk1( )Re ( )x nw n由得11( )( )Re ( )( )epXkDFT x nDFTw nWk*1( )() ( )2NNNWkWNkRk2( )Im ( )x nw n由得221( )( )Im ( )( )opXkDFT x nDFTw nWkj*1( )() ( )2NNNWkWNkRkj3. N=16 時，畫出基 -2 按時間抽取法及按頻率抽取法的 FFT 流圖（時間抽取采用輸入倒位序，輸出自然數順序，頻率抽取采用輸入自然順序，輸出倒位序）。 解：自然序 倒位序0 0000 0000 00001 1000 80010 0100 40011 1100 1

5、20100 0010 20101 1010 100110 0110 6 10111 1110 14自然序 倒位序8 1000 0001 19 1001 1001 910 1010 0101 511 1011 1101 1312 1100 0011 313 1101 1011 1114 1110 0111 715 1111 1111 15(1) 按時間抽取的基-2FFT流圖162 , 4LNL共有L = 4級蝶形運算，每級N / 2 = 8個蝶形運算每個蝶形的兩節點距離為 ，即從第一級到第四級兩節點距離分別為1，2，4，8。12m-2( )2rL mNWrkkLm系數的確定：即 的二進制左移位補

6、零rNW1( )mXk1( )mXj( )mXk( )mXj-1(2) 按頻率抽取的基-2FFT流圖 基本蝶形是DIT 蝶形的轉置同樣共有L = 4級蝶形運算，每級N / 2 = 8個蝶形運算每個蝶形的兩節點距離為 ，即從第一級到第四級兩節點距離分別為8，4，2，1。2L m12( )21rmNWrkkm系數的確定：即 的二進制左移位補零rNW1( )mXk1( )mXj( )mXk( )mXj-11j若不計乘及乘的運算量 則實際乘法次數為10次復數乘法216DFT256(-1)240NNN N直接計算需要次復數乘法 次復數加法22FFTlog322log64NNNN利用計算需要次復數乘法 次

7、復數加法9. 在下列說法中選擇正確的結論。線性調頻 z 變換 (CZT) 可以用來計算一個M點有限長序列 在 z 平面的實軸上各 點的 z 變換 ，使 h n kz H z(1) ， 為實數，1。,0,1,1kkzakN(2) ， 為實數，0 。,0,1,1kzak kN(3) (1)和(2)兩者都行。(4) (1)和(2)兩者都不行。即線性調頻 z 變換不能計算 H (z) 在 z 為實數時的抽樣。 10NnkknH zh n z其中抽樣點須滿足：0000, 0,1,1jkkkkzAWAWekN ， ， ， 為任意實數。 0A0W00對于說法（1），只需取 ， ， ，01A 10Wa0000

8、():kkCZTzzH z解：用于計算 平面上一段螺線作等分角的抽樣點 上 的復頻譜10100,1,.,1CZT()kkkzazakNH z即起點為 ，初始相角和角度差均為 ，為螺線的伸縮率，就形成了實軸上各抽樣點 ,。因此可以用算法來計算 所以說法(1)是正確的00(2), ,()kkkzakAWzzzH z對于說法 則無法通過選擇合適的 和，使之成為 平面上一段螺線作等分角后的一組抽樣點。因此不能用CZT算法來計算各 點的 變換。13. 我們希望利用一個單位抽樣響應點數N = 50 的有限沖激響應濾波器來過濾一串很長的數據。要求利用重疊保留法通過快速傅里葉變換來實現這種濾波器，為了做到這一

9、點，則：（1）輸入各段必須重疊P個抽樣點；（2）我們必須從每一段產生的輸出中取出Q個抽樣點，使這些從每一段得到的抽樣連接在一起時，得到的序列就是所要求的濾波輸出。假設輸入的各段長度為100個抽樣點，而離散傅里葉變換的長度為128點。進一步假設，圓周卷積的輸出序列標號是從 n = 0到 n = 127，則（a）求P； （b）求Q； （c）求取出來的Q個點的起點和終點的標號，即確定從圓周卷積的128點中要取出哪些點，去和前一段的點銜接起來。解：（a）由于用重疊保留法，如果沖激響應 h n的點數為N點，則圓周卷積結果的前面的 1N 個點不代表線性卷積結果，故每段重疊點數P為 150 149PN （b）每段點數為 72128，但其中只有100個點是有效輸入數據，其余28個點為補充的零值點