Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-06-11
2004-11-16
Chaki, Kakali (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S402000
Reexamination Certificate
active
06820104
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the determination of coefficients of a function. More particularly, the methods and computer program products of the present invention relate to reducing the number of computations and values that must be stored in the determination of the coefficients.
BACKGROUND OF THE INVENTION
Signal processing is an important function of many electronic systems. In particular, in many electronic systems, data is transmitted in signal form. Further, some electronic systems analyze and monitor the operation of mechanical or chemical systems by observing the characteristics of signals, such as vibration signals and other types of signals, that are output from these systems. In light of this, methods have been developed to characterize signals such that information or data in the signal is available for data processing.
As one example, in many electronic systems, time domain signals are typically transformed to the frequency domain prior to signal processing. A typical method for converting signals to the frequency domain is performed using Fourier Transforms. The Fourier Transform of a signal is based on a plurality of samples of the time domain signal taken over a selected time period, known as the base frequency. Based on these samples of the signal the Fourier Transform provides a plurality of coefficients, where the coefficients respectively represent the amplitude of a frequency that is a multiple of the base frequency. These coefficients of the Fourier Transform, which represent the signal in the frequency domain, are then used by electronic systems in processing the signal.
Although Fourier Transforms are among some of the most widely used functions for processing signals, there are other functions that are either currently used or will be used in the future, as a better understanding of their applicability is recognized. These functions include Bessel functions, Legendre Polynomials, Tschebysheff Polynomials of First and Second Kind, Jacoby Polynomials, Generalized Laguerre Polynomials, Hermite Polynomials, Bernoulli Polynomials, Euler Polynomials, and a variety of Matrices used in Quantum Mechanics, Linear Analysis functions, wavelets and fractals just to name a few.
Although Fourier transforms and the other functions mentioned above are useful in determining characteristics of signals for use in data processing, there are some drawbacks to their use. Specifically, application of these functions to signals is typically computationally intensive. This is disadvantageous as it may require the use of specialized processors in order to perform data processing. Further, and even more importantly, the time required to perform the number of computations using these functions may cause an unacceptable delay for many data processing applications. In fact, a goal of many data processing systems is the ability to process data signals in real time, with no delay.
For example, the Fourier Series is defined as an infinite series of coefficients representing a signal. To transform a signal using a Fourier Series would require an infinite number of computations. To remedy this problem, many conventional data processing systems use Discrete Fourier Transforms (DFT), as opposed to the infinite Fourier Series. The DFT is the digital approximation to the Fourier Series and is used to process digitized analog information. Importantly, the DFT replaces the infinite series of the Fourier Series with a finite set of N evenly spaced samples taken over a finite period. The computation of the DFT therefore provides the same number of coefficients as the samples received, instead of an infinite number of samples required by the Fourier Series. As such, use of the DFT provides the most satisfactory current means to process the signal.
Because of the importance of reducing the time required to process signals, however, methods have been developed to further reduce the number of computations required to perform a DFT of a signal. Specifically, the DFT procedure computes each coefficient by a similar process. The process for a general coefficient is; multiply each sample by the sine or cosine of the normalized value of the independent variable times the angular rate and sum over all of the samples. This procedure defines N multiply-add steps for each of N coefficients, which in turn, equates to N
2
multiply-add computations per DFT. As many samples of a signal are typically required to perform an adequate approximation of the signal, the DFT of a signal is typically computational and time intensive.
One of the methods developed to reduce the number of computations is the Butterfly method, which reduces the number of computations from N
2
to N times log (N). The Butterfly method is based on the fact that many of the trigonometric values of the DFT are the same due to periodicity of the functions. As such, the Butterfly method reduces the matrix associated with the DFT into N/2 two-point transforms (i.e., the transforms representing each coefficient a
n
and b
n
). The Butterfly method further reduces the redundant trigonometric values of the DFT. Although the Butterfly method reduces the number of computations over the more traditional DFT method, it also adds complexity to the Fourier transformation of a signal. Specifically, the Butterfly method uses a complex method for addressing the samples of the signal and the matrix containing the functions. This complexity can require the use of specialized processors and increase time for computation of the Fourier Transform. By its nature, the Butterfly is a batch process, which does not begin determination of the coefficients until after all of the samples have been received. Consequently, this method causes latency in the determination of the coefficients of the function, where the time between the arrival of the last sample and the availability of the coefficients is defined as the latency of the system.
An improved approach to reducing the time required to process signals is described in U.S. application Ser. No. 09/560,221 entitled: APPARATUS, METHODS, AND COMPUTER PROGRAM PRODUCTS FOR DETERMINING THE COEFFICIENTS OF A FUNCTION WITH DECREASED LATENCY filed Apr. 28, 2000 and corresponding PCT Application Number WO 00/67146, entitled: Computation of Discrete Fourier Transform, publication date Nov. 9, 2000. These applications are assigned to the inventor of the present application, and are incorporated herein by reference. The approach in WO 00/67146 reduces or eliminates the problem of latency for processing coefficients by using the property of independence of samples of functions like the DFT. The approach updates at least one of the coefficients of the function prior to receipt of the last sample of a sample set thereby reduce latency.
Despite the improvements in data processing accomplished by the apparatus and methods of U.S. Pat. No. 6,735,610), there are continuing needs to reduce the number of calculations required stored terms for determining the coefficients of a function.
SUMMARY OF THE INVENTION
As set forth below, the apparatus, methods, and computer program products of the present invention overcome many of the deficiencies identified with processing signals using functions, such as Fourier Transforms. In particular, the present invention provides methods and computer program products that determine the coefficients of a function representative of an input signal with reduced calculation complexity, such that the coefficients of the function are made available within a decreased time from receipt of the last sample of the signal. The present invention also provides methods and computer program products that reduce the amount calculations that must be performed in order to determine the coefficients of a function, such that less complex hardware designs can be implemented. Specifically, the time for performing computations can be conserved by reusing previously calculated terms so that terms having the same value are calculated fewer than the number of times that the term appears in the
Pelton Walter Eugene
Stoica Adrian
Alston & Bird LLP
Chaki Kakali
Do Chat C.
Pelton Walter Eugene
LandOfFree
Apparatus, methods, and computer program products for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus, methods, and computer program products for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus, methods, and computer program products for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3280918