数 理 着考处 为了得到(N),需要按式(739)的方式递推,首先计算出( j(2),…,(N-1,最后一步计算出(N 由于(m)是线性位不变系统的零状态响应,因此,线性位不变系 统的初始状态应为零,即(-2)=(-1)=0,那么,由式(739)可得 j(0)=2c0s25zj(-1)-(-2)+x(0)=x0) 2k j(1)=2cos=j(0)-(-1)+x(1)=2 2kT (0)+x(1) y,(2)=2 coS 2kπ()-y2(0)+x(2) D (N-1)=2cos 2k兀;(N 2)-y(N-3)+x(N-1) J,(N)=2cos (N-1)-元(N-2)
ˆ ( ) 7.3.9 ˆ (1) ˆ (2) , ( 1) ˆ ˆ ( ) ˆ ( ) ˆ ( 2) ( 1) 0 ˆ 7.3.9 2 ˆ (0) 2cos ( 1) ( 2) (0) (0) ˆ ˆ 2 ˆ (1) 2cos k k kk k k k k k kk k y N y y yN y N y n y y k y y y xx N k y π − −= −= = −− −+ = = " 为了得到 ，需要按式（ ）的方式递推，首先计算出 ， ， ，最后一步计算出 。 由于 是线性位不变系统的零状态响应，因此，线性位不变系 统的初始状态应为零，即 ，那么，由式（ ）可得 2 ˆ ˆ (0) ( 1) (1) 2cos (0) (1) 2 ˆ (2) 2cos (1) (0) (2) ˆ ˆ 2 ˆ ( 1) 2cos ( 2) ( 3) ( 1) ˆ ˆ 2 ˆ ( ) 2cos ( 1) ( 2) ˆ ˆ k k k kk k k k k k k k y y x xx N N k y yy x N k y N y N y N xN N k yN yN yN N π π π π π − −+ = + = −+ − = − − −+ − = − − − #
数 理 着考处 若有限长序列x(n)是复序列,利用式(739)所示的二阶递推计算 方法来计算(n)的一个值时,需要一次实数与复数的乘法运算和两次 复加运算。实数与复数的乘法涉及2次实数乘法,一次复加涉及2次实 数加法,那么计算y(n)的一个值时,需要2次实数乘法和4次实数加法 因此,对于一个固定的k值,由于计算(1)及(N)两值时,仅需要 次实数与复数的乘法运算和一次复加运算。为了得到(N),需要的实 数乘法次数为M=2N,需要的实数加法次数为M=2N 由图732可知,y(m)与少(n)具有下述关系 D,(n)=jk(n)-WNh(n-1) 7.3.10 由式(7.3.10)可得 y(N)=(N)-W(N-1) (73.11)
( ) 7.3.9 ˆ ( ) 2 2 ˆ ( ) 2 4 ˆ ˆ (1) ( ) ˆ ( k k k k k x n y n y n k yy N y 若有限长序列 是复序列，利用式（ ）所示的二阶递推计算 方法来计算 的一个值时，需要一次实数与复数的乘法运算和两次 复加运算。实数与复数的乘法涉及 次实数乘法，一次复加涉及 次实 数加法，那么计算 的一个值时，需要 次实数乘法和 次实数加法。 因此，对于一个固定的 值，由于计算 及 两值时，仅需要一 次实数与复数的乘法运算和一次复加运算。为了得到 ) 2 2 7.3.2 ( ) ( ) ˆ ( ) ( ) ( 1) (7.3.10) ˆ ˆ 7.3.10 ( ) ( ) ( 1) ˆ ˆ c c k k k k k Nk k k k Nk N M N M N yn yn y n y n Wy n y N y N Wy N = = =− − =− − ，需要的实 数乘法次数为 ，需要的实数加法次数为 。 由图 可知， 与 具有下述关系 由式（ ）可得 (7.3.11)
数 理 着考处 由式(7311)可知,对于一个固定的k值,利用(N-1)及(N)来 计算y(N时,需要一次复乘运算和一次复加运算,一次复乘涉及4次实 数乘法和2次实数加法,一次复加涉及2次实数加法,因此,利用(N-1) 及(N)来计算出y(N时,需要4次实数乘法和4次实数加法,考虑到计 算(N)的一个值时,需要2N次实数乘法和4(N-1次实数加法,那么, 计算y(N)的一个值时,需要2N+4次实数乘法和4(N-1)+4=4N次实数 加法,因此,完成N个y(N)=X(k)的运算时,需要的实数乘法次数M和 实数加法次数M分别为 (1)M。=2N(N+2) (2)M=4N2 与直接计算DFT的方法相比,实数乘法的次数M大约减少了一半,实 数加法的次数M增加了2N次, Goertzel算法的优点是避免了计算或存储系 数cos(2k/N)和W
7.311 ( 1) ( ) ˆ ˆ () 4 2 2( ˆ 1 ) ˆ () () 4 4 ˆ ( ) 2 4( 1) ( ) k k k k k k k k k yN yN y N y N yN yN y N N N y N − − − 由式（ ）可知，对于一个固定的 值，利用 及 来 计算 时，需要一次复乘运算和一次复加运算，一次复乘涉及 次实 数乘法和 次实数加法，一次复加涉及 次实数加法，因此，利用 及 来计算出 时，需要 次实数乘法和 次实数加法，考虑到计 算 的 一 个值时，需要 次实数乘法和 次实数加法，那么， 计算 的一个值时， 2 2 4 4( 1) 4 4 ( ) () 1 2 ( 2) 2 4 2 cos (2 ) k c a c a c a k N N NN N y N Xk M M M NN M N M M N Goertzel kN W π + − + = = = + = DFT 需要 次实数乘法和 次实数 加法，因此，完成 个 的运算时，需要的实数乘法次数 和 实数加法次数 分别为 （ ） （ ） 与 直 接计算 的方法相比，实数乘法的次数 大约减少了一半，实 数 加 法 的次数 增加了 次， 算法的优点是避免了计算或存储系 数 和
数 理 着考处 x3、算法的讨论 为了说明 Goertzel算法的优点,我们来研究一下如何计算 有限长实序列x(n)的Z变换X(z)在Z平面单位圆周上位于共轭位 置的值,即X(k)和X(N-k 若定义 (n)=x(n)*W(n)=∑x(m)R、(mWX"m(n-m) x(mR(mWM (n-m)k 由式(73.12)可得 (N)=∑x(m)R、(m=m=∑x(m)R(m)Wm n=-00 N-1 ∑x(mWm=∑x(nWwm=X(N-k) 甲X(N-k)=(m)=N (73.13)
3、算法的讨论 ( ) ( ) Goertzel () () () ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) nk n m k kN N N m n n mk N N m xn Z X z Z Xk XN k r n x n W u n x m R mW u n m x m R mW +∞ − =−∞ − =−∞ − =∗ = − = ∑ ∑ 为了说明 算法的优点，我们来研究一下如何计算 有限长实序列 的 变换 在 平面单位圆周上位于共轭位 置的值，即和 。 若定义 ( ) 1 1 ( ) ( ) 0 0 (7.3.12) 7.3.12 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (7.3.13) N N N m k mk k N N N N m m N N mN k nN k N N m n k nN r N x m R mW x m R mW x mW x nW X N k XN k r n − − =−∞ =−∞ − − − − = = = = = = = =− − = ∑ ∑ ∑ ∑ 由式（ ）可得 即
数 理 着考处 由式(73.13)可知,X(N-k)正是有限长序列x(n)=x(n)R(n) 作用于单位冲激响应为hn)=Wuv(m)的线性位不变系统时,系统的 零状态响应r(n)在n=N位的输出值 考虑到h(m)=WN"u(m),则描述线性位不变系统的转移函数为 H()=1-kx1 1<z≤∞ (73.14) 式(73.14)又可以写成 1-W-kz-1 H (1-=2)1-=)=B(=W=.11≤∞ (73.15) 式中,辅助线性位不变系统的转移函数为 (2 2k丌 (73.16) cOS 因此,完成X(N-k)二阶递推计算的信流图,如图7.3.3所示
1 7.3.13 ( ) ( ) ( ) ( ) () () ( ) () () 1 ( ) , 1 (7.3.14) 1 7.3.14 N nk N k nk N k N XN k xn xnR n hn W un rn n N hn W un H z z W z− − = = = = = < ≤∞ − 由式（ ）可知， 正是有限长序列 作用于单位冲激响应为 的线性位不变系统时，系统的 零状态响应 在 位的输出值。 考虑到 ，则描述线性位不变系统的转移函数为 式（ ）又可 1 1 1 1 1 2 1 ˆ ( ) ( )(1 ), 1 (7.3.15) (1 )(1 ) 1 ˆ ( ) , 1 (7.3.16) 2 1 2cos ( ) 7.3.3 k N k k k N N N W z H z Hz W z z Wz W z H z z k z z N XN k π − − − − − −− − − − = = − < ≤ ∞ − − = < ≤ ∞ − + − 以写成 式中，辅助线性位不变系统的转移函数为 因此，完成 的二阶递推计算的信流图，如图 所示