Efficient Detection Approach for DTMF Signal Detection

Abstract

A novel tone detection approach, designated as the multi-frequency detecting (MFD) algorithm, is presented in this work as an alternative to conventional single point detection approaches but it is an efficient way to achieve the aim of further computational load reduction for a dual-tone multi-frequency (DTMF) signal detection. The idea is that an optimal phase search is performed over the frequency band of interest in each tone detection, and then the optimal frequency response of a detector is built accordingly. In this manner, a DTMF detection task is done following one-time detection computation. This proposal demonstrates an overall computational load reduction of 80.49% and 74.06% in comparison with a discrete Fourier transform (DFT) approach and the Goertzel algorithm, respectively. This detection complexity reduction is an advantage and an important issue for applying DTMF detection technique to embedded devices.

1. Introduction

Dual-tone multi-frequency (DTMF) signals [1,2,3,4] were developed by Bell Labs for the purpose of automatic fulfilled long-distance calls. DTMF signal and the detection of DTMF have been widely used in modern communication systems. In a public switched telephone network (PSTN), the DTMF technique is applied to telecommunication signaling over analog telephone lines in the voice-frequency band among telephone handsets, other communications devices, and a switching center. Recently, the DTMF technique has also been widely applied to household intelligent alarm systems [5], remote control systems [6,7], VoIP systems [8], and so on.

Standardized by International Telecommunications Union (ITU) [9], the DTMF technique uses eight different frequency signals transmitted in pairs to represent 16 different figures and symbols, as tabulated in

Table 1. Relations between the paired frequencies and the corresponding symbols in dual-tone multi-frequency (DTMF) signals.

Symbols	1209 Hz	1336 Hz	1477 Hz	1633 Hz
697 Hz	1	2	3	A
770 Hz	4	5	6	B
852 Hz	7	8	9	C
941 Hz	*	0	#	D

‘*’, ‘#’: the dialed symbols on a telephone.

. It consists of two mutually exclusive frequency groups: the low-frequency group (<1 kHz) and the high-frequency group (>1 kHz). Four low-frequency tones (697, 770, 852, 941 Hz) are assigned to rows, while four high-frequency tones (1209, 1336, 1477, 1633 Hz) are assigned to columns. Thus, each pair of frequencies corresponding to the column and row are adopted as a unique DTMF tone. In addition, with a permitted frequency tolerance of approximately ± 1.5% of the tone frequency in ITU specification for valid DTMF tones, the frequency components in the exterior of ± 3.5% must be rejected, while those between ± 1.5% and ± 3.5% can be either accepted or rejected. Hence, a tone detection must be conducted over the frequency range of ± 3.5%.

Consequently, a tone detection algorithm is necessary at the receiving end to recognize a received DTMF signal. In the literature, DTMF detection algorithms [10,11,12,13,14,15,16] can be categorized into two types, namely, the discrete Fourier transform (DFT) based approaches [10,11,12] and the Goertzel-based algorithms [13,14,15,16]. In the former approaches, the frequency response of a received signal is calculated by the DFT formula, and then determines the tone frequency thereof. However, for the purpose of computational complexity reduction, only the frequency bin that corresponds to a detected tone is calculated. Such an approach is referred to one-point DFT detection approach as well. On the other hand, the Goertzel-based algorithms were demonstrated to provide a way for efficient evaluation of individual terms of the DFT. The Goertzel-based algorithms are widely used in DTMF signal detection, due to the advantage of a considerable computational time saving during a detection procedure. However, one thing that these two detection types have in common is that a tone detection task is performed at a single point each time, meaning that there is an inevitable and significant rise in the required computational load.

Alternatively, a number of studies [17,18,19,20] were published with a focus on the applications of tone detection algorithms to the design of field-programmable gate array (FPGA), very large scale Integration (VLSI) chips and digital signal processor (DSP) processors. As a matter of fact, the detection algorithms involved in the above-stated references belong to either DFT or Goertzel algorithm-based ones. In addition to the computational complexity, quantities, e.g., chip area occupied, power dissipation, and more, need to be taken into account in chip design. Not as in chip design, the computational complexity is the first priority issue when porting a tone detection code to a hardware platform, and the Goertzel algorithm stands as the most advantageous candidate in terms of the computational complexity.

If a tone detection code can be ported to a hardware platform, say an embedded system platform, via programming, then the hardware cost can be kept down, that is to say, a tone detection chip is not required in the embedded platform. Accordingly, a highly efficient DTMF detection algorithm, designated as the multi-frequency detecting (MFD) approach, is proposed in this study as an alternative to conventional single point detection approaches. It merely requires one-time detection computation to get a DTMF task done, accounting for a considerable computational load reduction. This detection complexity reduction is an important issue for applying a DTMF detection technique to embedded devices.

