9.1.2 The Goertzel Algorithm ◆Goertzel Filter: n-eNn]="4刊 x(n] yk[n] =H(2)=i 7 21 k=0,1,.,W-1 for causal LTI system x[n]=0,n<0→yk[n]=0,n<0 [n]=[n-l]W*+n,n=01,,N,-1]=-0 x[n]is a complex X[]=[nlw,k=0,1,,N-l→ X-∑[nWg n=0 Computational complexity for one X[k]:for all X[k]: 4N real multiplications;4N real additions;x N Slightly less efficient than the direct method(4N,4N-2);x N But it avoids computation and storage of W (N2) W吸N个)10 9.1.2 The Goertzel Algorithm ◆Goertzel Filter: (2 / ) [ ] [ ] j N kn h n u n e  = ( ) 1 1 1 k k N H z W z = − − − [ ] [ 1] [ ], k y n y n W x n k k N − = − +     , k n N X k y n = = kn ◆ WN But it avoids computation and storage of [ ] kn W u n N − = n N = 0,1,..., , k N = 0,1,..., -1 x n[ ] is a complex for causal LTI system x[n]=0, n<0 → yk [n]=0, n<0 k N = 0,1,..., -1 (N2 个) k WN (N 个) , 1 z  yk [ 1] 0 − = (    )(    ) (    ) [ ] [ 1] [ 1] [ ] [ ] k k y n y n y n W W k k k N N Re Im Re x n x Im Re j j jIm n − − = − + − + + +            1 0 [ ] [ ] N kn kn N N n X k x n W Re Re Im x n W Im − = = −    1 0 [ ] N kn N n X k x nW − = = ×N ◆Computational complexity for one X[k]: ◆4N real multiplications; 4N real additions; ◆Slightly less efficient than the direct method(4N, 4N-2); for all X[k]: ×N         (        ) (    ) [ ] [ 1] [ 1] [ 1] [ 1] [ ] [ ] k k k k N k N k k k N k N Re Re Im Im Re Im Im Re y n y n W y n W y n W y n W Re x n jIm x j n − − − − = − − − − + − + + +