Goertzel Algorithm - DFT Computations

DFT Computations

For the important case of computing a DFT term, the following special restrictions are applied.

• the filtering terminates at index where is the number of terms in the input sequence of the DFT
• the frequencies chosen for the Goertzel analysis are restricted to the special form

(7)

• the index number indicating the "frequency bin" of the DFT is selected from the set of index numbers

(8)

Making these substitutions into equation (6), and observing that the term, equation (6) then takes the following form.

(9)

We can observe that the right side of equation (9) is extremely similar to the defining formula for DFT term, the DFT term for index number K, but not exactly the same. The summation shown in equation (9) requires N+1 input terms, but only N input terms are available when evaluating a DFT. A simple but inelegant expedient is to extend the input sequence with one more artificial value . We can see from equation (9), the mathematical effect on the final result is the same as removing term from the summation, thus delivering the intended DFT value.

However, there is a more elegant approach that avoids the extra filter pass. From equation (1), we can note that when the extended input term is used in the final step,

(10)

Thus, the algorithm can be completed as follows:

• terminate the IIR filter after processing input term
• apply equation (10) to construct from the prior outputs and
• apply equation (2) with the calculated value, and with produced by the final direct calculation of the filter.

The last two mathematical operations are simplified by combining them algebraically.

(11)

Note that stopping the filter updates at term and immediately applying equation (2) rather than equation (11) misses the final filter state updates, yielding a result with incorrect phase.

The particular filtering structure chosen for the Goertzel Algorithm is the key to its efficient DFT calculations. We can observe that only one output value is used for calculating the DFT, so calculations for all the other output terms are omitted. Since the FIR filter is not calculated, the IIR stage calculations etc. can be discarded immediately after updating the first stage's internal state.

This seems to leave a paradox: to complete the algorithm, the FIR filter stage must be evaluated once using the final two outputs from the IIR filter stage, while for computational efficiency the IIR filter iteration discards its output values. This is where the properties of the direct-form filter structure are applied. The two internal state variables of the IIR filter provide the last two values of the IIR filter output, which are the terms required to evaluate the FIR filter stage.