The rest of this paper is outlined as follows. The related works are described in Section 2. Section 3 presents the proposed algorithm for DTMF tone detection. Experimental results are demonstrated and discussed in Section 4. This work is summarized at the end of this paper.

2. Related Works

In this section, two conventional single point detection approaches, the one-point DFT and Goertzel approaches, will be discussed. First, the DFT of a singal x[n] is defined as:

$$\begin{array}{ll}X[k]& ={\displaystyle \sum _{n=0}^{N-1}x[n]W_N^{nk}}={\displaystyle \sum _{n=0}^{N-1}x[n]e^{-j\frac{2\pi nk}{N}}}\\ & ={\displaystyle \sum _{n=0}^{N-1}x[n]\left\{\cos \left(\frac{2\pi nk}{N}\right)-j\sin \left(\frac{2\pi nk}{N}\right)\right\}}\end{array}$$

(1)

and is used to the one-point DFT approach along the frequency bin k. During a tone detection, X[k] is first evaluated corresponding to each tone frequency, and then the tone corresponding to the input signal x[n] can be identified. As indicated in Equation (1), a computational load of 2N real multiplications and (2N − 2) additions are required to evaluate X[k] at a specified k. That is, such computational load is required when the one-point DFT approach is performed at a specified k.

On the other hand, the direct-form realization of a Goertzel algorithm is presented in Figure 1 [13], and the operation thereof is expressed as:

$$v_k[n]=x[n]+2\cos (\frac{2\pi k}{N})v_k[n-1]-v_k[n-2]$$

(2)

$$X[k]=y_k[N]=v_k[N]-W_N^k{v}_k[N-1]$$

(3)

where X[k] is the DFT of a singal x[n]. In this manner, (2) is iterated N times until v_k[N] is acquired, and then X[k] is obtained by (3). In addition, k is constant when (2) and (3) are evaluated. In this context, evaluation of X[k] at a specified k requires a computational load of (N + 2) real multiplications and (2N + 1) additions. Obviously, this approach is found to have the same tone detection procedure as the above one-point DFT approach.

To further analyze the valid DTMF tones in ITU specification, an example of tone detection at a frequency of 1477 Hz with a sampling rate (SR) of 8000 Hz and a DFT size of 512 is illustrated in Figure 2. In this case, frequencies over the range of 1455 to 1499 Hz must be accepted, whereas those below 1425 or beyond 1529 Hz must be rejected. Hence, tone detections must be performed over the frequency bin k = 92 to 97.

Subsequently, a comparison is made between the one-point DFT approach and the Goertzel algorithm as follows. Taking Figure 2 as an instance, the former requires 2N real multiplications and (2N − 2) additions to evaluate X[k], given in (1), for frequency bin k ranging between 92 and 97, that is, the above-stated evaluations are performed for six times in total. In contrast, the latter requires (N + 2) real multiplications and (2N + 1) additions to evaluate X[k], given in (2) and (3), for k in the same range as in the former case, but the latter is found to have a 25% approximately computational load reduction in comparison with the former.

As described above, one thing that these two detection approaches have in common is that a tone detection task is performed at a single point each time, meaning that there is an inevitable and significant rise in the required computational load.

3. Proposed Algorithm

MFD is presented as a simplified but improved version of a typical DTMF detection algorithm. It is developed as a two-phase algorithm, the first of which is for offline detector design and the second is for tone detection. Phase 1 aims to design and then realize the optimal frequency response of a detector for a specified signal tone range of interest, and a lookup table is built accordingly. Subsequently, a tone detection is performed in Phase 2 using the optimal detector implemented previously.

The presented MFD detection approach is illustrated with an example in Figure 3. The frequency response of a detector is synthesized as a superposition of $W_N^{nk}$ corresponding to the k of interest, and the optimal frequency response thereof is found accordingly. Thus, this study presents a synthesized multi-frequency detector, formulated as a modified form of (1), that is,

$$\begin{array}{ll}\tilde{X}[k^{\prime }]& ={\displaystyle \sum _{n=0}^{N-1}x[n]{\tilde{W}}_{M,N,\theta }^{n{k}^{\prime }}}\\ & ={\displaystyle \sum _{n=0}^{N-1}x[n]{\displaystyle \sum _{m=0}^{M-1}\left\{\cos \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)-j\sin \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)\right\}}}\\ & ={\displaystyle \sum _{n=0}^{N-1}x[n]\left\{w_r(n)-j{w}_i(n)\right\}}\end{array}$$

(4)

and

$$\begin{array}{ll}{\tilde{W}}_{M,N,\theta }^{n{k}^{\prime }}& ={\displaystyle \sum _{m=0}^{M-1}{\tilde{W}}_{N,\theta }^{n{k}^{\prime }}}\\ & ={\displaystyle \sum _{m=0}^{M-1}{e}_{}^{-j(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta )}}\\ & ={\displaystyle \sum _{m=0}^{M-1}\{\cos \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)}-j\sin \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)\}\\ & =w_r(n)-j{w}_i(n)\end{array}$$

