Originally from: http://www.ece.utexas.edu/~mason/codesign/pass/embedded.html

Efficient Algorithms and Implementation of a DTMF Detector

Completed by:

Jimmy Mason

Matthew Felder

for:

EE382C - Embedded Software Systems

Dr. Brian Evans

March 10, 1997

The DTMF standard developed by Bell Laboratories is used in touch tone telephones and voice mail systems. Each telephone digit corresponds to a high and a low tone that are transmitted simultaneously. Four frequencies in both the high and low group give sixteen possible combinations- the twelve digits on most telephones and four digits used in military applications. A DTMF detector should conform to the CCITT recommendations [1,2]:

This is not a complete list. There are some signal level recommendations that are not necessary to discuss in this paper. A DTMF detector should also reject "digit simulation"- where a DTMF signal is erroneously detected in a speech pattern. The CCITT recommendations are not specific on the quality or methods for avoiding digit simulation. Test tapes are available for determining a DTMF detector’s sensitivity to digit simulation. These recommendations are difficult to meet in entirety. Published algorithms for DTMF detection fail to mention whether or not they meet CCITT specifications completely.

Efficient DTMF algorithms are needed to multiplex several channels through a single, inexpensive DSP chip (there are 23 channels in a T-1 line). A good DTMF algorithm will minimize the number of cycles and the data memory, while meeting the CCITT specifications. Program memory is not as critical for DTMF algorithms, but the program must obviously fit in the available memory.

GOERTZEL ALGORITHM 

The Goertzel algorithm is a filter bank implementation that directly calculates one Discrete Fourier Transform (DFT) coefficient. Goertzel is not considered a Fast Fourier Transform (FFT) because it is order n², not order nlog₂(n). The Goertzel algorithm is a second-order filter that extracts the energy present at a specific frequency. It is more efficient than an FFT when log₂N or fewer coefficients of the DFT are needed. Calculating the DFT at 8 frequencies is as efficient in execution time as finding a 256 point FFT. Finding the DFT for 16 frequencies (the 8 DTMF tones and their second harmonics) is more complex than finding the FFT. However, the filter bank implementation has the tremendous advantage that it can process the input data as it arrives. The FFT has to wait until the entire sample window has arrived. Therefore, the Goertzel algorithm reduces the data memory required significantly.

MODIFIED GOERTZEL ALGORITHM 

Figure 1 is a data flow graph for the Goertzel algorithm. The left half of the graph is the recursive part- the right half is only feed-forward. The output value is only needed for the last sample in the window. Therefore, the complexity can be reduced by calculating the feed-forward part for only the last sample of each window. Also, only the magnitude of the output is needed. By squaring the output of the filter the final simplified feed-forward calculation is:

[1] |X(k)|²=|S(N)|²-2cos(2P k/N)S(N)S(N-1)+S(N-1)²

Only one coefficient is needed for each filter: a_k=cos(2P k/N). The sixteen coefficients needed for the DTMF tones and their second harmonics can be stored in a look-up table for fast execution. For the rest of this paper any reference to the Goertzel algorithm is understood to include the modified Goertzel adaptation.

Mock, in his implementation of a DTMF decoder[3], uses sixteen Goertzel filters to detect the energy at the eight DTMF frequencies and their second harmonics. He uses the second harmonics to check for digit simulation. This method is also used by Gay [4] and Analog Devices [5]. These papers fail to mention that using sixteen Goertzel filters is more complex than finding the FFT. It should be noted that the advantage of the Goertzel algorithm is the savings in data memory, not the efficiency of calculation. Checking the second harmonic frequencies is a sufficient method for detecting speech, however it is rather costly in terms of the number of calculations.

NON-UNIFORM DISCRETE FOURIER TRANSFORM (NDFT) 

A complication of the DFT and FFT is that they are calculated at N evenly-spaced frequencies. The Bell Labs developers intentionally selected DTMF tones at co-prime frequencies (to reduce harmonic influences). Therefore, it is impossible to find a value for N that is large enough to manage the offset error of the sampled frequencies. A reasonably good value of N is 205 [3,5] (a value that attempts to minimize the average percent error of the DTMF frequencies). Unfortunately, this value is too high to meet the CCITT specifications for signal timing.

Gay[4] states that a 256-point FFT (or DFT) would be necessary to meet the CCITT frequency tolerance specifications- this claim is an oversimplification of the specifications. A 256 point DFT would sample the DTMF frequencies within a 1.5% tolerance, but this does not guarantee that a signal 1.5% off the frequency specification will be detected. Gay[4] introduces a method for eliminating the DFT error. This method is later identified by Bagchi [6] as the non-uniform discrete Fourier transform.

