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. The algorithm was first described by Gerald Goertzel in 1958. Like the DFT, the Goertzel algorithm analyses one selectable frequency component from a discrete signal. Unlike direct DFT calculations, the Goertzel algorithm applies a single real-valued coefficient at each iteration, using real-valued arithmetic for real-valued input sequences. 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.
The algorithm The main calculation in the Goertzel algorithm has the form of a digital filter, and for this reason the algorithm is often called a Goertzel filter. The filter operates on an input sequence x [ n ] {\displaystyle x[n]} in a cascade of two stages with a parameter ω 0 {\displaystyle \omega _{0}} , giving the frequency to be analysed, normalised to radians per sample. The first stage calculates an intermediate sequence, s [ n ] {\displaystyle s[n]} :
The second stage applies the following filter to s [ n ] {\displaystyle s[n]} , producing output sequence y [ n ] {\displaystyle y[n]} :
The first filter stage can be observed to be a second-order IIR filter with a direct-form structure. This particular structure has the property that its internal state variables equal the past output values from that stage. Input values x [ n ] {\displaystyle x[n]} for n < 0 {\displaystyle n<0} are presumed all equal to 0. To establish the initial filter state so that evaluation can begin at sample x [ 0 ] {\displaystyle x[0]} , the filter states are assigned initial values s [ − 2 ] = s [ − 1 ] = 0 {\displaystyle s[-2]=s[-1]=0} . To avoid aliasing hazards, frequency ω 0 {\displaystyle \omega _{0}} is often restricted to the range 0 to π (see Nyquist–Shannon sampling theorem); using a value outside this range is not meaningless, but is equivalent to using an aliased frequency inside this range, since the exponential function is periodic with a period of 2π in ω 0 {\displaystyle \omega _{0}} . The second-stage filter can be observed to be a FIR filter, since its calculations do not use any of its past outputs. Z-transform methods can be applied to study the properties of the filter cascade. 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 n = 0 {\displaystyle n=0} :
Numerical stability It can be observed that the poles of the filter's Z transform are located at e + j ω 0 {\displaystyle e^{+j\omega _{0}}} and e − j ω 0 {\displaystyle e^{-j\omega _{0}}} , 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. A numerically stable version was proposed by Christian Reinsch.
DFT computations For the important case of computing a DFT term, the following special restrictions are applied.
The filtering terminates at index n = N {\displaystyle n=N} , where N {\displaystyle N} is the number of terms in the input sequence of the DFT. The frequencies chosen for the Goertzel analysis are restricted to the special form
The index number k {\displaystyle k} indicating the "frequency bin" of the DFT is selected from the set of index numbers
Making these substitutions into equation (6) and observing that the term e + j 2 π k = 1 {\displaystyle e^{+j2\pi k}=1} , equation (6) then takes the following form:
… excerpt ends here. Continue reading the full article.
