0
$\begingroup$

Assuming I only care to calculate the magnitude and phase of ONE single frequency from a signal, how can I get this information without calculating anything else?

For example I want to come up with an algorithm that is similar to that of the DFT, except given an input frequency (say 440Hz) it will return only the magnitude and phase at THAT specific frequency and nothing else. Doing a full DFT would be overkill because it calculates over a wide range of frequencies. In this particular case assume I only want to know about this one frequency and don't need any surrounding context.

I know this doesn't seem particularly useful but I would like to figure this calculation out so I can expand it to include specific surrounding frequencies as well without all the computational overhead of performing a full DFT.

$\endgroup$
2
  • $\begingroup$ Please see this $\endgroup$
    – Jdip
    Commented Apr 30 at 2:53
  • 1
    $\begingroup$ Thanks @Jdip that actually looks like the EXACT equation I came up with LOL. Glad I was going down the right path $\endgroup$
    – tjwrona
    Commented Apr 30 at 3:02

2 Answers 2

3
$\begingroup$

You can simply use the DTFT

$$ X(\omega) = \sum_{n= -\infty}^{+\infty}x[n]e^{-j\omega n} $$

for any frequency you want.

The summation limits can be a bit tricky. In practice you can't sum from $ -\infty$ to $+\infty$ so you you need to carefully manage your summation range with respect to the period of the analysis frequency and you may have to consider applying a window.

$\endgroup$
2
  • $\begingroup$ Is omega just 2 * pi * f / f_s? If so I think I am on the right track here $\endgroup$
    – tjwrona
    Commented Apr 30 at 3:03
  • 1
    $\begingroup$ And if you care about utmost efficiency, consider using the Goertzel algorithm dsp.stackexchange.com/a/67756/21048 . $\endgroup$ Commented Apr 30 at 3:36
0
$\begingroup$

For example I want to come up with an algorithm that is similar to that of the DFT, except given an input frequency (say 440Hz) it will return only the magnitude and phase at THAT specific frequency and nothing else.

Note that "phase" is a relative measure, always. In other words, you need to define your local idea of a cosine to be that of "0 phase". Without a reference, the phase is completely random. For example, if you started your analysis of your 440 Hz tone just 1/220 s later, you'd get the opposite phase!

With that out of the way, sure, the Goertzel algorithm is "the DFT, but just for one frequency". More generally, spectral estimators would be what you're after when looking for a single frequency – and using a spectral estimator that's not just the DFT would be a good thing, because the frequency resolution of the DFT is given by twice the sampling rate, divided by the length of your DFT.

To know the spectral power at exactly 440 Hz, you'd need a DFT (or the Goertzel) that has a length $N$ such that 440 Hz is a multiple of the $N$th part of the sampling rate, i.e,

$$ N = k\cdot \frac{f_s}{440\,\text{Hz}}$$

needs to hold true for some integer $k$, and even then you'd need to beware the energy in the spectral side lobes of your window (sinc, if just the DFT). But when choosing $N$ such that the above works out, you at least only have to worry about the sidelobes of your own window, not of all the frequency-shifted windows.

Estimators like MUSIC don't suffer that restriction: You can choose their observation length $N$ purely to achieve the resolution (the fundamental truth of the time-bandwidth limit, which also underlies Heisenberg's Uncertainty Principle, still applies. You can't get arbitrarily good spectral separation: to completely isolate the effect of two tones lying 0.1 Hz apart, you will need to observe for at least 2· 1/(0.1 Hz) = 20 s; no cheating math, no cheating quantum physics, either.

Which spectral estimator you want? Impossible to tell without knowing your signal and noise model! Do you know that there's white noise only, and a known number of narrowband signals or even discrete tones in there? That would call for MUSIC. White noise + known number of tones, but not where they are? ESPRIT. Got compute power, and want to overcome the spectral leakage of the pure-DFT spectrogram mentioned above? Thomson Multi-Taper. Signal comes from something you know is an autoregressive system (say, a naturally excited RC oscillator)? Yule-Walker. Totally happy with the DFT, just need one bin of it? Goertzel.

The list goes on; writing down the problem you're solving in the most precise terms possible (for example, in a new question) would help people choose an appropriate estimator!

I can expand it to include specific surrounding frequencies as well without all the computational overhead of performing a full DFT.

"as well as surrounding frequencies" sounds like you're actually not that bad off with the full DFT, implemented as an FFT; the complexity savings inherent to the FFT are so high that the Goertzel algorithm done for a subset of $K$ out of $N$ frequencies is only lower if $K \ll N$, typically, 1 or 2. A naive Goertzel (second order) implementation has $2N +4$ multiplications¹; the classical FFTs have $N\log_2(N)$ multiplications, and these are very well-understood; for the $K$-point Goertzel to be lower in cost than the FFT, $$K\cdot\left(2N + 4 \right) < N \log_2(N) \iff K <\frac{\log_2(N)}{2+4/N}\le \frac{\log_2(N)}{2}$$ must hold true. Assuming, out of the blue, that $N=1024$ for you (equivalently to a 46.875 Hz frequency resolution at 48 kHz sampling rate), then

$$K \le \frac{10}{2}\iff K \in \{0, 1, 2, 3, 4, 5\}.$$

So, unless you feel you are likely to implement a world-class Goertzel to compete with the world-class FFTs that you get for reasonable FFT lengths, I'd say, forget about Goertzel should you need more than 2 frequencies, and just use the FFT (as implementation of the DFT).

Again, this is only if the periodogram (i.e., spectral estimation based on the DFT) is actually the estimator you want. Which I kind of don't believe.


¹ assuming this is all fixed point, because one usually doesn't ask at this level about optimizations at audio rates on machines that natively do floating point audio processing, multiplications are the limiting factor, not additions; the opposite is true if this is about floating point. If you're on a PC, processing a single or a handful of audio streams with an FFT, your bottleneck is not your computational throughput, but simply the speed at which you can get audio signal from your SSD array. For live audio processing, not even the latency of a full FFT would matter, compared to number of samples you need to do it (or any Goertzel). The amount of audio samples per second are simply not very much data for modern hardware, and optimizing that does smell of premature optimization with no benefit. When you have the compute power, use the optimal estimator in terms of estimation quality, not performance.

$\endgroup$
2
  • $\begingroup$ Would using a regular FFT still be the right choice when I need to look up very specific frequencies? For example I need to check frequencies that line up with musical notes. If I do an FFT with a size of 1024 some of the bins won't line up directly with the notes I am looking for. $\endgroup$
    – tjwrona
    Commented Apr 30 at 14:09
  • $\begingroup$ That's literally what most of my answer is about. If you need more help, you will need to edit your question (or ask a new one, if that changes your current question too much), explaining what you want to do with these results, AND what your signal model is AND what your noise model is. $\endgroup$ Commented Apr 30 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.