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 ONlogN 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πkN= W N k 2 k N W N k . Note that because W N - N k W N - N k always equals 1, the DFT equation can be rewritten as a convolution, or filtering operation: Note that this last expression can be written in terms of a recursive difference equation yn= W N - k yn-1+xn y n W N - k y n 1 x n where y-1=0 y 1 0 . The DFT coefficient equals the output of the difference equation at time n=N n N : Xk=yN 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 1 W N k z 1 gives the transfer function YzXz=Hz=11- W N - k z-1=1- W N k z-11- W N k + W N - k z-1-z-2=1- W N k z-11-2cos2πkNz-1-z-2 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 Figure 1

We want yn y n not for all nn, but only for n=N n N . We can thus compute only the recursive part, or just the left side of the flow graph in Figure 1, for n=01…N 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 yN=Xk y N X k . If the data are real-valued, only real/real multiplications and real additions are needed until the final multiply.

For certain frequencies, additional simplifications requiring even fewer multiplications are possible. (For example, for the DC ( k=0 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 logN N frequencies are needed, ONlogN O N N FFT algorithms that compute all frequencies simultaneously will be more efficient.