The NDFT allows the calculation of the Fourier Transform of a discrete time signal at arbitrary locations on the z-plane. Using the NDFT it is possible to calculate the Fourier Transform at the exact DTMF frequencies- removing one source of error. The Goertzel algorithm is easily adapted to the NDFT. The constant for each filter is a_k=cos(2P f/f_s) where f is the DTMF frequency and f_s is the sampling frequency. The feed-forward equation is as follows:

[2] |X(f)|²=|S(N)|²-2cos(2P f/f_s)S(N)S(N-1)+S(N-1)²

Gay[4] states that using the NDFT, a sampling window of N=106 meets the CCITT frequency resolution recommendations. He does not support this claim. Matlab simulations show an energy spreading affect, whereby the energy of a sine wave is distributed to the surrounding spectrum. The spreading effect at N=106 will cause incorrect detection of lower band DTMF signals outside of the 3.5% range. Higher values of N will reduce the low-band complications by increasing the frequency spectrum resolution. Unfortunately, the higher definition can make it difficult to detect high-band DTMF tones inside the 1.5% limit. It is desirable to choose a value of N that will provide the best adherence to both the upper and lower-band frequency tolerances.

After finding the best value for N it is necessary to find a suitable method for meeting the CCITT signal timing recommendations. Only one of the articles [4] attempts to meet the latest CCITT signal timing specifications. Gay recommends a sampling window of 13.33ms (N=106) in order to guarantee two full windows of a 40ms signal duration. A DTMF signal is detected during the first window and verified in a second window before acknowledgment. It is possible that a 23ms DTMF signal will be erroneously detected even though it doesn’t fully overlap two sampling windows (there will be at least 13.75% signal loss). This method is considered "close enough" to the specifications. If N is increased to better match the frequency specifications, it will not be possible to use Gay’s method for checking the signal duration. A new method for meeting the signal timing specifications must be developed.

The subband NDFT is a method outlined by Bagchi [6] to reduce the calculations for an NDFT implementation of a DTMF detector. The subband NDFT discards the upper half of the telephone spectrum, downsampling by two (figure 2). This method will halve the necessary calculations for each Goertzel filter (only half as many samples enter the filter). The subband NDFT will require only slightly more program memory. Each filter requires two coefficients- one more than the NDFT Goertzel filter.

Unfortunately, this method is simplistic in that it ignores that speech or other noise may be present in the upper half of the spectrum. The proposed SNDFT algorithm assumes that no energy is present in the upper band- it will be very sensitive to noise or speech. Also, since the upper band is discarded, it is impossible to check the second harmonics to decrease the likelihood of digit simulation. In order to use the subband NDFT an alternative method for upper-band energy and speech detection must be used.

An alternative method for detecting non-DTMF energy is to calculate the total energy in the signal and compare it to the energy in the two detected DTMF frequencies. If the energy in the two frequencies comprises most of the total energy, it is unlikely that noise or speech is causing a false DTMF signal. The total energy can be calculated by accumulating the squared value of the incoming signal. Comparing the total energy to the DTMF energy is a more efficient method for detecting speech than checking all eight second harmonics. It has not been determined which method is better suited to avoid digit simulation.

Two DTMF decoder designs could improve upon the designs discussed in the references. The first idea is a modification to Gay’s implementation [4]. It is possible to reduce the necessary calculations by finding only the two second harmonics corresponding to the detected frequencies. The first window of detection can determine which second harmonics to check during the second (verification) window. Only ten of sixteen filters will be running during each window, a reduction of calculations by 5/8. A Synchronous Data Flow (SDF) graph for this design is shown in figure 3. Only multiple-token edges are labeled in the SDF graph.

A second design attempts to best match the CCITT frequency tolerance specifications at the expense of extra calculations. It has been determined that a sampling window of N=165 will best match the frequency specifications. In order to also meet the signal timing recommendations, a novel overlapping window approach is implemented. Two windows run concurrently, one window delayed by 83 samples. Checking two successive, overlapping windows provides the best possible adherence to all CCITT specifications. In worst case conditions 3% of a 40ms signal will be lost- this will probably not affect the detection of the signal. The CCITT frequency tolerances require rejection of tones less than 23ms long. A 23ms tone is guaranteed at least a 19% signal loss (this is an improvement over the 13.5% guaranteed loss in Gay’s approach). This method is therefore more likely to reject tones less than 23ms long. Subband NDFT Goertzel filters should be used to reduce the necessary calculations. To detect non-DTMF energy, the power in the DTMF frequencies will be compared to the total power. Figure 4 shows a Boolean Data Flow (BDF) model for this design- the nine connections from the SNDFT filters are for the eight DTMF frequencies and the total power calculation. This implementation should require fewer calculations than any of the reference detectors, while providing the best possible adherence to the CCITT recommendations.

REFERENCES