Goertzel algorithm
The Goertzel algorithm is a digital signal processing (DSP) technique for efficiently evaluating individual terms of the discrete Fourier transform (DFT), enabling the detection of specific frequencies within a sampled signal using fewer computational resources than a full DFT or fast Fourier transform (FFT) when only a single or few frequency bins are needed.[1] Originally proposed by Gerald Goertzel in 1958 as a method for computing finite trigonometric series, it implements a second-order infinite impulse response (IIR) filter that recursively processes input samples to yield the magnitude and phase of a targeted DFT coefficient.[2]
At its core, the algorithm operates by applying a linear time-invariant (LTI) filter with an impulse response tailored to the desired frequency k, where the DFT output X is obtained as the filter's response at the end of the input sequence of length N.[3] This requires approximately N real multiplications and 2N additions in total, plus a few operations for the final complex multiplication, making it computationally superior to the FFT's O(N \log N) operations for isolated frequency analysis.[3] Unlike the FFT, it does not require the block size N to be a power of two, offering flexibility in resolution (e.g., 80 Hz at 8 kHz sampling with N = 100).[4]
The algorithm's efficiency has made it a staple in real-time applications such as dual-tone multi-frequency (DTMF) signaling for touch-tone telephones, call progress tone detection (e.g., dial or busy signals), and frequency response testing in telecommunications.[4] Optimized variants further reduce complexity by directly computing the squared magnitude, avoiding unnecessary phase calculations for tone presence detection.[4] Its low CPU demands suit embedded systems, where it outperforms FFT-based methods for sparse frequency monitoring.[4]
Introduction
Overview and Purpose
The Goertzel algorithm is a computational technique in digital signal processing that enables the efficient evaluation of individual coefficients in the discrete Fourier transform (DFT) of a discrete-time signal. It operates as a second-order infinite impulse response (IIR) filter tuned to a specific frequency, allowing the isolation of a single frequency bin from the input sequence without performing a full spectral analysis. Originally formulated for the evaluation of finite trigonometric series, the algorithm has become a standard method for targeted frequency detection in signal processing contexts.[2][3]
The primary purpose of the Goertzel algorithm is to compute one or a small number of DFT coefficients selectively, avoiding the overhead of transforming the entire signal spectrum. This makes it particularly valuable in resource-constrained or real-time environments where only specific frequency components, such as tones in audio signals, need to be analyzed. By leveraging a recursive structure, the algorithm minimizes redundant calculations inherent in broader transforms like the DFT.[3]
In operation, the algorithm takes as input a finite-length time-domain sequence x for n = 0, 1, \dots, N-1, along with a target frequency index k, and outputs the corresponding complex DFT coefficient X(k), which represents the signal's amplitude and phase at the normalized frequency $2\pi k / N. A key benefit is its linear time complexity of [O(N](/page/O(n)) operations per frequency bin, significantly lower than the O(N \log N) required by fast Fourier transform (FFT) algorithms for complete spectra, thus offering substantial savings when full computation is unnecessary.[3]
Historical Background
The Goertzel algorithm was invented by Gerald Goertzel, an American theoretical physicist, in 1958 while affiliated with the Nuclear Development Corporation of America. Originally developed in the context of nuclear physics computations, the algorithm provided an efficient method for evaluating finite trigonometric series, which are fundamental in analyzing periodic phenomena.
Goertzel detailed the algorithm in his seminal paper, "An Algorithm for the Evaluation of Finite Trigonometric Series," published in The American Mathematical Monthly. This two-page article outlined a recursive technique requiring approximately N multiplications and 2N additions for an N-term series, offering significant computational savings over direct summation methods prevalent at the time. The work built on the mathematical framework of the discrete Fourier transform (DFT) but optimized it for single-frequency evaluation, reflecting the practical needs of mid-20th-century scientific computing in physics.
During the 1970s and 1980s, as digital signal processing (DSP) emerged with the advent of affordable digital hardware, the Goertzel algorithm saw widespread adoption in telephony and audio applications. Its efficiency for detecting specific frequencies made it ideal for dual-tone multi-frequency (DTMF) signaling in touch-tone telephones, where it enabled robust tone detection under noisy conditions. Key milestones included its integration into implementations compliant with International Telecommunication Union (ITU) recommendations, such as ITU-T Q.24 for multifrequency signaling systems, which specified performance criteria for DTMF detection that the algorithm effectively met.[5]
As of 2025, the Goertzel algorithm remains relevant in resource-constrained environments like embedded systems and Internet of Things (IoT) devices, valued for its minimal memory footprint and low computational overhead compared to full DFT computations. Its core recurrence relation continues to support targeted frequency analysis in applications ranging from sensor data processing to real-time audio monitoring.[6]
Mathematical Foundation
The Discrete Fourier Transform (DFT) of a finite-length sequence x, where n = 0, 1, \dots, N-1, is defined as
X(k) = \sum_{n=0}^{N-1} x \exp\left(-j \frac{2\pi k n}{N}\right)
for frequency indices k = 0, 1, \dots, N-1.[7] This formulation requires N^2 complex multiplications to compute all N coefficients, representing a significant computational burden when only a subset of the spectrum is needed.[8]
The Goertzel algorithm computes an individual X(k) by recasting the DFT summation as the response of a tuned digital filter to the input sequence, leveraging the periodic nature of the complex exponential \exp\left(-j \frac{2\pi k}{N}\right).[7] This approach exploits the trigonometric identity underlying the DFT, where X(k) can be separated into real cosine and imaginary sine components, avoiding the full matrix-vector multiplication of the standard DFT.[9] It is particularly suited for partial spectrum analysis, such as isolating a single frequency bin without evaluating the entire transform.[8]
The equivalence between the Goertzel algorithm and the DFT bin X(k) is established by deriving a recursive form of the summation that preserves the exact value for finite N.[7] Specifically, the algorithm evaluates the polynomial P(z) = \sum_{n=0}^{N-1} x z^{-n} at z = \exp\left(j \frac{2\pi k}{N}\right) using nested multiplication (Horner's method), which unfolds to match the DFT sum precisely.[8] This holds under the assumption of basic complex exponential properties and finite summation, ensuring the output aligns with the standard DFT for the selected k.[9]
Derivation of the Recurrence Relation
The derivation of the recurrence relation for the Goertzel algorithm begins with the expression for a single bin of the discrete Fourier transform (DFT), given by
X(k) = \sum_{n=0}^{N-1} x \, e^{-j 2\pi k n / N},
where x is the input sequence of length N, and k is the frequency index of interest.[10]
Using Euler's formula, e^{-j\theta n} = \cos(\theta n) - j \sin(\theta n) with \theta = 2\pi k / N, the DFT bin can be separated into its real and imaginary parts:
X(k) = \sum_{n=0}^{N-1} x \cos(\theta n) - j \sum_{n=0}^{N-1} x \sin(\theta n).
This form highlights the trigonometric series that the algorithm efficiently evaluates. The original algorithm by Goertzel targeted such finite trigonometric sums, and its adaptation to the complex DFT follows similarly by deriving a recursive structure.[11]
To obtain the recurrence, consider the DFT as the output of a linear time-invariant filter whose impulse response is the complex exponential geometric series h = e^{-j \theta n} for $0 \leq n < N. The z-transform of this finite geometric series is H(z) = \sum_{n=0}^{N-1} e^{-j \theta n} z^{-n} = \frac{1 - e^{-j \theta N} z^{-N}}{1 - e^{-j \theta} z^{-1}}. Since e^{-j \theta N} = 1, this simplifies, but for efficient computation, the Goertzel approach uses an infinite impulse response (IIR) approximation matched to the finite case via boundary adjustments. The denominator $1 - e^{-j \theta} z^{-1} corresponds to a first-order recurrence, but to enable real-valued arithmetic, the poles at e^{\pm j \theta} (conjugates on the unit circle) lead to a second-order characteristic equation z^2 - 2 \cos(\theta) z + 1 = 0.[10]
The corresponding second-order linear difference equation for an auxiliary sequence s_n is thus
s_n = x + 2 \cos(\theta) \, s_{n-1} - s_{n-2}, \quad n = 0, 1, \dots, N-1,
which arises directly from the real coefficient filter H(z) = \frac{1 - e^{-j \theta} z^{-1}}{1 - 2 \cos(\theta) z^{-1} + z^{-2}}, where the numerator ensures the finite-length response matches the DFT sum. This equation is obtained by multiplying the first-order complex recurrence s_n = x + e^{-j \theta} s_{n-1} by the conjugate factor and combining, leveraging the identity e^{-j \theta} + e^{j \theta} = 2 \cos(\theta). The trigonometric recurrence for the cosine and sine components follows from this structure, reducing complex multiplications.[8][10]
The initial conditions are set as s_{-2} = 0 and s_{-1} = 0, ensuring the recursion starts with s_0 = x{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}. These zero-state initial conditions align the IIR filter response with the finite DFT sum via the numerator and final adjustment, accounting for the boundary effects in the finite series.[10]
After computing the sequence up to n = N-1, the DFT bin is obtained via the adjustment
X(k) = s_{N-1} - e^{-j \theta} s_{N-2},
which incorporates the remaining phase correction from the filter's numerator to yield the exact DFT value. This step resolves the IIR approximation into the precise finite sum, confirming the recurrence's validity for single-bin computation.[10]
Algorithm Implementation
Step-by-Step Procedure
To implement the Goertzel algorithm for computing a single bin of the discrete Fourier transform (DFT), begin with precomputation of the frequency-specific parameters based on the DFT length N and the target bin index k. Calculate the angular frequency \theta = 2\pi k / N and the recurrence coefficient c = 2 \cos(\theta).[11][4]
Initialize the state variables to zero: set s_{-2} = 0 and s_{-1} = 0. This ensures the recursion starts from a neutral state.[4]
Process the input sequence x iteratively for n = 0 to N-1. For each sample, compute the next state using the recurrence relation s_n = c \cdot s_{n-1} - s_{n-2} + x, then update the previous states by shifting: s_{n-2} = s_{n-1} and s_{n-1} = s_n. This loop requires careful indexing to avoid off-by-one errors, typically implemented with temporary variables for the current and prior states. After the loop, compute the final state s_N = c \cdot s_{N-1} - s_{N-2}.[11][4]
After computing s_N, extract the complex DFT coefficient X from the final states s_N and s_{N-1}. The real part is given by \operatorname{Re}\{X\} = s_N - s_{N-1} \cos(\theta), and the imaginary part by \operatorname{Im}\{X\} = s_{N-1} \sin(\theta). An alternative non-complex form computes the magnitude squared directly as |X|^2 = (s_N - s_{N-1} \cos(\theta))^2 + (s_{N-1} \sin(\theta))^2 for applications like tone detection.[4]
The following pseudocode illustrates a simple iterative implementation in a code-like structure:
precompute θ = 2 * π * k / N
precompute c = 2 * cos(θ)
precompute cos_θ = cos(θ)
precompute sin_θ = sin(θ)
initialize s_prev2 = 0
initialize s_prev1 = 0
for n = 0 to N-1:
s_current = c * s_prev1 - s_prev2 + x[n]
s_prev2 = s_prev1
s_prev1 = s_current
s_N = c * s_prev1 - s_prev2
real_part = s_N - s_prev1 * cos_θ
imag_part = s_prev1 * sin_θ
precompute θ = 2 * π * k / N
precompute c = 2 * cos(θ)
precompute cos_θ = cos(θ)
precompute sin_θ = sin(θ)
initialize s_prev2 = 0
initialize s_prev1 = 0
for n = 0 to N-1:
s_current = c * s_prev1 - s_prev2 + x[n]
s_prev2 = s_prev1
s_prev1 = s_current
s_N = c * s_prev1 - s_prev2
real_part = s_N - s_prev1 * cos_θ
imag_part = s_prev1 * sin_θ
This procedure assumes real-valued input x and ideal arithmetic; the resulting X matches the corresponding DFT bin up to scaling conventions in some contexts.[11][4]
Numerical Stability and Mitigation
The recursive nature of the Goertzel algorithm corresponds to a second-order IIR filter with poles on the unit circle in the z-domain, rendering it marginally stable and susceptible to error accumulation from rounding in finite-precision arithmetic. In fixed-point or low-precision floating-point implementations, these rounding errors propagate through the recurrence relation, causing deviations that grow quadratically with the sequence length N.[12]
For long input sequences (N > 1000), the accumulation of such errors can result in significant deviation from the true DFT bin value, potentially exceeding several percent of the correct magnitude in unmitigated 16-bit implementations. Error bounds indicate that relative errors scale approximately as O(N² ε), where ε is the machine precision, leading to practical limitations in high-precision applications.[12]
To address these issues, fixed-point implementations commonly employ Q15 or Q31 formats with dynamic scaling to prevent overflow and maintain headroom for intermediate values, ensuring the recursive states remain within the representable range. Alternative formulations, such as the magnitude-squared variant, compute the squared magnitude |X(k)|² directly using real-valued operations on the final states (s[N] and s[N-1]), thereby avoiding complex arithmetic and reducing sensitivity to phase-related rounding errors—particularly useful in applications like DTMF tone detection.[13] For streaming or very long sequences, periodic resetting of the filter states after each block of N samples prevents unbounded error growth, while employing double-precision floating-point arithmetic provides near-full accuracy for critical scenarios.[14]
Empirical analyses demonstrate that, with proper scaling in 16-bit fixed-point arithmetic, the algorithm achieves less than 1% deviation from reference DFT values for sequences up to N < 1024, balancing computational efficiency and accuracy in embedded systems.[15]
Efficiency and Comparison
Computational Complexity
The Goertzel algorithm, in its standard second-order form, achieves a time complexity of O(N) for evaluating a single DFT bin from an input sequence of length N, requiring N+2 real multiplications and 2N+1 real additions across the recursive filtering and final complex value computation stages. This linear scaling arises from performing one iteration of the recurrence relation per input sample, followed by a constant-time post-processing step to extract the real and imaginary components of the bin value. In contrast, a full radix-2 FFT demands approximately 2N \log_2 N real multiplications for all N bins, highlighting the Goertzel's efficiency for isolated frequency analysis.[16]
The space complexity is O(1), independent of N, as the algorithm maintains only two scalar state variables—corresponding to the previous two outputs of the recurrence, s_{n-1} and s_{n-2}—along with a few precomputed constants like the cosine coefficient. This minimal memory footprint makes it particularly suitable for resource-constrained environments, such as embedded systems, where storing intermediate results for an entire FFT (O(N)) would be prohibitive.
When extended to M distinct frequencies, the time complexity becomes O(M N), as each bin requires a separate pass through the input with its unique coefficient, though shared input buffering can mitigate some overhead; this remains advantageous if M \ll N, such as in tone detection applications needing only a handful of bins. On embedded hardware like microcontrollers, benchmarks demonstrate the Goertzel can outperform a full FFT by factors of 10–100 in execution time, depending on N and optimization.[15]
Advantages Over FFT for Single Bins
The Fast Fourier Transform (FFT) computes all N frequency bins of the discrete Fourier transform (DFT), incurring a computational complexity of O(N log N) even when only a single bin is required, which represents an inefficiency for applications needing selective frequency analysis.[17] In contrast, the Goertzel algorithm achieves O(N) complexity for evaluating a single DFT bin, performing N+2 real multiplications and 2N+1 real additions, thereby avoiding unnecessary computations for unused bins.[17] This linear scaling makes Goertzel particularly advantageous in scenarios where computational resources are limited, such as embedded systems.
Beyond asymptotic efficiency, the Goertzel algorithm offers practical implementation benefits over the FFT. It eliminates the need for data bit-reversal reordering and precomputed twiddle factors, simplifying the code and reducing memory overhead, as only a single real-valued coefficient is required per iteration.[17] Additionally, Goertzel supports real-time streaming processing without buffering an entire block of N samples, enabling immediate computation upon receipt of each input value, which is ideal for continuous signal monitoring.[17] Unlike the FFT, which typically requires N to be a power of 2 for optimal performance, Goertzel operates effectively with arbitrary N and allows precise targeting of any frequency between 0 and the sampling rate, enhancing flexibility in non-standard sampling scenarios.[18]
These attributes position the Goertzel algorithm favorably for use cases involving fixed or known frequencies on resource-constrained platforms, such as detecting standard tones in telecommunications (e.g., DTMF signaling) or monitoring specific harmonics in low-power sensors.[15] However, its advantages diminish when multiple bins (M) are needed; Goertzel scales as O(MN), becoming less efficient than FFT when M exceeds roughly log₂ N, as the latter leverages parallelism and shared computations across all bins.[17]
Applications
Power Spectrum Estimation
The Goertzel algorithm is particularly suited for power spectrum estimation in real-valued signals, where only the magnitude-squared of specific discrete Fourier transform (DFT) bins is required, such as for detecting energy at targeted frequencies without needing phase information. This approach leverages the recursive computation to evaluate the power spectral density at a single frequency bin k, defined by the angle θ = 2πk/N, where N is the number of samples. After executing the core recursion s_n = 2 cos(θ) s_{n-1} - s_{n-2} + x_n for n = 0 to N-1 (with s_{-2} = s_{-1} = 0), the magnitude-squared |X(k)|^2 is obtained directly as (s_N)^2 + (s_{N-1})^2 - 2 s_N s_{N-1} cos(θ).[4]
This formula derives from expanding the full complex DFT bin expression while eliminating the imaginary component, as |X(k)|^2 = Re{X(k)}^2 + Im{X(k)}^2, where Re{X(k)} = s_N - s_{N-1} cos(θ) and Im{X(k)} = s_{N-1} sin(θ), simplifying to the real-only form shown. The process avoids explicit computation of the sine term and complex multiplications, making it ideal for applications focused on energy detection, such as identifying signal power levels in noisy environments. By forgoing the square root operation (which would yield the magnitude |X(k)|), further computational savings are achieved when only relative power comparisons are needed.[4]
Compared to computing the full complex DFT bin, this power-only variant reduces operations by avoiding the sine precomputation and imaginary part evaluation, resulting in a simpler and faster implementation. This efficiency is pronounced for real-time systems processing sparse frequency spectra, where full FFT computation would be overkill. For instance, in detecting a 941 Hz tone within an 8 kHz sampled signal of length N=205 amid additive noise, the algorithm yields a magnitude-squared value peaking at around 100 million, enabling clear discrimination of the signal energy from background levels through threshold comparison.[4]
Single DFT Bin Computation
The Goertzel algorithm computes a single complex DFT coefficient X(k), providing both magnitude and phase information essential for phase-sensitive applications in spectrum analysis, such as signal filtering or correlation where the full bin value is required.[8]
Following the recursive computation of the state variables s_n for n = 0 to N, the complex output is derived using only real arithmetic:
\text{Re}\{X(k)\} = s_{N} - s_{N-1} \cos \theta, \quad \text{Im}\{X(k)\} = s_{N-1} \sin \theta,
where \theta = 2\pi k / N. This formulation, rooted in the original recursive evaluation of trigonometric series, ensures the DFT bin matches the direct summation result while avoiding complex operations in the loop.[8]
The algorithm operates entirely in real arithmetic during recursion by multiplying inputs and states by the real coefficient $2 \cos \theta, with \cos \theta and \sin \theta precomputed outside the loop for efficiency. This approach minimizes computational overhead, making it suitable for resource-constrained environments needing the complete complex bin.[8]
In spectrum analysis, the full complex X(k) facilitates tasks like coherent demodulation or phase-based feature extraction, extending beyond magnitude-only computations.[8]
Phase Detection in Signals
The Goertzel algorithm computes a complex-valued DFT bin X(k) consisting of real and imaginary parts, from which the phase angle \phi of the signal component at frequency k can be extracted as \phi = \atan2(\imag(X(k)), \real(X(k))).[8] This phase value represents the angular shift of the sinusoidal component relative to a reference, enabling precise timing analysis in periodic signals.[4]
In communications systems, the extracted phase facilitates detecting the onset and offset of tones, such as in dual-tone multi-frequency (DTMF) signaling, where timing synchronization ensures accurate decoding.[8] It also measures delays in echoes, as the phase difference between transmitted and received signals at a known frequency directly corresponds to the time shift \tau = \phi / (2\pi f), aiding in applications like acoustic ranging or network latency assessment.[19]
To enhance phase accuracy, windowing functions such as the Hamming window are applied to the input signal prior to Goertzel processing, minimizing spectral leakage that can distort phase estimates in non-stationary or finite-length signals.[8] For noisy environments, averaging phase results across multiple overlapping signal blocks improves robustness, reducing variance in the estimate while preserving computational efficiency.[19]
In audio processing, the phase from Goertzel computation supports stereo imaging by quantifying inter-channel phase differences at dominant frequencies, which informs spatial rendering algorithms.[8] Similarly, it aids beat detection by tracking phase evolution over time, allowing synchronization to rhythmic components in music signals.[4]
Processing Complex-Valued Signals
The Goertzel algorithm can be extended to complex-valued input sequences, such as those arising in IQ-modulated or baseband signals, by applying the recursive procedure independently to the real and imaginary parts of the input. This adaptation leverages the real-valued nature of the feedback coefficients in the standard recursion, enabling two parallel real-valued Goertzel filters—one for the real component and one for the imaginary component—to compute the corresponding parts of the output. The recursion for each component follows the form
s_n = 2 \cos \theta \cdot s_{n-1} - s_{n-2} + c_n,
where c_n is either the real or imaginary part of the complex input x, \theta = 2\pi k / N, and initial conditions s_{-2} = s_{-1} = 0. After processing all N samples, the complex DFT bin value is obtained as X(k) = s_N - e^{-j\theta} s_{N-1}, where s_N and s_{N-1} are the complex combinations of the parallel filter outputs.[20]
An alternative formulation employs complex coefficients directly in the recursion:
s_n = \left(2 \cos \theta - e^{j \theta}\right) s_{n-1} - s_{n-2} + x,
which computes the full complex state but is often simplified to the parallel real recursions to minimize complex multiplications during the iterative steps. In practice, the parallel approach is preferred for hardware implementations, as it avoids complex arithmetic in the loop while preserving the exact DFT computation.[8]
This adaptation is particularly useful in radar systems for processing complex baseband signals from FMCW radars to extract frequency components related to target vital signs or positions, and in wireless communications for efficient demodulation of analytic signals in frequency-hopping schemes. For instance, in multi-person vital sign estimation using radar, the generalized Goertzel processes complex IQ data to isolate narrowband components without full FFT computation.[21]
The computational cost approximately doubles compared to the real-valued case due to the two parallel recursions, requiring about 2N real multiplications overall, yet retains O(N complexity per bin. Numerical stability mirrors the real-valued version, with potential accumulation of rounding errors in both components necessitating fixed-point scaling or periodic resets in long sequences.[20]