Detect a specific frequency/tone from raw wave-data

Question

I am reading a raw wave stream coming from the microphone.
(This part works as I can send it to the speaker and get a nice echo.)

For simplicity lets say I want to detect a DTMF-tone in the wave data. In reality I want to detect any frequency, not just those in DTMF. But I always know which frequency I am looking for.

I have tried running it through FFT, but it doesn't seem very efficient if I want high accuracy in the detection (say it is there for only 20 ms). I can detect it down to an accuracy of around 200 ms.

What are my options with regards to algorithms? Are there any .Net libs for it?

Corron

Any I want, right now 44,1k (16-bit stereo). I receive a 2k sample every ~20ms. – Corron

Answer 1

You may want to look at the Goertzel algorithm if you're trying to detect specific frequencies such as DTMF input. There is a C# DTMF generator/detector library on Sourceforge based on this algorithm.

Cherub

Would Goertzel work even with other noise (for instance music), or does it require a more or less clean tone? – Corron

I don't see why it wouldn't work in the presence of other noise; it should at the very least be no worse than any other discrete Fourier transform algorithm. – Cherub

Answer 2

Very nice implementation of Goertzel is there. C# modification:

private double GoertzelFilter(float[] samples, double freq, int start, int end)
    {
        double sPrev = 0.0;
        double sPrev2 = 0.0;
        int i;
        double normalizedfreq = freq / SIGNAL_SAMPLE_RATE;
        double coeff = 2 * Math.Cos(2 * Math.PI * normalizedfreq);
        for (i = start; i < end; i++)
        {
            double s = samples[i] + coeff * sPrev - sPrev2;
            sPrev2 = sPrev;
            sPrev = s;
        }
        double power = sPrev2 * sPrev2 + sPrev * sPrev - coeff * sPrev * sPrev2;
        return power;
    }

Works great for me.

Lecky

Answer 3

Let's say that typical DTMF frequency is 200Hz - 1000Hz. Then you'd have to detect a signal based on between 4 and 20 cycles. FFT will not get you anywhere I guess, since you'll detect only multiples of 50Hz frequencies: this is a built in feature of FFT, increasing the number of samples will not solve your problem. You'll have to do something more clever.

Your best shot is to linear least-square fit your data to

h(t) = A cos (omega t) + B sin (omega t)

for a given omega (one of the DTMF frequencies). See this for details (in particular how to set a statistical significance level) and links to the litterature.

Azide

I did not know about Görtzel algorithm before, it should be way faster than least square fitting a sine wave. – Azide

I don't understand what you're saying about FFTs. DTMF frequencies are from 697Hz to 1477Hz, each at least 73Hz apart. At 8kHz a 256-point FFT would work fine. Of course using FFTs to detect specific frequencies is overkill, but it should still work. – Havard

@Gabe: if your data is 20ms, FFT will get you data at frequencies 50Hz, 100Hz, 150Hz, etc., whatever is your sampling rate. Combined with leakage, you are likely not to detect anything (which is what OP observes) – Azide

Doing a 256-point FFT at 8kHz requires a 32ms sample, which is still several times shorter than the 200ms minimum that the OP was able to achieve. – Havard

Answer 4

I found this as a simple implementation of Goertzel. Haven't gotten it to work yet (looking for wrong frequency?), but I thought I'd share it anywas. It is copied from this site.

        public static double CalculateGoertzel(byte[] sample, double frequency, int samplerate)
        {
            double Skn, Skn1, Skn2;
            Skn = Skn1 = Skn2 = 0;
            for (int i = 0; i < sample.Length; i++)
            {
                Skn2 = Skn1;
                Skn1 = Skn;
                Skn = 2 * Math.Cos(2 * Math.PI * frequency / samplerate) * Skn1 - Skn2 + sample[i];
            }
            double WNk = Math.Exp(-2 * Math.PI * frequency / samplerate);
            return 20 * Math.Log10(Math.Abs((Skn - WNk * Skn1)));
        }

Corron