This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Dual tone multi frequency signal detection is one of the most used technologies in developing cost effective telecommunication equipment. Dual Tone Multifrequency (DTMF) signals are used in many areas such as touch tone telephone systems. DTMF signaling is a standard in telecommunication systems. This is a standard where keystrokes from the telephone keypad are translated into dual tone signals over the audio link. It has been gaining popularity for some years now because advantages over the traditional telephone signaling scheme. Digital devices are rapidly taking the place of analog devices. Dual tone multi frequency signal detection with a better quality has become for this ideal replacement.In this paper various methods of dual tone Multi frequency signal detection are discussed such as Quick DFT, Non Uniform DFT, Support vector machines, Goertzel algorithm.
Dual Tone Multi Frequency signaling is used in interactive computer applications such as telephone dialing, voice mail, and electronic banking systems. Generation of DTMF tones involves the relatively simple task of generating two sine waves where each signal corresponds to one of sixteen touchtone digits (0-9, A-D,* #) and consists of a low-frequency tone and a high frequency tone. Four low-frequency tones and four high-frequency tones are possible. DTMF detection amounts to detecting two sinusoids in noise subject to constraints on frequency resolution, time duration, and signal power.
Since analog devices are replaced with digital devices , digital DTMF decoders have become more and more prominent. Digital implementation of signals compared to analog signals implementation has a better advantages such as reprogram ability, stability, low chip count and as well as accuracy. Low chip count is nothing but using the Digital Signal Processor (DSP) chip instead of using several analog chips for detecting DTMF tones. The DTMF system consists of eight different types of signals, in which two signals are used at a time to decode the selection given by the user by pressing a button on the keypad of the device as shown in the figure. These types of dual tone frequencies eliminate any harmonics or disturbances which are being incorrectly detected by the receiver.
Keypad display of telephone
The transmitter of a DTMF signal transmits two frequency signals from both high low group frequencies. This type of signal represents a symbol or a digit corresponding to row and column shown in the figure 1. For example, when digit "9"is pressed by the user on the keypad, the two signals are generated i.e., 852HZ and 1477HZ which are selected and transmitted. Tone detection circuitry of the DTMF system will detect the pressed key by analyzing the two transmitted signals of low frequency and high frequency groups  i.e. 1477Hz and 852Hz. The common techniques which are used in the design and analysis of the detection of dual tone multi frequency signals are
Filtering Design Approach
Discrete Fourier Transform
Sub-Band Non-Discrete Fourier Transform 
In this paper the above mentioned approaches are studied in terms of their speed and complexity. Speed is the most prominent role in Dual-Tone Multi-Frequency detection. Since Dual-Tone Multi-Frequency signal detection is performed by time multiplexing on a digital signal processor (DSP) chip. Larger number of Dual tone multi frequency channels can be detected if the decoding time is less .
The DTMF standard was first initially developed by Bell core and recently redefined by the International Telecommunication Union (ITU). The Dual Tone Multi Frequency dialing system traces its roots by a technique AT&T developed a technique in the 1950s which is called Multi-Frequency (MF). It was used within the AT&T telephone network which allows the possibility of direct calls between the switching facilities and by using in-band signaling. But in the early 1960s, a new technique was invented by AT&T. It was introduced by its Cell System telephone companies as "modern" way for network customers to make calls.
AT&T's Compatibility Bulletin described this product as a method for push button signaling from customer stations using the voice transmission path. The consumer product was marketed by AT&T in the name of Touch-Tone which is the registered trademark and it is standardized by the ITU-T recommendation . Establishments of other compatible telephone equipment called this system as a "Tone" dialing or "Dual-Tone Multi-Frequency". Therefore, Dual- Tone Multi-Frequency (DTMF) is considered is an international signaling standard for telephone digits which are nothing but the buttons on the keypad .These types of signals are used in several interactive applications such as telephone banking pager systems and touch tone telephone signaling which are being used now a day.
The filtering detection of Dual Tone Multi Frequency signal is the most basic and simplest method of all detection techniques. This technique involves a series of steps. Firstly the signal is fed through a low pass / high pass filters and then sent through a set of band pass filters. The low pass / high pass group filters will divide the DTMF signal into two groups of signals i.e. low frequency and high frequency group of Dual-Tone Multi- Frequency Signals.
The frequency domain detection techniques generally depend on the Goertzal algorithm which computes the running Discrete Fourier Transform (DFT) at the selected frequency bin. The location of the bin and the number of samples to be processed are selected with respect to each individual frequency from the high and low frequency groups. The DFT components are calculated for each of the four frequencies in high frequency and low frequency groups and are compared to the highest energy frequency in each group. The digit is declared by combining the two dominant frequencies .
The filtering approach of Dual Tone Multi Frequency is the conceptually the simplest method of all detection techniques. The DTMF signal is first filtered by a set or pair of low pass / high pass filters and then sent through a set of band pass filters as shown in Figure. The set of low pass / high pass group filters will divide the signal into two groups of signals i.e. low frequency and high frequency group of Dual-Tone Multi- Frequency Signals. The number of frequencies in each range determines the number of blocks of blocks of band pass filters.
DTMF detection using filters
The filters which are used in this type of approach can be realized using IIR filters or FIR filters. If group filters are usually realized as 6th or 4th order elliptic filters, while band pass filters are 4th or 2nd order Butterworth filters, it is realized as IIR. If group filters are not used, but band pass filters are of high order i.e. greater than 30, then it can be realized as FIR. These types of filters are used in hardware due to its high computational complexity. Modern tone detection schemes do not use this approach, since it is not suitable for detection of tones in multiple channels .
Discrete Fourier Transform
In the past many researchers have proposed numerous techniques for digital Dual Tone Multifrequency detection, but most researchers have proposed on digital filtering or Discrete Fourier Transform (DFT). In digital filtering, Dual Tone Multifrequency signals are passed through filters such as digital band pass filters which are centered at the signaling frequencies. The power at each frequency is measured repeatedly in order to detect the DTMF signals or tones. A digital signal processing chip then interprets and converts them for the proper switching. The DFT is also capable of measuring the power of signal at the signaling frequencies to detect the DTMF tones, but it also has the need to check for signals for at least some minimum duration. This explains how a given digital single channel data stream can detect the presence of valid Dual Tone Multifrequency tones.
The algorithm of the Discrete Fourier Transform should be capable of determining the exact Dual-Tone Multi-Frequency frequencies which are present accurately and the relative signal strength or power at each of the frequencies and the duration is to be determined.
Several methods are being implemented for determining the component of signal at a given frequency. The Discrete Fourier Transform can be used to represent non periodic discrete signals as the algebraic sum of its own frequency components .
The general form of Discrete Fourier Transform is
where x[n] is the finite duration sequence of length N and
n = 0, 1, 2,N âˆ’ 1
Consider the signal,
Then the sampled signal will be
The Discrete Fourier Transform of the signal is given by,
For n = 0, 1, 2, N âˆ’ 1.
First a block of samples are chosen, and its DFT is calculated for a set of certain frequencies which are to be used in signalization. If x[n] represents receiving signal then the DFT of 'N' samples of x[n], receiving signal will be calculated as in Eq. 1.Since the no. of frequencies is less, and the use of Fast Fourier Transform (FFT) algorithms is not a suitable option. The most efficient way is to use the Goertzel's algorithm for small number of frequencies in order to calculate the DFT.
The Goertzel's algorithm is basically based on special second order cell, which uses input signal as the sample signal gives the output as the DFT coefficients. The Goertzel algorithm has the ability to calculate the magnitude of the frequency domain at the certain frequency. The Goertzel is not considered a Fast-Fourier-Transform (FFT) because of its order n2, nor order n log2 n . This type of algorithm consists of a group of a second order IIR filters which extracts the energy which is present at the specific frequency . This is more efficient compared to a Fast Fourier Transform (FFT) when log2 N or at the fewer coefficients of the DFT are required. The filter bank implementation has the tremendous advantage that it can process the input data as it arrives but the Fast Fourier Transform has to wait until the entire sample window has arrived . But here the Goertzel algorithm reduces the data memory which is required significantly. As it can be observed that Goertzel algorithm is more efficient way in detecting Dual Tone Multi Frequency signal.
Consider the twiddle factor property,
If both sides of Equation 5 are multiplied with
We will get
The above Discrete Fourier Transform Equation can be related to the band pass filter by defining a new sequence
The below transfer function shows that the coefficient is complex which requires complex multiplication and addition.
By replacing the real coefficient in the place of complex coefficient, it can reduce computational load.
After reduction the transfer function looks like
Goertzel algorithm block diagram
From the Figure 3, Real coefficients are used in the feedback.
The Recursive computation of is expressed as
The Complex computation can be eliminated by calculating the magnitude square of X(k) for tone detection.
The square magnitude is computed as
The above equation does not contain any complex coefficients.
The second order recursive computation of the Discrete Fourier Transform by using Goertzel algorithm shown in Fig. 3, which computes a new output for every new input sample x[n].
The Discrete Fourier Transform result, X(k), is equivalent to when n = N, i.e., X(k) = yk(N). Since other value of , in which n 6= N, does not contribute to the end result X(k). There is no need to compute until n = N. This implies that the Goertzel algorithm is functionally equivalent to a Second-Order IIR filter, except that the one output result of the filter is generated only after N input samples have occurred .
Sub-Band Non-Uniform DFT
In order to detect Dual Tone Multi Frequency signal, its energy at the eight Dual Tone Multifrequency frequencies is determined by calculating the samples of the NDFT frequencies. In the proposed SB-NDFT algorithm, these NDFT samples are calculated by dividing the input signal into two sub-bands. Since Dual Tone Multi Frequency signals occupy the low frequency part of the telephone bandwidth, the higher sub-band can be discarded for a fast and approximate computation .
This algorithm is based on the fact that all useful frequencies in DTMF algorithms are below 2 KHz, which can permit sub-band decomposition and the use of two times lower the sample rate (4 KHz) .
The non uniform discrete Fourier transform (NDFT) of a sequence x[n] of length N is defined as
Where k = 0, 1, 2, N âˆ’ 1.
The problem of determining the energies present, in the signal at the DTMF frequencies is, therefore, equivalent to The computing of NDFT samples located at the eight DTMF frequencies is equivalent in determining the energies present in the signal at DTMF frequencies. This is also equivalent to modified Goertzel algorithm . The sub band NDFT which is also represented as SB-NDFT is a method which is used for computing the NDFT based on a sub band decomposition of the input signal.
Consider a sequence x[n] with an even number of samples N. We first decompose x[n] into two subsequences, and , of length N/2 each:
For n = 0, 1, 2, ...(N/2)-1.
These sequences are simply low pass / high pass filtered and down sampled versions of x[n].
By substituting for x[n] in the NDFT expression in Equation (11), it can be obtained
Where GL(z2 k) and GH(z2 k) are the NDFTs of the sequences, and , evaluated at z = z2 k. Therefore, we can find the NDFT of x[n] at the point z = z2
k by computing the NDFTs of the smaller sequences, and ,at the point
z = z2 k and then combining them.
For Dual Tone Multi Frequency detection, we only require the squared magnitudes of the approximate NDFT samples.
The factor of eight in Eq.14 can be neglected in the calculation, because only the relative squared magnitudes are of importance .
The value of is computed by using the modified Goertzel algorithm  as shown in Figure 4.
SB-NDFT decoding algorithm block diagram
In the computation the two coefficients for each frequency indicated as, in Figure4,ak and bk can be obtained
TEST RESULTS DISCUSSION
The Dual Tone Multi Frequency detection of algorithm which is based on the Sub Band Non Uniform Discrete Fourier Transform SB-NDFT has a much lesser computable complexity compared with other algorithms such as algorithms based on the DFT (Goertzel Algorithm) and NDFT.
Let us consider that, 'N' be the number of samples required to detect Dual Tone Multi Frequency digits under the conditions which are specified by the AT&T standard recognition, Touch Tone Technology. Since the minimum duration of a DTMF signal is as less as 40 ms, and the sampling rate of 8 kHz and the no. of samples available for decoding or detecting each DTMF digit is 0.04 ms x 8000KHz = 320. So here the value of 'N' which is required depends on the type of the algorithm which has been implemented. For Example, the algorithms based on the DFT and NDFT require (N + 4) real multiplications and (2N+2) real additions for each frequency, leading to a total of (8N + 32) real multiplications and (16N + 16) real additions for the eight DTMF frequencies . By this we can observe that the SB-NDFT algorithm is much more efficient and also reduces computation speed by nearly half as compared with those based on the DFT and NDFT which is very important. We can also design a DTMF detection algorithm based on the SB_DFT by just replacing that !k = 2_k/N . Eight integer values are assigned for 'k' such that the corresponding frequencies of DTMF frequencies is closest as kfs/N. However the computational complexity of SB_DFT is similar to that of SB-NDFT, but the sampling error which is caused by uniform sampling leads to a low level performance.
In order to compare the performance of the present algorithm with the other algorithms, We have tried to define a new technique. Let us Assume that desired dialed DTMF digit, was detected successfully, then the figure of merit value corresponds to the minimum differences among the dB-levels. The dB levels of the highest row and second highest row and column tones,
F = min (Dr, Dc) (16)
Dr = 10 log Xr âˆ’ 10 log Xrs
Dc = 10 log Xc âˆ’ 10 log Xcs (17)
Here, Xr-maximum value detected at row, Xc-maximum values among the energies detected at the column tones respectively, Xrs-second highest value among the energy detected at row, Xcs-second-highest values among the energies detected at the column tones. Subsequently F should be greater than zero i.e. F > 0, for successful detecting of DTMF tone. A higher figure of merit is required which shows that the operational tones are detected at certain levels are reliably higher than that of the non operational tones.
B. Performance Comparison
In this paper we have determined the Figure of Merit F which is attained by each algorithm for a given no. of input samples 'N'. For each value of 'N', the Figure of Merit is determined by computing all the sixteen DTMF digits, each under three different conditions of twist i.e. No twist, Maximum reverse twist, and Maximum normal twist . After obtaining the lowest value of figure of merit, the DTMF signal is generated by adding two sinusoid signals at the operational row frequencies and at the operational column frequencies and also six sinusoids with 30 dB lower amplitudes at the other six frequencies. To simulate the receiving conditions specified in the AT&T Touch Tone Recommended standard, we vary the two operational frequencies within tolerance bands about ±1.5% tolerance about the standard frequencies, by considering delta f to be multiples of 5 Hz . We have compared the four algorithms by determining the minimum no .of samples required to attain a certain change in figure of merit. This is shown in Table 1 for the values of the Figure of Merit. As shown in Table 1, It is not possible to attain a high figure of merit using the DFT and SBDFT algorithms. Finally, we determine the total computation required to detect the energies present in the input signal at the eight DTMF frequencies, using the minimum number shown in the table 1. The number of real multiplications M, and the number of real additions A, is shown in Table 2. Clearly this shows that SB-NDFT algorithm requires fewer computations to attain a certain figure of merit. The gain is substantial when compared to the other methods .
This paper presented a good understanding about the energies present at the different types of dual tone multi Frequency signals by eliminating calculations in the high frequency band of two band decomposition. The fact of DTMF frequencies reside in low frequencies is also been realized. Performance comparisons have been observed of DTMF algorithms based on the Discrete Fourier Transform and Sub band NDFT. It has been discovered that the sub band NDFT requires much lesser computation compared to other algorithm in order to obtain desired outcomes.
By proposing this paper on Dual Tone Multi Frequency signal detection, I strongly believe that this work will be very helpful for other researchers who can use this paper as a platform for further developments.