goertzel

Builtin index · Signal processing

result = goertzel(x, k)

Input: x, k · Output: result

What it is

x is a length-N real vector; k is the bin index to evaluate (a number, need not be an integer — evaluates the DFT at an arbitrary point between the FFT's grid bins) or a length-K vector of bins.

Overloads

One call shape — this function is not overloaded.

Code	Input	Output	Description
`result = goertzel(x, k)`	`x` vector`x` is a length-N real vector. `k` number or vector`k` is the bin index to evaluate (a number, need not be an integer — evaluates the DFT at an arbitrary point between the FFT's grid bins) or a length-K vector of bins.	`result` scalar, CVec, or vector	Returns a single complex scalar for a scalar `k`, or a length-K `CVec` for a vector — the K-point DFT this is named for: K arbitrary points in O(n·K), each independently, instead of every bin of a full N-point `fft` whether wanted or not. The standard tool for checking a handful of specific frequencies without paying for a whole FFT.

Examples

From the documentation, and run by the build -- the output and the figure below are what the engine actually produced. Simplest first.

fs = 1000
n = 0:1:63
t = n / fs
x = sin(2*pi*100*t)

X = fft(x)
xr = idft(X)
print("idft roundtrip max err: {max(abs(xr - x))}")

k100 = 100 * length(x) / fs        # bin index equivalent to 100 Hz

bin100 = goertzel(x, k100)
print("goertzel magnitude at bin {k100}: {abs(bin100)}")
same = goertzel_freq(x, fs, 100)   # the Hz-parameterized convenience form

print("goertzel_freq agrees: {abs(same - bin100) < 1e-9}")

half = rfft(x)
back = irfft(half, 64)
print("rfft/irfft roundtrip max err: {max(abs(back - x))}")

output

idft roundtrip max err: 1.604386e-14
goertzel magnitude at bin 6.4: 32.158025
goertzel_freq agrees: true
rfft/irfft roundtrip max err: 3.330669e-16

from signal-processing

How it works

goertzel(x, k) -- the DFT value at a single "bin" k in O(n), the standard tool for checking a handful of specific frequencies without paying for a whole FFT. k need not be an integer: this evaluates the DFT at an arbitrary frequency point between the FFT's own grid bins, not just a fast way to recover an on-grid one. k may also be a vector of bins, evaluating each independently and returning a CVec -- the K-point DFT this is named for: K arbitrary points in O(n*K), instead of every one of a full N-point fft's bins whether wanted or not.

From the note above this builtin in the interpreter, where the reasoning was written down as it was built.