The Goertzel Algorithm

Every time you press a button on a telephone keypad, the network must figure out which digit you dialled — and it does so by listening for a pair of audio tones. The classic tool for spotting a specific frequency in a signal is the Fast Fourier Transform (FFT), but the FFT gives you all frequencies at once. If you only care about a handful of them, you are doing a lot of unnecessary work.

In 1958, Gerald Goertzel published a remarkably simple fix. His algorithm computes a single bin of the Discrete Fourier Transform (DFT) using nothing more than a two-step recurrence — essentially a tiny digital filter run once through the signal. It costs $O(N)$ multiplications for one frequency, compared with $O(N \log N)$ for a full FFT over $N$ samples.

The crossover is surprisingly useful: whenever you need fewer than roughly $\log_2 N$ frequencies out of a block of $N$ samples, Goertzel wins. That threshold covers DTMF decoding (8 target tones from 8 ms blocks), pitch detection in voice codecs, and dozens of other embedded tasks where CPU cycles are precious.

The algorithm's elegance comes from rewriting the DFT evaluation as a second-order IIR recurrence whose only free parameter is a single cosine value precomputed from the target frequency. No complex exponentials at runtime, no lookup tables, no FFT butterfly network — just two additions and one multiplication per sample.

Press any keypad button to synthesize its two DTMF tones, then click Decode to run the Goertzel algorithm and identify which digit was pressed. The bar chart shows the energy the algorithm measures at each of the 8 standard DTMF frequencies — two bars will spike for every valid digit.

<!-- {{c_html_intro}} -->
<div class="layout">
  <div class="keypad-area">
    <p class="hint">{{hint_para}}</p>
    <div class="keypad" id="keypad">
      <!-- {{c_keys_comment}} -->
    </div>
    <div class="pressed-info" id="pressedInfo"></div>
    <button id="decodeBtn" class="decode-btn" disabled>{{btn_decode}}</button>
  </div>
  <div class="chart-area">
    <div class="chart-title">{{chart_title}}</div>
    <div id="chart" class="chart"></div>
    <div id="result" class="result"></div>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.layout { display: flex; gap: 1rem; flex-wrap: wrap; }
.keypad-area { flex: 0 0 auto; }
.chart-area { flex: 1 1 200px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; max-width: 280px; }
/* {{c_keypad_comment}} */
.keypad { display: grid; grid-template-columns: repeat(3, 56px); gap: 6px; margin-bottom: .6rem; }
.key { width: 56px; height: 56px; font: 700 18px system-ui; border: 2px solid #1d3557;
       background: #fff; color: #1d3557; border-radius: 10px; cursor: pointer;
       display: flex; flex-direction: column; align-items: center; justify-content: center;
       transition: background .12s, color .12s; user-select: none; }
