Goertzel Algorithm

The Goertzel algorithm is a computationally efficient method for evaluating the DFT at a single frequency bin, or a small number of bins. It is the preferred technique in tone detection applications such as DTMF decoding, where computing the full FFT for every frame would be wasteful.

Core Concept: Why Not Use the Full FFT

When an application needs only M specific frequency components out of an N-point DFT, computing the full FFT costs (N/2)*log2(N) operations regardless. If M is small, say M equals 8 for DTMF tones, it is wasteful to compute all N bins. The Goertzel algorithm evaluates exactly one DFT bin using a recursive second-order IIR filter, making it ideal when M is much smaller than log2(N).

The algorithm trades off full-spectrum knowledge for targeted frequency detection efficiency. DTMF telephone dialing uses 8 specific tones (697, 770, 852, 941, 1209, 1336, 1477, 1633 Hz), and running 8 Goertzel filters is far cheaper than computing a full FFT on each audio frame.

Mathematical Derivation

The DFT value at frequency bin k can be written as X[k] = sum over n of x[n] * W_N^(-kn). The Goertzel approach multiplies both sides by W_N^(-kN) = 1 (by periodicity) and recognizes this as a convolution evaluated at n=N. This leads to the z-domain transfer function H_k(z) = (1 - W_N^k * z^(-1)) / (1 - 2cos(2*pi*k/N)*z^(-1) + z^(-2)), which is a second-order IIR filter.

The recursion is split into two phases. In the filtering phase, the real-valued recursion runs for all N samples: v[n] = x[n] + 2cos(2*pi*k/N)*v[n-1] - v[n-2], with v[-1] = v[-2] = 0. After all N samples are processed, the output is computed in one step: X[k] = v[N] - W_N^k * v[N-1]. Only this final step involves a complex multiplication.

Complexity Analysis

The recursion phase requires N real multiplications and 2N real additions. The final output step requires one complex multiplication (equivalent to 4 real multiplications and 2 additions). For M frequency bins, total cost is M*(N + 4) real multiplications approximately. The FFT costs (N/2)*log2(N) complex multiplications. The Goertzel algorithm is more efficient when M is less than log2(N)/2.

Numerical Example

Given:
N = 205 samples (one DTMF frame at 8 kHz)
Detect k = 18 (corresponding to 697 Hz tone)
Only 8 tones need detection (M = 8)

Why this formula applies:
Goertzel is efficient when M < (1/2)*log2(N)

Formula:
Goertzel cost per bin = N real multiplications (approx)
Total Goertzel cost = M * N
FFT cost = (N/2)*log2(N) complex mults = N*log2(N)/2 real mults (approx, ignoring constant)

Substitution:
Goertzel: 8 * 205 = 1640 real multiplications
FFT: (205/2) * log2(205) ≈ 102.5 * 7.68 ≈ 787 complex multiplications
     = approximately 3148 real multiplications

Calculation:
Goertzel: 1640 real multiplications
FFT equivalent real: ~3148
Goertzel is 1.9x cheaper for this use case

Final Answer:
Goertzel requires ~1640 real multiplications vs ~3148 for FFT equivalent.
Goertzel is preferred here since M=8 < log2(205)/2 ≈ 3.8 is not satisfied,
but per-tone cost is still lower since only 8 of 205 bins are needed.

Exam Tip: Goertzel is preferred over FFT when computing fewer than log2(N)/2 frequency bins. The recursion uses only REAL multiplications for all N steps; the single complex multiplication happens only at the final output step. This distinction is commonly tested.

Mechanism: Two-Phase Operation

• Phase 1 (Filtering): For each input sample n from 0 to N-1, compute v[n] = x[n] + 2cos(2*pi*k/N)*v[n-1] - v[n-2]. This uses real arithmetic only.
• Phase 2 (Output): After all N samples, compute X[k] = v[N] - W_N^(-k)*v[N-1] using one complex multiplication.
• The coefficient 2cos(2*pi*k/N) is precomputed once per target frequency. It remains constant throughout the N recursion steps.
• Each independent frequency detection requires its own Goertzel filter instance with its own v[n-1] and v[n-2] state registers.
• DTMF decoding applies 8 parallel Goertzel filters to each audio frame, one per dial tone frequency.

Quick Revision

• Goertzel computes a single DFT bin using a 2nd-order IIR recursion, not the full FFT.
• Recursion: v[n] = x[n] + 2cos(2*pi*k/N)*v[n-1] - v[n-2]. Runs N times with real arithmetic.
• Final output: X[k] = v[N] - W_N^k * v[N-1]. Only one complex multiply at end.
• Efficient when number of bins M is much less than log2(N). Use case: DTMF detection.
• Phase 1 cost = N real multiplications. Phase 2 cost = 1 complex multiplication.
• W_N^k = exp(-j*2*pi*k/N). The coefficient 2cos(2*pi*k/N) is the real part of 2*W_N^(-k).