How to Learn the Goertzel Algorithm: Single-Bin DFTs, Second-Order Recurrences, Tone Detection and Numerical Stability

Wait, What?

If you only need one note from a spectrum, computing the whole FFT can be the wrong question.

The Goertzel algorithm evaluates one selected frequency component of a finite sequence using a second-order recurrence. It is famous for tone detection, especially DTMF-style applications, because it lets small processors measure a small number of frequencies without computing an entire spectrum.

For learners, Goertzel is a compact route from complex exponentials to recurrence relations. For professionals, it opens harder questions: when does Goertzel beat an FFT, how should windowing and frequency mismatch be handled, how do amplitude and phase scale, what happens in fixed-point arithmetic, and where does numerical stability become the limiting factor?

Quick Answer

Learn Goertzel through DFT meaning → one-bin evaluation → recurrence derivation → state update → final complex output → magnitude/power → frequency-bin choice → windowing → block length trade-offs → FFT crossover → numerical stability → embedded implementation and testing.

1. Start with the DFT job

For an N-sample sequence x[n], the kth DFT coefficient is:

X[k] = Σ x[n] exp(-j 2πkn/N),  n = 0..N-1

If you need all N frequency bins, an FFT is usually the right family of algorithms. But if you need only one or a few selected frequencies, evaluating a complete FFT may do much more work than necessary. Goertzel reorganizes the single-bin calculation into a recurrence with one real coefficient per sample for real input.

2. The recurrence

For target angular frequency ω = 2πk/N, define:

c = 2 cos(ω)
s[n] = x[n] + c s[n-1] - s[n-2]

with initial states zero. After processing the block, the final states can be combined to recover the complex DFT coefficient at the selected frequency. One common form is:

real = s[N-1] - cos(ω) * s[N-2]
imag = sin(ω) * s[N-2]
X = real - j * imag

Index conventions differ across derivations, so do not memorize a formula without checking which two final state variables it assumes. The invariant to understand is that the recurrence has accumulated exactly the weighted history needed for one finite trigonometric sum.

3. Work one tiny block by hand

Use N = 8 and target k = 1. Compute ω = 2π/8 = π/4 and c = 2cos(π/4) = √2. Feed a simple signal such as x = [1,0,0,0,0,0,0,0]. Because an impulse has equal magnitude in every DFT bin, the resulting coefficient should have magnitude 1 under the unnormalised DFT convention.

Then feed a pure cosine exactly at bin k. Trace each recurrence state. This is slower than coding but far faster than debugging an implementation whose sign or final-state formula is wrong.

4. Why the method is efficient for a few frequencies

Each sample update needs a small constant number of arithmetic operations. One target frequency therefore costs O(N). M target frequencies cost O(MN). An FFT costs roughly O(N log N) to obtain the whole transform.

That gives the real decision rule: Goertzel is attractive when M is small relative to N and when streaming or memory constraints favour a tiny state per target frequency. Once you need many bins, an FFT usually wins. The crossover depends on implementation, vectorization, hardware, real-versus-complex transforms and library quality; benchmark the actual platform instead of repeating a universal percentage threshold.

5. Frequency bins are a measurement decision

The standard DFT bins occur at:

f_k = k * sample_rate / N

If the tone of interest is not exactly on a bin, energy leaks into neighbouring frequencies. You may choose the nearest bin, evaluate a non-integer frequency form, alter N, resample, or use a different estimator. The correct choice depends on whether you are detecting a known tone, estimating its exact frequency, or measuring power in a band.

This is an important boundary: Goertzel computes a selected Fourier component. It does not magically eliminate spectral leakage caused by finite observation windows.

6. Windowing still matters

A rectangular block assumes the signal is abruptly cut at the block boundaries. If the target sinusoid is not periodic within the block, discontinuities create leakage. Applying a Hann, Hamming or other window changes leakage, main-lobe width and amplitude scaling.

Professionals therefore document the entire measurement chain: sample rate, block length, target frequency, window, normalization, magnitude or power formula, threshold and noise model. A Goertzel recurrence alone is not a complete tone detector.

7. Magnitude, power and phase

Once the real and imaginary components are recovered:

magnitude = sqrt(real^2 + imag^2)
power     = real^2 + imag^2
phase     = atan2(imag, real)

But absolute amplitude depends on DFT normalization and the applied window. If you need calibrated physical amplitude, derive and test the scale factor rather than copying a magnitude formula from a code sample.

8. Tone detection needs a decision rule

For a detector, computing a frequency component is only the measurement stage. The system must decide whether a tone is present. Threshold design should consider noise floor, adjacent frequencies, harmonics, block length, expected signal level and false-positive cost.

In dual-tone systems, both required tones must be present within accepted level/twist limits, and unwanted harmonics or competing tones may need rejection checks. This is why a professional DTMF detector is more than eight Goertzel loops.

9. Block length controls several things at once