.key sub { font-size: 9px; font-weight: 400; color: #888; margin-top: 1px; }
.key:hover { background: #e8eef3; }
.key.active { background: #1d3557; color: #fff; }
.key.active sub { color: #aac; }
.pressed-info { font-size: .8rem; color: #555; min-height: 1.3em; margin-bottom: .4rem; }
.decode-btn { font: 600 14px system-ui; padding: .45rem 1.1rem; border: 1px solid #1d3557;
              background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.decode-btn:disabled { opacity: .45; cursor: not-allowed; }
/* {{c_chart_comment}} */
.chart-title { font-size: .8rem; font-weight: 600; color: #555; margin-bottom: .3rem; }
.chart { display: flex; align-items: flex-end; gap: 3px; height: 120px; }
.bar-wrap { display: flex; flex-direction: column; align-items: center; flex: 1; height: 100%; justify-content: flex-end; }
.bar { width: 100%; background: #c9ccd1; border-radius: 3px 3px 0 0; transition: height .25s, background .25s; }
.bar.hit { background: #1d3557; }
.bar-label { font-size: 9px; color: #666; margin-top: 2px; text-align: center; line-height: 1.1; }
.result { margin-top: .5rem; font-size: 1rem; font-weight: 700; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.err { color: #c92f3c; }

// Code not found

Notice that the decoder reads only 8 energy values — one Goertzel pass per frequency — and ignores everything else in the signal. A full FFT over the same block would compute hundreds of bins; Goertzel discards all but the 8 it needs, doing proportionally less work.

The DFT value at bin $k$ for a length-$N$ signal $x[0], \dots, x[N-1]$ is:

$$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j 2\pi k n / N}$$

Goertzel's insight is to evaluate this as the output of a second-order IIR filter at time $n = N$. Define the recurrence:

$$s[n] = x[n] + 2\cos\!\left(\frac{2\pi k}{N}\right) s[n-1] - s[n-2]$$

with $s[-1] = s[-2] = 0$. After iterating for all $N$ samples, the DFT bin is recovered in one final step:

$$X[k] = s[N] - e^{-j 2\pi k / N} \cdot s[N-1]$$

What this costs:

• Initialization: precompute $\omega = 2\pi k / N$ and $c = 2\cos\omega$ — one cosine call, done once.
• Main loop: $N$ iterations, each with 2 additions and 1 multiplication by $c$. Total: $N$ real multiplications.
• Final step: one complex multiply to extract $X[k]$.

Comparison with FFT:

For DTMF: $N = 205$ samples at 8 kHz gives a block length of ~26 ms. A full FFT would cost $\approx 205 \times 7.7 \approx 1{,}580$ real multiplications; 8 Goertzel passes cost $8 \times 205 = 1{,}640$ — almost exactly at the crossover. But Goertzel only needs 8 passes, while the FFT always runs all $N/2 \cdot \log_2 N$ — so in practice Goertzel wins because you do not have to discard 97% of the output.

The algorithm was published by Gerald Goertzel in 1958 in a short paper in the American Mathematical Monthly. It predates the FFT (rediscovered by Cooley and Tukey in 1965) and remains one of the most efficient single-frequency detectors known.

Any time a system must monitor a small number of known frequencies in a real-time data stream, Goertzel is the natural fit:

• DTMF decoding: every landline telephone exchange, VoIP gateway and IVR system uses Goertzel (or a direct descendant) to decode the 8 tone pairs produced by keypad presses. The ITU-T Q.23 and Q.24 recommendations effectively mandate this approach.
• Guitar and instrument tuners: a tuner needs to detect the fundamental pitch of one string at a time. Running one Goertzel pass per candidate note is cheaper than a full FFT and more accurate than zero-crossing counting.
• Power-grid frequency monitoring: utility meters and protection relays monitor the 50 Hz or 60 Hz fundamental plus a handful of harmonics. Goertzel targets exactly those bins without wasting cycles on the rest of the spectrum.
• Ultrasonic range finders: many sonar systems transmit a known frequency and listen for the echo. One Goertzel pass on the receive buffer is enough to measure amplitude and phase of the return signal.
• Caller-ID and modem tones: FSK modems and caller-ID decoders watch for mark/space frequencies; Goertzel tracks both simultaneously with two parallel passes.

The broader lesson is algorithmic: the FFT is a masterpiece of divide-and-conquer, but it is a batch algorithm. When your problem is inherently sparse in frequency space — you care about $M \ll N/2$ bins — targeted algorithms like Goertzel beat the general tool on every axis: fewer operations, less memory, and lower latency.

The Goertzel algorithm is a masterclass in matching the tool to the task. When you need the full frequency picture of a signal, the FFT is unbeatable. But when you need just a handful of specific frequencies — as every DTMF decoder, instrument tuner and grid monitor does — a targeted $O(N)$ recurrence leaves the $O(N \log N)$ general solution far behind.

Gerald Goertzel's 1958 paper is barely two pages long. It predates the FFT by seven years and is still running on microcontrollers, DSP chips and telephone exchanges across the world today. Not every algorithmic problem calls for the most general solution — sometimes the smarter move is to ask only the question you actually need answered.