The Goertzel algorithm is a technique in digital signal processing (DSP) for efficient evaluation of the individual terms of the discrete Fourier transform (DFT).
It is useful in certain practical applications, such as recognition of dual-tone multi-frequency signaling (DTMF) tones produced by the push buttons of the keypad of a traditional analog telephone.
[1] Like the DFT, the Goertzel algorithm analyses one selectable frequency component from a discrete signal.
For covering a full spectrum (except when using for continuous stream of data where coefficients are reused for subsequent calculations, which has computational complexity equivalent of sliding DFT), the Goertzel algorithm has a higher order of complexity than fast Fourier transform (FFT) algorithms, but for computing a small number of selected frequency components, it is more numerically efficient.
The simple structure of the Goertzel algorithm makes it well suited to small processors and embedded applications.
The Goertzel algorithm can also be used "in reverse" as a sinusoid synthesis function, which requires only 1 multiplication and 1 subtraction per generated sample.
This particular structure has the property that its internal state variables equal the past output values from that stage.
The Z transform of the first filter stage given in equation (1) is The Z transform of the second filter stage given in equation (2) is The combined transfer function of the cascade of the two filter stages is then This can be transformed back to an equivalent time-domain sequence, and the terms unrolled back to the first input term at index
, on a circle of unit radius centered on the origin of the complex Z-transform plane.
This property indicates that the filter process is marginally stable and vulnerable to numerical-error accumulation when computed using low-precision arithmetic and long input sequences.
[7] For the important case of computing a DFT term, the following special restrictions are applied.
[8] We can see from equation (9) that the mathematical effect on the final result is the same as removing term
is used in the final step, Thus, the algorithm can be completed as follows: The last two mathematical operations are simplified by combining them algebraically: Note that stopping the filter updates at term
[9] The particular filtering structure chosen for the Goertzel algorithm is the key to its efficient DFT calculations.
Examining equation (6), a final IIR filter pass to calculate term
It is equally valid to apply equation (11) and calculate the signal power from term
Both cases lead to the following expression for the signal power represented by DFT term
It is possible[10] to organise the computations so that incoming samples are delivered singly to a software object that maintains the filter state between updates, with the final power result accessed after the other processing is done.
, and filter iterations are terminated, equation (11) must be applied to evaluate the DFT term.
The final calculation uses complex-valued arithmetic, but this can be converted into real-valued arithmetic by separating real and imaginary terms: Comparing to the power-spectrum application, the only difference are the calculation used to finish: This application requires the same evaluation of DFT term
Then the signal phase can be evaluated as taking appropriate precautions for singularities, quadrant, and so forth when computing the inverse tangent function.
After that, the two complex-valued partial results can be recombined: In the complexity order expressions, when the number of calculated terms
But because FFT code is comparatively complex, the "cost per unit of work" factor
is often larger for an FFT, and the practical advantage favours the Goertzel algorithm even for
As a rule-of-thumb for determining whether a radix-2 FFT or a Goertzel algorithm is more efficient, adjust the number of terms
in the data set upward to the nearest exact power of 2, calling this
, and the Goertzel algorithm is likely to be faster if FFT implementations and processing platforms have a significant impact on the relative performance.
Some FFT implementations[11] perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work."
FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage.
Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data.