Signal Processing Toolbox™

goertzel - Discrete Fourier transform using second-order Goertzel algorithm

Syntax

y = goertzel(x,i) y = goertzel(x,i,dim)

Description

goertzel computes the discrete Fourier transform (DFT) of specific indices in a vector or matrix.

y = goertzel(x,i) returns the DFT of vector x at the indices in vector i, computed using the second-order Goertzel algorithm. If x is a matrix, goertzel computes each column separately. The indices in vector i must be integer values from 1 to N, where N is the length of the first matrix dimension of x that is greater than 1. The resulting y has the same dimensions as x. If i is omitted, it is assumed to be [1:N], which results in a full DFT computation.

y = goertzel(x,i,dim) returns the discrete Fourier transform (DFT) of matrix x at the indices in vector i, computed along the dimension dim of x.

Note fft computes all DFT values at all indices, while goertzel computes DFT values at a specified subset of indices (i.e., a portion of the signal's frequency range). If less than log₂(N) points are required, goertzel is more efficient than the Fast Fourier Transform (fft).

Two examples where goertzel can be useful are spectral analysis of very large signals and dual-tone multi-frequency (DTMF) signal detection.

Examples

Estimate the frequency of the two tones generated by the "1" button on a telephone keypad.

% Frequency tones of the telephone pad (Hz)
f = [697 770 852 941 1209 1336 1477]; 
Fs = 8000; 
N = 205;	

% Tones of 25.6 ms 
tones = sum(sin(2*pi*[697;1209]*(0:N-1)/Fs)); 

% Indices of the DFT 
k = round(f/Fs*N); 

% DC is represented by the value 1  
ydft = goertzel(tones,k+1); 

% Frequencies at which DFT estimated  
estim_f = round(k*Fs/N);  

% Peaks detected around 697 & 1209 Hz 
stem(estim_f,abs(ydft))

Algorithm

goertzel implements this transfer function

where N is the length of the signal and k is the index of the computed DFT. k is related to the indices in vector i above as k = i - 1.

The signal flow graph for this transfer function is

Image of the signal flow graph

and it is implemented as

where

and

To compute X[k] for a particular k, the Goertzel algorithm requires 4N real multiplications and 4N real additions. Although this is less efficient than computing the DFT by the direct method, Goertzel uses recursion to compute

and

which are evaluated only at n = N. The direct DFT does not use recursion and must compute each complex term separately.

References

[1] Burrus, C.S. and T.W. Parks. DFT/FFT and Convolution Algorithms. John Wiley & Sons, 1985, pp. 32-26.