# What are some methods for detecting a sinusoid in noise?

I'm looking for a broad classification on the kinds of techniques available. Something I can use to begin a literature survey.

Some details:

1. should be feasible for real-time implementation.

2. Binary decision, I should be able to input the signal continuously, and the algo has to detect the start and stop times of the sinusoid in the waveform.

3. There is no other signal, i.e. if the sinusoid is not present, then there will only be noise

4. the input is band-limited, and the sinusoid, if present, is assured to be within that band.

5. Tradeoffs are between speed (how soon after the appearance of the sinusoid can the algo detect its presence) and false positives (should be minimal)

6. I can't provide any exact numbers about acceptable performance measures, because I'm not sure myself. I intend to implement all your suggestions for my application and find out myself. I'm just looking for the "standard" techniques for tackling this problem.

Further details:

1. The input is the output of a band pass filter, so the noise is also significant only in the pass band.

2. There is no surety when the sinusoid may appear. The duration of the sinusoid is in the range of 50-100 ms. The amplitudes of the sinusoid will fluctuate.

-
Probably a sliding (or a walking) window Fourier analyser would do the job. There are some more details needed: is noise also band-limited? Is there a guaranteed tune-up time when only noise is present in the input? Are noise and sinusoid amplitude-stable over time? –  mbaitoff Jan 29 '13 at 3:20
As far as I understood, you are going to detect beeps over a noisy channel. You should then specify an amplitude (energy) threshold that would distinct a beep among the noise. You also mention the band-limit of the beep. Does that mean that a beep spectrum is wide-band or that a beep spectrum is narrow but anywhere within the band. You should also specify how a beep is perceived - is it like fast or slowly rising/falling tone, is it accompanied by turn-on/turn-off click, and how short/long could they be relative to scanning window. –  mbaitoff Jan 29 '13 at 5:37
Thanks! That gives MUCH more information about the problem. –  Peter K. Jan 29 '13 at 13:24
Do you know anything about the distribution of the noise? Also, how precisely do you know the frequency of the sinusoid a priori (if at all)? –  Jason R Jan 29 '13 at 15:34
@Jason R the noise is Gaussian. The frequency of the sinusoid is not known. It is only assured to be in the range of 80-250 Hz. Different "beeps" will be at the same center frequency but amplitudes may vary. –  ankit Jan 29 '13 at 15:53

Depending on the frequency of sampling, a FFT (Fast Fourier Transform) will work. For example, if your sampling rate is only once every 20 ms, you'll only get a few samples of the sinusoid, but if you're sampling every 0.5 ms then you'd get a lot more samples. FFTs usually work best with a large number of samples to average over. In that case even if your signal is the sum of a few sinusoids, they can be accurately determined.

Alternatively, you could have a look at the MUSIC algorithm. I'm not too sure about the details of how it is implemented, but it has been implemented in several real-time detection scenarios. An alternative to MUSIC is the Esprit algorithm.

Still, if your sample size is large enough and the noise doesn't swamp the signal entirely, then an FFT will be (on average) the fastest option.

-
Shortened MUSIC implementation: $P_{MUSIC}(\omega) = \frac{1}{e^H P_n e}$ where $P_n = E_n E_n^H$ and $e^H = [ 0 , e^{j \omega} , ... , e^{(N-1) \omega} ]$. $E_n$ is an NxP matrix where the columns are the eigenvectors corresponding to the P smallest eigenvalues of the autocorrelation matrix, $R_{xx}$. Determining what P should be is non-trivial and covered by Wax and Kailath (1985), though you can sometimes do an "eyeball" estimation to determine signal eigenvalues vs. noise eigenvalues. –  Dave C Jan 29 '13 at 16:43

One way to detect a sinusoid is to use the Goertzel algorithm. Rick Lyons gives a nice write-up here about how to use it for detection.

That second link has this equation for filtering your incoming signal and calculating the "decision statistic":

-
The Goertzel algorithm seems to be a mono-frequency resonant detector. How does this work for broadband tones in original poster task? –  mbaitoff Jan 29 '13 at 14:58
The OP seems to want "bandlimited" not "broadband". If you choose the Goertzel length well, then it should be able to cope with "bandlimited" sinusoids. I agree that there is a trade-off: a sinusoid precisely on the Goertzel center frequency will give a higher reading than one of the same amplitude at a different frequency. Most FFT-based approaches have the same problem. You can always run a two or three Goertzel detectors with different center frequencies if this is an issue. –  Peter K. Jan 29 '13 at 15:13
@PeterK, Why would one not simply use a family of complex DFT tones to down-mix against? (In other words, what advantage does the GA have over the former technique?). Interesting answer btw. –  Mohammad Jan 29 '13 at 15:23
@Mohammad: A family of complex DFT tones is just what the Goertzel algorithm is implementing (if you implement several, frequency-offset Goertzel filters). –  Peter K. Jan 29 '13 at 16:47
The family of Goertzel algorithms can be thought of as simply the computational fusion of a complex exponential/sinewave generator plus a vector dot product, identical to getting the magnitude of a complex downmix using the same trig function generator (except possibly for numerical stability and dynamic range issues). –  hotpaw2 Jan 29 '13 at 20:38

