Patent Publication Number: US-7715996-B1

Title: Method of estimating digital signal frequency

Description:
FIELD OF THE INVENTION 
     The present invention relates, in general, to measuring a signal, and, in particular to waveform analysis of frequency. 
     BACKGROUND OF THE INVENTION 
     Frequency estimation is the cornerstone of digital signal processing, whether for analysis of radar, sonar, speech, or telephony signals. The Fourier transform, embodied in the modern FFT algorithm, has been the leading method of frequency estimation both in hardware and software. Twenty years before the advent of the FFT, Gabor introduced the notion of Instantaneous Frequency (IF) for a signal, which is derived from a complex extension using the Hilbert transform. The critical property that allowed such a different approach is the orthogonality of any signal to its Hilbert transform; Gabor&#39;s IF notion applied ideas from classical complex analysis. 
     The Fourier transform suffers from the well-known localization constraint, an inability to resolve time and frequency equally well, while the Hilbert transform is an infinite impulse response (IIR) filter, hence realizable digitally only approximately. 
     Typical of prior art methods employing the Fourier transform to estimate frequency include: 
     U.S. Pat. No. 4,904,930, entitled “ESTIMATION OF CARRIER FREQUENCY ESTIMATION,” U.S. Pat. No. 5,729,124, entitled “ESTIMATION OF SIGNAL FREQUENCY USING FAST WALSH TRANSFORM,” and U.S. Pat. No. 6,577,968 entitled “METHOD OF ESTIMATING SIGNAL FREQUENCY,” each disclose a method of estimating frequency using the either a Fourier transform or a Walsh-Hadamard transform, a generalized class of Fourier transforms. The present invention does not use Fourier or Walsh transforms, as do the methods described in U.S. Pat. Nos. 4,904,930, 5,729,124, and 6,577,968. U.S. Pat. Nos. 4,904,930, 5,729,124, and 6,577,968 are hereby incorporated by reference into the specification of the present invention. 
     There exists a need to estimate frequency of a signal in a less computationally complicated manner. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to estimate the frequency of a received signal in a less computationally complicated manner. The method uses a differentiation operation to generate a complex extension of a real signal, and then produce an estimate of frequency from the phase of the resulting complex extension. 
     The present invention estimates digital signal frequency without the use of Hilbert or Fourier transforms common in prior art methods. 
     The first step of the present method is receiving a signal. 
     The second step of the present method is digitizing the received signal. 
     The third step of the present method is segmenting the digitized signal into one or more data blocks. 
     The fourth step of the present method is selecting one of the data blocks. 
     The fifth step of the present method is to differentiate the data block selected in the fourth step. 
     The sixth step of the present method is calculating the orthogonal of the differentiated data block of the fifth step to the data block selected in the fourth step. 
     The seventh step of the present method is computing the phase using the data block selected in the fourth step and the result of the sixth step. 
     The eighth step of the present method is unwrapping the phase from the seventh step. 
     The ninth step of the present method is differentiating the phase determined in the eighth step to estimate frequency. 
     The tenth, and final, step of the present method is repeating the fourth step through the ninth step for each data block the signal was divided into in the third step. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
         FIG. 1  is a flowchart of steps of the present invention; and 
         FIG. 2  is a flowchart of the steps of an alternate embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention is a method of estimating digital signal frequency without the use of Fourier or Hilbert transforms. The invention replaces the Hilbert transform by the much simpler differentiation operation, and orthogonality is established using the Gram-Schmidt process. 
     A flowchart of the steps of the present invention is shown in  FIG. 1 . 
     The first step  1  of the present method is receiving a signal. 
     The second step  2  of the present method is digitizing the received signal. 
     The third step  3  of the present method is segmenting the digitized signal into one or more data blocks. 
     The number of data blocks is user-selectable and may be either overlapping blocks or disjointed. 
     Data segmentation may be performed using disjoint or overlapping increments defined by a user-selected number of samples. Tapering may also be applied to data segments using any of the known window tapers, such as triangular, trapezoidal, Gaussian, Hamming, Hanning, Kaiser, and so on. 
     The fourth step  4  of the present method is selecting one of the data blocks. 
     The fifth step  5  of the present method is to differentiate the data block selected in the fourth step. Differentiation means to use the next-sample numerical difference or to use higher order numerical differences. 
     The sixth step  6  of the present method is calculating the orthogonal of the differentiated data block of the fifth step  5  to the data block selected in the fourth step  4 . 
     The Gram-Schmidt process is used to obtain the required orthogonality between a signal and its derivative. The complex extension then leads to computation of phase using either the inverse tangent function or the complex logarithm. 
     To use the Gram-Schmidt process, the following steps are preferably used: 
     First, compute the vector dot product of data from the fourth step  4  of the present method with itself. 
     Second, compute the vector dot product of data from the fourth step  4  of the present method with data from the fifth step  5  of the present method. 
     Third, divide the result of the second step in the Gram-Schmidt process above by the first step in the Gram-Schmidt process above. 
     Fourth, multiply result in the third step of the Gram-Schmidt process above by digital data from the fourth step  4  of the present method. 
     Fifth, subtract result of the fourth step of the Gram-Schmidt process above from the data in the fifth step  5  of the present method. 
     The result of the fifth step of the Gram-Schmidt process above will be orthogonal to data in Step  4  of the present method, and comprises the sixth step  6  of the present method. 
     The seventh step  7  of the present method is computing the phase using the data block selected in the fourth step  4  and the result of the sixth step  6 . 
     The complex extension leads to computation of phase using either the inverse tangent function or the complex logarithm. 
     Thus, the phase angle between the data from the fourth step  4  of the present method and the sixth step  6  may be computed from the arctangent (or inverse tangent) of data from the sixth step  6  divided by data from the fourth step  4 ; or by following the following steps: 
     First, multiply data in the sixth step  6  of the present method by the imaginary unit i (square root of minus one). 
     Second, add the result of the first step above to the result of the fourth step  4  of the present method. 
     Third, compute the complex logarithm of the result of the second step above. 
     Fourth, take the imaginary part of the third step above, yielding the wrapped phase. 
     The eighth step  8  of the present method is unwrapping the phase from the seventh step  7 . 
     Persons skilled in the art will recognize that phase unwrapping refers to the process of contiguously joining phase segments as soon as they exceed 2*Pi radians. 
     The ninth step  9  of the present method is differentiating the phase determined in the eighth step  8  to estimate frequency. 
     Differentiation the phase means next-sample numerical difference. In an alternate embodiment, the data is smoothed through averaging. 
     To improve the quality of frequency estimation over segmented digital data, linear regression may first be applied to the unwrapped phase; the coefficient of the 1 st  order term is then the estimated frequency over the chosen segment. Linear regression also provides a measure of frequency accuracy, not available through Fourier or Hilbert transform based methods. 
     Therefore, in another alternate embodiment shown in  FIG. 2 , the ninth step  9  in the preferred embodiment is replaced with the following variant (steps  1 - 8  are the same as the preferred embodiment described above). 
     First in step  19 , a linear regression fit through the phase estimate in the selected data block is derived. 
     Second in step  20 , the coefficient of the 1 st  order term is used as the frequency estimate over the selected block. 
     As noted above, this alternate embodiment has two advantages: it allows one to obtain a more robust estimate of frequency from phase; and linear regression provides an estimate of frequency accuracy. 
     Higher order derivatives may also be used in generating the complex extension of the real signal. 
     Referring again to  FIG. 1 , the tenth, and final, step  10  of the present method is repeating the fourth step  4  through the ninth step  9  for each data block the signal was divided into in the third step  3 . 
     The present invention presents a number of benefits over prior art techniques. All operations are in the time domain, and no filtering is involved. 
     While the preferred embodiments of the invention have been illustrated and described, it will be apparent to those of ordinary skill in the art that various changes and modifications may be made without deviating from the inventive concepts set forth above.