1
$\begingroup$

This week I was having an interview with a Professor for Grad School. He asked a bunch of questions related to signal processing that lead up to some questions about power leak on the FFT spectrum. So far so good, but then he caught me when he asked something around those lines:

"given just an FFT spectrum, with no prior information about the signal or the sampling frequency, how one can differentiate if two bins close together are a case of power leakage or two distinct frequencies?"

At the time of the interview nothing came to mind so I just answered that it was not possible but since then I was wondering if there is a way of making this distinction. I tried looking online but couldn't find any material that answered this so any help would be greatly appreciated.

Thanks!

$\endgroup$
1
  • $\begingroup$ He implies an incomplete (in the sense that it does not allow to calculate probabilities) signal model in the alternatives offered, yet states that there is no information about the signal. It was not a well thought out question from him, if it was an honest question. $\endgroup$ – Olli Niemitalo Sep 14 '20 at 5:39
2
$\begingroup$

Assuming the spectrum is sufficiently interpolated to see the detail within the resolution bandwidth (which is a reasonable assumption given the question), and the waveform isn't further windowed beyond the rectangular window (as I would argue that any such windowing that is applied is equivalent to the presence of multiple tones closely spaced given windowing is an applied amplitude modulation) then one obvious way to quickly distinguish these two cases is by observing the width of the main lobe (as well as all other features such as null locations, or non-existence of the nulls, but the main lobe width would be robust under noise conditions)-- given the kernel of the rectangular window (the DFT of the window ) convolves in frequency with each tone. If there is one tone we would see the kernel alone. If there are two tones spaced closer to together, then both tones would convolve with the kernel, and therefore widen the result. (The kernel for a rectangular window in time is the Dirichlet Kernel in frequency, basically an aliased Sinc function, so if the spectral peaks are the same width as the Dirichlet Kernel, which is known, not computed, then we can easily declare that peak to be a single tone).

If sufficiently interpolated and noise free then we can also quickly detect this by the lack of frequency nulls (although the nulls are soon buried by any noise so this would not be a robust test). If the spectrum wasn't interpolated and the frequencies are so close that a bin width increase is not obvious, then we could compare the phase and magnitudes of the leakage values in all other bins to what would be expected with the underlying Dirichlet Kernel, under noise conditions we could use all bins and a correlation to what would be expected for a single tone to provide a confidence of one tone or not.

Further Details on using Main Lobe Width Measurement

