Some applications require only a few DFT frequencies.
One example is frequencyshift keying (FSK) demodulation, in which typically two frequencies
are used to transmit binary data; another example is DTMF, or touchtone
telephone dialing, in which a detection circuit must constantly monitor the line for
two simultaneous frequencies indicating that a telephone button is depressed.
Goertzel's algorithm reduces the number of realvalued multiplications by almost a factor
of two relative to direct computation via the DFT equation.
Goertzel's algorithm is thus useful for
computing a few frequency values; if many or most DFT values are needed,
FFT algorithms that compute all DFT samples in
ONlogN
O
N
N
operations are faster.
Goertzel's algorithm can be derived by converting the DFT equation
into an equivalent form as a convolution, which can be efficiently implemented as a digital filter.
For increased clarity, in the equations below the complex exponential is denoted as
e−(i2πkN)=
W
N
k
2
k
N
W
N
k
.
Note that because
W
N

N
k
W
N

N
k
always equals 1,
the DFT equation can be rewritten as a convolution, or filtering operation:
Xk=∑
n
=0N−1xn1
W
N
n
k
=∑
n
=0N−1xn
W
N

N
k
W
N
n
k
=∑
n
=0N−1xn
W
N
(
N

n
)
(

k
)
=(((
W
N

k
x0+x1)
W
N

k
+x2)
W
N

k
+…+xN−1)
W
N

k
X
k
n
N
1
0
x
n
1
W
N
n
k
n
N
1
0
x
n
W
N

N
k
W
N
n
k
n
N
1
0
x
n
W
N
(
N

n
)
(

k
)
W
N

k
x
0
x
1
W
N

k
x
2
W
N

k
…
x
N
1
W
N

k
(1)
Note that this last expression can be written in terms of a recursive
difference equation
yn=
W
N

k
yn−1+xn
y
n
W
N

k
y
n
1
x
n
where
y−1=0
y
1
0
.
The DFT coefficient equals the output of the difference equation at time
n=N
n
N
:
Xk=yN
X
k
y
N
Expressing the difference equation as a
ztransform and
multiplying both numerator and denominator by
1−
W
N
k
z−1
1
W
N
k
z
1
gives the transfer function
YzXz=Hz=11−
W
N

k
z−1=1−
W
N
k
z−11−((
W
N
k
+
W
N

k
)z−1−z−2)=1−
W
N
k
z−11−(2cos2πkNz−1−z−2)
Y
z
X
z
H
z
1
1
W
N

k
z
1
1
W
N
k
z
1
1
W
N
k
W
N

k
z
1
z
2
1
W
N
k
z
1
1
2
2
k
N
z
1
z
2
This system can be realized by the structure in
Figure 1
We want
yn
y
n
not for all nn, but only for
n=N
n
N
.
We can thus compute only the recursive part, or just the left side of
the flow graph in Figure 1, for
n=01…N
n
0
1
…
N
, which involves only a
real/complex product rather than a
complex/complex product as in a direct DFT, plus one complex
multiply to get
yN=Xk
y
N
X
k
.
The input
xN
x
N
at time
n=N
n
N
must equal 0!
A slightly more efficient
alternate implementation
that computes the full recursion only through
n=N−1
n
N
1
and combines the nonzero operations of the final recursion with the final complex multiply
can be found
here,
complete with pseudocode (for realvalued data).
If the data are realvalued, only real/real multiplications and real additions are needed until the
final multiply.
The computational cost of Goertzel's algorithm is thus
2N+2
2
N
2
real multiplies and
4N−2
4
N
2
real adds, a reduction of almost a factor of two in the number of real multiplies relative
to direct computation via the DFT equation.
If the data are realvalued, this cost is almost halved again.
For certain frequencies, additional simplifications requiring even fewer multiplications are possible.
(For example, for the DC
(
k=0
k
0
)
frequency, all the multipliers equal 1 and only additions are needed.)
A correspondence by C.G. Boncelet, Jr. describes some of these additional
simplifications.
Once again, Goertzel's and Boncelet's algorithms are efficient for a few DFT frequency samples; if more
than
logN
N
frequencies are needed,
ONlogN
O
N
N
FFT algorithms that compute all frequencies simultaneously will be more
efficient.

G Goertzel. (1958). An Algorithm for the Evaluation of Finite Trigonomentric Series. The American Mathematical Monthly.

C.G. Boncelet, Jr. (1986, Dec). A Rearranged DFT Algorithm Requiring N^2/6 Multiplications. IEEE Trans. on Acoustics, Speech, and Signal Processing, ASSP34(6), 16581659.