Goertzel's Algorithm 1.5 2004/05/14 13:56:56 GMT-5 2006/09/12 13:44:59.410 GMT-5 Douglas L. Jones dl-jones@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Kyle Evan Clarkson kclarks@rice.edu DFT FFT Goertzel Goertzel's algorithm reduces the cost of computing a single DFT frequency sample by almost a factor of two. It is useful for situations requiring only a few DFT frequencies. Some applications require only a few DFT frequencies. One example is frequency-shift keying (FSK) demodulation, in which typically two frequencies are used to transmit binary data; another example is DTMF, or touch-tone telephone dialing, in which a detection circuit must constantly monitor the line for two simultaneous frequencies indicating that a telephone button is depressed. Goertzel's algorithm reduces the number of real-valued multiplications by almost a factor of two relative to direct computation via the DFT equation. Goertzel's algorithm is thus useful for computing a few frequency values; if many or most DFT values are needed, FFT algorithms that compute all DFT samples in O N N operations are faster. Goertzel's algorithm can be derived by converting the DFT equation into an equivalent form as a convolution, which can be efficiently implemented as a digital filter. For increased clarity, in the equations below the complex exponential is denoted as 2 k N W N k . Note that because W N - N k always equals 1, the DFT equation can be rewritten as a convolution, or filtering operation: X k n N 1 0 x n 1 W N n k n N 1 0 x n W N - N k W N n k n N 1 0 x n W N ( N - n ) ( - k ) W N - k x 0 x 1 W N - k x 2 W N - k … x N 1 W N - k Note that this last expression can be written in terms of a recursive difference equation y n W N - k y n 1 x n where y 1 0 . The DFT coefficient equals the output of the difference equation at time n N : X k y N Expressing the difference equation as a z-transform and multiplying both numerator and denominator by 1 W N k z 1 gives the transfer function Y z X z H z 1 1 W N - k z 1 1 W N k z 1 1 W N k W N - k z 1 z 2 1 W N k z 1 1 2 2 k N z 1 z 2 This system can be realized by the structure in

We want y n not for all n, but only for n N . We can thus compute only the recursive part, or just the left side of the flow graph in , for n 0 1 … N , which involves only a real/complex product rather than a complex/complex product as in a direct DFT, plus one complex multiply to get y N X k . The input x N at time n N must equal 0! A slightly more efficient alternate implementation that computes the full recursion only through n N 1 and combines the nonzero operations of the final recursion with the final complex multiply can be found here, complete with pseudocode (for real-valued data). If the data are real-valued, only real/real multiplications and real additions are needed until the final multiply. The computational cost of Goertzel's algorithm is thus 2 N 2 real multiplies and 4 N 2 real adds, a reduction of almost a factor of two in the number of real multiplies relative to direct computation via the DFT equation. If the data are real-valued, this cost is almost halved again. For certain frequencies, additional simplifications requiring even fewer multiplications are possible. (For example, for the DC ( k 0 ) frequency, all the multipliers equal 1 and only additions are needed.) A correspondence by C.G. Boncelet, Jr. describes some of these additional simplifications. Once again, Goertzel's and Boncelet's algorithms are efficient for a few DFT frequency samples; if more than N frequencies are needed, O N N FFT algorithms that compute all frequencies simultaneously will be more efficient. G Goertzel An Algorithm for the Evaluation of Finite Trigonomentric Series The American Mathematical Monthly 1958 C.G. Boncelet, Jr. A Rearranged DFT Algorithm Requiring N^2/6 Multiplications IEEE Trans. on Acoustics, Speech, and Signal Processing 1986 ASSP-34 6 1658-1659 Dec