Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-11-15
2004-07-20
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C341S061000
Reexamination Certificate
active
06766338
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of digital signal processing, and more particularly to converting a digital signal density to a different digital signal density.
BACKGROUND OF THE INVENTION
In digital systems, the digital signal consists of discrete data samples taken at periodic time intervals from a continuous analog source. These individual data samples make up the digital signal. The number of samples in a set period of time determines the accuracy of the digital signal that represents the original analog source. More samples in a period of time allows for a digital signal to more closely resemble the original analog source. The Sample Rate is the number of samples from a signal taken during a set period of time. For example, a 32,000 Hz sample rate has 32,000 samples per second. In digital systems with multiple components, it is often the case that different components require the signal to be sampled at different rates. For example, sometimes data is sampled at a lower frequency due to storage, processor, or bandwidth restrictions. These restrictions result in a digital signal that has a lower sampling rate than what is desired at the digital to analog conversion part of the system. When the desired signal sample rate is different than the source signal sample rate, the source signal is altered to match the desired sample rate. For this alteration to happen, new samples are added to or subtracted from the original signal. For example, if a 32,000 Hz sample rate is being converted to 44,100 Hz, 12,100 additional samples are created.
One method of sample rate conversion (SRC) is to perform interpolation on the original samples to create new samples. Interpolation is computation of a new value from the existing data. There are several methods of digital sample rate conversion. Some methods use more memory than others do, while others use more processor resources. Usually there is a trade-off between memory and processor resources for each method and application. In applications requiring less memory usage, LaGrange Interpolation is favorable since it does not require a large table to determine a new sample. However, new coefficients are calculated to determine new samples, making LaGrange Interpolation more processor intensive than other sample rate converters.
The system and apparatus of U.S. Pat. No. 5,892,694 uses the sample rate conversion method of upsampling the input stream by integer value M, convolving with a low pass filter to obtain the new samples, and then downsampling the output by integer N. It uses the least common multiple to upsample before downsampling. The problem with this method is that it uses a great deal of memory and computation.
The sampling frequency converter of U.S. Pat. No. 5,365,468 oversamples the input stream by a small integer amount, rather than by the least common multiple. It then takes the oversampled data and does polynomial interpolation to get new samples on either side of the desired output sample. It then performs linear interpolation between those two samples to get the output sample. This still requires a great deal of computation because it uses a polynomial interpolator and then linear interpolation, and the result is not as accurate as desired.
U.S. Pat. No. 5,859,787 discloses methods for resampling including convolving a given set of samples with the impulse response function of a low pass filter. The invention relates to arbitrary-ratio signal resampling techniques. Arbitrary-ratio resampling techniques can be applied to create a constant sampling rate output stream from a source where a sampling rate, is either not precisely known in advance or which may drift. The invention provides a method for resampling which convolves a given set of samples with the impulse response function of a low pass filter. The values of the impulse response used for the convolution calculation are computed at the time of resampling from a segmented polynomial approximating the impulse response. The segmented polynomial of the invention is represented, for each segment of the polynomial, by a number of coefficients. These coefficients are determined by fitting, in a least means squared sense, the polynomial to the impulse response function at a large number of points. This technique stores a large superset of impulse response samples as discrete coefficients in a memory device. Values of the impulse response used for convolution are calculated by an approximation that uses the stored impulse response. This approximation decreases the accuracy of the digital signal.
SUMMARY OF THE INVENTION
Accordingly, a need has arisen in the art for an improved sample rate conversion system. The present invention provides a method that substantially reduces or eliminates problems associated with prior data rate conversion systems.
In accordance with the present invention, a LaGrange Interpolation is used in a finite impulse response filter through which the input is convolved to produce the desired output signal. LaGrange Interpolation uses N+1 samples to achieve an N
th
order computation. Each interpolated sample is created from the weighted average of N+1 of the original samples. The weights of the weighted average are obtained by using calculated coefficients based on the position of the new sample. The distance of the new sample from the nearest input sample is used to generate unique coefficients. To determine how much to increment the distance, a ratio is defined. This ratio is the input sample rate divided by the output sample rate. The ratio is used in determining when to retrieve a new input sample, and the determination of the distance of the new sample from the input sample. Whenever a new sample is created, the ratio is added to a “distance counter.” The distance counter stores the decimal portion of the results and whenever the distance counter exceeds 1, then 1 is subtracted and a new input sample is added to the set of N+1 input samples used in the interpolation process, and the oldest input sample is discarded. This distance counter determines when a new input sample is added, and the distance counter is also used to calculate the coefficients.
Calculating the coefficients uses approximately N squared plus N multiplications and N squared plus N additions to update the N+1 coefficients for each new output sample. These calculations can become very processor intensive when working with high orders. The multiplications are necessary for each sample created, and, therefore, high orders are impractical since it would use enormous processor resources.
Once the coefficients are determined, they are multiplied with an existing sample. The summation of the multiplications will yield the new sample. Once a new sample is found, the distance counter is incremented by the ratio and the process of determining the coefficients in obtaining a new sample is repeated.
In order to eliminate the processing requirements associated with the calculation of the coefficients, coefficients can be calculated prior to resampling and stored in a table. To avoid increased memory requirements, coefficients are only calculated for pre-determined values of the distance counter, which, in turn, are determined by the ratios of the known input and output sample rates. For a 16
th
order LaGrange Interpolation, for example, 17 coefficients will be determined for each value of the distance counter.
Although the methods of this invention are particularly suitable for digital audio signals, in particular, real time processing at different output and input sample rates, the method may be used for any digital processing requirement, such as in cell phones, hard disk drives, voice over Internet devices and other devices.
REFERENCES:
patent: 5365468 (1994-11-01), Kakubo et al.
patent: 5821884 (1998-10-01), Lee
patent: 5859787 (1999-01-01), Wang et al.
patent: 5892694 (1999-04-01), Ott
patent: 6317765 (2001-11-01), Page et al.
patent: 6362755 (2002-03-01), Tinker
Pohlmann, Ken C.;Principals of Digital Audio(3rdEd.), p
Handley Stephen R.
Hayes Jeffrey Scott
Lin Rocky Chau-Hsiung
Brady III W. James
Mai Tan V.
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
High order lagrange sample rate conversion using tables 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 High order lagrange sample rate conversion using tables for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High order lagrange sample rate conversion using tables for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205848