Goertzel algorithm

The Goertzel algorithm is a method from digital signal processing and represents a special form of discrete Fourier transformation (DFT). In contrast to the various fast calculation methods used in discrete Fourier transformation (FFT) , which always calculate all discrete spectral components in one block , it is possible with the Goertzel algorithm to only calculate individual discrete spectral components. The algorithm was developed in 1958 by Gerald Goertzel (1919–2002).

function

The algorithm is based on a structure consisting of a digital filter that has been expanded to include a state control. The states divide the calculation into the backward branch, in which the input values ​​sampled in the time domain are loaded, and in a forward branch, which supplies the output signal. The rearward loop (engl. At each digital sample of sample ) to pass through and is as a recursive digital filter constructed with two state memories and an accumulator. The forward branch is only run through once after N sampled values ​​and supplies the calculated complex output value, the spectral component according to magnitude and phase, from the state memories.

The frequency selectivity can be adjusted through the choice of the filter coefficients used. The quality factor can be influenced by the choice of the number of samples N. N can have any natural values.

However, an independent Goertzel structure is required for each spectral component. This algorithm is therefore particularly advantageous and requires less computational effort when the complete spectrum is not to be calculated, but only individual spectral components from it.

Detailed mathematical derivations of the algorithm can be found in the literature sources given below.

algorithm

The real part and the imaginary part of a spectral component of a discrete signal are determined using a recursive algorithm. The starting conditions are . over ${\displaystyle s}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle \omega }$ ${\displaystyle U_{N+2}=U_{N+1}=0}$

${\displaystyle U_{k}=s_{k}+2\,U_{k+1}\cos \omega -U_{k+2}\qquad }$ For ${\displaystyle k=N,(N-1),\dots ,1}$

surrendered

${\displaystyle C=s_{0}+U_{1}\,\cos \omega -U_{2}}$

${\displaystyle S=U_{1}\sin \omega }$

The angle function and only needs to be accessed once. ${\displaystyle \cos \omega }$ ${\displaystyle \sin \omega }$

Estimation of effort

In the Goertzel algorithm, additions / subtractions and multiplications are necessary for each calculation of a spectral component . If you compare this effort with the calculation effort for the fast Fourier transformation , the Goertzel algorithm is always more efficient when less than 5/6 log ₂ ( N ) spectral components are to be calculated. For each spectral component (m) is another Goertzelstruktur necessary while in the fast Fourier transform of the computational effort with N log ₂ N increases. ${\displaystyle 2N+2}$ ${\displaystyle N+2}$

The algorithm can be implemented efficiently in digital signal processors .

Applications

The applications are in the detection of individual frequencies ( tone detection ) in a signal, for example in the detection of the signaling frequencies in the multi-frequency dialing method used in the telephone sector . In this case, only the amount of the spectral component has to be evaluated, which allows further simplifications in the calculation.

literature

• Gerald Goertzel: An Algorithm for the Evaluation of Finite Trigonometric Series. In: American Math. Monthly. Vol 65. 1958, pp. 34-35.
• Alan V. Oppenheim: Time Discrete Signal Processing. Oldenbourg Verlag, Munich 1999, ISBN 3-486-24145-1 (German translation of Discrete-Time Signal Processing , Prentice Hall Inc. 1989)

Web links

• Goertzel algorithm function call in MATLAB (Engl.)

Individual evidence

1. ^ Karl Dirk Kammeyer, Kristian Kroschel: Digital signal processing: filtering and spectral analysis with MATLAB exercises . Springer-Verlag, 2009, ISBN 978-3-8348-0610-9 , pp. 274 ( google.de [accessed June 24, 2017]).