Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341:DISCRETE-TIME SIGNAL PROCESSING OpenCourseWare 2006 Lecture 20 The Goertzel Algorithm and the Chirp Transform Reading:Sections 9.0-9.2 and 9.6 in Oppenheim,Schafer Buck (OSB). In the previous lecture we discussed a well-known class of algorithms for computing the DFT efficiently.While the fast Fourier transform's various incarnations have gained considerable popularity,careful selection of an appropriate algorithm for computing the DFT in practice need not be limited to choosing between these so-called "fast"implementations.We'll there- fore focus in this lecture on two other techniques for computing the DFT:the Goertzel algorithm and the chirp transform. Before going further,think about the following question: Given a signal x[n]with corresponding 8-point DFT X[k],what is the most efficient way,in terms of total multiplications required,to compute X[5]from xn]? To start,note that using a radix-2 FFT algorithm isn't the best choice;judicious application of the canonical DFT equation is enough to beat it.Computing X[5]requires roughly 810g28=24 complex multiplications when employing a radix-2 FFT algorithm,since Xk fork =0,1,...,7 must first be computed.However,calculating]=e/)5n using OSB Equation 8.11 requires only 8 complex multiplications and is strikingly simple compared to the radix-2 FFT algorithms,depicted in OSB Figure 9.10.This example illustrates the point that while the FFT algorithms may be useful for a wide class of problems,they are by no means the most efficient choice in all situations. 1 The Goertzel Algorithm We'll now discuss the Goertzel Algorithm,an efficient method(in terms of multiplications)for computing Xk for a given k.The derivation of the algorithm,which is developed in OSB Section 9.2,begins by noting that the DFT can be formulated in terms of a convolution. N-1 X[附= xmw, WN=ej装nk n=0 N-1 ∑W-,ww=11 Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing OpenCourseWare 2006 Lecture 20 The Goertzel Algorithm and the Chirp Transform Reading: Sections 9.0 - 9.2 and 9.6 in Oppenheim, Schafer & Buck (OSB). In the previous lecture we discussed a well-known class of algorithms for computing the DFT efficiently. While the fast Fourier transform’s various incarnations have gained considerable popularity, careful selection of an appropriate algorithm for computing the DFT in practice need not be limited to choosing between these so-called “fast” implementations. We’ll there￾fore focus in this lecture on two other techniques for computing the DFT: the Goertzel algorithm and the chirp transform. Before going further, think about the following question: Given a signal x[n] with corresponding 8-point DFT X[k], what is the most efficient way, in terms of total multiplications required, to compute X[5] from x[n]? To start, note that using a radix-2 FFT algorithm isn’t the best choice; judicious application of the canonical DFT equation is enough to beat it. Computing X[5] requires roughly 8 log 2 8 = 24 complex multiplications when employing a radix-2 FFT algorithm, since X[k] for k = 0, 1, . . . , 7 must first be computed. However, calculating X[5] = 7 −j(2�/8)5n using OSB Equation n=0 x[n]e 8.11 requires only 8 complex multiplications and is strikingly simple compared to the radix-2 FFT algorithms, depicted in OSB Figure 9.10. This example illustrates the point that while the FFT algorithms may be useful for a wide class of problems, they are by no means the most efficient choice in all situations. The Goertzel Algorithm We’ll now discuss the Goertzel Algorithm, an efficient method (in terms of multiplications) for computing X[k] for a given k. The derivation of the algorithm, which is developed in OSB Section 9.2, begins by noting that the DFT can be formulated in terms of a convolution. N−1 X[k] = � x[n]Wnk N , WN = e−j 2� N nk n=0 N−1 = � x[n]W−k(N−n) N , W−kN N = 1 n=0 1