Everything depends on SNR. The lower the SNR, the more processing you have to do to separate signal from noise. I have solved a similar problem in the past, where I was looking for an intermittent, low SNR sinusoidal signal across a fairly broad range of frequencies. This is what worked for me:

1. Perform an offline characterization of the noise of your system (in the frequency domain). If the ambient noise level changes over time, periodically update this noise level online when the algorithm has high confidence that the signal of interest is not present. If the noise isn't very stationary then this might not help much (and could hurt).
2. Perform a sliding FFT on discrete time windows. Look for frequencies with energies that are some threshold above the background noise. Get a list of candidate “peaks” that might be the signal of interest. I opted to keep a circular buffer of data including samples from previous time windows so that the FFT had a better frequency resolution.
3. Build sinusoidal matched filters for the peak frequencies of interest identified in the FFT. Look for responses above some threshold. The match filter (a.k.a. the autocorrelation function) can attenuate noise really well and in my system it was quite good at pulling detections from what at first glance appeared to be hopeless data. As a time domain filter, the matched filter can also tell you when the signal appears and when it disappears.

As others have recommended, I experimented with the MUSIC algorithm to separate signal from noise. For my problem it was slightly better at finding low SNR candidate signals than the FFT, but since the computational burden was so much higher (and my algorithm was running on a wimpy fixed point DSP) I opted not to use it. It was easier to just set the detection threshold lower with the FFT, detect more spurious peaks, and eliminate them in the matched filtering stage. Low SNR detection can be a bit of a dark art but if you know enough about your system you can reliably detect signals with a lower amplitude than ambient noise levels. It all depends on what information you know about your system that you can exploit.

-
"Low SNR detection can be a bit of a dark art" Very true. I am curious, you get a spurious peak in the FFT, construct a matched filter, (how did you pick length), and then cross-correlate, and then sometimes reject the answer? How could you have even had a spurious peak in the first place then? –  Mohammad Jan 30 '13 at 2:07
You get the length of the matched filter from knowing your sampling rate and the frequency of the candidate peaks. You construct one full sine wave and check the correlation of the constructed sine wave over the current window of time domain data. But you only construct the matched filters at frequencies that have been determined as candidate peaks in the FFT. The matched filter is better able to find low SNR detections than the FFT and it serves as a validation. If you have high SNR then FFT peaks don't need any extra validation, but if SNR is low the FFT tends to give false peaks. –  Bob D'Agostino Jan 30 '13 at 3:06
Bob, I see. And how do you decide that a peak exists in the FFT initially? (What metric do you use to compute that?) Something like max over mean? –  Mohammad Jan 30 '13 at 4:09
@BobD'Agostino: The DFT can be viewed as a bank of critically-sampled filters, each with an impulse response that is a complex exponential function. It's not clear how this would be much different from the approach that you're suggesting, unless your "peak frequencies of interest" are measured at fractional DFT bin offsets, thus allowing the filter to be better centered on the tone of interest. At low SNR, though, it can be difficult to locate the precise peak locations. –  Jason R Jan 30 '13 at 13:28

I would propose the following:
1. organize a sliding window that is wide enough to contain the whole band of the signal (at least several periods of the lowest frequency signal)
2. Perform a FFT of samples that are currently within a window, obtain a power spectrum from it.
3. Crop the spectrum with the known band limits.
4. Sort the remaining power spectrum values in decreasing order. Since the noise is gaussian, the noise spectrum would be averagely flat within the band, and if the mono-tonic beep was present in the window, it would produce the spike(s).
5. Identify the typical spike bandwidth. Take the highest amplitude samples from a cropped-sorted power spectrum, obtain an average. That would be the potential "beep" energy.
6. Also obtain an average of the remaining band samples, that would be the noise energy.
7. Compute a ratio of energies obtained in (5) and (6). If the ratio exceeds the given threshold, set the flag indicating that the beep is found. If not, set the flag that there's currently no beep.
8. Slide the window to the next frame (either sample-by sample, or by some larger step).

-
I think this is interesting but you lost me on the averaging and sorting part. Could you please clarify your steps? Thanks. –  Mohammad Jan 29 '13 at 18:31
Actually it is not necessary to sort the power samples, you may just search for frequency peaks and take some samples around the peak and average them. Probably sorting is not even needed here unless you are going to search for median. –  mbaitoff Jan 30 '13 at 13:57

This is a statistics problem. If you can characterize the noise, then you can look for particular characteristics of your signal of interest whose probability is below some likelihood (your required false positive error rate) to just randomly appear in the noise.

If you know the minimum duration of your sinusoid of interest (say 50 mS), you can try overlapped sliding FFT windows the length of that duration and look for spectral peaks above some threshold calculated by characterizing the noise. If the same peak above the noise floor appears in multiple successive FFT windows, then the length of the sinusoid might be corresponding longer, depending on your FFT frame length and overlap.

-