(5)

$$w_r(n)={\displaystyle \sum _{m=0}^{M-1}\cos \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)}$$

(6)

$$w_i(n)={\displaystyle \sum _{m=0}^{M-1}\sin \left(\frac{2\pi n(k^{\prime }+m)}{N}+m\theta \right)}$$

(7)

where ${\tilde{W}}_{M,N,\theta }^{n{k}^{\prime }}$ denotes a proposed synthesized multi-frequency detector. The idea is that M number of $W_N^{nk}$ components over the frequency band of interest is synthesized ahead of a DTMF detection, and then a distinct phase angle θ is assigned. k’, representing the starting index over the detected frequency band, and M are respectively defined as:

$$k^{\prime }=\mathrm{INT}\left(\frac{f\ast N\ast (1-T_{\mathrm{off}})}{SR}+1\right)$$

(8)

$$M=\mathrm{INT}\left(\frac{f\ast N\ast (1+T_{\mathrm{off}})}{SR}\right)-k^{\prime }+1$$

(9)

where f denotes the tone of interest, SR the sampling rate, T_off the value of frequency tolerance, and INT(·) the integer part of a number. As illustrated in Figure 2, f = 1477 Hz, k’ = 92 and M = 6 on a condition that T_off = 3.5%. As well, tabulated in

Table 2. Values of k and M versus the tone frequencies on a condition that N = 512 and T_off = 3.5%.

Frequency (Hz)	Value of k		Value of M
	Min. (k’)	Max.
697	44	46	3
770	48	51	4
852	53	56	4
941	59	62	4
1209	75	80	6
1336	83	88	6
1477	92	97	6
1633	101	108	8

are the values of k and M versus the tone frequencies on a condition that N = 512 and T_off = 3.5%.

Furthermore, presented in Figure 4 are the frequency response comparison among synthesized detectors with various combinations of M and θ. From Figure 4a, it is found that the MFD result shares the same frequency response with DFT in the case of M = 1, and the DTMF signal with frequency shift cannot be successfully detected. As demonstrated in Figure 4b–d, namely the cases of M = 2, θ = 0, π/3, 102π/180, respectively, the frequency response of a detector shows a strong dependence on the phase angle.

As a target of this paper, the phase angle θ is then tuned so as to optimize the frequency response of a detector. As illustrated in Figure 4c, g_pr denotes the pass-band ripple of the frequency response, g_sr the maximal ripple of the stop-band, and g_ps = g_sr − g_pr the differential gain between the pass- and the stop-bands. In a bid to optimize the frequency response of a detector with respect to the phase angle θ in (5), a cost function in the determination of the optimized phase angle θ_opt is defined as

$${\theta }_{\mathrm{opt}}=\arg \underset{\theta }{\min }\left\{g_{\mathrm{pr}}\left(\theta \right)\right\},0\le \theta <2\pi$$

(10)

An open-loop search is conducted here to locate the optimal phase angle θ_opt over the range of 0°≤ θ < 360°. As illustrated in Figure 4d–f, θ_opt are consequently located at 102π/180, 230π/180, 264π/180 in the cases of M = 2, 4, 6, respectively. With reference to the frequency responses in Figure 4d–f, nearly consistent performance is provided among cases with various M values in this proposal.

In addition, different M values among various tone frequencies, listed in Table 2, are adopted to evaluate the optimal phase θ_opt by performing (5) and (10), and then the g_pr, g_sr, g_ps values can be estimated. Presented in

Table 3. Optimal design parameters for a detector versus the tone frequencies.

Frequency (Hz)	M	Parameters of an Optimal Detector
		θopt	gpr (dB)	gsr (dB)	gps (dB)
697	3	282π/180	0.1431	6.4597	6.3166
770	4	229π/180	0.2530	7.5342	7.2812
852	4	230π/180	0.2537	7.5365	7.2829
941	4	129π/180	0.3386	7.5170	7.1784
1209	6	264π/180	0.3246	7.2856	6.9610
1336	6	264π/180	0.3227	7.2913	6.9686
1477	6	264π/180	0.3203	7.2759	6.9556
1633	8	248π/180	0.3120	7.6119	7.2998

are respective optimal design parameters for detectors among various tone frequencies. In addition, the frequency response for an optimal detector versus the tone frequencies is presented in Figure 5.

