JP3045197B2 - Codebook design method for vector quantizer - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for designing a vector quantizer for coding an audio or video signal.

[0002]

2. Description of the Related Art As one of high-efficiency quantization methods for encoding audio signals and image signals, vector quantization and matrix quantization (hereinafter, these are represented by the term vector quantization) are known. ing. In vector quantization, a representative vector pattern is stored in a portion called a codebook according to a given number of bits. The performance of a quantizer depends on how this representative pattern is determined.

An LBG algorithm is known as a codebook design technique in vector quantization. This method prepares a training vector data series having a distribution that well represents the distribution of the vector space to be vector-quantized, and uses a codebook to minimize the sum of distortion when quantizing these learning data. Is a method of designing

The LBG algorithm sets the initial number of representative vectors to one, and alternately performs an operation for obtaining an optimal representative vector and an operation for increasing the number of representative vectors by a factor of two.
Obtain the desired number of representative vectors.

[0005] In the operation for obtaining the optimum representative vector, first, a process of updating which representative vector the learning data belongs to is performed, and the representative vector is updated so that the total sum of the distortion is minimized in the belonging state. I do. The representative vector gradually approaches an optimal one by repeatedly performing the above-described belonging update process and the representative vector update process alternately until convergence. This operation is Lloyd-Max or k
Called the averaging algorithm.

The LBG algorithm means an operation of dividing a set of learning vectors into several subsets. The above subset is called a cluster, and the division operation is called clustering. For details of the LBG algorithm, refer to the document Y. Linde. A. Buzo.
"An Algorithm for Vector Quantizer Desig" by RMGray
n ”.IEEE Trans.Commun.COM-28 pp84-95,1980.

[0007]

In the vector quantization,
It has been pointed out that there is no relationship between the representative vector and the code actually transmitted, so that if a code error occurs in the transmission path, the quality is significantly degraded.

As one method for solving this problem, the above L
It is reported that if a measure taking into account a code error is used as a distortion measure of the BG algorithm and learning is performed so that the total sum of the measures is minimized, even if a code error occurs, damage is relatively small.

References: Kumazawa, Kasahara, Namerikawa "Construction of Vector Quantizer Considering Channel Error" Transactions of the Institute of Electronics, Information and Communication Engineers, Vol.J67-B No.1 1984 ”, And cannot be designed to have a structure that is as resistant to code errors as expected due to falling into a local minimum solution. The reason is that since the LBG algorithm is an asymptotic method of gradually approaching the optimal solution, it easily falls into the local minimum solution, and once it falls, there is no means to escape from it.

[0010] The present invention has been made in view of the above,
It is an object of the present invention to provide a codebook designing method for a vector quantizer which is resistant to code errors and can design a higher-performance codebook.

[0011]

In order to achieve the above object, a codebook designing method for a vector quantizer according to the present invention is directed to a vector quantization for designing an optimal codebook for a vector quantizer using learning data. A codebook design method for a device, in which it is assumed that a learning vector is quantized and transmitted on a transmission path having a code error. Update the representative vector based on the minimization of the sum of the average values of the distortions of the learning vector and the reproduction vector on the receiving side under the assumption, and update the representative vector on the receiving side under the assumption. The codebook index is changed so that the evaluation function of the codebook that reflects the average value of the distortion between the reproduction vector and the learning vector is reduced. The above process is used alternately and repeatedly. And gist to design the optimal codebook when a more code error.

Further, in the present invention, in order to obtain a solution that is closer to "optimum", that is, a codebook that is more resistant to code errors, an indexing operation is introduced into the above-mentioned LBG algorithm. The indexing change operation provides a means for the LBG algorithm to get out of the local minimum solution and approach a “true” solution. In other words, the reindexing operation serves to change state dynamically.

It is assumed that, in the LBG algorithm, a codebook having the number of representative vectors (clusters) N _i has already been obtained. If, N _i is if reach several of interest, the process ends. If it has not reached, the division operation of each cluster is performed.

Next, using the representative vector of each of the divided clusters as an initial value, the process of belonging update of each learning data and the process of updating the representative vector are alternately repeated until convergence (Lloyd-Max algorithm). At this time, a scale in which a code error is considered is used as the distortion scale. When the above process converges, the sum of the distortions does not decrease even if the process continues further.