Increasing N improves nominal frequency resolution because bin spacing shrinks. It also increases detection latency, memory if samples are retained, recurrence duration and possible numerical error accumulation. Short blocks respond faster but separate close frequencies less sharply.

Choose N from the system requirement, not because powers of two “look like DSP.” Goertzel does not require a power-of-two block length.

10. Numerical stability is a real professional concern

The classic recurrence behaves like a second-order resonator whose poles lie on the unit circle in exact arithmetic. Finite precision can accumulate roundoff, especially for long blocks, frequencies near 0 or Nyquist, or constrained fixed-point implementations. Modern DSP discussions emphasize that treating the recurrence as automatically numerically benign is a mistake.

Mitigations include choosing suitable precision, rescaling, limiting block length, using stable formulations, comparing against direct DFT/FFT references, and analyzing fixed-point word growth. If you need a continuously sliding estimate, do not assume the block Goertzel recurrence can simply be extended forever without stability analysis.

11. Fixed-point design exposes hidden arithmetic

On microcontrollers or DSPs without fast floating point, coefficients and states may be quantized. Then you must budget:

• coefficient precision;
• state word length;
• intermediate multiplication width;
• rounding versus truncation;
• saturation versus wraparound;
• input scaling and headroom;
• output normalization.

The recurrence can amplify internal state relative to input amplitude, so “the ADC is 12-bit” does not mean a 16-bit state is automatically safe.

12. A production benchmark should compare the right alternatives

Compare at least:

• direct single-frequency DFT;
• Goertzel for M selected tones;
• real FFT for the entire block;
• possibly filter-bank or heterodyne approaches for continuous detection.

Measure CPU time, memory, latency, frequency error, amplitude error and robustness in noise. A microbenchmark that ignores detector accuracy is not a useful engineering result.

13. Test signals that expose mistakes

• an impulse, whose DFT magnitude is known across bins;
• a cosine exactly on the target bin;
• a sine exactly on the target bin to test phase/sign;
• a tone halfway between bins to expose leakage;
• zero input;
• white noise with known variance;
• two simultaneous tones;
• very small and near-full-scale amplitudes;
• long blocks to reveal state growth;
• comparison with a trusted FFT/DFT implementation.

14. How to learn it efficiently

Begin with prediction rather than implementation. Show an 8-sample signal and ask which frequency should dominate. Run a trusted DFT. Investigate only one bin. Then introduce the recurrence and trace its two state variables. Modify the frequency or block length. Finally make a reusable Goertzel function with explicit normalization and tests.

This follows the PRIMM progression. Use subgoal labels such as Select target frequency → Precompute coefficient → Accumulate recurrence → Recover complex coefficient → Normalize → Apply detector rule. Programming-education research on subgoal-labelled worked examples supports explicitly naming these procedural chunks for novices. Deliberate debugging exercises are also worthwhile: a 2024 meta-analysis found a meaningful overall effect of debugging interventions in computational-thinking learning.

Common failure states

• Using the wrong final-state formula for the chosen recurrence indexing.
• Forgetting the sign convention of the DFT and reporting conjugated phase.
• Assuming the nearest DFT bin equals the true target frequency.
• Ignoring window gain when estimating amplitude.
• Comparing raw magnitude against a threshold without accounting for N.
• Using Goertzel for hundreds of bins when an FFT would be cheaper.
• Running a block recurrence indefinitely as a sliding filter without stability analysis.
• Implementing fixed point without bounding internal state growth.
• Calling a spectral measurement a complete tone detector without a decision model.

Practice ladder

• Beginner: compute one 8-point DFT bin directly and compare with Goertzel.
• Foundation: implement one-bin magnitude for real signals and test impulse/cosine inputs.
• Intermediate: add arbitrary target frequencies, windowing and calibrated amplitude.
• Advanced: build a multi-tone detector and measure false positives under noise and frequency offset.
• Professional: implement floating- and fixed-point versions, compare with FFT/filter-bank alternatives, analyze numerical error and tune the detector against real signal data.

Learning Hall boundary

This article owns Goertzel as efficient evaluation of one or a few finite Fourier components and the engineering of tone detection around it. It does not replace the FFT, general spectral analysis, digital filter design, audio feature extraction or statistical detection theory.

Evidence and further reading

• Gerald Goertzel, “An Algorithm for the Evaluation of Finite Trigonometric Series,” American Mathematical Monthly 65(1), 1958.
• Rick Lyons’ DSPRelated discussions, including numerical-stability cautions and modern implementation notes, are useful engineering complements to the original mathematical paper.
• For teaching design, see subgoal-labelled worked examples and debugging-intervention meta-analysis.

Professional rule: you understand Goertzel when you can derive the recurrence from a selected DFT frequency, recover the complex coefficient with the correct convention, choose it over an FFT for a defensible reason, and quantify the measurement error introduced by windowing, finite precision and frequency mismatch.