How to detect a DTMF sound?

This article explains how to implement a 1D FFT - How to implement the FFT algorithm[^]

For simplicity, I would suggest you try with a DFT first. The processing may be slow, but its much simpler to implement. This page contains both a description and a code listing of both FFT and DFT: http://paulbourke.net/miscellaneous/dft/[^]

The simplest peak detection method is finding values above the mean of all samples and looking for changes in slope. Copying this from another post:

Between any two points in your data, (x(0),y(0)) and (x(n),y(n)), add up y(i+1)-y(i) for 0 <= i < n and call this T ("travel") and set R ("rise") to y(n)- y(0) + k for suitably small k. T/R > 1 indicates a peak. This works OK if large travel due to noise is unlikely or if noise distributes symmetrically around a base curve shape. For your application, accept the earliest peak with a score above a given threshold, or analyze the curve of travel per rise values for more interesting properties.

----

For simplicity I would recommend using a ready-made library over trying to write the whole algorithm. I would stick to C# over C++.

Try this: http://www.tapiex.com/ToneDecoder.Net.htm[^]
It can easily decode DTMF from an Audio file or a stream, which is what I assume you are after.

They have some help files here: http://www.tapiex.com/TDNet_Help/[^]

From their manual:

PhoneToneDecoder decode variant of tone signals such as DTMF, Caller-ID, TTY, SAME etc.

There are three ways to feed the audio data to this component.
From the file (.wav, .mp3, .raw etc).
Stream data capture by WaveEx control
Stream data feed by manually via WaveStreamInput method.

-----

What you can also do is record the WAV file then decode it. I have had good success using the NAudio library with C# earlier. The library also has functions to compute the FFT.
Consider this tutorial series: http://www.youtube.com/watch?v=6XvWRzWzgNI[^]

You can also try this: http://msdn.microsoft.com/en-us/library/ff827802.aspx[^]

Of course, because of the Shannon-Nyquist theorem, you'd have to compare at least two detected frequencies next to each other and only leave the one with the loudest tone in.
Maybe run an iteration over it beforehand and erase the more silent tones next to each other.
You could probably even better only detect the exact frequencies of the 4x4 matrice and don't run a complete detection over the spectrum.
I know that it was sloppy.
But two tests showed that it still worked. At least with no disturbing noise around it.
I'll explain it: if you let echo a tone with the amplitude of the slope on every signal position ( next value versus previous is the amplitude of the sinus wave echoed on that position) and repeat that over several signal positions, if the echoed tone is in the signal, there will be an amplification. Otherwise, other tones will not be amplified but blocked. Ever noticed that when you sing along with the pitch in which a string is tuned, that it will start to ring? Also, besides octaves, fifths, fourths and after that major thirds upwards will also be activated, but less loud. Because of that fact, you could accelerate the detection recursively if you started some octaves higher and only hangled down if the amplitude was over a threshold.