Data processing: speech signal processing – linguistics – language – Speech signal processing – For storage or transmission
Reexamination Certificate
2001-05-14
2004-08-31
To, Doris H. (Department: 2655)
Data processing: speech signal processing, linguistics, language
Speech signal processing
For storage or transmission
C704S262000, C704S264000, C704S219000
Reexamination Certificate
active
06785646
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the compression/decompression of data and more particularly to improving the performance of the coding/decoding of waveforms, including speech.
Advances in technology has allowed waveforms, such as audio and speech, to be efficiently communicated in digital rather than analog format. Today there are many different types of codec's (coding/decoding circuits or software routines), which inputs a waveform, for example, speech, and outputs a series of codes. At the receiving side these codes are then used to reconstruct an approximation to the waveform.
There are generally three general types of coders: a vocoder, a waveform coder, and a hybrid coder. The first, vocoding, encodes information about how the speech signal was produced by the human vocal system. Vocoding uses techniques, for example Linear Predictive Coding (LPC), which determine parameters about how the speech was created and use these parameters to encode the waveform. While vocoding techniques can produce human understandable speech at very low bit rates, usually below 4.8 kbps, the reproduced speech signal often sounds quite synthetic. The second, waveform coding, tries to encode the waveform itself. An example of waveform encoding is Pulse Code Modulation (PCM) encoding. Waveform coding produces a decoded waveform that has the same general shape as the original. However, as information is lost using this procedure, waveform coders in general do not perform well at data rates below 16 kbps. The last, hybrid coders try to exploit the advantages of both vocoding and waveform techniques. A typical hybrid is an Analysis-by Synthesis coder. In order to code an original waveform such as speech, a codebook having vectors representing vector quantized waveforms is used to feed a synthesis filter which reconstructs an approximation of the original waveform. The index of the vector giving the reconstructed waveform with the closest match to the original waveform is then sent as the encoded waveform. Hybrids encode speech in such a way that results in a low data rate while keeping the speech intelligible. Typical bandwidth requirements lie between 4.8 and 16 kbps, inclusive.
One typical hybrid coder is a Code Excited Linear Predictive (CELP) coder (see CCITT Recommendation G.728 (1992), “Coding of speech at 16 kbit/s using low delay code excited linear prediction.”). The G.728 codec can send encoded speech at about 16 kbits/s. The original waveform is partitioned into one or more sections called frames. Each frame is then quantized into a number of samples. For example, G.728 may use 20 samples representing about a 2.5 ms frame of speech and have synthesis filter parameters that are based on a high order short term linear predictor. In this example the frame may be represented by a 5 element vector, of which there are about 128 variations (or 7 bits). An index to a codebook gives a vector which is sent through the synthesis filter to give a reconstructed frame. This reconstructed frame is compared with the original frame and a weighted error is determined. The goal is to obtain the index with the minimum weighted error, for example, the minimum squared difference between the reconstructed frame associated with the index and the original frame. For the above G.728 example, 10 bits may be sent as a code for a frame with seven bits being the codebook index and the other three representing a gain. This conventional codebook search algorithm sequentially searches through the whole codebook, i.e., the index goes from 1 to N, where N is the number of vectors in the codebook. In the above G.728 example, N=128. This exhaustive search is computationally intensive, i.e., many clock cycles are used.
The widespread use of Digital Signal Processors (DSP's) in conjunction with the CPU has reduced the computational burden. A DSP may perform a plurality of instructions in parallel, i.e., during the same clock cycle. However, improvement in performance is still needed as the search is still computationally intensive. This is because there are many frames and each frame requires an exhaustive search through the codebook. In addition, these DSP's may have a small register set which complicates the task of having the DSP perform some or all of the computations.
Thus what is needed are techniques to further improve performance of the codebook search while taking into account the limitations on the number of DSP registers.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a method and system to improve the cookbook search algorithm used in a coding/decoding device or routine. The codebook search algorithm is performed by a processing system that allows for parallel execution of instructions, for example a DSP. This permits the use of a memory location rather than a register to store the index to the codebook. As there is parallel data movement capability, modifications, for example, incrementing, of the codebook index can be stored in and retrieved from memory with minimal, if any, effect on the search performance. And another DSP register to maintain the above codebook index is not needed. The improvement of the algorithm by modifying the data structure having the filter coefficients and codebook index, results in a reduction of at least one clock cycle in the search algorithm.
An embodiment of the present invention provides a method for coding of a first waveform. First a plurality of vectors determined from a plurality of waveforms is stored in a computer readable medium, for example a volatile or non-volatile memory. Next a minimum weighted error using a plurality of filter coefficients and the plurality of vectors is determined. The minimum weighted error gives a closest match between the first waveform and a second waveform synthesized from a selected vector of the plurality of vectors. Then an indication of said selected vector is provided as part of a coding of the first waveform. The plurality of filter coefficients have added to them at least one duplicate filter coefficient such that the performance of determining the minimum weighted error is improved, by for example, at least one clock cycle.
Another embodiment of the present invention includes a method for improving a codebook search used in the encoding of a waveform, for example, speech, by a processor, for example, a DSP, where the codebook includes a plurality of vectors. First the method determines a data array including an array of filter coefficients. Next a first plurality of filter taps for a first vector is calculated. A filter tap is based on a filter coefficient and an element of a vector. A filter output is determined, using the first plurality of filter taps and a weighted error is then determined based on the filter output and a vectorized portion of the waveform. After a weighted error is calculated and a minimum error index determined, the process is repeated with a second plurality of filter taps being determined for a second vector, where at least one filter tap of the second plurality of filter taps is calculated in parallel when the weighted error associated with the first plurality of filter taps was determined.
These and other embodiments of the present invention are described in more detail in conjunction with the text below and attached figures.
REFERENCES:
patent: 5717824 (1998-02-01), Chhatwal
patent: 6073092 (2000-06-01), Kwon
Simons John
Wang Yunbiao
Renesas Technology Corporation
To Doris H.
Townsend and Townsend / and Crew LLP
Vo Huyen
LandOfFree
Method and system for performing a codebook search used in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing a codebook search used in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing a codebook search used in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341642