Герцель алгоритмі: дискретті Фурье түрлендірілімінің тиімді есептеуі

Technique in digital signal processing
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.

It can be observed that the poles of the filter's Z transform are located at and , 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.

This application requires the same evaluation of DFT term , as discussed in the previous section, using a real valued or complex valued input stream. Then the signal phase can be evaluated as

taking appropriate precautions for singularities, quadrant, and so forth when computing the inverse tangent function.

Since complex signals decompose linearly into real and imaginary parts, the Goertzel algorithm can be computed in real arithmetic separately over the sequence of real parts, yielding , and over the sequence of imaginary parts, yielding After that, the two complex valued partial results can be recombined: