Efficient Fixed-Point Implementation of the Goertzel Algorithm on a Blackfin DSP

Hazarathaiah Malepati and Yosi Stein

January 18, 2010

Hazarathaiah Malepati and Yosi Stein

This "Product How-To" article focuses how to use a certain product in an embedded system and is written by a company representative.

In this article, we will briefly discuss the Goertzel algorithm flow and its fixed-point implementation on the Analog Devices Blackfin BF5xx processor family using the Blackfin's special arithmetic modes. In particular, we will discuss an efficient implementation of 16.16 fixed-point multiplications on the 16-bit MAC-friendly Blackfin DSP processor.

Goertzel Algorithm
The Goertzel algorithm is widely used for the detection of a few frequencies in a given signal input.

Though an N-point Fast Fourier Transform (FFT) algorithm efficiently computes N Discrete Fourier Transform (DFT) coefficients given the N input samples, some applications, such as dual tone multi-frequency (DTMF) don't require all the DFT coefficients. In such cases, the Goertzel algorithm can be used to compute the required DFT coefficients (or frequencies) of the input signal x[n] efficiently using a second order linear filter.

In [Pro1992], a recursive expression for computing k^th DFT coefficient is derived from the standard DFT equation as:

Now, the Z domain transfer function governing the above difference equation can be expressed as:

The final expressions for implementation of the Goertzel algorithm are obtained from the above system functions as below:

From Equation (1),

From Equation (4), we are only interested in the infinite impulse response (IIR) filter output to compute the DFT coefficient. Thus, we need not compute the finite impulse response (FIR) filter Y_k[z]/S_k[z] output for each input sample s_k.

The magnitude square value of k^th DFT coefficient can be obtained from Equation (4) as:

The computation s_k for using Equation (3) requires one multiply and two add operations per sample. In applications like DTMF detection, we are only concerned with the magnitude square of the k_th DFT coefficient, i.e. |X[k]², as given in Equation (5).

Unlike DFT, which requires storing many twiddle factors, we need not store any coefficients in the Goertzel algorithm. We use only one coefficient (q = 2cos(2πk/N) ) in the computation and this can be held using a single data register.