Goertzel algorithm
The Goertzel algorithm is a method of digital signal processing, and is a special form of the discrete Fourier transform (DFT) dar. In contrast to the various fast calculation methods for the discrete Fourier transformation (FFT), that calculate always all of the discrete spectral components in a block, it is possible with the Goertzel algorithm to calculate only single discrete spectral components. It was developed in 1958 by Gerald Goertzel algorithm ( 1919-2002 ).
Function
The algorithm is based on a structure consisting of a digital filter, which is expanded to a state controller. The states divide the computation in the backward branch in which the time-domain sampled input values are loaded, and in a forward branch, which supplies the output signal. The backward loop is executed at each digital sample (English sample) and is structured as a recursive digital filter with two state memories and an accumulator. The forward branch is executed once after N samples and supplies from the State Save the calculated complex output value, the spectral component magnitude and phase.
By choosing the filter coefficients used therein, the frequency selectivity can be adjusted. By choosing the number of samples N can influence the quality factor. N can take any positive integer values.
Per spectral component, however, a separate Goertzel structure is necessary. Therefore, this algorithm is particularly advantageous and apply with less computing effort, if not the entire spectrum to be calculated, but only individual spectral components of it.
Detailed mathematical derivations of the algorithm can be found in the literature sources listed below.
Effort estimation
Per calculation of a spectral 4N additions and 4N multiplications are necessary for the Goertzel algorithm. Comparing this with the amount of computation effort in the fast Fourier transform of the Goertzel algorithm is always more efficient if less than 5/6 log2 ( N) is the spectral components are to be calculated. For each spectral component ( m ) is another Goertzelstruktur necessary, whereas the fast Fourier transform of the amount of calculation increases only Nlog2N.
The algorithm can be efficiently implemented in digital signal processors.
Applications
The applications are the detection of individual frequencies ( tone detection ) in a signal, such as in the detection of signaling frequencies in the multi- frequency selection method used in the telephone sector. In this case only the magnitude of the spectral component to be analyzed, which allows further simplification in the calculation.