Goertzel Algorithm - Digital Signal Processing and Applications with the C6713 and C6416 DSK - page 495

x ( n ) y ( n )

2 cos (2 p k / N )

Z -1

- W N K

-1

Z -1

FIGURE G.2. Second-order Goertzel algorithm.

starting with the initial condition y k ( - 1) = 0 and running through N iterations to

obtain the solution X ( k ) y k ( N ). The x ( n )'s are processed in time order, and pro-

cessing can start as soon as the first one comes in. This structure needs the same
number of real multiplications and additions as the direct DFT but 1/ N the number
of trigonometric evaluations.
The second-order Goertzel algorithm can be obtained by multiplying the numer-
ator and denominator of (G.7) by 1

=

- W - k z -1 to give

1 - Wz

kNz

N k

+- 1

() =

Hz (G.8)

( )

- 1 - 2

12 - cos 2 p + z

The flow graph for this equation is shown in Figure G.2. Notice that the left half of
the graph contains feedback flows and the right half contains only feedforward
terms. Therefore, only the left half of the flow graph must be evaluated each itera-
tion. The feedforward terms need only be calculated once for y k ( N ). For real data,
there is only one real multiplication in this graph and only one trigonometric eval-
uation for each frequency. Scaling is a problem for fixed-point arithmetic realiza-
tions of this filter structure; therefore, simulation is extremely useful.
The second-order Goertzel algorithm is more efficient than the first-order
Goertzel algorithm. The first-order Goertzel algorithm (assuming a real input func-
tion) requires approximately 4 N real multiplications, 3 N real additions, and two
trigonometric evaluations per frequency component as opposed to N real multi-
plications, 2 N real additions, and two trigonometric evaluations per frequency
component for the second-order Goertzel algorithm. The direct DFT requires
approximately 2 N real multiplications, 2 N real additions, and 2 N trigonometric eval-
uations per frequency component.
This Goertzel algorithm is useful in situations where only a few points in the spec-
trum are necessary, as opposed to the entire spectrum. Detection of several discrete
frequency components is a good example. Since the algorithm processes samples in
time order, it allows the calculation to begin when the first sample arrives. In con-
trast, the FFT must have the entire frame in order to start the calculation.
Section 10.1 describes a DTMF project. It is implemented using the Goertzel's
algorithm on the C6416 DSK (see Appendix H) and can be readily transported to
the C6713 DSK.