Goertzel algorithm
Encyclopedia
The Goertzel algorithm is a digital signal processing
(DSP) technique for identifying frequency
components of a signal, published by Gerald Goertzel in 1958. While the general Fast Fourier transform
(FFT) algorithm computes evenly across the bandwidth of the incoming signal, the Goertzel algorithm looks at specific, predetermined frequencies.
A practical application of this algorithm is recognition of the DTMF
tones produced by the buttons pushed on a telephone keypad.
It can also be used "in reverse" as a sinusoid synthesis function, which requires only 1 multiplication and 1 subtraction per generated sample.
, given an input sequence, 
:
where
and 
is some frequency of interest, in cycles per sample, which should be less than 1/2. This effectively implements a second-order IIR
filter with poles at
and 
, and requires only one multiplication (assuming 
is pre-computed), one addition and one subtraction per input sample. For real
inputs, these operations are real.
The Z transform of this process is
Applying an additional, FIR
, transform of the form
will give an overall transform of
The time-domain equivalent of this overall transform is
,
which becomes, assuming
for all 
or, the equation for the
-sample DFT
of
, evaluated for 
and multiplied by the scale factor 
.
Note that applying the additional transform Y(z)/S(z) only requires the last two samples of the
sequence. Consequently, upon processing 
samples 
, the last two samples from the 
sequence can be used to compute the value of a DFT
bin, which corresponds to the chosen frequency
as
For the special case often found when computing DFT
bins, where
for some integer, 
, this simplifies to
In either case, the corresponding power can be computed using the same cosine term required to compute
as
and 
can be retained in variables and new values of 
can be shifted through as they are computed, assuming that only the final two values of the 
sequence are required. The code may then be as follows:
Instead of storing the history of samples in an array it is also possible to process the incoming samples iteratively in real-time.
bin for a complex sequence of length N, this algorithm requires 2N multiplications and 4N additions/subtractions within the loop, as well as 4 multiplications and 4 additions/subtractions to compute
, for a total of 2N+4 multiplications and 4N+4 additions/subtractions (for real sequences, the required operations are half that amount). In contrast, the Fast Fourier transform
(FFT) requires 2log2N multiplications and 3log2N additions/subtractions per DFT
bin, but must compute all N bins simultaneously (similar optimizations are available to halve the number of operations in an FFT when the input sequence is real).
When the number of desired DFT
bins, M, is small (e.g., when detecting DTMF tones), it is computationally advantageous to implement the Goertzel algorithm, rather than the FFT. Approximately, this occurs when
or if, for some reason, N is not an integral power of 2 while you stick to a simple FFT algorithm like the 2-radix Cooley-Tukey FFT algorithm
, and zero-padding the samples out to an integral power of 2 would violate
Moreover, the Goertzel algorithm can be computed as samples come in, and the FFT algorithm may require a large table of N pre-computed sines and cosines to be efficient.
If multiplications are not considered as difficult as additions, or vice versa, the 5/6 ratio can shift between anything from 3/4 (additions dominate) to 1/1 (multiplications dominate).
Digital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...
(DSP) technique for identifying frequency
Frequency
Frequency is the number of occurrences of a repeating event per unit time. It is also referred to as temporal frequency.The period is the duration of one cycle in a repeating event, so the period is the reciprocal of the frequency...
components of a signal, published by Gerald Goertzel in 1958. While the general Fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(FFT) algorithm computes evenly across the bandwidth of the incoming signal, the Goertzel algorithm looks at specific, predetermined frequencies.
A practical application of this algorithm is recognition of the DTMF
Dual-tone multi-frequency
Dual-tone multi-frequency signaling is used for telecommunication signaling over analog telephone lines in the voice-frequency band between telephone handsets and other communications devices and the switching center. The version of DTMF that is used in push-button telephones for tone dialing is...
tones produced by the buttons pushed on a telephone keypad.
It can also be used "in reverse" as a sinusoid synthesis function, which requires only 1 multiplication and 1 subtraction per generated sample.
Explanation of algorithm
The Goertzel algorithm computes a sequence,, given an input sequence, :where
and is some frequency of interest, in cycles per sample, which should be less than 1/2. This effectively implements a second-order IIRInfinite impulse response
Infinite impulse response is a property of signal processing systems. Systems with this property are known as IIR systems or, when dealing with filter systems, as IIR filters. IIR systems have an impulse response function that is non-zero over an infinite length of time...
filter with poles at
and , and requires only one multiplication (assuming is pre-computed), one addition and one subtraction per input sample. For realReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
inputs, these operations are real.
The Z transform of this process is
Applying an additional, FIR
Finite impulse response
A finite impulse response filter is a type of a signal processing filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response filters, which have internal feedback and may continue to respond indefinitely...
, transform of the form
will give an overall transform of
The time-domain equivalent of this overall transform is
,which becomes, assuming
for all or, the equation for the
-sample DFTDiscrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
of
, evaluated for and multiplied by the scale factor .Note that applying the additional transform Y(z)/S(z) only requires the last two samples of the
sequence. Consequently, upon processing samples , the last two samples from the sequence can be used to compute the value of a DFTDiscrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
bin, which corresponds to the chosen frequency
asFor the special case often found when computing DFT
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
bins, where
for some integer, , this simplifies toIn either case, the corresponding power can be computed using the same cosine term required to compute
asImplementation
When implemented in a general-purpose processor, values for and can be retained in variables and new values of can be shifted through as they are computed, assuming that only the final two values of the sequence are required. The code may then be as follows:
s_prev = 0
s_prev2 = 0
normalized_frequency = target_frequency / sample_rate;
coeff = 2*cos(2*PI*normalized_frequency);
for each sample, x[n],
s = x[n] + coeff*s_prev - s_prev2;
s_prev2 = s_prev;
s_prev = s;
end
power = s_prev2*s_prev2 + s_prev*s_prev - coeff*s_prev*s_prev2;
Instead of storing the history of samples in an array it is also possible to process the incoming samples iteratively in real-time.
Computational complexity
To compute a single DFTDiscrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
bin for a complex sequence of length N, this algorithm requires 2N multiplications and 4N additions/subtractions within the loop, as well as 4 multiplications and 4 additions/subtractions to compute
, for a total of 2N+4 multiplications and 4N+4 additions/subtractions (for real sequences, the required operations are half that amount). In contrast, the Fast Fourier transformFast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(FFT) requires 2log2N multiplications and 3log2N additions/subtractions per DFT
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
bin, but must compute all N bins simultaneously (similar optimizations are available to halve the number of operations in an FFT when the input sequence is real).
When the number of desired DFT
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
bins, M, is small (e.g., when detecting DTMF tones), it is computationally advantageous to implement the Goertzel algorithm, rather than the FFT. Approximately, this occurs when
or if, for some reason, N is not an integral power of 2 while you stick to a simple FFT algorithm like the 2-radix Cooley-Tukey FFT algorithm
Cooley-Tukey FFT algorithm
The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform algorithm. It re-expresses the discrete Fourier transform of an arbitrary composite size N = N1N2 in terms of smaller DFTs of sizes N1 and N2, recursively, in order to reduce the...
, and zero-padding the samples out to an integral power of 2 would violate
Moreover, the Goertzel algorithm can be computed as samples come in, and the FFT algorithm may require a large table of N pre-computed sines and cosines to be efficient.
If multiplications are not considered as difficult as additions, or vice versa, the 5/6 ratio can shift between anything from 3/4 (additions dominate) to 1/1 (multiplications dominate).
External links
- http://netwerkt.wordpress.com/2011/08/25/goertzel-filter/ C Code implementation of iterative Goertzel algorithm
- http://www.eetimes.com/design/signal-processing-dsp/4024443/The-Goertzel-Algorithm
- http://cnx.org/content/m12024/latest/
- http://www.embedded.com/showArticle.jhtml?articleID=17301593