第四章习题讲解 2024/10/21
第四章习题讲解 2024/10/21 1
1.如果一台通用计算机的速度为平均每次复乘54s, 每次复加0.5us,用它来计算512点的DFTx(n)],问 直接计算需要多少时间，用FFT运算需要多少时间。 (1)直接利用DFT计算： 复乘次数为N,复加次数为N(N-1)。 复乘所需时间 T=5×106×W2=5×106×5122=1.31072s 复加所需时间 T2=0.5×106×N×(N-1) =0.5×106×512×(512-1)=0.130816s 所以直接利用DFT计算所需时间： T=T+T,=1.441536s 2024/10/21 2
1.如果一台通用计算机的速度为平均每次复乘 ， 每次复加 ，用它来计算512点的 ，问 直接计算需要多少时间，用 运算需要多少时间。 5s 0.5s DFT x n ( ) FFT 解：(1)直接利用 计算： 复乘次数为 ，复加次数为 。 DFT 2 N N N( −1) 复乘所需时间 6 2 6 2 1T N s 5 10 5 10 512 1.31072 − − = = = 复加所需时间 ( ) ( ) 6 2 6 0.5 10 1 0.5 10 512 512 1 0.130816 T N N s − − = − = − = 所以直接利用DFT 计算所需时间： 1 2 T T T s = + =1.441536 2024/10/21 2
2)利用FFT计算： 复乘次数为。log2N,复加次数为N1og,N。 2 复乘所需时间 7=5x10×Y1og,N =5x106×512 og2512=0.01152s 复加所需时间 T2=0.5×10-6×N1og2N =0.5×106×5121og2512=0.002304s 所以用FFT计算所需时间 T=T+T3=0.013824s 2024/10/21 3
复乘所需时间 6 1 2 6 2 5 10 log 2 512 5 10 log 512 0.01152 2 N T N s − − = = = 6 2 2 6 2 0.5 10 log 0.5 10 512log 512 0.002304 T N N s − − = = = 复加所需时间 所以用 FFT 计算所需时间 1 2 T T T s = + = 0.013824 (2) 利用 计算： 复乘次数为 ，复加次数为 。 FFT 2 log 2 N N 2 N N log 2024/10/21 3
2.已知X(k),Y(k)是两个N点实序列x(n),y(n)的DFT 值，今需要从X(k),Y(k)求x(n),y(n)的值，为了提 高运算效率，试用一个N点FFT运算一次完成。 2024/10/21
2.已知 ， 是两个N点实序列 ， 的 值，今需要从 ， 求 ， 的值，为了提 高运算效率，试用一个N点 运算一次完成。 X k( ) Y k( ) x n( ) y n( ) DFT X k( ) Y k( ) x n( ) y n( ) IFFT 2024/10/21 4
例：设x(n)和x(n)都是N点的实数序列，试用 一次N点DFT运算来计算它们各自的DFT: DFT[x (n)=X (k) DFT[x,(n)]=X,(k) 解：利用两序列构成一个复序列 w(n)=x (n)+jx,(n) 则 W(k)=DFT[w(n)]=DFT[x (n)+jx2 (n)] DFT[x (n)]+jDFT[x,(n)] X(k)+jX2(k) Re[w(n】>W,() Jlm[w(n】>Wp() 2024/10/21
例：设x1 (n)和x2 (n)都是N点的实数序列，试用 一次N点DFT运算来计算它们各自的DFT: 1 1 DFT x n X k [ ( )] ( ) = 2 2 DFT x n X k [ ( )] ( ) = 解：利用两序列构成一个复序列 1 2 w n x n jx n ( ) ( ) ( ) = + 1 2 W k DFT w n DFT x n jx n ( ) [ ( )] [ ( ) ( )] = = + 则 1 2 = + DFT x n jDFT x n [ ( )] [ ( )] 1 2 = + X k jX k ( ) ( ) Re[ ( )] ( ) w n W k ep Im[ ( )] ( ) op j w n W k 2024/10/21 5
由x,(n)=Re[w(n)]得 X (k)=DFT[x (n)]=DFT{Re[w(n)]=W(k) =2(》+W(V-,]R( 由x2(n)=Im[w(n)]得 X:(k)-DFTl:()-DFT{Iml(() 子》.-g-.R因 2024/10/21
1 由 得 x n w n ( ) Re[ ( )] = 1 1 ( ) [ ( )] {Re[ ( )]} ( ) X k DFT x n DFT w n W k = = = ep 1 * [ (( )) (( )) ] ( ) 2 = + − W k W N k R k N N N 2 由 得 x n w n ( ) Im[ ( )] = 2 2 1 ( ) [ ( )] {Im[ ( )]} ( ) X k DFT x n DFT w n W k op j = = = 1 * [ (( )) (( )) ] ( ) 2 W k W N k R k N N N j = − − 2024/10/21 6
解：由题意X(k)=DFT[x(n)],Y()=DFT[y(n)] 构造序列Z(k)=X(k)+Y() 对Z(k)作一次V点FFT可得序列(n) E(n)=IDFT[Z(k) 又根据DFT的线性性质 =(m)=IDFT[Z(K)]=IDFT[X(k)+jY(k)] IDFT[X (k)]+jIDFT[Y (R)] =x(n)+y(n) 而x(n),y(n)都是实序列 x(n）=Re[z(n)] y(n)=Im[=(n)] 2024/10/21
解：由题意 X k DFT x n Y k DFT y n ( ) = = ( ) ( ) ( ) ， 构造序列 Z k X k jY k ( ) = + ( ) ( ) 对 Z k( ) 作一次N点IFFT可得序列 z n( ) 又根据DFT的线性性质 = + IDFT X k jIDFT Y k ( ) ( ) 而 x n( ) ， y n( ) 都是实序列 ( ) ( ) ( ) ( ) Re Im x n z n y n z n = = z n IDFT Z k ( ) = ( ) z n IDFT Z k IDFT X k jY k ( ) = = + ( ) ( ) ( ) = + x n jy n ( ) ( ) 2024/10/21 7
3.N=16时，画出基-2按时间抽取法及按频率抽取法 的FFT流图（时间抽取采用输入倒位序，输出自然数 顺序，频率抽取采用输入自然顺序，输出倒位序)。 解： 自然序 倒位序 自然序 倒位序 0 0000 0000 0 8 1000 0001 1 1 0001 1000 8 9 1001 1001 9 2 0010 0100 4 101010 0101 5 3 0011 1100 12 111011 110113 4 0100 00102 121100 00113 5 0101 101010 131101 101111 6 0110 01106 141110 01117 7 0111 1110 14 15 1111 1111 15 2024/10/21 8
3. N=16 时，画出基 -2 按时间抽取法及按频率抽取法 的 FFT 流图（时间抽取采用输入倒位序，输出自然数 顺序，频率抽取采用输入自然顺序，输出倒位序）。 解： 自然序 倒位序 0 0000 0000 0 1 0001 1000 8 2 0010 0100 4 3 0011 1100 12 4 0100 0010 2 5 0101 1010 10 6 0110 0110 6 7 0111 1110 14 自然序 倒位序 8 1000 0001 1 9 1001 1001 9 10 1010 0101 5 11 1011 1101 13 12 1100 0011 3 13 1101 1011 11 14 1110 0111 7 15 1111 1111 15 2024/10/21 8
(1)按时间抽取的基-2FFT流图 N=16=2,L=4 共有L=4级蝶形运算，每级N/2=8个蝶形运算 Xm-1() X(k) X(j) X(i) 每个蝶形的两节点距离为2m1，即从第一级到 第四级两节点距离分别为1,2,4,8。 系数W的确定：r=(k)22m 即的二进制左移L-m位补零 2024/10/21 9
(1) 按时间抽取的基-2FFT流图 16 2 , 4 L N L = = = 共有L = 4级蝶形运算，每级N / 2 = 8个蝶形运算 每个蝶形的两节点距离为 ，即从第一级到 第四级两节点距离分别为1，2，4，8。 1 2 m− - 2 ( ) 2 r L m W r k N k L m = − 系数 的确定： 即 的二进制左移 位补零 r WN 1 ( ) X k m− 1 ( ) X j m− ( ) X k m ( ) X j m -1 2024/10/21 9
X(0) >X(1) X(2) →X3) X4) X5) X(6 →X8) →X9) oX(10) →X(11) →X(12) X(13) X(14) (15) →X(15) 2024/10/21 图P4-3(a) 10
2024/10/21 10