1-W吹21 1 1-W211-w*2-1 1-W啖z-1 1-(2c0s)21+2-21 the filtering operation can also be equivalently performed by xn] 1-W脓2-1 (2c0s)2+22 yhin], 1- with the associated flow graph depicted in OSB Figure 9.20. Since we're only evaluating the output of this filter at y[N],the multiplier-W need only be used at time nN.With this in mind,the algorithm requires N real multiplications and a single complex multiplication to compute Xk for a given k.This compares favorably to N complex multiplications as required by the canonical DFT equation and approximately Nlog2 N complex multiplications as required by the radix-2 FFT algorithms,when computing Xk]for a given k.A final note about the Goertzel algorithm:since it is not restricted to computingfor integer values of the algorithm has the convenient property that it can efficiently compute X(e)for arbitrary choice of w. 2 The Chirp Transform Algorithm The chirp transform algorithm,which is derived in detail in OSB Subsection 9.6.2,computes X(ej)for uniformly-spaced samples of w anywhere along the unit circle,as depicted in OSB Figure 9.25.The algorithm therefore computes X(eeo+kaa)=∑wo rinle--ao+kam，k=0,1,.,M-1 or equivalently, N-1 X(e)=∑xme-u",k=0,1,,M-1, n=0 where wk=w0+k△w,k=0,1,,M-1. Defining W=e-i4,this becomes N-1 X()= e-jwonwnk n=0 N-1 nle-j-onwn2wkp2w-(k-n)2 wmp[（e-owr2pz)*W-n2冈 3= � � , � � � �� � � 2 −1 1 − Wk N z 1 = N z−1 1 − W−k 1 − Wk z−1 N −1 1 − Wk N z −2 1 − 2 cos 2�k z−1 + z N the filtering operation can also be equivalently performed by −1 1 − Wk x[n] −� 1 − � 2 cos 2�k N � z z− −� yk[n], 1 + −2 z N with the associated flow graph depicted in OSB Figure 9.20. Since we’re only evaluating the output of this filter at yk[N], the multiplier −W k N need only be used at time n = N. With this in mind, the algorithm requires N real multiplications and a single complex multiplication to compute X[k] for a given k. This compares favorably to N complex multiplications as required by the canonical DFT equation and approximately N log2 N complex multiplications as required by the radix-2 FFT algorithms, when computing X[k] for a given k. A final note about the Goertzel algorithm: since it is not restricted to computing N−1 x[n]Wnk for integer values of k, the algorithm has the convenient property n=0 N that it can efficiently compute X(ej�) for arbitrary choice of �. The Chirp Transform Algorithm The chirp transform algorithm, which is derived in detail in OSB Subsection 9.6.2, computes X(ej�) for uniformly-spaced samples of � anywhere along the unit circle, as depicted in OSB Figure 9.25. The algorithm therefore computes N−1 x[n]e X −j(�0+k��)n (ej(�0+k��) ) = , k = 0, 1, . . . , M − 1 , n=0 or equivalently, N−1 X(ej�k ) = x[n]e−j�kn, k = 0, 1, . . . , M − 1, n=0 where �k = �0 + k��, k = 0, 1, . . . , M − 1. Defining W = e−j��, this becomes N−1 j�k X(e ) = e−j�0nWnk n=0 N−1 = x[n]e−j�0nWn2/2Wk2/2W−(k−n)2/2 n=0 −j�0nWn2/2x[n] � W−n2/2 = Wn2/2 e . 3