Some applications require only a few DFT frequencies.
One example is frequency-shift keying (FSK) demodulation, in which typically two frequencies
are used to transmit binary data; another example is DTMF, or touch-tone
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 real-valued 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
z-transform 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 real-valued data).
If the data are real-valued, 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 real-valued, 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, ASSP-34(6), 1658-1659.
Alternate FFT Structures
