Abstract:
A method of detecting frequency errors exceeding a predetermined limit in a sampled signal includes the step of determining a peak amplitude of the signal at a tone frequency for a first frame of samples of the sampled signals using a filter having a first amplitude versus frequency response. A peak amplitude of signal at the tone frequency is determined for a second frame of samples of the sampled signal using a filter having a second amplitude versus frequency response. A ratio between the peak amplitude of the first frame and the peak amplitude of the second frame is calculated and compared against a threshold to detect frequency errors exceeding the predetermined limit. Among other things, this method decouples the frequency error detection problem from the twist factor estimation problem.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates in general to analog signalling and in particular, to frequency error detection methods and systems using the same. 
   2. Description of the Related Art 
   Dual Tone Multiple Frequency (DTMF) encoding is a common form of signaling used in telecommunications applications, such as touch-tone telephones. Typically, a composite signal representing given information (e.g. a letter or number) is generated by summing two audible tones of different frequencies. This composite signal is then transmitted, for example over the telephone lines, and then decoded at the receiving end to recover the original information. 
   Consider the typical touch-tone phone. The number buttons, along with the * and # buttons, are arranged in a rectangular array of rows and columns. Each row and each column is associated with a distinct frequency. In the conventional telecommunications scheme, the standard row frequencies are 697 Hz, 770 Hz, 852 Hz and 941 Hz and the standard column frequencies are 1209 Hz, 1336 Hz, 1477 Hz and 1633 Hz. Thus, when a given button is pressed, a composite signal is generated from the frequencies assigned to the corresponding row and column. For example, if the “1” button is pressed, the composite signal is generated from the Row  1  frequency of 697 Hz and the Column  1  frequency of 1209 Hz. 
   While DTMF signaling is relatively straightforward in theory, several difficulties arise in practical applications. Among other things, the frequencies and pulse width must be controlled to insure the integrity of the encoding process. Generally, the DTMF telecommunications specification requires that frequencies within 1.5% of nominal always be detected, those with 3.5% or more frequency error never be detected, and those with a frequency error in the range of 1.5 to 3.5% be interpreted as “don&#39;t care.” Similarly, pulses longer than 40 ms should always be detected, those shorter than 23 ms should never be detected, and those having a pulse width in the range of 23-40 ms should be interpreted as “don&#39;t care.” The minimum amplitude which must be detected is −36 dB. 
   The DTMF specification accounts for some signal degradation during transmission. There are two primary forms of degradation that must be considered during the detection process, name, Twist Factor and Tone Frequency Tolerance. The Twist Factor is essentially the difference in amplitude of the different frequencies making up the composite signal as a result of non-uniform power loss. Typically, the detector must be capable of detecting a signal. When power is high, frequency tone should be within +4 to −8 dB of the low frequency tone. Tone frequency tolerance is specified in terms of percentage of nominal frequencies. For example, a disallowed 3.5% variation at the tone frequency of 697 Hz is 24 Hz. At the same time, an allowed frequency variation of 1.5% at 1633 Hz is also 24 Hz. Hence, using an absolute tolerance (e.g. 24 Hz) as a basis for determining if a tone is within tolerance will lead to erroneous results. 
   DTMF has many advantages, and therefore improvements in the circuits and methods of signal detection are highly desirable. Correct tone detection with optimized time of detection overhead leads to quicker establishment of calls, which in turn improves infrastructure utilization. 
   SUMMARY OF THE INVENTION 
   A method is disclosed for detecting frequency errors in a sampled signal exceeding a predetermined limit. A peak amplitude of the tone frequency is detected for a first frame of the samples using a filter having a first amplitude versus frequency response and a peak amplitude of the tone frequency is determined for a second frame of samples using a filter having a second amplitude versus frequency response. A ratio is calculated between the peak amplitude of the first frame and the peak amplitude of the second frame, the ratio compared against a threshold to detect frequency errors exceeding the predetermined limit. 
   The principles of the present invention provide an efficient means for detecting frequency deviation in a transmitted signal. This method decouples the frequency error detection problem from the twist factor estimation problem and this makes it robust. Among other things, processing overhead is minimized all through the reuse of data used to implement the first filter during the implementation of the second filter. This is particularly advantageous in embodiments employing a digital signal processor or similar digital filtering device. The inventive concepts can be applied to any one of a number of applications, including DTMF tone decoding, Doppler Shift detection, and frequency domain multiple access applications. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: 
       FIG. 1A  is a functional block diagram of a VoIP system which allows voice and data communications across an Internet Protocol network (Internet); 
       FIG. 1B  illustrates one possible alpha-numeric key configuration of keypad; 
       FIGS. 2A and 2B , illustrate cases where the response (gain versus frequency) curves for exemplary conventional row and column DTMF filters are shown, along with the received tones shown by dashed lined vectors and the detected tones shown by solid line vectors; 
       FIG. 3  illustrates functional blocks implementing by algorithms executed by DSP, although these blocks could be implemented, either in whole or in part, in discrete hardware/software devices; 
       FIG. 4  illustrates a preferred frame validation procedure; 
       FIGS. 5A and 5B  illustrate cases where the amplitude versus frequency curves for the M sample frames are sharper than those of the N sample frames; 
       FIGS. 5C and 5D  illustrate a preferred filtering procedure for implementing a selected one of the eight Goertzel filters. 
   

   DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The principles of the present invention and their advantages are best understood by referring to the illustrated embodiment depicted in  FIGS. 1-5C  of the drawings, in which like numbers designate like parts. 
     FIG. 1A  is a functional block diagram of a VoIP system  100  which allows voice and data communications across an Internet Protocol network (Internet)  101 . At the highest level, system  100  includes an end-user terminal  102  communicating with Internet  101  through an Internet Service Provider (ISP) and a corresponding telecommunications connection  104  (e.g. a conventional telephone line, Digital Subscriber Line, cable, or wireless link) or direct digital link. 
   End-user terminal includes a set of input/output (I/O) devices  105 . For purposes of the present invention, an audio hand- or headset  106  is shown, along with a DTMF keypad  107 . In actual embodiments, input/output devices  105  may also include a computer keyboard, display and/or audio speaker system. 
   In the illustrated embodiment, end-user terminal  102  is based on an information processing system  108  including a digital signal processor  110 , a microprocessor  111 , along with memory and peripherals  112 . Voice and DTMF data being exchanged between I/O devices  105  and DSP  110  interface through a code-decode (Codec) and signal conditioning unit  109 . 
   Microprocessor  111  executes the program instructions necessary for overall control of system  108 . DSP  108 , among other things, executes the algorithms, such as filtering and compression/decompression algorithms, necessary to process voice and audio data. With respects to the preferred embodiment of the present inventive principles described below, DSP also performs DTMF tone detection in response to inputs to keypad  107 . 
     FIG. 1B  illustrates one possible alpha-numeric key configuration of keypad  107 . In this case, four rows and four columns of keys are shown, with each row assigned a corresponding tone frequency and each column assigned a corresponding tone frequency, for a total of 8 discrete frequencies. The depression of the key at the intersection of a given row and a given column results in the generation of a DTMF signal composed of the two corresponding tone frequencies. It should be noted that the use of an alpha-numeric keypad of four rows and four columns was arbitrarily chosen for illustrative purposes. In actual applications, the number of rows and columns vary, and the keys may represent information other than the depicted alpha-numeric scheme. Notwithstanding, the theory of operation remains the same. 
   As previously indicated, the detected amplitude in the DTMF tones can vary due to either the twist factor, frequency variation, or both. In practice, it is generally not possible to distinguish the source of the amplitude loss. This is illustrated in  FIGS. 2A and 2B , where the response (gain versus frequency) curves  201   a,b  for exemplary conventional row and column DTMF filters are shown, along with the received tones  203   a,b  shown by dashed lined vectors and the detected tones  202   a,b  shown by solid line vectors. In  FIG. 2A , the error is caused by the twist factor alone, while in  FIG. 2B , the error is caused by frequency deviation alone. 
   In accordance with the inventive concepts, techniques are provided for detecting DTMF tones which isolate twist factor from the effects of frequency error. A conceptual block diagram of these techniques is shown in FIG.  3 . Preferable, the functional blocks shown in  FIG. 3  are implemented by algorithms executed by DSP  108 , although these blocks could be implemented, either in whole or in part, in discrete hardware/software devices. 
   In the illustrated embodiment, the DTMF signal generated by the keypad is sampled in frames of  102  samples (N,M=102). As discussed further below, two  102  frames are used during the detection process since the minimum specified DTMF pulse width is 320 samples wide. As the samples are received, they are stored in sample buffer  301 . When 102 samples have been received, a flag is set the entire 102-sample frame is transferred into a temporary buffer accessible by DSP  108 . 
   The validity of each frame is then tested at block  302  to discriminate between transient (invalid) tones and valid DTMF tones. A preferred frame validation procedure  400  is illustrated in FIG.  4 . Here, the frame is divided into two subframes, a small subframe of L number of samples and large subframe of N−L number of samples, which could be for example, 20 and 82 samples respectively. The frame power for each of the two subframes is then taken at Steps  401  and  402 , where the frame power for each subframe is calculated as:
 
 E=Σx ( i ) 2   (1)
         where x(i) is the amplitude of the unfiltered samples, and i=1 to L for the small subframe and i=L+1 to N for the large subframe.       

   At Step  403 , the ratio of energies E large /E small  is compared with the sample ratio N−L/L. If the ratio E large /E small  is close (within a selected tolerance) to the ratio N−L/L, then the frame is declared valid (Step  404 ). On the other hand, if E large /E small &gt;&gt;N−L/L, then the frame is declared a transient frame (Step  405 ) and is not processed further. 
   After frame validation, the samples are passed to a bank of 8 Goertzel filters  303 , one for each of the eight possible DTMF tones in the illustrated system. Two N sample frames (indexed frames i and j respectively where j=i+1) are used for each detection, with the initial conditions for the second frame being derived during the calculation of the first frame. A preferred filtering procedure  500  for implementing a selected one of the eight Goertzel filters is illustrated in FIGURE  5 C. 
   The Goetzel filters used in the preferred embodiment of the present invention can be described by the equations:
 
 v   K ( n )=2 cos(ω K ) v   k ( n− 1)− v   k ( n− 2)+ x ( n )  (2)
 
 y   k ( N )= v   K ( N )−exp [− j w   K   ]v   K ( N− 1)= X ( k )  (3)
 
  E   K   =y   K ( N ) y   K *( N )  (4)
 