Finally, a lookup table is built for a quick reference of ${\tilde{W}}_{M,N,\theta }^{n{k}^{\prime }}$ (i.e., w_r(n) and w_i(n)) at various tone frequencies, and, thus, eliminates repeated computations. As a one-point DFT algorithm does, this proposal requires 2N and (2N − 2) number of multiplication and addition operations, but merely requires a one-time detection computation to complete a DTMF detection task. As a consequence, the single point detection disadvantage, a problem that a typical DFT and a Goertzel algorithm have in common, is resolved. In simple terms, this proposal, as a high-performance algorithm, results in a tremendous computational load reduction. The proposed detection approach is illustrated as a brief flowchart in Figure 6.

4. Experimental Results

The MFD detection approach is proposed here as an efficient way to improve the computational complexity required in a DTMF signal detection. In this work, performance is compared in terms of computational load and detection accuracy among the presented MFD, DFT, and a Goertzel algorithm.

Tabulated in

Table 4. Computational load comparison among various methods; discrete Fourier transform (DFT).

Item	DFT	Goertzel	Proposed
Multiplications	2NM	M(N + 2)	2N
Additions	M(2N − 2)	M(2N + 1)	2N − 2
Total	M(4N − 2)	M(3N + 3)	4N − 2

is the computational load comparison among various methods. Since single point detections are performed by a DFT approach and a Goertzel algorithm, M operations are required to detect the DTMF signals with a frequency shift, depending on the tone frequencies. In contrast, one-time detection is performed in this proposal, resulting in a considerable computational load reduction.

In most cases, the value of N is specified at 512 when performing a DTMF detection task. Accordingly, the number of total operations required for each tone frequency among various methods is presented in

Table 5. Comparison of the number of total operations required versus the tone frequency.

Frequency (Hz)	M	Required Total Operations
		DFT	Goertzel	Proposed
697	3	6138	4617	2046
770	4	8184	6156	2046
852	4	8184	6156	2046
941	4	8184	6156	2046
1209	6	12,276	9234	2046
1336	6	12,276	9234	2046
1477	6	12,276	9234	2046
1633	8	16,368	12,312	2046
Overall		83,886	63,099	16,368

for the purpose of further analyzing the computational load comparison. Simultaneously, in comparison with the DFT approach, a comparison of the computational saving (CS) versus the tone frequency between a Goertzel algorithm and the proposed approach is given in

Table 6. Comparison of the computational saving (CS) versus the tone frequency with DFT approach as a benchmark.

Frequency (Hz)	Computational Saving (%)
	Goertzel	Proposed
697	24.78	66.67
770	24.78	75.00
852	24.78	75.00
941	24.78	75.00
1209	24.78	83.33
1336	24.78	83.33
1477	24.78	83.33
1633	24.78	87.50
Overall	24.78	80.49

. In addition, these experimental results confirm that this proposal provides a CS of 66.67%–87.50% and 55.69%–83.38% in total operations, respectively, compared with the DFT and the Goertzel algorithm.

For each detection procedure of a DTMF signal, an overall operation required and an overall CS comparison with the DFT approach as a benchmark are respectively given in the last row of Table 5 and Table 6 as well. The proposed detection algorithm gives a remarkable computational load reduction in comparison with the Goertzel and DFT approaches.

Subsequently, an experiment of detection accuracy versus signal-to-noise ratio (SNR) is conducted in this work. In each SNR level experiment, a total of 16,000 test samples are produced for detection experiment. Each DTMF signal in Table 1 has 1000 test samples, and each sample is a DTMF signal with white Gaussian noise (WGN). Presented in

Table 7. Comparison on the detection accuracy versus signal-to-noise ratio (SNR).

SNR (dB)	Detection Accuracy (%)
	DFT, Goertzel	Proposed
5	100	100
4	100	100
3	100	100
2	100	100
1	100	100
0	100	99.97

is the comparison on the detection accuracy versus SNR among various approaches. It shows that the accuracy of the proposed approach drops at SNR of 0 dB, while the DFT and the Goertzel algorithm remains a 100% accuracy.

However, according to ITU standard [9,10], the signal strength is specified to be 15 dB SNR and higher. In such a condition, a 100% accuracy in DTMF signal detection is provided by the presented MFD algorithm. That is, this proposal is experimentally validated as a superior candidate relative to the counterparts.

5. Conclusions

As an improved version of DFT, the MFD method with an optimal phase search was proposed for the purpose of computational load reduction for a DTMF signal detection. Experimental results show that the number of total operations required for DFT, Goertzel, and presented MFD algorithms in a DTMF signal detection are 83,886, 63,099, and 16,368, respectively. Superiority of this proposed MFD approach is validated by an overall computational load reduction of 80.49% and 74.06%, respectively, compared with a DFT approach and a Goertzel algorithm, while a 100% detection accuracy is provided as long as SNR is higher than 0 dB. This detection complexity reduction is an advantage and an important issue for applying DTMF detection technique to embedded devices. As scheduled, a continuous effort will be made to improve the resistance to noise of the proposed algorithm in the very near future.