Introduction

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)O(N) multiplications for one frequency, compared with O(Nlog⁡N)O(N \log N) for a full FFT over NN samples.

The crossover is surprisingly useful: whenever you need fewer than roughly log⁡2N\log_2 N frequencies out of a block of NN 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.

Try It: DTMF Decoder

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.

<!-- DTMF decoder demo — keypad + Goertzel energy bar chart -->
<div class="layout">
  <div class="keypad-area">
    <p class="hint">Press a key to synthesize its DTMF tone pair. Then click <b>Decode</b> to run the Goertzel algorithm on all 8 standard frequencies.</p>
    <div class="keypad" id="keypad">
      <!-- Keys are built dynamically in JS -->
    </div>
    <div class="pressed-info" id="pressedInfo"></div>
    <button id="decodeBtn" class="decode-btn" disabled>Decode</button>
  </div>
  <div class="chart-area">
    <div class="chart-title">Goertzel energy per DTMF frequency</div>
    <div id="chart" class="chart"></div>
    <div id="result" class="result"></div>
  </div>
</div>

/* DTMF decoder layout styles */
* { 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; }
/* Keypad grid */
.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; }
/* Energy bar chart */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// DTMF standard: 4 row frequencies x 3 col frequencies = 12 tones
// Row frequencies (Hz)
const ROW_FREQS = [697, 770, 852, 941];
// Column frequencies (Hz)
const COL_FREQS = [1209, 1336, 1477];
const ALL_FREQS = [...ROW_FREQS, ...COL_FREQS];
// Keypad digit layout (row-major)
const KEYS = [
  ['1','2','3'],
  ['4','5','6'],
  ['7','8','9'],
  ['*','0','#']
];

// Goertzel algorithm: compute energy at targetFreq using N samples
// Returns the squared magnitude (energy) at the target frequency bin
function goertzel(samples, targetFreq, sampleRate) {
  const N = samples.length;
  const omega = (2 * Math.PI * targetFreq) / sampleRate;
  const coeff = 2 * Math.cos(omega); // the only precomputed constant: 2*cos(omega)
  let s1 = 0, s2 = 0;
  // second-order IIR recurrence: s[n] = x[n] + coeff*s[n-1] - s[n-2]
  for (let n = 0; n < N; n++) {
    const s0 = samples[n] + coeff * s1 - s2;
    s2 = s1;
    s1 = s0;
  }
  // squared magnitude: |X[k]|^2 without the final complex multiply
  return s1 * s1 + s2 * s2 - coeff * s1 * s2;
}

// Synthesize a DTMF tone block (sum of two sine waves)
const SAMPLE_RATE = 8000;
const BLOCK_SAMPLES = 205; // ~26 ms at 8000 Hz sample rate — ITU-T recommended minimum

function synthesize(rowFreq, colFreq) {
  const buf = new Float64Array(BLOCK_SAMPLES);
  for (let n = 0; n < BLOCK_SAMPLES; n++) {
    buf[n] = 0.5 * Math.sin(2 * Math.PI * rowFreq * n / SAMPLE_RATE)
           + 0.5 * Math.sin(2 * Math.PI * colFreq * n / SAMPLE_RATE);
  }
  return buf;
}

let currentKey = null;
let currentSamples = null;
let energies = new Array(7).fill(0);

// Build the keypad grid from the KEYS layout
const keypadEl = document.getElementById('keypad');
const pressedEl = document.getElementById('pressedInfo');
const decodeBtn = document.getElementById('decodeBtn');
const chartEl = document.getElementById('chart');
const resultEl = document.getElementById('result');

// Build bar chart elements for each DTMF frequency
const barEls = ALL_FREQS.map((f, i) => {
  const wrap = document.createElement('div');
  wrap.className = 'bar-wrap';
  const bar = document.createElement('div');
  bar.className = 'bar';
  bar.style.height = '0px';
  const lbl = document.createElement('div');
  lbl.className = 'bar-label';
  lbl.textContent = f + ' Hz';
  wrap.appendChild(bar); wrap.appendChild(lbl);
  chartEl.appendChild(wrap);
  return bar;
});

