0
$\begingroup$

Assume a dataset where the rows represent signals: each signal $s$ is sampled at a sampling rate $f_s$ and available as an array of common length $T$. For an increasing sequence of integer times $t_i < T$, I would like to find out the information gain reached by considering the rest time $T-t_i$. Intuitively, I would like to find out a $t_{\dagger}$ for which the amplitude of the different frequencies in the signal has already converged. The motivation behind this is that I would like to potentially shorten the measurement time in the future, assuming the data distribution remains the same.

My approach has been to analyze the convergence in the FFT spectra of the increasing time slices, with the FFT computed from time $t=0$ to the corresponding $t_i$.

Are there any more adequate ways of doing this?

$\endgroup$
  • $\begingroup$ Is that convergence over one signal or many signals? Because if it is over one signal, even if you fix your $N_{FFT}$, the variances will be over bands of different width as you increase the duration of the signal. So, yes, it will appear to be "converging" but it could also be because of a re-distribution of the SNR. What exactly is the motivating problem? $\endgroup$ – A_A Dec 7 '18 at 11:39
  • $\begingroup$ @A_A The convergence is over many signals. I will edit the question to clarify. The motivating problem: I want to find out whether at the stopping time $t_{\dagger}$ I already have enough information so that in the future I can reduce the measurement time about specific frequencies, assuming the data distribution remains the same. $\endgroup$ – AlexGuevara Dec 7 '18 at 11:43
  • 1
    $\begingroup$ your goal of shortening a test would fall in the category of Sequential probability ratio tests developed by Wald for use in industrial testing. I don’t know the details of why or what you are trying to test but the SPRT seems to be the direction of what you want $\endgroup$ – Stanley Pawlukiewicz Dec 8 '18 at 0:56
  • $\begingroup$ @StanleyPawlukiewicz thank you for pointing me in this direction! If you care to elaborate on the SPRT as an answer, I will gladly accept it. $\endgroup$ – AlexGuevara Dec 12 '18 at 5:57
1
$\begingroup$

I'm afraid the premise of your approach is faulty as can be shown with a single counterexample. Suppose your signal is a simple real pure tone sinusoidal. When the interval length reaches 3 cycles, bin index 3 (zero based) of the DFT will be non-zero and all the rest of the DFT bins will be zero. (Considering only the lower half of the DFT values because a real valued signal as the upper half is a conjugate mirror of the lower half.) Then as your interval increases the DFT starts to smear with leakage. When you reach 3 and 1/2 cycles, the smearing will be the greatest and the magnitudes of bins 3 and 4 will be nearly equal and their phases nearly 180 degrees apart. When you get up to 4 cycles in your sampling interval, once again all the bin values are zero except for bin 4. That behavior will repeat for each whole number of cycles your interval reaches and therefore there will never be any kind of convergence happening.

It is not clear to me from your question, but are you assuming your signals are mixes of steady pure tones?

$\endgroup$
  • $\begingroup$ Thank you for your clarification. Assuming the signals were simply mixes of steady pure tones (even if unrealistic), could you suggest any alternatives to the faulty approach? $\endgroup$ – AlexGuevara Dec 7 '18 at 19:46
  • $\begingroup$ @AlexGuevara,That is precisely what my blog articles are leading up to. You can find a link to my blog on my profile page (click on my name to find it). Send me an email, address in profile, and I will reply with a preview/summary. Solving this problem is what got me into DSP. $\endgroup$ – Cedron Dawg Dec 7 '18 at 20:25
1
$\begingroup$

The consideration of time duration with the FFT, assuming stationary signals (multiple tones but they are not changing with time), is Frequency Resolution; how well you can still distinguish between two closely spaced tones (at approximately the same power level). The longer duration in time, the tighter the achievable resolution. For a rectangular window (which means you are taking the FFT of a data set directly without any modification of the envelope of the signal), the frequency resolution is 1/T where T is the duration of your (non-zero padded) data in time. This ends up being 1 bin width (1 point) in frequency given the relationship between the sampling rate, the number of points in the FFT and the time duration of the signal. You can zero pad the signal (meaning add more zeros to make the length of the data set longer) which will result in more points in frequency, but this simply interpolates more frequency samples of the underlying Discrete Time Fourier Transform (DTFT) but does not in any way increase the resolution (which makes sense, you did not add any more data).

When you have closely spaced tones that are at significantly different power levels, then the dynamic range (ability to see both strong and weak tones simultaneously) is of concern and in this case we often window the data first, which serves to reduce spectral leakage (sidelobes from one tone burying another weaker tone), at the expense of frequency resolution: so you gain dynamic range but the frequency resolution is degraded as a result.

A third consideration related to this is scalloping loss: which is the variation in amplitude for signals that are located exactly on a frequency bin versus mid-way between bins, which is what Cendron is referring to in his answer. This isn't an actual "loss" since the energy is just being smeared to adjacent bins, but does indicate the variation that could exist when only one bin is considered.

This is further demonstrated in the plots below, showing the frequency response for each bin in an example 10 point FFT. The first one shows the case for a Rectangular window (where the frequency response is called the Dirichlet Kernel) and the second one for when a Blackman Window (Showing how the variation can be significantly reduced through the use of windowing).

The lines show the output magnitude of EACH bin, given a frequency anywhere along the horizontal axis; for example in the top plot, if you drew a vertical line at x = 4.5, consistent with an actual input signal at this frequency location, every single bin in the 10 point FFT will have an output level somewhere between -20 dB and -4 dB (approximately). Compare this to the case where the input signal is exactly on a bin center, for example a vertical line at x = 5, only that bin has a magnitude output as the response from all the other bins is 0. From this we see that the magnitude of any one bin will vary up to 3.92 dB, given a consistent amplitude input signal that changes only in frequency, but this is just from energy that is getting translated to the other bins as the frequency is changed.

The second plot shows the same result when a window is used (in this case a 10 point Blackman Window), specifically showing the loss due to windowing (as we have selectively reduced our input signal) but more importantly showing the decreased variation as we vary the input signal along the x-axis (as detailed in the third plot).

From these examples you also clearly see the trade-off in frequency resolution and dynamic range that was referred to earlier.

Scallloping Loss Rectangular Window

Scallloping Loss Blackman Window

Zoom in of Blackman window

You can further reduce scalloping loss effects for applications when you are streaming FFT results over time on longer data sets by using overlap-add techniques. This is all explained in detail in a classic paper by fred harris, "On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform", found at this link: http://web.mit.edu/xiphmont/Public/windows.pdf

$\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.