Here, a codebook index change operation is performed. The distortion measure considering the code error is, for example,
It represents the average value of distortion on the receiving side when it is assumed that a transmission path having a code error is transmitted. Therefore, the Lloyd
Even if the sum of the distortions can no longer be reduced by the -Max algorithm, the sum of the distortions can be reduced by an indexing operation, for example, by exchanging any two indexes. As an example, any 2
One index is exchanged, and if the total sum of distortions taking account of the code error becomes smaller, exchange is performed, and if not, another set of indexes is exchanged. This operation is repeated until the sum of the distortions does not become small even when any index set is exchanged. Here, the exchange of the index may be exchanged between two or three or more.

Although it is possible to return to the subsequent cluster dividing operation, the Lloyd-M
Since it is considered to have escaped from the local minimum solution of ax, Lloyd-Max, that is, belonging update processing of each learning data again,
The process of updating the representative vector is repeated alternately until convergence.

Thereafter, the operation returns to the cluster dividing operation. The process of dividing the cluster and the above-described distortion minimizing operation are repeated, and the process ends when a desired number of representative vectors are obtained.

[0018]

According to the codebook designing method of the vector quantizer of the present invention, when it is assumed that a learning vector is quantized and transmitted on a transmission path having a code error, each learning vector is converted into a codebook in consideration of a code error. The representative vector is updated based on the minimization of the sum of the average values of the distortion between the learning vector and the reproduction vector on the receiving side under this assumption. The codebook index is changed so as to reduce the evaluation function of the codebook that reflects the average value of the distortion between the reproduced vector and the learning vector, and the above process is used alternately to optimize the case where there is a code error. Codebook is designed.

The introduction of a distortion measure taking account of errors into the already reported LBG algorithm often results in a local minimum solution, making it impossible to design a codebook sufficiently resistant to code errors. By using, the risk of falling into a local minimum solution can be reduced and a higher performance codebook can be designed.

The index remapping operation can also be applied only once to a codebook having a final target number of representative vectors by the LBG method using a distance scale considering a code error. At first glance, this seems to require less computation. However, in practice, it is very difficult to optimize such an indexing remapping operation. Because the index change operation itself,
This is because it easily falls into the local minimum solution. Therefore,
Even if you spend much more computation time compared to the present invention,
The performance is hardly improved as compared with the codebook created by the LBG method.

On the other hand, in the method according to the present invention, the LBG method and the index changing operation interact with each other, and a slight increase in the amount of calculation can easily lead to a state near the optimum.

[0022]

An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 shows a configuration example of a vector quantization method using a codebook designed according to the present invention. On the transmitting side, the M representative vectors c stored in the codebook 1
The distortion between (r) and the input vector x is calculated by the distortion calculation unit 2, the index r that minimizes the distortion is determined by the distortion determination unit 3, and the encoding unit 4 encodes and transmits. On the other hand, on the receiving side, the decoding unit 5 receives the coded and transmitted index r, decodes it as the index r ′, and sets the corresponding representative vector via the codebook 6 to c.
(R '). Here, if there is no code error in the transmission path, that is, there is no problem if r = r ′, but in the case of a transmission path of poor quality such as wireless communication, one or two bits of the code r are inverted. Is often detected. Therefore, if the codebook is designed such that a large difference does not occur between c (r) and c (r ') even if 1 or 2 bits of r are inverted, deterioration of quality due to code errors is minimized. Can be suppressed.

FIGS. 2 and 3 are flowcharts showing an outline of an example of a method for designing a high-performance codebook in view of the fact that quality degradation is small even if a code error occurs, as described above. Prior to this, data for learning is prepared. The learning data is preferably selected so that the space in which the data to be encoded in the actual encoding is distributed is effectively represented by a finite data sequence. Generally, the number of learning data should be large. If the distribution of the training data is significantly biased compared to the distribution of the data to be actually coded, the performance of the codebook designed according to the present invention will decrease.

Let the prepared learning vector data series be {x _i }, i = 1, 2,..., N. In FIG. 2, M represents a cluster, that is, the number of representative vectors. M is set to _Mo as an initial value (step 110). Normally M _o good is very convenient to set to 1, it does not necessarily have to be in one. Next, the initial value of the representative vector is determined (step 120). _Mo =
In the case of 1, an arbitrary value may be set. Because _Mo
In this case, the initial value of the representative vector has no meaning at all. When M _o ≠ 1, an appropriate initial value must be set. As an example, there is a method of appropriately picking up from learning vectors and setting them as initial values. Next, the loop counter Rep is reset to 0 (step 130). Next, using the representative vector determined in step 120 as an initial value, the representative vector is updated by the Lloyd-Max algorithm using a distortion measure taking error into account (step 140). FIG. 4 shows details of the update operation in step 140. FIG. 5 shows details of the learning data belonging update process (step 310) in FIG. Now, it is assumed that M representative vectors have been determined. These are {c _j }, j = 1, 2,..., M. In the update of belonging of learning data, it is determined which representative vector each of the N pieces of learning data belongs to. In FIG. 5, a distortion measure d (x _i , c _j ) is calculated in consideration of a code error between the i-th learning data and the j-th representative vector (step 440).

The above distortion measure is defined as follows. The probability that the code k is received on the receiving side when the code j is transmitted is represented as p (k | j). As an example of simply calculating p (k | j),
Assuming that the channel is a random binary target channel, the number of code bits is n, the Hamming distance between code k and code j is h, and the random bit error rate of the transmission channel is e, p (k | J) = e ^h (1-e) ^nh . When there is a possibility that an error having a characteristic different from that of a random error such as a burst error may occur, an error probability considering them may be used as p (k | j). Furthermore, when an error correction code is used in combination for encoding for transmission, an error probability when the error correction code is used may be used.When an error detection code is used, an error is detected on the receiving side. The error probability after the restoration processing may be used. Further, even if the error rate is slightly larger than the actual probability, learning can improve the reliability.

When a measure representing the distance between two vectors x _i and c _j is represented by d _v (x _i , c _j ),

[0027]

(Equation 1)

Is defined as This represents when a code error has occurred, the expected value of _{d v (x i, c j} ) at the receiver. The definition of d _v (x _i , c _j ) is arbitrary, but generally a Euclidean distance or a weighted Euclidean distance is used. x _i and c _j are represented by x _i = (x _i1 , x _i2 , x _i3 ,..., x _ip ) c _j = (c _j1 , c _j2 , c _j3 ,..., c _jp ), respectively. , The weighted Euclidean distance is

[0029]

(Equation 2)

## EQU2 ## In the case of Euclidean with no weight, it is sufficient to set w _ir = 1.0. When these distances are used, d
It is known that the calculation of (x _i , d _j ) can be realized at high speed. That is,

[0031]

(Equation 3)

Therefore,

[0033]

(Equation 4)

Accordingly, y _jr and a _jr need only be calculated once when the quantizer is initialized, regardless of the input.

[0035]

(Equation 5)

Thus, the calculation can be simplified. Note that, as a scale for searching the codebook, it is not necessary to calculate x _ir ² in the above equation.

The above d (x _i , c _j ) is calculated from j to 1 to M, and the i-th data for learning is assigned to the representative vector having the smallest d (x _i , c _j ). . I-th
Be (i) = j indicates that the data number belongs to the j-th representative vector.

The above operation is performed for all i, and it is determined which representative vector each learning data is to be assigned to.

Next, returning to FIG. 4, the total sum D of distortion is calculated (step 320). The sum of distortions D is defined as follows.

[0040]

(Equation 6)

Or

[0042]

(Equation 7)

The above two equations are equivalent. Note that the above equation 2
The second Σ represents the sum of i satisfying Be (i) = j. If D obtained by the above equation is smaller than a predetermined threshold value, the process is terminated here. If not, the representative vector becomes optimal for belonging of the learning data updated in step 310. Update as follows.

The expression for updating the representative vector differs depending on the definition expression d _v (x _i , c _j ) of the distance between the vectors. As described above, using the weighted Euclidean distance, the new representative vector c ′ _j = (c ′ _j1 , c ′ _j2 , c ′ _j3 ,..., C ′ _jp )

[0045]

(Equation 8)

Is as follows. Note that this equation is obtained by converting the above equation (* 1) to c.
It is derived by setting the value of partial differentiation with _jr to 0, and D
Indicates the minimum value of c _jr . Using this new representative vector, the process returns to step 310 again, and the process of updating the belonging of the learning data is performed.

When the processing of FIG. 4 converges and ends, the representative vector update processing (step 140) by the Lloyd-Max algorithm in FIG. 2 ends. In the next step 150, the value of the loop counter Rep is checked, and if it is equal to or greater than the predetermined maximum number of loops Rep _- max, the flow proceeds to step 180; Re
p _- max of 1 is usually sufficient. Note that Rep _- max is 0
Is equal to the conventional LBG method.

In step 160, indexing of the codebook is performed. FIG. 6 shows the details of the processing.

In FIG. 6, h represents a loop counter. The initial value of h is set to 0 (step 510). In the codebook evaluation function E calculation process (step 520), an initial evaluation function E for the current codebook is calculated. As the evaluation function E, the above-described sum D of distortions, that is, the expression (* 1) should be used. However, recalculating the sum D of distortion using all learning data every time a certain index is exchanged with a certain index requires a very large amount of calculation. Therefore, as a simple means, the probability p (k
| J) may be defined as follows.

[0050]

(Equation 9)

[0051] _{However, d e (c j, c} k) represents the distance between the representative vector c _j and c _k, as an example

[0052]

(Equation 10)

As described above, the distance may be defined by the Euclidean distance.

Also, considering the frequency at which c _j is used,

[0055]

[Equation 11]

It is also possible to use Here, Pr (j) represents the probability that the j-th representative vector is used. in this way
If the evaluation scale of the Lloyd-Max algorithm is different from the scale of the index change, there is a possibility that the distortion is increased in the other process, while the distortion is decreased in the other. However, as a result of the experiment, even if the evaluation function of the index change is simplified, no adverse effect is observed.

The initial evaluation function value obtained by the above equation is E min
(Step 530). Next, an evaluation function value E is calculated when it is assumed that any two indices j ≠ k are exchanged (steps 540 and 550). j, k
May be determined using random numbers. Also, 1 ≦ j
The evaluation function E may be calculated for all combinations of ≦ M and 1 ≦ k ≦ M, and j and k when E becomes the smallest may be used. If the value E of the evaluation function obtained by exchanging j and k is smaller than Emin, the representative vectors to which the indexes j and k are assigned are exchanged with each other (step 570). At this time, the loop counter h is cleared to 0, and the process returns to step 540 again. Conversely, if E has not become smaller than Emin, 1 is added to the value of the loop counter h (step 580). At this time, if the value of h becomes larger than the predetermined value L,
The process ends assuming that the evaluation function does not become smaller even if any index is exchanged (step 590). If it is smaller than L, the process returns to step 540. Here, the index exchange is performed by using two indexes. However, in order to further avoid the danger of the local minimum solution, the evaluation function may be calculated by exchanging three or more indexes.

After changing the index, the loop counter Rep is incremented by 1 (step 170), and the process returns to step 140 to apply the error measure Lloyd-Max algorithm again to update the representative vector. Step 140
And 160 are alternately performed, even if the local minimum solution is not obtained in step 140 and sufficient performance is not obtained, there is a possibility that the local minimum is escaped by the replacement of the index in step 160. Is expected to approach. If the computational complexity is allowed, Rep
_- the value of max may be two or more.

In step 180, if the number of clusters, that is, the number M of representative vectors does not reach the number of clusters 2 ^B determined by the number of bits B allocated in advance, each cluster is divided by 16-a (step 190). ). The number of clusters is 2 due to division
Double. Assuming that the number of clusters so far is M and the number of clusters after division is M ′, the index from M + 1 to 2M can be newly used by M ′ = 2M division. Here, the initial value of the representative vector is determined in step 210, and the process returns to step 130. In the above example, the cluster is divided and increased twice. However, the number is not necessarily doubled, and some may be divided by the cluster and some may not. Set the initial value M _o of M to one and going to the twofold by resolution of one, at step 180, can be easily terminated as M = 2 ^B, it is convenient.

The initial value of the representative vector is determined as follows.

The initial values of the representative vectors from 1 to M are:
The current representative vector is used as the initial value. Assuming that the new initial value is c _j ′, c ′ _j = c _j , j = 1, 2,..., M. Also, the initial values corresponding to the newly generated index are c ′ _j = c _j + Δ, j = M + 1, M + 2,..., 2M. Δ is a minute vector.

In this way, the number of clusters is increased, M ′ ← M is set, and the process returns to step 130 to repeat the above procedure.

If the number of clusters has reached the target number in step 180, the learning process is terminated, and the representative vector at that time is set as the final representative vector of the codebook.

Note that the initial number of representative vectors is M _o = 2 ^B
In the case of, it is apparent that the processing associated with the cluster division, such as steps 190, 200, and 210, is unnecessary.

FIG. 3 shows a simplified version of the procedure of FIG. FIG.
The difference is that the processes in steps 250 and 260 are performed once each. Naturally, better results are obtained in FIG. 2, but the configuration in FIG. 3 may be used to simplify the calculation. Further, basically, the configuration shown in FIG. 3 may be used, and in step 270, steps 140 and 160 may be performed alternately as shown in FIG. 2 only for the loop immediately before M = 2 ^B.

The learning method of the codebook of the general vector quantizer has been described. However, with the vector quantizer having the simple configuration as described above, the number of bits to be allocated increases, and the amount of calculation and storage for quantization increases exponentially. Even in consideration of this, it is necessary to reduce the number of quantization bits to about 10 to 13 bits or less in order to perform real-time processing and reduce the calculation cost. However, in practice, 20 to 30 bits are often required to obtain good quantization quality. To solve such a problem, a multi-stage vector quantization method is known as a method with a small amount of calculation and with little deterioration in quality. FIG. 7 shows the configuration of the multistage vector quantization method. FIG. 7 illustrates the case of three stages in order to simplify the description. The multi-stage vector quantization method is a method of cascading a plurality of small-scale vector quantizers. Each small-scale vector quantizer is roughly divided into codebooks, vector adders,
It is composed of three parts of the distortion determination unit. In the first stage, the vector adder may be omitted. The operation of the first-stage vector quantizer is the same as that of the ordinary vector quantizer described above. M ₁ representative vectors are stored in the codebook 50, and these are sequentially sent to the distortion determination unit 53. Assuming that the j-th representative vector is c _jr ⁽¹⁾ (r represents the dimension of the vector), the distortion determination unit 53 determines the distortion between c _jr ⁽¹⁾ and the input vector x _ir, and minimizes the distortion. The resulting representative vector is converted to the first-stage quantized value (vector) q _ir ⁽¹⁾
And In the s-th stage after the second stage, the j-th representative vector c _jr ^(s) stored in the s-th codebook is added to the quantized value q _ir ^{(s-1) up} to the s-th stage. The _j′ ^- th representative vector c _{j ′ r} ^(s) that minimizes the distortion between q _ir ^(s−1) + c _jr ^(s) and the input vector x _ir is set as the s-th stage representative vector, and q _{ir ^{(s) = q ir (s}} -1) + c j'r ^{(s) is} the quantization value to s-th stage.

The distortion scale at this time may be any scale such as the Euclidean distance. If a distortion measure taking into account a code error such as the expression (* 2) described later is used, a quantizer with little deterioration even if a code error occurs can be obtained.

This operation is repeated by the number of stages, and when the quantized value up to the final stage is determined, the quantized value x _ir ^* of the input vector x _ir is output from the terminal 58. In the above description, the representative vector (quantized value up to each stage) is determined to be one optimal one in each stage. However, in the middle stage, some quantization candidates are left, and the quantization vector up to the final stage is determined. If the quantization value is determined to be optimal, the calculation performance is better, though the calculation amount is slightly increased. For details of the multi-stage vector quantization method, refer to the literature: BHJuan
g, AHGray, “Multiple Stage Vector Quantization f
or Speech Coding ”Proc.ICASSP82, p.p597-600 (1982)
It is described in.

The present invention can be easily applied to the design of the codebook of such a multi-stage vector quantizer only by changing the distortion scale. That is, the codebook design of the multistage vector quantizer is designed in order from the first stage.
Since the first stage is substantially equivalent to a normal vector quantizer, the present invention can be used as it is. Also for the second and subsequent stages, the distortion scale calculation process in FIG.
40), the equation for defining the distortion, the updating equation for the representative vector updating process (step 340) in FIG. 4, and FIG.
Codebook evaluation function E calculation processing steps 520 and 5 in
It is only necessary to change the definition formula of 50 and apply the present invention to the codebook design of each stage.

First, the definition of the distortion scale is, as described above,
When the distance between the input vector x _ir and the quantized value (vector) q _ijr ^(s) = q _ir ^(s-1) + c _jr ^(s) is represented by a weighted Euclidean distance,

[0071]

(Equation 12)

Is obtained. In this case, x _ir and q _ijr ^(s)
May be converted to a cepstrum, and then the Euclidean distance may be taken. The distance between the vectors is represented by the above d _v (x _i ,
q _ij ^{(s )} ), the distortion measure taking the code error into account is:

[0073]

(Equation 13)

The above d (x _i , q _ij ^(s) ) is calculated from j is 1 to M (M is the number of representative vectors), and
The ith data for learning is assigned to the j'th representative vector in which (x _i , q _ij ^(s) ) is reduced. Here, the quantization value (vector) q _ir ^(s-1) up to the previous stage is

[0075]

[Equation 14]

As shown in the above, it may be represented by the sum of the representative vectors of each stage,

[0077]

(Equation 15)

Then,

[0079]

(Equation 16)

That is, it may be represented by an average value (expected value) at the time of reception. Generally, the latter has better performance. Further, the expression of d (x _i , q _ij ^(s) ) is expanded,

[0081]

[Equation 17]

By calculating in advance, the processing can be sped up at the time of actual quantization.

The sum of the distortions is, as described above,

[0084]

(Equation 18)

Or

[0086]

[Equation 19]

## EQU10 ## Here, Be (i) = j indicates that the ith learning data vector belongs to the representative vector j at the s-th stage. N is the number of learning data.

The updating of the representative vector is performed by the following equation.

[0089]

(Equation 20)

The difference from the design of the codebook of the ordinary vector quantizer is that the quantized value q _ir ^(s−1) from x _ir to the previous stage is used.
Is the average. It should be noted that in the case of normal vector quantization and in the case of multi-stage vector quantization, 1
Even in the case of the first-stage quantization, if the quantization value up to the immediately preceding stage is considered to be 0, it can be considered as a special case of multi-stage vector quantization.

The definition equation of the codebook evaluation function E calculation processing (steps 520 and 550) in FIG. 6 is desirably expressed by the sum of distortions D, that is, equation (* 3), as described above. But for simplicity

[0092]

(Equation 21)

[0093] Alternatively, considering the frequency at which c _j ^(s) is used,

[0094]

(Equation 22)

[0095] Alternatively, Where Pr (j) is j
The probability that the th representative vector is used is denoted by d _c (c _j
^(s) , c _k ^(s) ) represents the distance between the representative vectors c _j ^(s) and c _k ^(s) , and may be defined as a Euclidean distance as an example.

With the above modifications, the present invention can be used for codebook design of a multistage vector quantizer.

As described above, in actual communication, transmission is often performed with some error correction code. However, it is often not possible to add a sufficient error correction code due to restrictions on the bit rate of the communication channel. In such a case, the method of the present invention is effective. It is possible to take measures against code errors in all stages by using only the present invention without using an error correction code. However, a method in which an error correction code is partially used and combined with the present invention is also effective. In the case of multi-stage vector quantization, the first stage has the property that the deterioration of the quality with respect to the code error is the largest, and the sensitivity to the code error decreases in the order of the second stage, the third stage, and so on. Therefore, when the error correction code cannot be sufficiently added, the first stage is strongly protected by the error correction code, and the second and subsequent stages are more protected than the error correction code.
In the present invention, by designating a codebook that is resistant to code errors by appropriately setting the code error rate, it is possible to configure an encoder that causes less quality deterioration in a place where there is no error, and has less quality deterioration even if an error occurs. Can be. For example, according to the present invention, the first stage learns the codebook with a bit error rate of zero or a sufficiently small value, and the second and subsequent stages are about the bit error rate of the transmission path or the first and subsequent stages. Design the codebook by setting the lower stage to be slightly higher than the actual bit error rate and the latter stage to be the actual error rate or slightly lower, and in the actual encoding situation, Efficiency is good if only the first-stage code is transmitted with an error correction code.

Some error correction codes have a slightly lower error correction capability but a higher error detection capability. This means that it is not possible to detect which bit is inverted in a plurality of received bit sets, but it is possible to detect that any bit is inverted. In this way, even if the error cannot be corrected, if the error is found, the receiving side can stop using the code and take an appropriate action. For example, in the case of an audio signal and the like, since the time axis has a strong correlation with data before and after,
In many cases, deterioration can be suppressed to a smaller extent by estimating a signal at the time of detecting an error from a received signal (code) having no error before and after, using a received incorrect code. For example, a method is often used in which the data of one frame (transmission unit) before is repeatedly used as it is, or a reproduction vector at the time is obtained by linearly interpolating the preceding and succeeding reproduction vectors. As described above, when designing a codebook using the present invention, the error rate of the transmission path, the error correction code, and the restoration method when using the error detection code may be taken into consideration.

The present invention may be applied to, for example, speech coding. One of the speech coding schemes in which the method of the present invention is effective is the CELP scheme. In this method, the input speech signal is subjected to linear prediction analysis, and the resulting linear prediction coefficient is converted into a parameter called, for example, a line spectrum pair (LSP). LSPs are often used because of their excellent quantization characteristics.
There is also a method of converting into a parameter called an ARCOR coefficient. Here, these parameters are collectively referred to as linear prediction parameters. In the CELP method, first, this linear prediction parameter is quantized. Next, the excitation signal is determined so that the distortion between the input signal and the signal obtained by driving the linear filter obtained from the linear prediction parameters with the excitation signal is minimized. Since both the quantization of the linear prediction parameter and the quantization of the excitation signal usually use vector quantization, the method of the present invention provides excellent results.

An example of a method of applying the present invention to quantization of a linear prediction parameter will be described. First, a linear prediction coefficient obtained by performing a linear prediction analysis on an input speech signal is converted into a line spectrum pair (LSP). Assuming that the order of the linear prediction analysis is p, the LSP is obtained as a p-order vector, and this vector is quantized so that it can be represented by a certain code.
Note that LSP is a parameter representing the envelope characteristic of the audio spectrum. The method of calculating the LSP from the audio signal is described in, for example, the document “Digital Audio Processing” by Sadahiro Yoshii (Tokai University Press).

Here, as an example, the order of the linear prediction analysis order is 10 and the time period (frame period) for calculating the LSP is preferably about 20 ms. Normally, the order of analysis is set to the 10th to 16th order, and the frame period is set to about 10 to 40 ms. As data for learning, it is good to prepare as much data as the calculation time permits, but it is sufficient if there are approximately 1500 seconds of different utterances of a plurality of speakers. In order to maintain sufficient quality when LSP is vector-quantized, 20 to 30 bits are required for one vector. Therefore, realization with a single-stage vector quantizer requires only a small amount of calculation and storage. Not realistic from a point of view. Therefore, as an example, three-stage multi-stage vector quantization is used, and for example, the first stage has 8 bits, the second stage has 8 bits, and the third stage has 6 bits.
Bit. The required number of bits per vector differs depending on the quantization method of the driving sound source.
Sufficient quality can be obtained with 22 bits.

LBG learning considering a code error, and
The setting of the error rate of the distance scale at the time of actual quantization varies depending on the application.
It may be set to about 3.0%. However, if the code error rate is set to a high value, the quality at the place where there is no code error is degraded, so if it is desired to emphasize the quality when there is no code error, the error rate may be set lower than the above value,
If importance is placed on the prevention of deterioration when a code error occurs, the value may be set slightly higher than the above value. Since the first stage has relatively high sensitivity to code errors, it is efficient to use an error correction code or an error detection code only in the first stage. In this case, the setting of the error rate at the time of learning / quantization in the first stage may be set to a sufficiently low value or may be set to 0, and in the second and subsequent stages, the error rate according to the transmission path is set.
When only the occurrence of an error is detected on the receiving side using the error detection code, the reproduction of the vector from the received code is stopped, and the vector at the time when the error is detected is estimated from the previous and subsequent time vectors. Good to do. The Euclidean distance, the weighted Euclidean distance, the cepstrum distortion, or the like may be used as the distortion measure between the vectors.

In order to investigate the effect of the method of designing a codebook for a vector quantizer according to the present invention, an experiment under the following conditions was performed by computer simulation.

In this experiment, a memoryless Gaussian information source is vector-quantized and its performance is compared with that of the conventional method. The vector dimension was eight dimensions, the number of quantization bits was eight bits, and the vector quantizer was configured in one stage. The Euclidean distance was used as the distance measure between vectors. The training data uses 10,000 vectors, and the test uses 5,000 vectors outside of learning.
Evaluation was made based on the overall SN ratio. The code error rate during learning and quantization was set to 1.0%, and in the test, the change in the SN ratio was examined by changing the channel error rate from 0.0 to 10%. In addition to the method of the present invention, the LBG method that does not consider the code error rate at all, the LBG method that uses a measure that considers the code error as the distortion measure (set to 1.0% error rate), Further, after the LBG method considering the above error is completed, a method of applying index remapping to the completed codebook was examined. Fig. 7 shows the results.
Shown in When no code error is taken into account, the signal is rapidly degraded together with the code error, as indicated by a triangle and a broken line. On the other hand, in the method according to the present invention, although the quality is slightly degraded where there is no code error, even if a code error occurs, the degradation is suppressed to a small extent. In addition, the LBG method of the error scale shown by the solid circle and the solid line also maintains a sufficiently good quality, but the present invention shows better results. In addition, the method of re-indexing after completion of the LBG method (square mark and dashed line) has little improvement compared to the error scale LBG.

As described above, it has been shown that the present invention is a very excellent method for designing a vector quantizer when there is a code error. In this experiment, the performance was compared using a memoryless Gaussian information source. However, in the case of a signal having a strong correlation such as an actual audio signal or image signal, a larger effect is expected.

[0106]

As described above, according to the present invention,
The risk of falling into a local minimum solution can be reduced, a higher-performance codebook can be designed, and a near-optimal state can be easily achieved by a slight increase in the amount of computation.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of configuring a vector quantizer using a codebook designed according to the present invention.

FIG. 2 is a flowchart schematically showing the flow of a codebook learning method according to the present invention.

FIG. 3 is a flowchart schematically showing the flow of a codebook learning method according to the present invention.

FIG. 4 is a flowchart showing a detailed process of step 140 which is a process of updating a representative vector by the Lloyd-Max algorithm in the process of FIG. 3;

FIG. 5 is a flowchart illustrating a detailed process of step 310, which is a process of updating belonging of learning data in the process of FIG. 4;

FIG. 6 is a flowchart showing a detailed process of step 160, which is the codebook index change process shown in FIG.

FIG. 7 is a block diagram illustrating a configuration example of multi-stage vector quantization.

FIG. 8 is a diagram showing a result of an experiment of a code error performed by computer simulation in order to examine an effect of the present invention.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Codebook 2 Distortion calculation part 3 Distortion determination part 4 Encoding part 5 Decoding part 6 Codebook

──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Kazunori Mano 1-6-1, Uchisaiwaicho, Chiyoda-ku, Tokyo Nippon Telegraph and Telephone Corporation (72) Inventor Hiroto Suda 1-1-6, Uchisaiwaicho, Chiyoda-ku, Tokyo Examiner, Nippon Telegraph and Telephone Corporation Kenichi Ishii (56) References JP-A-62-188575 (JP, A) JP-A-1-205638 (JP, A) JP-A 1-223229 (JP, A) JP Hei 1-259626 (JP, A) IEICE Technical Report, IEICE Technical Report Vol. 84, No. 60, pp17-23, CS84-32, "A Study on Allocation of Transmission Codes for Vector Quantization to Reduce Channel Distortion" Aizawa et al. (58) Fields investigated (Int. Cl. ⁷ , DB name) H03M 7/30

Claims (3)

(57) [Claims] 1. A codebook design method for a vector quantizer for designing an optimal codebook for a vector quantizer using learning data, wherein a learning vector is quantized and transmitted on a transmission path having a code error. In the case where it is assumed that the learning vector is attributed to each representative vector in the codebook in consideration of the code error, the distortion between the learning vector and the reproduction vector on the receiving side under the assumption is updated. The representative vector is updated based on the minimization of the sum of the average values, and the code is set so as to reduce the evaluation function of the codebook reflecting the average value of the distortion between the reproduction vector and the learning vector on the receiving side under the above assumption. Change the book index,
A codebook designing method for a vector quantizer, characterized by designing an optimal codebook in the case of a code error by repeatedly using the above processing. 2. A process of determining an initial number of representative vectors and an initial value of a representative vector, and repeatedly and alternately using a process of updating the belonging of the learning vector and a process of updating the representative vector; A desired number of representative vectors is determined by repeating a process of performing index replacement using a process of performing index replacement and a process of increasing the number of representative vectors. 2. The codebook design method for a vector quantizer according to 1. 3. A process of updating the belonging of the learning vector, a process of using the process of updating the representative vector alternately and repeatedly, and a process of replacing the index using the process of replacing the codebook index. 3. A process for increasing the number of representative vectors after repeating the above two processes alternately.
A codebook design method for the vector quantizer described.