// Render bar heights proportional to measured energy
function renderChart(hits) {
  const maxE = Math.max(...energies, 1e-9);
  energies.forEach((e, i) => {
    const h = Math.round((e / maxE) * 100);
    barEls[i].style.height = h + 'px';
    barEls[i].className = 'bar' + (hits && hits.has(i) ? ' hit' : '');
  });
}

// Run Goertzel on all 7 DTMF frequencies and find the best row+col
function decode() {
  if (!currentSamples) return;
  energies = ALL_FREQS.map(f => goertzel(currentSamples, f, SAMPLE_RATE));

  // Pick the highest-energy row frequency and highest-energy column frequency
  const rowEnergies = energies.slice(0, 4);
  const colEnergies = energies.slice(4, 7);
  const bestRow = rowEnergies.indexOf(Math.max(...rowEnergies));
  const bestCol = colEnergies.indexOf(Math.max(...colEnergies));
  const detectedKey = KEYS[bestRow][bestCol];

  const hits = new Set([bestRow, 4 + bestCol]);
  renderChart(hits);

  if (detectedKey === currentKey) {
    resultEl.textContent = i18nFmt('✓ Detected: %key%', { key: detectedKey });
    resultEl.className = 'result ok';
  } else {
    resultEl.textContent = i18nFmt('✗ Got %detected% instead of %expected%', { detected: detectedKey, expected: currentKey });
    resultEl.className = 'result err';
  }
}

// Attach click handlers to each key button
KEYS.forEach((row, ri) => {
  row.forEach((label, ci) => {
    const btn = document.createElement('button');
    btn.className = 'key';
    const rowF = ROW_FREQS[ri];
    const colF = COL_FREQS[ci];
    btn.innerHTML = label + '<sub>' + rowF + '+' + colF + '</sub>';
    btn.title = i18nFmt('Key %key%: %row% Hz + %col% Hz', { key: label, row: rowF, col: colF });
    btn.addEventListener('click', () => {
      document.querySelectorAll('.key').forEach(k => k.classList.remove('active'));
      btn.classList.add('active');
      currentKey = label;
      currentSamples = synthesize(rowF, colF);
      energies = new Array(7).fill(0);
      renderChart(null);
      pressedEl.textContent = i18nFmt('Pressed: %key% → %row% Hz + %col% Hz', { key: label, row: rowF, col: colF });
      resultEl.textContent = '';
      resultEl.className = 'result';
      decodeBtn.disabled = false;
    });
    keypadEl.appendChild(btn);
  });
});

decodeBtn.addEventListener('click', decode);
renderChart(null);
Result
Console

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 Real Complexity

The DFT value at bin kk for a length-NN signal x[0],…,x[N−1]x[0], \dots, x[N-1] is:

X[k]=∑n=0N−1x[n]⋅e−j2πkn/NX[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=Nn = N. Define the recurrence:

s[n]=x[n]+2cos⁡ ⁣(2πkN)s[n−1]−s[n−2]s[n] = x[n] + 2\cos\!\left(\frac{2\pi k}{N}\right) s[n-1] - s[n-2]

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

X[k]=s[N]−e−j2πk/N⋅s[N−1]X[k] = s[N] - e^{-j 2\pi k / N} \cdot s[N-1]

What this costs:

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

Comparison with FFT:

Method Multiplications for MM frequencies out of NN samples
Goertzel (per freq) NN real
Full FFT N2log⁡2N\frac{N}{2} \log_2 N complex ≈Nlog⁡2N\approx N \log_2 N real
Break-even M≈log⁡2NM \approx \log_2 N frequencies

For DTMF: N=205N = 205 samples at 8 kHz gives a block length of ~26 ms. A full FFT would cost ≈205×7.7≈1,580\approx 205 \times 7.7 \approx 1{,}580 real multiplications; 8 Goertzel passes cost 8×205=1,6408 \times 205 = 1{,}640 — almost exactly at the crossover. But Goertzel only needs 8 passes, while the FFT always runs all N/2⋅log⁡2NN/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.

Where It Matters

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≪N/2M \ll N/2 bins — targeted algorithms like Goertzel beat the general tool on every axis: fewer operations, less memory, and lower latency.

Conclusion

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)O(N) recurrence leaves the O(Nlog⁡N)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/goertzel-algorithm/Content licensed under CC BY-NC 4.0.