Low level tone detection and measurement project

[belgiex]

I have a requirement for the following project: Detect and identify signal single frequency tone in noisy analog signal. Tone frequency range 1000-4000 Hz. Frequency resolution steps 15 Hz. 30 readings per second. Want lowest cost solution to implement using PIC family microprocessor. Looking for suggestions on how to do this.

[UncleBog]

Goertzel filter.

[bigtoy]

Goertzel filter.

What he said. I've used these for DTMF tone decoding. Works well, simple to implement.

[Signal]

30 readings per second.

Do you mean ADC reading, so sampling rate 30 samples per seconds?
Or do you you expect a decision for each 33 ms window?
Noise is white or just unknown?
All you need is a frequency of tone? What is the threshold of detection in dB over noise level?
We know about signal that it is a single tone. But what duration and how stable is it? How fast do you need to detect it? With delay not greater than 30 ms? Or 30 periods of tone? Actually maximum achievable performance depends on noise level and of course on ability of chosen PIC.

<...>PIC family<...>

... means almost nothing. For lower end I'd start from PIC18 as it has hardware multiplier. Fro higher end - dsPIC/PIC24 or PIC32.

Goertzel filter.

What he said. I've used these for DTMF tone decoding. Works well, simple to implement.

DFT(FFT) is not optimal here. Goertzel is not applicable here at all.

[belgiex]

Do you mean ADC reading, so sampling rate 30 samples per seconds?

No, sampling rate will be greater than Nyquist minimum (8Khz) because of 4 kHz audio frequency maximum.

Or do you you expect a decision for each 33 ms window?

Yes.

Noise is white or just unknown?

Unknown.

All you need is a frequency of tone? What is the threshold of detection in dB over noise level?

Yes all I need is to determine frequency of tone. Threshold TBD.

We know about signal that it is a single tone. But what duration and how stable is it?

Stability is good and is function of frequency (lower frequency longer tone duration), worst-case tone duration (shortest duration) .05 sec at 4000 Hz

How fast do you need to detect it?

Every .05 sec.

With delay not greater than 30 ms? Or 30 periods of tone?

Tone detection 30 times/second

Actually maximum achievable performance depends on noise level and of course on ability of chosen PIC.

Agree.

DFT(FFT) is not optimal here. Goertzel is not applicable here at all.

The research that I have performed Goertzel is not applicable (need ability to see at least 200 different frequencie). FFT application (spectrum analyzer) is what I thought was possible. Why is FFT not optimal?

[Signal]

The research that I have performed Goertzel is not applicable (need ability to see at least 200 different frequencie). FFT application (spectrum analyzer) is what I thought was possible. Why is FFT not optimal?

FFT is not optimal because it is too indirect to calculate 512 coefficients to get 256 amplitudes to search among them for peak then to find frequency that is between two most significant nearby "harmonics"... such waste of power.
FFT is just fast DFT. DFT is just a bunch of fixed width correlations between signal and set of orthogonal "templates" (sin and cos). You need something different.

What you need is to use apriori information about your signal to find the shortest path to desired parameter.

First point you have to know about - all three parameters of one sine wave (amplitude, phase and frequency) can be derived from only three samples. theoretically. without noise, etc.

There is the least complicated model of periodic signal with additive noise - autoregressive model.

For single sinusoid:

          sᵢ = A sin(2πif/F_s+φ) ,

the model is:

          sᵢ = Ksᵢ₋₁ − sᵢ₋₂ ,

where K = 2cos(2πf/F_s).

For single sinusoid with noise:

          xᵢ = sᵢ + noiseᵢ ,

the model looks:

          xᵢ = Kxᵢ₋₁ − xᵢ₋₂ + nᵢ − Knᵢ₋₁ + nᵢ₋₂ .

You can start from major simplification:

          xᵢ + xᵢ₋₂ = Kxᵢ₋₁ + eᵢ  ,

          K = (xᵢ + xᵢ₋₂)∕xᵢ₋₁ + e'ᵢ  .

It's better to select set of samples with bigger |xᵢ₋₁| for better arithmetic accuracy of last equation solution.
As an option you can adapt sampling rate (just decimating ADC samples) after obtaining first estimation of K.
Then add some averaging or make iterative adaptation of estimated K or do more sophisticated min(F(e')) or min(F(e)) or even min(F(noise)) optimization.
Comparing mean and deviation you can set detection threshold.

Develop algorithm in PC simulation environment (Matlab, Octave, FreeMat or Python or whatever) to estimate actual computational burden to select proper target devices (uC and ADC).

Here are some keywords for start:
ML (maximum likelihood), AR (Autoregressive frequency estimation), ARMA (Autoregressive Moving Average), MUSIC (MUltiple SIgnal Classification).
https://en.wikipedia.org/wiki/MUSIC_(algorithm)
Most difficulties and complications of these methods relate to common case of this task - multiple harmonics and maximum achievable performance with presence of known noise.

Also knowing LMS is a good background to start understanding adaptive algorithms.

How fast do you need to detect it?
Every .05 sec.
With delay not greater than 30 ms? Or 30 periods of tone?
Tone detection 30 times/second

I meant that you can take into account a possible tradeoff - to use weak microcontroller (PIC18 for example) but get some delayed result due to calculation time with some unprocessed period of signal.
Another choice  - select sliding window iterative sample by sample algorithm with updated result ready at each sample (or at last sample of block) or block pipelined processing (calculation upon previously recorded window while next window is sampling and get result after new window recording is finished - thus maximum 30ms delay of result from most recent sample of 30ms window)

Edit: use math symbols

[Signal]

For given regression:

      xᵢ₋₁ + xᵢ₊₁ = Kxᵢ + eᵢ ,

and Least Squares criterion:

           ∑eᵢ²→min ,

the solution looks very simple:

    K = ∑xᵢ(xᵢ₋₁+xᵢ₊₁) ∕ ∑xᵢ² .

So for block processing (without iterative replacement of division) you need:
   storage for 4 variables plus current sample
   3 additions and 2 multiplications per sample
   1 division per N samples.

Sliding window allows to make decision each sample with the cost of additional 2N buffer (plus 2 addition per sample and 1 division per decision).
Window that not slides but makes steps instead requires much less buffer and still allows to increase averaging window preserving tempo of decisions.
Also you can recall exponential averaging if it fits better with your task.

https://en.wikipedia.org/wiki/Least_squares
https://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)

edit: use math symbols from http://htmlarrows.com, https://en.wikipedia.org/wiki/List_of_mathematical_symbols

[belgiex]

Signal,

Have been traveling.

You have provided much information to think about.

Belgie