数 理 着考处 V,(n) 图7.3.1X(k)的一阶复递推计算流图 由式(73)可知,描述线性位不变系统输出y(m)与输入x(n) 关系的差分方程为 y,(n)-WNyk(n-D=x(n) (734 由式(7.34)可得 y, (n)=Wrky (n-1)+x(n) 7.35) 由于X(k)=y(N),为了得到X(k,因此,需要按式(7.3.5) 的方式递推,首先计算出y(1),y4(2,…,y(N-1),最后一步计算 出y4(N)
7.3.3 ( ) ( ) ( ) ( 1) ( ) (7.3.4) 7.3.4 ( ) ( 1) ( ) ( k k k Nk k k Nk y n xn y n W y n xn y n W y n xn − − − −= = −+ 由式（ ）可知，描述线性位不变系统输出 与输入 关系的差分方程为 由式（ ）可得 7.3.5) () ( ) ( ) 7.3.5 (1) (2) , ( 1) ( ) k kk k k Xk y N Xk y y yN y N = " − 由于 ，为了得到 ，因此，需要按式（ ） 的方式递推，首先计算出 ， ， ，最后一步计算 出
数 理 着考处 由于y2(m)是线性位不变系统的零状态响应,因此,线性位不变 系统的初始状态应为零,即y(-1)=0,那么,由式(73.5)可得 yk(O)=Wxyk(-1)+x(0)=x(0) yk(1)=WNy(0)+x(1)=Wxx(O)+x(1) y(2)=Wy(1)+x(2)=W2x(0)+Wxx(1)+x(2) y(N-1)=Wy(N-2)+X(N-1) =W-)2x(O)+W(=22x(1)+…+Wx(N-2)+x(N-1) V(M=WN DK(N-1)+x(N) WNKx(0)+W- -kx(1)+.+Wxkx(N-1)
2 ( ) ( 1) 0 7.3.5 (0) ( 1) (0) (0) (1) (0) (1) (0) (1) (2) (1) (2) (0) (1) (2) ( 1) ( 2) ( 1) k k k k Nk k k k Nk N k k k k Nk N N k k N k N y n y y Wy x x y Wy x Wx x y Wy x W x Wx x y N W y N xN W − − − − −− − − − = = −+ = = += + = += + + −= − + − = # 由于 是线性位不变系统的零状态响应，因此，线性位不变 系统的初始状态应为零，即 ，那么，由式（ ）可得 ( 1) ( 2) ( 1) (0) (1) ( 2) ( 1) ( ) ( 1) ( ) (0) (1) ( 1) N k N k k N N k k Nk Nk N k k NN N x W x W xN xN y N W y N xN W x W x W xN − − − − − − − − − + ++ −+ − = −+ = + ++ − "
数 理 着考处 般情况下,输入的有限长序列x(m)是复序列,利用式(7.3.5) 所示的一阶复递推计算方法来计算y(n)的一个值时,需要一次复乘 一次复加,一次复乘涉及4次实数乘法和2次实数加法,一次复加涉 及2次实数加法,因此,计算y(n)的一个值时,需要4次实数乘法和 4次实数加法。那么对于一个固定的k值,为了计算出X(k)=y(N 需要4N次实数乘法和4N次实数加法。因此,将DFT运算化为线性 卷和运算时,完成N个X(k)的运算需要的实数乘法次数为M。=4N2, 需要的实数加法次数为M=4N2。与直接计算DFT的方法相比,稍 微差一点,即实数乘法次数相同,而实数加法次数M增加了2N次。 然而这种方法的优点是避免了计算或存储系数Wk
( ) 7.3.5 ( ) 4 2 2 ( ) 4 4 ( ) ( ) 4 4 k k k x n y n y n k X k y N N N = DFT 一般情况下，输入的有限长序列 是复序列，利用式（ ） 所示的一阶复递推计算方法来计算 的一个值时，需要一次复乘 一次复加，一次复乘涉及 次实数乘法和 次实数加法，一次复加涉 及 次实数加法，因此，计算 的一个值时，需要 次实数乘法和 次实数加法。那么对于一个固定的 值，为了计算出 ， 需要 次实数乘法和 次实数加法。因此，将 运算化为线性 卷和运算时， 2 2 ( ) 4 4 2 c a a k N N Xk M N M N M N W − = = DFT 完成 个 的运算需要的实数乘法次数为 ， 需要的实数加法次数为 。与直接计算 的方法相比，稍 微差一点，即实数乘法次数相同，而实数加法次数 增加了 次。 然而这种方法的优点是避免了计算或存储系数
数 理 着考处 x2、 Goertzel算法的推导 下面介绍将上述迭代算法的实数乘法次数减少一半的方法, 即 Goertzel算法。 考虑到式(7.3.3),则有 1-V H(=) (1-WN2)1-W=-) H(=)(1-W (73.6) 式中,辅助线性位不变系统的转移函数为 2k丌 1< 7.37) 1-2 cos 2+z N 因此,完成的二阶递推计算的信流图,如图73,2所示
2、Goertzel算法的推导 1 1 1 1 1 2 Goertzel 7.3.3 1 ˆ ( ) ( )(1 ) , 1 (7.3.6) (1 )(1 ) 1 ˆ ( ) , 1 (7.3.7) 2 1 2cos k N k k k N N N W z H z Hz Wz z W z Wz H z z k z z N π − − − − − − − − = = − < ≤ ∞ − − = < ≤ ∞ − + 下面介绍将上述迭代算法的实数乘法次数减少一半的方法， 即 算法。 考虑到式（ ），则有 式中，辅助线性位不变系统的转移函数为 因此，完成的二阶递推计算的信流图，如图 所示。 7.3.2
数 理 着考处 图7.3.2X(k)的二阶递推计算流图 由式(73.7)可知,描述线性位不变系统输出(n)与输入x(n) 关系的差分方程为 D(n)-2cos 2kT (n-1)+y(n-2)=x(n) (73 由式(7.3.8)可得 2k丌 D (n)=2cos H(n-1)-k(n-2)+x(m) 73.9)
7.3.7 ˆ ( ) ( ) 2 ˆ ˆˆ ( ) 2cos ( 1) ( 2) ( ) (7.3.8) 7.3.8 2 ˆ ˆˆ ( ) 2cos ( 1) ( 2) ( ) (7.3.9) k k kk k kk y n xn k y n y n y n xn N k y n y n y n xn N π π − − + −= = − − − + 由式（ ）可知，描述线性位不变系统输出 与输入 关系的差分方程为 由式（ ）可得