Olin Lathrop wrote:
> Russell McMahon wrote:
> > > Basically multiply the incoming signal by the sine and cosine of
> > > each of the DTMF frequencies. Add the products for each frequency,
> > > then low pass filter those sums individually....
> >
> > Fourier would be proud.
> > (SFT strikes again :-) )
> 
> I'm not sure what your point is.  I'm assuming SFT is supposed to mean Slow
> Fourier Transform, as apposed to FFT (Fast Fourier Transform)?  Do you see
> a way to apply the FFT algorithm to checking for the existance of a few
> known frequencies that aren't in a nice evenly spaced progression?
> 
> Remember that the FFT algorithm is a very clever optimization for
> performing time domain to frequency domain conversion under just the right
> circumstances.  It's not clear to me the circumstances apply here to the
> point where doing a FFT would be less computation than what I described.
> 
> What I described requires 16 multiplies per sample, plus some low pass
> filtering and of course the integer indexing and bookkeeping operations.
> If this is done on a machine with a hardware multiplier, these really
> aren't a big deal.

The FFT is an optimization of the more general DFT (discrete Fourier transform)
that takes advantage of the many redundaant operations in the latter. If you
only care about a few of the frequency bins in the output of the DFT, it is
often better (in terms of CPU cycles) to ignore those redundancies and simply
calculate those bins directly with the DFT algorithm. This also gives you the
opportunity to do a "sliding window" version of the DFT, which is more or less
what Olin is describing. I've used this technique myself on several occasions.

I would also point out that in a tone-detection application, in which you only
care about magnitude and not about phase, the low-pass filtering doesn't need
to be a separate step. Instead of an IIR low-pass filter at the output, you
can create an implicit FIR low-pass filter by applying a "window" function
directly to the sine/cosine coefficients. Essentially, what you then have is
a pair of narrow quadrature-phase bandpass filters for each frequency, and
you're measuring the magnitude of their combined outputs (sum of squares).

-- Dave Tweed
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist