Data processing: speech signal processing – linguistics – language – Speech signal processing – For storage or transmission
Reexamination Certificate
2000-03-07
2004-10-19
Dorvil, Richemond (Department: 2654)
Data processing: speech signal processing, linguistics, language
Speech signal processing
For storage or transmission
Reexamination Certificate
active
06807527
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method and an apparatus for a speech coding algorithm, in particular for a code excited linear predictive (CELP) coding algorithm. CELP algorithms are utilised in two-way voice communications, e.g. between a base station and a mobile station in a cellular system. A method for a CELP algorithm includes the steps of pre-processing a sampled speech s{n} in a signal pre-processor so as to output at least a noise filtered speech output vector and a channel noise estimate, model parameter estimation of the noise filtered speech output vector so as to output a prediction residual and a long term prediction gain, encoding the prediction residual so as to output an adaptive codebook vector including an index of impulse response functions of a filter and a vector gain, and formatting the encoded speech packets.
The CELP algorithm was found to provide good speech quality at intermediate bit rates, that is 4800 or 9600 bps. However, the vector quantization of the excitation signal requires an extremely high computational effort. Several suggestions have been made for speeding up the vector quantization including the use of overlapping codebook vectors.
BACKGROUND OF THE INVENTION
Code excited linear predictive (CELP) algorithms are described by S. Sinhal and B. S. Atal: “Improving performance of multi-pulse LPC coders at low bit rates” in Proc. Int. Conf. Acoust., Speech, Signal Process. (San Diego), 1984, pp. 1.3.1-1.3.4 and by W. B. Kleijn, D. J. Krasinski, and R. H. Ketchum: “Fast methods for the CELP speech coding algorithm” in IEEE Trans. Acoust., Speech, Signal Process., Vol.38, No. 8, pp. 1330-1342, 1990. CELP coding algorithms are utilised for processing sampled speech on a subframe by subframe basis. The spectral envelope of the speech signal is described by a filter of which the coefficients are obtained using the linear prediction technique. The coefficients are quantized so that the filter can be constructed on both the transmitter and the receiver side. The filter coefficients are determined by an analysis-by-synthesis procedure. A set of such candidate excitation sequences or vectors is stored in a codebook. The index of the vector producing the most accurate speech is transmitted to the receive end of the channel. The input speech on the transmitter side is regained on the receiver side by synthetic speech that is generated using the vector of which the index has been transmitted.
The main task is to find an optimum vector in the codebook which describes most accurately the input speech. Fast vector quantization and excellent synthetic speech quality makes the CELP algorithms attractive for speech coding applications. The implementation of the CELP algorithm in a spread spectrum digital system is described in the IS-127 Standard “Enhanced Variable Rate Codec, Speech Service Option 3 for Wideband Spread Spectrum Digital Systems”, Apr. 19, 1996, Section 4.5.7, “Computation of the algebraic CELP Fixed Codebook Contribution”. The codebook utilised in this standard is a fixed codebook with an algebraic codebook (ACELP) structure.
In order to find the optimum codevector in the algebraic codebook the ACELP codebook is searched by minimising the mean-squared error (MSE) between the weighted input speech and the weighted synthesis speech. In other words, the codebook is searched by maximising the term
T
k
=
C
k
2
E
k
,
where C
k
is the correlation of the impulse response and the perceptual domain target signal and E
k
is the energy or covariance of the impulse response of the codebook vector, both at position k. The codebook vector is a series of unit pulses, each pulse being at an appropriate position in the codebook and having an appropriately chosen sign.
In order to determine the optimum algebraic codebook vector the correlation and energy terms should be computed for all possible combinations of pulse positions and signs. This, however, is a prohibitive task. In order to simplify the search, two strategies for searching the pulse signs and positions as explained below are used.
The pulse signs are pre-set (outside the closed loop search) by considering the sign of an appropriate reference signal. Amplitudes are pre-set by setting the amplitude of a pulse at a position equal to the sign of the reference signal at that position. With this “new” components a modified correlation C
k
′ and a modified energy E
k
′ is calculated.
Having pre-set the pulse amplitudes as explained above the optimum pulse positions are determined using an efficient non-exhaustive analysis-by-synthesis search technique. In this technique the term T
k
is tested for a small percentage of position combinations using an iterative “depth-first” tree search strategy.
Once the positions and signs of the excitation pulses are determined, the “new” codebook vector is built as a series of unit pulses, each pulse being at a “new” position in the codebook.
The gain of the fixed codebook vector is determined afterwards by:
g
c
=
C
k
E
k
.
This fixed codebook search algorithm as proposed in the IS-127 Standard has the following disadvantages:
The term
T
k
=
C
k
2
E
k
is a non-linear multidimensional multi-extremum function. The task of searching for an extremum of this non-linear multidimensional multi-extremum function is solved in a combinatorial way that can result in finding a local extremum rather than a global one, when the available computational performance is limited.
The computation of the minimising function is very time consuming and necessitates a large number of computation cycles. Namely, the fixed codebook search method as proposed in the IS-127 Standard assumes a linear search for pulse positions in each track and requires 1144 calculations. Moreover, the evaluation of T
k
includes a division operation that augments considerably the complexity of the algorithm.
Thus, there is a need for a method and an apparatus for a CELP algorithm which is faster than the prior art implementations and which is less expensive in terms of computational cycles, which however maintains the maximum achievable accuracy.
SUMMARY OF THE INVENTION
The underlying problem of the invention is solved basically by applying the feature laid down in the independent claims. Preferred embodiments are given in the dependent claims.
The need for improved efficiency of a fast multi-pulse coding algorithm for speech residuals on frames with a constant length is met by the present invention. The method and apparatus according to the present invention, provide for a fast convergence of the algorithm such that the optimum vector may be searched for more efficiently than with the prior art.
The basic idea underlying the invention is the decomposition of the task of finding an optimum codebook vector into two sub-tasks:
calculation of the amplitude gains for the coding pulses (first stage);
computation of the optimum sample positions for the coding pulses (second stage).
It should be noted that the calculation sequence according to the present invention is reverse to the one that is described in the prior art according to the IS-127 Standard.
The method according to the invention permits to reduce the multidimensional multi-extremum non-linear task of searching for optimum coding pulse positions of a discrete source signal to an optimum extremum search task with a multidimensional square form that is minimised sequentially for every pulse. This decreases essentially the computation time and provides a higher coding accuracy.
At the first stage the optimum codevector gain “g
c
” is determined according to the equation:
g
c
=
a
∑
i
=
1
N
[
x
(
i
)
]
2
∑
i
=
1
N
i
·
[
h
(
N
-
i
+
1
)
]
2
,
where x is a source discrete signal (perceptual domain target signal vector),
h is a special function (impulse response of the filter),
a is an experimentally determined weighting coefficient, and
N is a subframe length.
An optimum value for the weighting coefficient “a” is experimentally determined for an appropriate function “h” and a gi
Diachenko Juri
Rozhdestvenskij Juri
Clingan, Jr. James L.
Dorvil Richemond
Motorola Inc.
Retsky Jonathan R.
Storm Donald L.
LandOfFree
Method and apparatus for determination of an optimum fixed... 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 apparatus for determination of an optimum fixed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determination of an optimum fixed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300807