where k=1 to 8 is the index for the filter, n=1 to N is the current sample in a N sample frame, and E k  is the energy at frequency ω k .
 
   At Step  501 , the initial conditions are set for the first sample of the first frame, with init( 1 )=init( 2 )=0. At Step  502 , the first two values of V k , namely V k ( 0 ) and V k ( 1 ) in accordance with Equation (2). Thereafter, Equation (2) is iteratively applied at Steps  503 - 505 . Specifically, so long as the end of the frame has not been reached (i.e. n≦N−1), samples of amplitude x(n) are retrieved from the sample buffer and the current value v k (n) calculated. 
   After Equation (2) has been iteratively applied, an intermediate value v K−  partial(N) is calculated at Step  506  in accordance with Equation (5):
 
 v   k− partial( N )=2 cos(ω K )· v   k ( N− 1)· v   k ( N− 2)  (5)
 
   The peak energy for each filtered tone in the first frame can be calculated by taking |Y k (N)| 2 . Notwithstanding, according to the inventive concepts, a more straight forward operation is to use the intermediate result vk_partial(N) calculated at Step  506  and at Step  507  in the operation:
 
 E   i ( N )= v   K ( N− 1) 2   +v   K− partial( N ) 2 −2 cos(ω k )· v   K ( N− 1)· v   K− partial( N )  (6)
 
   The computed value of E i (N) is evaluated at Step  508 , and if an invalid tone is detected, the process returns to Step  501 , otherwise the process continues to Step  509 . 
   According to the inventive concepts, the results obtained from filtering the first frame of N samples are used as the initial conditions for filtering the second frame of M samples. Specifically, the new initial values are taken at Step  509 , where init( 1 ) is the value of vk_partial(N) and init( 2 ) is the value of vk(N−1) for the last frame. 
   The first two values of V k , V k ( 0 ) and V k ( 1 ) are calculated at Step  510  using Equation (2) and the initial condition from Step  509 . Equation (2) is then iteratively applied to the remainder of the second frame (i.e. m≦M) to calculate vk(M) at Steps  511 - 513 . 
   Using Eq. (5), the intermediate result vk_partial(M) is calculated for the second frame (Step  514 ) along with the peak energy for the frame E j (M) (Step  515 ). 
   The use of the results from the processing of the first frame as initial conditions for processing the second frame substantially reduces processing time. For example, in the present case where N=M=102, the processing of the entire 204 samples takes approximately half the time which would have been required if a 204sample frame was directly calculated as discussed above. 
   To determine whether the tone being processed by the given filter has a frequency error within or outside of the maximum specified, the ratio energy E i (N) for the N sample to the energy E j (M) is analyzed at Step  516 . E j (M) effectively corresponds to the energy of N+M samples, hence scaled appropriately for comparison. 
   As shown in  FIGS. 5A and 5B , the amplitude versus frequency curves  501   a,b  for the M sample frames are sharper than those of the N sample frames. Thus, when the ratio of E j (M) to E i (N) is close to one, the error is small, as shown in FIG.  5 A. However, as the frequency error increases, the ratio correspondingly deviates from one, as shown in FIG.  5 B. As a result, a threshold on the ratio E j (M)/E i (N) can be set (step  517 ), below which the frequency error can be declared as out of specification (Step  518 ) and above which the tone can be declared within specification (Step  519 ). Advantageously, the threshold can be set differently for different tone frequencies. 
   It should be noted that the principles discussed above can be extended to include the second harmonics of the DTMF tones. In this case, a second set of 8 Goertzel filters are provided which extract the second harmonics from the tones output from the keypads. In this case, the energy ratios are E j (M)/E i (N) for each second harmonic are measured against a threshold to determine if the allowable frequency error has been exceeded. The extraction and testing of additional harmonics allows for improved discrimination of the DTMF tones from other signals, such as those produced by speech. 
   Finally, each “digit” is validated (block  305 , FIG.  3 ). In the preferred embodiment, the row and column tones for the current digit or letter entry from the keypad are observed over a total of four frames. Specifically, an entry is declared valid if for the row and column tones of the corresponding composite signal:
 
 F   i   =F   i−1  AND  F   i−3 =Null(6)
 
where F i  is the frequency detected digit (letter) for the current frame, F i−1  is that detected for the immediately preceding frame and F i−3  is the frequency of the digit (letter) detected for the third previous frame. Note, this procedure does not rely on data from the 2nd previous frame (i.e. F i−2 ) since this frame could be a transient frame. Advantageously, no additional processing overhead is required since the frame data has already been extracted during the filtering process described above.
 
   Finally, while the inventive concepts have been described in view of DTMF-based systems, these concepts can be useful in many other applications, especially in those in which small frequency drifts of short duration signals must be efficiently detected and evaluated. Among these applications are Doppler radar, where the shift in the received signal frequency with reference to a nominal must be estimated, all frequency domain multiple access (DMA) applications, and digital subscriber line (DSL) applications, where sampling frequency drift estimation is required and in Signal analyzer which analyses periodic signals for frequency first and harmonic level contents. 
   Although the invention has been described with reference to a specific embodiments, these descriptions are not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as alternative embodiments of the invention will become apparent to persons skilled in the art upon reference to the description of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. 
   It is therefore, contemplated that the claims will cover any such modifications or embodiments that fall within the true scope of the invention.