This process of main lobe width measurement would be precise in confirming a single tone down to very small frequency offsets in the case of a single exponential tones of the form $e^{j\omega t}$, but will have a lower offset limit for the case of real tones due to the interaction of the two exponential tones that each real tone contains ($cos(\omega t) = 0.5(e^{j\omega t} + e^{-j\omega t}))$. In which case we would see even for a single tone a small variation in main lobe width versus frequency that becomes more pronounced as we approach the Nyquist boundaries. The effects of this, and interaction from any other tones further away for the same reason, become significantly reduced if the waveform was windowed prior to computing the DFT (which can't be assumed based on what the OP has stated, and as I already mentioned I would argue the result of windowing a single tone results in the presence of multiple closely spaced tones!). To show the practical extent of using the main lobe width approach, I plot the variability of the main lobe width versus frequency for the rectangular window case at the bottom of the post, which provides insight into the practical limitation of how close we can distinguish multiple tones (pretty close! down to 0.02 bins for most of the frequency range, and 0.2 bins for all frequencies except the end points).

To demonstrate this effect of simply measuring the width of the main lobe for the case of an interpolated spectrum, and its relative insensitivity to noise to address hotpaws comment, see this example below with a rectangular window and two equally leveled tones that are within one bin width (the resolution bandwidth of the rectangular window is 1 bin, so more than that would not be sufficient for "close"):

DTFT of F1, F2, F1+F2

Here is the comparison of the composite signal with and without noise, where the noise is only 6 dB lower:

F1+F2 with and without noise

(And in this case, even if the spectrum was not interpolated, meaning the only samples available are at the integer bin locations; we can see how the increased width of the main lobe would still be obvious through inspection)

For further details on the limitations of the main-lobe width measurement for a real tone, the following plot below shows the variation of the main-lobe bin width at -3 dB for a rectangular windowed 128 point DFT (interpolated by zero-padding out to 12800 points), where the "truth" given by a single exponential tone approaches 0.886 bins for large $N$ (where $N$ is the number of samples, derived from $2\omega/\pi$ for $Sinc(\omega) = \sin(\omega)/\omega = 0.707$, and can be exactly determined for any size N from the Dirichlet Kernel, $D(\omega)$, from $2\omega/\pi$ for $D(\omega) = 0.707$, where:

$$D(\omega) = \frac{\sin(N\omega/2)}{N\sin(\omega/2)}$$

and $\omega$ is the normalized radian frequency in units of radians/sample : $\omega \in [0, 2\pi)$ for $N \in [0, N)$

With the results shown in the plot immediately below:

bin width of D(x)

As given by the convolution, this bin width will be increased by the frequency separation of two tones that are less than 1 bin apart, and as long as that separation is greater than twice the variability of a single tone, it would be detectable (for example the variability when we are more than 10 bins away from the Nyquist boundaries is less than 0.01 bins, which holds as N is increased). This plot below was simulated but could be analytically predicted by the interference pattern of the underlying Sinc function that becomes the Dirichlet Kernel through aliasing. This demonstrates the practicality of using this for distinguishing a single tone from multiple tones closely spaced.

bin width variation

$\endgroup$
2
  • $\begingroup$ This assumes the main lobe isn’t widened by the local noise floor, so there is some ambiguity if the noise floor isn’t zero. $\endgroup$ – hotpaw2 Sep 13 '20 at 13:27
  • $\begingroup$ @hotpaw2 If you have any reasonable SNR of the two tone relative to the noise I don't see how the noise floor can possibly widen the main lobe of any significance, given this is a convolution of the spectrums ?? $\endgroup$ – Dan Boschen Sep 13 '20 at 13:28
1
$\begingroup$

One way is to estimate the tone (pure sinusoidal signal) parameters from the DFT values, then generate a matching DFT (by formula or by generating a signal and taking the DFT), then measure the variation between the actual and theoretical. Any variation is due to either two (or more) close tones, nearby tones, variations from pureness, or noise. So, it can get complicated.


Dan's answer is a solid theoretical way to look at it. Mine is based on a different set of theories. Both approaches are working on the principle of measuring the width of the center lobe compared to the expected value for a single tone. I would point out though that pragmatically, mine is a lot more computational efficient and doesn't require a priori knowledge of expected lobe widths (as you are calculating it each time). Interpolation of the DFT to get the DTFT is very expensive computationally.

Here is the equivalent interpolation done in the signal instead of the spectrum. The math is the same:

Resampling and removing high frequency noise?

In more depth:

Absolute convergence of periodic sinc interpolation

Speculation:

Had you asked your interviewer, before attempting to answer, if there were only two tones present and how much noise to expect, it wouldn't have mattered how much you stammered they would have been thinking "he gets it" and just heard "blah blah blah" as they were looking down at the next question.

The best way I have found so far to actually measure the difference between two closely spaced tones, presuming the same amplitude, is to remove the effects of the other tones from the spectrum, take the inverse DFT, and use the frequency of the apparent tone (midway between the two tones) and the frequency of the envelope (related to the difference in frequency of the two tones). It could be done with a numerical model in the spectrum (a priori knowledge), but the few times I've taken a stab at deriving equations I end up with having to make an approximation, so I've stopped. The algebra gets complicated fast. Search on "beat phenomenon" for more details on a wavering envelope on a tone from the sum of two pure tones.

$\endgroup$
0
$\begingroup$

If the phase (recast in terms of oddness to evenness ratio) of the two sinusoids are not the same, and you have the complex spectrum, then the phase of the two bins will be twisted. For just one sinusoid, the (odd/even or center justified) phase will be the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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