Goertzel algorithm

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.

ω0, giving the frequency to be analysed, normalised to radians per sample.

The first stage calculates an intermediate sequence, s[n]=x[n]+2cos⁡(ω0)s[n−1]−s[n−2]. 1

The second stage applies the following filter to x[n] for s[−2]=s[−1]=0. To avoid aliasing hazards, frequency n=0:

e−jω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 edit For the important case of computing a DFT term, the following special restrictions are applied. The filtering terminates at index k indicating the "frequency bin" of the DFT is selected from the set of index numbers k \\in \\{ 0, 1, 2, ..., N-1 \\}. </math>"},"3":{"wt":"8"}},"i":0}}]}'>e+j2πk=1, equation (6) then takes the following form: y[N] = \\sum_{n=0}^{N} x[n]e^{-j 2 \\pi \\frac{n k}{N}}. </math>"},"3":{"wt":"9"}},"i":0}}]}'>X[k], the DFT term for index number N input terms are available when evaluating a DFT. A simple but inelegant expedient is to extend the input sequence x[N] from the summation, thus delivering the intended DFT value. However, there is a more elegant approach that avoids the extra filter pass. From equation (1), we can note that when the extended input term s[N] from the prior outputs s[N] value and with y[N] is used for calculating the DFT, so calculations for all the other output terms are omitted. Since the FIR filter is not calculated, the IIR stage calculations x[N]=0 applies a complex multiplier of magnitude 1 to the previous term y[N−1] represent equivalent signal power. It is equally valid to apply equation (11) and calculate the signal power from term X[k]: \\begin{align}\n X[k] \\, X'[k] & = y[N] \\, y'[N] = y[N-1] \\, y'[N-1] \\\\\n & = s^2[N-1] + s^2[N-2] - 2 \\cos \\left(2 \\pi \\frac{k}{N} \\right) \\, s[N-1] \\, s[N-2].\n\\end{align} </math>"},"3":{"wt":"12"}},"i":0}}]}'>x[N−1], 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: \\begin{align} \n c_r &= \\cos(2 \\pi \\tfrac{k}{N}), \\\\\n c_i &= \\sin(2 \\pi \\tfrac{k}{N}), \\\\\n y[N] &= c_r s[N-1] - s[N-2] + j c_i s[N-1].\n\\end{align} \n</math>"},"3":{"wt":"13"}},"i":0}}]}'>(Same IIR filter calculations as in the signal power implementation) XKreal = sprev * cr - sprev2; XKimag = sprev * ci; Phase detection edit This application requires the same evaluation of DFT term yi[n]. After that, the two complex-valued partial results can be recombined: y[n] = y_\\text{r}[n] + j y_\\text{i}[n].</math>"},"3":{"wt":"15"}},"i":0}}]}'>M DFT terms using K has complexity N, the Goertzel algorithm requires 2N+4 multiplications and N values has complexity 3log2(N) additions/subtractions per DFT bin, for each of the log⁡N, the advantage of the Goertzel algorithm is clear. But because FFT code is comparatively complex, the "cost per unit of work" factor log2(N). As a rule-of-thumb for determining whether a radix-2 FFT or a Goertzel algorithm is more efficient, adjust the number of terms M≤5N26Nlog2(N2) FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations 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. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants Mock, P. (March 21, 1985), "Add DTMF Generation and Decoding to DSP-μP Designs" (PDF), EDN, ISSN 0012-7515; also found in DSP Applications with the TMS320 Family, Vol. 1, Texas Instruments, 1989. ↑ Cheng, Eric; Hudak, Paul (January 2009), Audio Processing and Sound Synthesis in Haskell (PDF), archived from the original (PDF) on 2017-03-28 ↑ "Goertzel's Algorithm". Cnx.org. 2006-09-12. Retrieved 2014-02-03. ↑ Press; Flannery; Teukolsky; Vetterling (2007), "Chapter 12", Numerical Recipes, The Art of Scientific Computing, Cambridge University Press Further reading edit View original on Wikipedia | Back | FazBrowse Home