14
$\begingroup$

What techniques might one use to estimate the onset time of a sinusoidal tone burst in a noisy signal?

Assume the tone burst has a known fixed frequency (but unknown phase) and a very sharp rise time, and that the goal is to estimate the onset time within better than half the rise time, and/or one period of the frequency of the tone, if possible. How might the estimation techniques change if the S/N ratio is very low (much less than 1)?

Added: Assume the tone burst is of unknown length, but longer than a small multiple of the rise time and the frequency period.

Added: A DFT/FFT shows the very probable existence of a tone. The problem is figuring out exactly precisely where in the FFT window the tone (or perhaps multiple tone bursts of the same frequency) may have started within the FFT window, or determining if the current tone started outside that DFT window, provided I have all that additional time domain data.

Radar pulse detection accuracy is closer to the resolution I need, except I only have an edge, as the tone is of unknown length, and, other than a known rise time, unmodulated. Narrow band pass filters distort the rise time, and thus kill edge arrival estimation resolution.

$\endgroup$
  • 1
    $\begingroup$ Can we assume anything about the noise? Is it stationary? Does it follow any sort of a distribution? $\endgroup$ – Phonon Sep 1 '11 at 19:34
  • 2
    $\begingroup$ Are false alarms from your detector undesirable? Do you have a specification on the probability of correctly detecting each pulse? This is very similar to (a simplified version of) front-end radar signal processing; locating (possibly-modulated) pulses embedded in noise and estimating their parameters. $\endgroup$ – Jason R Sep 1 '11 at 19:48
  • 1
    $\begingroup$ Do you need to do this in real time, or is it an offline analysis? $\endgroup$ – nibot Sep 3 '11 at 0:08
  • 2
    $\begingroup$ @hotpaw2: What didn't you like about the Goertzel algorithm as per this SO answer? $\endgroup$ – Peter K. Sep 3 '11 at 15:40
  • 1
    $\begingroup$ The Goertzel algorithm is used for tone detection, which seems to be what you are after. The output of the filter is an estimate of the "power" of the signal at the frequency for which it is tuned. Choose a threshold. If the filter output is above this, you have detected a tone. Set your threshold appropriately, and you can detect the onset of the tone earlier (and also be more prone to false alarms). $\endgroup$ – Peter K. Sep 3 '11 at 15:48
6
$\begingroup$

As we've been discussing in the comments, the Goertzel algorithm is the usual way to detect a tone in noise. After the discussion, I'm not sure it's quite what you are after (you want the onset time), but there seemed to be confusion over how the Goertzel algorithm might be applied to your problem, so I thought I'd write it up here.

Goertzel Algorithm

The Goertzel algorithm is good to use if you know the frequency of the tone you are looking for (call it $f_g$), and if you have a reasonable idea of the noise level so that you can select an appropriate detection threshold.

The Goertzel algorithm can be thought of as always calculating the output of ONE FFT bin:

$$y(n) = e^{\jmath 2\pi f_g n} \sum_{k=0}^n x(n) e^{-\jmath 2\pi f_g k}$$

where $f_g$ is the frequency you're looking for.

The Wikipedia page has a better way to calculate this.

Here is a (feeble) Scilab attempt at implementing it:

function [y,resultr,resulti] = goertzel(f_goertzel,x)
realW = 2.0*cos(2.0*%pi*f_goertzel);
imagW = sin(2.0*%pi*f_goertzel);

d1 = 0;
d2 = 0;

for n = 0:length(x)-1,
    y(n+1) = x(n+1) + realW*d1 - d2;
    d2 = d1;
    d1 = y(n+1);
    resultr(n+1) = 0.5*realW*d1 - d2;
    resulti(n+1) = imagW*d1;
end
endfunction

Consider the signal with $f = 0.0239074$ and $\phi = 4.4318752$ :

$$x = \sin(2\pi fn + \phi) + \epsilon(n)$$

where $\epsilon(n)$ is zero-mean, unit variance Gaussian white noise.

In this example, the tone starts one third of the way into the signal at index 1001.

If we run the Goertzel algorithm on it with $f_g = f - 0.001$ then we get the top two traces of the figure.

If we run the Goertzel algorithm on it with $f_g = f$ then we get the bottom two traces of the figure.

The four traces are:

  • $x$ (blue) and $y$ (red) for $f_g = 0.0229074$
  • The resulting $\sqrt{resultr^2 + resulti^2}$
  • $x$ (blue) and $y$ (red) for $f_g = 0.0239074$
  • The resulting $\sqrt{resultr^2 + resulti^2}$ (solid line) and the first result (dashed line).

As you can see, the case where the tone we are interested in is present peaks at about 250. If we set the detection threshold at about half this value (125), then the detection occurs (the square-rooted value is greater than 125) at about index 1450 --- 450 samples after the tone started.

This threshold (125) will not cause a detection in the other case (for this run, anyway), but the maximum value of that output is 115.24, we we cannot reduce the threshold too much without getting a false detection.

Reducing the threshold to 116 will cause detection in the true case (for this run) at index 1401... but we run the risk of more false alarms.

enter image description here

$\endgroup$
  • $\begingroup$ A running Goertzel filter is more suitable if one is only looking for an existence estimate within a fixed length window. A running Goertzel without a loss/decay term changes it's bandwidth over its length, and the narrower bandwidth later in time provides a worsening arrival time estimate, more sensitive to noise and threshold errors. $\endgroup$ – hotpaw2 Sep 5 '11 at 15:09
  • $\begingroup$ @hotpaw2: Correct. You can introduce a "forgetting factor" to keep Goertzel running, but otherwise it remembers everything. $\endgroup$ – Peter K. Sep 5 '11 at 15:27
  • $\begingroup$ Remembers everything? It's an FIR that can be implemented in recursive form. What have I missed here? $\endgroup$ – Oliver Charlesworth Sep 5 '11 at 21:28
  • $\begingroup$ @Oli: If you look at the equation for $y(n)$ above, you'll note that it doesn't end. Yes, it's estimating a (scaled) DFT coefficient, but it's definitely not FIR. $\endgroup$ – Peter K. Sep 5 '11 at 23:26

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.