3.2 Goertzel's algorithm

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 fortwo 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 forcomputing a few frequency values; if many or most DFT values are needed, FFT algorithms that compute all DFT samples in $O(N\lg 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 $e^{-(i\frac{2\pi k}{N})}=W_N^k$ . Note that because $W_N^{-Nk}$ always equals 1, the DFT equation can be rewritten as a convolution, or filtering operation:

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

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 $\lg N$ frequencies are needed, $O(N\lg N)$ FFT algorithms that compute all frequencies simultaneously will be more efficient.