JPH01205638A - Method for quantizing multiple vectors and its device - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a method of encoding signal sequences such as audio and images with a small amount of information, and is particularly effective in multiplexing when errors occur in transmitted codes. The present invention relates to a vector quantization method and apparatus.

[Conventional technology]

Vector quantization is known as a powerful method for compressing and encoding information in a signal sequence.

This is done by grouping a predetermined number of discretized signal sample values to be encoded into vectors, comparing each vector with a representative vector in a codebook created in advance, and finding the most distorted signal sample value. The number of the representative vector that becomes smaller is used as the output code.

FIG. 1 shows a schematic configuration thereof, in which 21 and 23 are codebooks, 22 is an encoder, and 24 is a decoder. Each symbol has the following meaning.

U: Input vector u(i): i-th element of input vector U i=0.1.・
..., ni-1 ni: Number of vector dimensions r: Code transmission rate [bits/sample] b: Quantized transmission code (kr bits) Z: Code length zl: First representative vector z of codebook Z (i
ll: Representative vector 2. i-th element M: number of representative vectors Zj of codebook Z (M=2") 1=0.1...1M-1 do = quantization distortion codebook 21.23 each has M=2" It has representative vectors z, (j!-0, 1, . . . =, M l). On the transmitting side, for each input vector U, the encoder 22 refers to the codebook 21 and calculates M-2''a (([expressed as the square of the distance between each of the vectors Zj and the input vector U). Calculate all the distortions d, select the representative vector with the minimum distortion d, and set the number 2 of the representative vector to kr
It is sent as a bit-length transmission code. The strain d, is the following formula (
Calculate using 1).

dj=l u−z 1 1” On the receiving side, based on the received transmission code b (representative vector number), the decoder 24 refers to the codebook 23 and selects the representative vector corresponding to the transmission code b. and output it.

[Invention or problem to be solved]

With this quantization method, if an error occurs in the transmission path, there is no distance relationship between the representative vector number and the value of that representative vector, so a vector that is completely different from the input vector will be reproduced. There are essential flaws.

In order to prevent this, conventionally it has been necessary to keep the error rate low by using an error correction code, that is, by providing redundancy to the transmission code. In this case, by using, for example, 50% of the information bits as redundant bits, it is possible to substantially reduce the bit error rate. However, even if there are no code errors, the same amount of redundant bits is still required. That is, when the total amount of information to be transmitted is the same, even when no error occurs, only ⅔ of the information is allocated to the information focus, resulting in large quantization distortion. In practice, the code error rate fluctuates over time, and it is difficult to change the form of the transmission code to suit the situation, so the performance will be greatly sacrificed when there are no errors or when there are many errors. There was a need. Therefore, error correction codes have not always been effective for reducing distortion with a constant amount of information. Also,
For distance calculation (calculation of quantization distortion d) in vector quantization of the conventional encoder 22 shown in FIG.
representative vectors 2. It is necessary to have a codebook 21 with a memory capacity to store , and also to calculate the distortion d for each of the M pieces. The problem was that it increased with an exponential function.

[Means and effects for solving the problem] An object of the present invention is to prevent large distortions from being caused in the decoded signal even if a code error occurs when compressing and encoding information on signal sequences such as audio and images. It is an object of the present invention to provide a vector quantization method and device that does not cause the above problem and requires less calculation amount and/or storage capacity for encoding.

According to the present invention, in a coding method in which an input signal sequence is combined into one vector for each plurality of samples and quantization is performed using each vector as a unit, codebooks of plural systems are provided, and each input vector is Then, one representative vector is obtained from the codebook of each system so that the distortion between the input vector and the average vector of the representative vectors of each codebook is minimized, and the numbers of each of the obtained representative vectors are multiplexed. Output.

In this way, by performing vector quantization using multiple codebooks and dividing the transmission code into multiple parts, the quantization distortion becomes slightly larger when there are no code errors compared to conventional vector quantization. , when a code error occurs, the increase in distortion due to it can be suppressed to a small level.

〔Example〕

FIG. 2 shows a vector quantization device 1 (1
0 is used in the transmission system, 11 and 12 and I5 and 16 are codebooks, respectively.
13 is an encoder, 14 is a multiplexer, 17 is a decoder, and 18 is an output vectorizer. That is, this embodiment shows a case where two systems of codebooks are provided. Here, codebook 11.
15 is the X system, and codebook 12.16 is the Y system. The symbols used in the following explanation are defined as follows.

U: To the input vector: Number of dimensions of the vector, that is, the number of samples that make up the input vector r: Transmission rate (bits/sample) b = Quantized transmission code (kr bits) X, Y: Codebook x (i, j) : Representative output vector χj from codebook X
i-th element y(i, m) 'representative output vector ym from codebook Y
i-th element u(i): i-th element of input vector U, i.e., i-th sample value N: number of representative vectors of each codebook X, Y (= 1/2 i: o, 1... , ni-1, l: 0, 1,..., N-L m: Q, 1,..., N-1 In the case of this embodiment, each codebook 11.12 has 2 kr/Z representative vectors. The codebook on the receiving side is 15.1.
6 each have 2kP/1 representative vector. Codebooks 11, 12, 15, and 16 of each system are created by determining representative output points through learning using learning samples that are statistically the same as the input to be quantized.

The method will be explained later. Alternatively, a vector extracted from a learning sample is used as a representative output vector.

In the vector quantization device on the transmitting side, for one input vector U, the encoder 13 refers to two code length ratios of 12, and adds -r bits of 172 to the information 31 assigned to the quantized transmission code. In other words, the number of bits of each system's quantization code (a, b) is expressed as -r/2. The multiplexer 14 multiplexes the quantization codes of each system, i.e., k-r.
Vector quantization code b=bXb expressed in bits.

and transmits it to the receiving side 2 (10). On the receiving side 2 (10), the decoder 17 decodes the code 9b,
, b, respectively with reference to the codebook 15°16,
Obtain the output vectors x and y of each system. Vector combiner 1
8, find the arithmetic mean of the output vectors x and y of each system,
Let it be the final output vector.

FIG. 3 shows a specific configuration example of the vector quantization device 1 (10) of the present invention. Each column of the codebook 11 of the
). Similarly, each column of the Y system codebook 12 also includes a representative vector ym and its vector number m (quantization code by).
Consisting of

As shown in FIG. 2, the number of representative output vectors xj, y+m of codebook 11.12 of each system is 21+r/! Therefore, the vector numbers j and m (quantization codes for one system, b,) have a kr/2 bit structure.For convenience, in FIG. It shows.

The encoder 13 can be functionally divided into an average vector calculation section 131, a square distance calculation section 132, and a minimum distance determination section 133.

The average vector calculation unit 131 sequentially calculates the average vector vj, for all combinations of each representative vector xj of the codebook 11 of the X system and each representative vector ym of the codebook 12 of the Y system.

Find vJ++a-(xj+ym)/2 (2). The square distance calculation unit 132 calculates the distortion d between the input vector U and the average vector Wj, represented by the square distance.
j+s dj++* = l u−y Jllm l ”=
l u-(x j + y m ) / 2 l
” (Find 31 for all combinations of (Jllm).j.

Since there are N values for each m, there are a total of N2 dj,,
will be calculated. In FIG. 1, M−N! It is clear that

The minimum distance determining unit 133 determines the representative pect 1Ltx of each system.
j, VN, and the input vector U and average vector vJ corresponding to the combination.

Distortion d41. are input sequentially, and the representative output vector of the combination in which the flux dj, s takes the minimum value is ``J + V 11
Determine. Then, this determined representative output vector x
The codebook 11゜12 of each system is referred to based on j, ym, and the vector number J, m-1 - quantization code b yo +
Output as bV.

Vector numbers j, m (quantization code) of each system.

by) is multiplexed by the multiplexer 14, and the original vector quantization code for the input vector U is obtained. In Figure 3, each vector number (quantization code) of the X and Y systems
b,=1111. “1111 for b, = ooo t
(1001'' indicates time multiplexing. Instead of time multiplexing, frequency multiplexing or other diversity techniques may be used.

As is clear from the above description, in the vector quantization device using the two codebooks of the present invention shown in FIG. Vectors xj and ym are selected, and jlm is determined such that their average, (x j +y+a)/2, and distortion d of the input vector are minimized, so the selected representative vectors xj and y- are close to each other. has a very high probability of being selected, so these quantization codes, =
When L b, x (il) is multiplexed (combined) and transmitted as a vector quantization code b = Jm, the first half (j) or the second half (m) of the code received on the receiving side in Fig. 2
Even if either one of them contains a 1-bit error, if the other is correct, one of these decoded vectors It does not become far different from the input vector U, that is, the distortion of the decoded vector due to transmission errors becomes smaller accordingly. Furthermore, in the embodiment of the present invention explained in FIGS. 2 and 3, two codebooks are used to store N = 21r/i representative vectors, so if there is a memory that can store a total of 2N representative vectors, good.

In contrast, the prior art vector quantization shown in FIG. 1 requires a memory to store M=21''-N2 representative vectors.

The calculation of the squared distance d 11j shown in equation (3) can be expressed in more detail as shown in equation (4) below. However, in order to make the equations easier to read, all explanations below are based on x/2. Replace y/2 with x and y, respectively.

FIG. 4 shows the configuration of the average vector calculation section 131 and the squared distance calculation section 132 in FIG. 3 when calculating the distortion d j+a based on 2(4), together with the codebook 11.12. X codebook 11 and Y codebook 1 for input vector U
The representative vectors xj, ym are read out one by one from 2, and the corresponding first elements of these vectors u(i), x(
i, j), y(i, m) by the adder 31 to u(i
) x(i, J) y(i, Sho), and the summed output is squared by a square accumulator 32 and cumulatively added. A total of three operations such as two additions (subtractions) and one square cumulative addition are performed on vector elements i-〇 to i=-1, and as a result, the selected representative vector xj
Distortion d59 for the pair of and ym. is obtained. There are N2 combinations of representative vectors xj and ym, and by finding the distortion dj+6 for all of them, the minimum (
7) To determine le (j, m) given d, , 3
kN'' times of calculations, which is equivalent to the amount of calculations required by the conventional vector quantization device shown in FIG. (from i= to −1 is executed N2 times).In other words, in the embodiment of the present invention shown in FIG.
Although the total memory capacity required for this is significantly smaller than that of FIG. 1, it has the drawback of increasing the amount of computation required. An embodiment that improves this point will be described next with reference to FIG.

When formula (4) is expanded, it becomes the following formula (5).

The first term of the expanded equation (5) is the selection of the representative vector (j,
n+). Therefore, to determine the vector code combination (Jllll) that minimizes distortion d4,1, u”
There is no need to calculate (i). Therefore, instead of formula (5), the combination of codes (j, m) that minimizes d'j+l) defined by the following formula (7) may be determined.

+F(j, m) (7) In equation (7), the second term P (j, m) is unrelated to the input vector U as defined in equation (6), and the codebook
It can be calculated only from representative vectors xj and ym selected from Y. Therefore, all (j, m) combinations (N
F (j, m
) is stored in memory, and d′1. When calculating yo, the corresponding F(j.

11) can be read and used to reduce the amount of calculation in equation (7).

FIG. 5 shows the average vector calculation unit 1 in the embodiment shown in FIG.
31. The square distance calculation unit 132 and the codebook 11°12 are calculated using the formula (
7) This is an example of a basic configuration. As mentioned above, the expression (
6), all combinations (j.

A table memory 33 is provided that stores the value of F (J + a+) calculated for m). Equation (the first term of force is the inner product of vectors U and xj and vectors U and ymO
This is the sum with the inner product, and is calculated by inner product calculators 34 and 35, respectively. The inner product calculation results are each given to the adder 35 as a scalar value, and the corresponding F(j) is read out from the table memory 33.

m). The output of the adder 36 is d'j1. according to equation (7). This is the calculation result. In the embodiment shown in FIG. 5, the calculation of the inner product by the inner product calculator 34.35 is 2
kN times, and the scalar addition/subtraction by the adder 36 is 2N'' times.The storage capacity of the required storage device is 1 codebook 12 times.
2kN and Nz of table memo IJ33.

Table 1 shows the storage capacity and calculation amount required for the vector quantization device according to the prior art shown in FIG. 1 and the embodiments shown in FIGS. 4 and 5 according to the present invention, respectively. N=16
It is calculated and shown as follows.

Table ■ = 16. In the above explanation, quantization distortion d□ or d ′j+
An example is shown in which the squared distance is used to represent fi. These can be applied when converting spectral envelope parameters into LSP parameters or logarithmic cross section functions and vector quantizing them in speech encoding. However, in order to quantize the audio waveform signal or the prediction residual signal with high efficiency, it is necessary to perform adaptive weighted distance calculation in the frequency domain. In that case, the distance scale is expressed as follows:
・・・・・・(8) j = 0・N−1, m=o・N−1 where −(i)
represents the first element of vector weight W, and u(i)
It changes every time d changes, but while finding the minimum value of d, u(i)
It is fixed with. Note that if w(i) is fixed regardless of u(i), it can easily be reduced to the case of a squared distance.

Expanding equation (8), omitting the first term that does not contribute to determining the minimum distortion, and leaving only the second and third terms as d'', J-0,1s・, N-1 , m=o, L, ., N
−IP(i+j+s)−(x(i,j)+y(i,s)
) ” −(Formula 10〇〇(7)F(i, j, m)
In order to calculate and store all the elements in advance, a memory with kN'' elements is required, unlike the case of equation (6).Furthermore, in order to calculate and store all the elements of
) kN'' dot product operations are required to calculate the second term of ).

In order to calculate the first term of equation (9), 5(i) defined by the following equation 21 is set in advance by 1 for i=0.1..., k
Calculate only times.

5(1) = −2w(i)u(i)
02) Furthermore, for 5(i), the inner product of N elements is 2
G and H defined by the following equations 03) and 04) are obtained.

As a result of this preparation, d''j+lI in equation (9) can be found by the following scalar operation.

d”j+s =G(j)+[!(m)+E(j,m)
FIG. 6 shows a configuration for performing the above calculation in the embodiment of FIG. 3. The table memory 33 stores kN2 F(i, j,, m) given by Om.
The value of is roughly calculated and written. The weight vector W is input together with the input vector U to the vector quantization device, and the corresponding first elements of these vectors are calculated by the multiplier 37 as shown in 202).

The weighted input vector 5(i) (i=
0. 1. . . k-1) are given to inner product calculators 34 and 35, respectively, and are separated from representative vectors xj and ym read from codebook 11 and 12, respectively.

The inner product shown in (b) is taken. On the other hand, the weight vector W is (
j, m) read from the table memory 33 corresponding to vector F(1+J+■)(i=0.1...k
-1) and the inner product calculator 38 calculates the inner product represented by equation θ0. The inner product calculation results from the inner product calculators 34, 35, and 38 are fed to the adder 36, where two scalar additions are performed, and the value d''j+s corresponding to the distortion when the input vector shell is encoded into jlm is can get.

Table 1 shows the arithmetic units and storage capacity required for the embodiment shown in Figure 6.
For comparison, formula (1) corresponding to Figure 1 is included in Table 0 shown in Figure 1.
The calculation amount and memory capacity required for the vector quantization operation when the weight W is added to the equation (4) corresponding to FIG. Since it can be easily obtained in the same way as , its explanation will be omitted.

k=16. In the case of weighted distance, N = 16, compared to ■, the calculation amount or storage capacity increases for ■ and ■, respectively, but ■
By combining and ■, both the amount of calculation and storage capacity can be reduced compared to the case of ■. That is, F(i+j+
It is sufficient to have only a part of m) as a table. If the proportion of tables is λ (0 × λ<1), the amount of calculation is 2N
``+2kN+(3-2,,t)kN'', and the storage capacity becomes t2kN+λkN''.By appropriately selecting λ, the amount of computation and storage capacity can be mutually accommodated to satisfy the given design conditions. It is possible to meet each other.

It is also possible to further expand F(i+j+m) in equation (10) and have each term in a separate table. In this case, the amount of calculations and storage capacity will increase compared to case (2) if left as is, but by omitting part or all of the calculation of the product term of x (i, j) · y (i, m), d It is possible to perform an approximate calculation of ``j++a.'' At this time, although it is not necessarily possible to select the code that minimizes distortion, the amount of calculation and storage capacity can be significantly reduced.

It can also be easily applied to the case where the distance measure includes a free parameter τ that is a constant times the vector of the codebook, as in equation 07).

j = O, -N -1, m = 0...-N
When quantizing the residual signal of -1 speech in the time domain, the distortion scale shown in the following equation is conventionally often used. This distortion d.

The calculation is performed using one codebook Z f=0.1. ...1M-1 is used. When this distortion measure is applied to the vector quantization method of the present invention, the distortion dj,s can be expressed as follows.

However, h (i, g) is the matrix H that performs the convolution product
i line of

represents the element of column g, and τ is the strain d13. This is a parameter determined so that .

Distortion d11 in equations (3), (4) and (5). The definition of % reflects the performance when there are no code errors. In order to further strengthen against code errors, it is also effective to define distortion as in the following equation θ'I).

dj+m=771 u-N/J+lI+”
+(1+μ)(I u−x j M+l u−y
m l” l/4 −07) Here, μ is a parameter from O to 1, and if μ is 1, it is equivalent to the distortion in equation (3), and if μ is decreased, the redundancy of each codebook increases, and 2 If only one of the systems has no errors, distortion can be reduced.In other words, it becomes resistant to code errors.

Furthermore, when considering transmission line code errors, xj and y of U
The following equation can be considered as a definition of distortion for -.

/21” q (f N) q (glm) here q
(f l J) indicates the probability that vector number j will be mistaken for f on the transmission path. The same applies to q(m1g).

Although these distortion measures are based on square distance, they can easily be applied to the weighted square distance described above or other measures. Furthermore, since this assumes that information is divided equally among multiple systems, the final output vector is determined by an arithmetic average, but if the distribution of information differs for each system, it is determined by a weighted average. For example, when using square distance for two systems, the transmission rate of each system is r(x), r(y), and vj+li = (XJ・2mu(X)+y,・
2 facing) / (2!r (*) + 22r ly
l ), which means that the expected value of the distortion of χ is 2−z
This is based on the fact that it can be approximated to the r-axis +.

The procedure for creating the two codebooks 11 and 12 used in the embodiment of the invention shown in FIGS. 2 to 6 will now be described with reference to the flowchart in FIG. 7. Although this flowchart is an example of alternatingly modifying two codebooks to locally minimize distortion, it can easily be applied to the creation of two or more codebooks.

In step S7, a large number of vectors consisting of consecutive samples extracted at arbitrary positions from the learning sample series are prepared, and these are arbitrarily divided into two of the same number, and each is used as an initial representative vector to create an initial codebook. X, Y
make. Or, using learning samples, group of vectors created by normal vector quantization learning is added to the codebook
The codebook Y may be a group of vectors created using the error sequence as a learning sample.

Next, in step S, using a sufficiently larger number of learning vectors than the number of representative vectors as input vectors U, for each input vector, for example, the distortion d according to equation (3) is calculated for all representative vector sets xj, y-. , x j , y m of the representative vector with the smallest distortion d is determined. That is, each input vector is quantized by the quantization method of the present invention, and it is determined to which set of representative vectors xJ, ym each input vector U belongs.

In step S2, the sum of the minimum distortions d for each input vector calculated in step St is calculated, and the value is the threshold (
If it is less than 5 or the improvement rate of L is less than the dark value, codebook X,
It is determined that Y is composed of the desired representative vectors, and codebook learning is stopped. If not, the process proceeds to the next step S, and first, the content ym of the codebook Y is improved while the content χj of the codebook X is fixed.

That is, in step 5S-t, &1l(xj,
y−), the representative vector yIl is regarded as a variable vector, and the equation obtained by partially differentiating the sum of distortions of all input vectors U including the variable vector y11 in the set of belonging vectors with respect to the variable vector yI11 is denoted as O, and 0 representative vector y whose new representative vector ym is the vector value y obtained by solving the equation for the variable vector quantity ym.

All two input vectors (
P is variable) u@In u+st+ ...1'
@JL @p and the set of vectors to which they belong is (Xt++ym), (xfmax, 3' am)+
(X f3+ 3' J+...(x,,,y
, ), then ylI is given as their center of gravity by the following equation. However, fe takes any value from 0 to N-1.

p 11-1 Next, using the codebook X fixed in step 5S-t and the codebook Y updated, for each input vector U, the assignment to Determine the attribution to Y while keeping it fixed, and proceed to step 3-
In step 3, the codebook Y is updated in the same manner as in step S, -1.

In step S4, the set of representative vectors (xj,
ys).

Step S4 is equivalent to step S1.

In step SS, the contents of codebook X are improved while the contents of codebook Y are fixed. That is, the set of representative vectors (xj, y
In step 5li-1, the representative vector x
Regarding j as a variable vector, the equation obtained by partially differentiating the sum of distortions of all input vectors U that includes the variable vector χj in the string of belonging vectors with respect to the variable vector xj is set to 0, and the equation is solved for the variable vector xj. LIJI all nine input vectors (Q is variable) whose membership vector set includes the 0 representative vector xj with the value xj as the new representative vector xJ.

uJffi...uj, and the set of vectors to which they belong is expressed as ()(j+ y**), ()(J+
3'*g)..., (X j , )' so), xj is their center of gravity and is given by the following equation.

However, g'e takes any value from O to N-1.

Next, in step 5S-Z, using the updated codebook In 5S-3, the codebook X is updated again in the same manner as in step S-1.

Returning to step St, repeat the calculations similar to steps 5t-5s below, and in step S2, if the total distortion is less than the dark value or the improvement rate of D is less than the dark value, the codebook
, Y ends.

In the above steps 5x-t + 5s-i and 5
S-Z.

5S-S may be omitted. Also steps 5s-z, 5
ff-i and ss-! , 5s-3 may be repeated alternately.

Figure 8 shows how the distortion decreases due to codebook learning.
This is shown in . In the flowchart of FIG. 7, the step symbols are ・,mu,◆.

Δ5◇ is S+, 33-1, 5x-z, Ss-
+, corresponds to 5s-t. Step 33-1 +
Even if the set of steps 33-2 and the set of steps 5S-1+5S-2 are repeated several times, the distortion continues to decrease.

Figures 9A and 9B compare the range of damage caused when there is a transmission code error.
In the case of system quantization, FIG. 9B shows the case of two systems quantization according to the present invention. Error bits are shown in circles. By giving codebooks and transmission codes of multiple systems to one input vector, the unit of transmission code is divided, so the probability that an error will occur in all systems is equal to the error rate of a normal transmission code that is not divided. It will be small in comparison. In other words, as shown by the hatching in Figures 9A and 9B, in the case of two systems, the range affected by a 1-bit code error is! It will be half of that of the system.

r for the series with memoryless Laplace distribution in Figure 10
In the figure, (a) shows two systems of quantization according to the present invention, and (b) to (e) show the performance when = 1. is the conventional one-system quantization. The horizontal axis is the bit error rate, and the vertical axis is the SNR. From FIG. 10, it can be seen that the two-system quantization has almost the same performance as the one-system quantization with the same number of dimensions when there is no code error, and is superior when there is a code error.

FIG. 11 compares two systems of quantization according to the present invention with a combination of a conventional vector quantization code and an error correction code under the condition that the total amount of information is constant. Here, seven types of BCH codes capable of multiple error correction were used as correction codes. The numbers in parentheses indicate, from left to right, all information bits, information source bits, and error correctable bits. Even when there are no errors in any of these codes, distortion increases due to redundant bits, and code errors exceed a certain level. In this case, there is a problem that distortion increases rapidly, and the quantization of the present invention is superior.

Figure 12 shows an example in which the two-channel vector quantization of the present invention is applied to transform coding using weighted vector quantization, which is one of the most effective methods for medium-band speech coding. The linear prediction parameter (αi) is applied to the analyzer 41 and is applied to the inverse filter 42 as a filter coefficient, and the audio signal S is passed through the inverse filter 42 to obtain the linear prediction residual signal R. The residual signal R is cosine transformed by a cosine transformer 43, and its 0CT (discrete cosine transform) coefficients are rearranged on the frequency axis and divided into a plurality of subvectors. The vector L1 obtained in this way is vector quantized by the two-channel weighted vector quantizer 1 (10) according to the present invention with weighting of the spectral envelope and transmitted as waveform information B. Along with this, the pitch period ΔL and the linear prediction parameter Auxiliary information A consisting of (αi) and signal power P is also encoded and transmitted.Decoder 2 on the receiving side (10 refers to the codebook 15.16 and extracts a set of representative vectors from the received waveform information code B). xj,
ym is decoded and the average thereof is output from decoders 17 and 18. This average vector is applied to an inverse cosine transformer 14 and a residual signal R' is decoded. On the other hand, the received parameter information A is decoded by the parameter decoder 45, and the linear prediction parameter (αi) thereof is given to the synthesis filter 46 as a filter coefficient. The residual signal R' is passed through a synthesis filter 46 to synthesize speech.

Two-channel quantization codebook 11.12 (and 15.
16), we first learn from a Gaussian random number sequence with all scales weighted with long-term average spectra. In the vector created at this time, the power of the component corresponding to the high frequency range on the frequency axis becomes almost 0, and the high frequency component of the decoded voice is missing. To alleviate this problem, the representative vector is replaced with a vector with the minimum weighted distance among the Gaussian random numbers in the learning series.

FIG. 13 shows the SNR for the code error in the transmission difference shown in FIG. 12, compared to the case of using the conventional one-channel vector quantization shown in FIG. As the input speech S, voices of one male and one female are repeatedly used with different code error patterns, and each SNR is an average of about 90 seconds. In all cases except (a), normal one-channel vector quantization is used for waveform quantization. Double error correction of (31, 21) is possible in the waveform information for all auxiliary information B and (C) CH
Error correction was performed using codes. Supplementary information is 20% of the overall information.
This is because while the increase in waveform distortion due to the redundant bits of the error correction code is small, the damage is great when an error occurs in the waveform information.

From the results shown in FIG. 13, it can be seen that the two-channel quantization can reduce the waveform distortion compared to the other methods with respect to an error of about 0.3% from the case where there is no error.

Next, a case will be described in which the present invention is applied to the quantization of the linear prediction parameter (αi) for speech encoding shown in FIG. Here, first, the linear prediction coefficient (αi) is converted into an LSP (line spectrum pair) parameter that facilitates filter stability management and has good interpolation characteristics (US Patent Nct43932).
72), then vector/scalar quantization is performed on this parameter using 8 bits for the vector part and 13 bits for the scalar part, and each of the 8 bits corresponding to the vector part at this time is forcibly inverted and decoded. The first comparison of the spectral distortion (LPC cepstral distance) between ordinary vector quantization and the quantization of the present invention when
This is Figure 4. The vertical axis shows the cepstrum distance, the horizontal axis shows the inverted bit position in the code, the 0 bar is the result of normal vector quantization, and the vertical striped bar is the result of vector quantization according to the present invention.Evaluated by spectral distortion. is LSP
This is because a code error in a linear prediction parameter such as a parameter is directly reflected as quantization distortion of encoded speech. The smaller the value of spectral distortion, the less deterioration it shows. From this figure, it can be seen that the present invention, which is divided into two channels, has less influence on spectral distortion. 'Furthermore, when there are no errors, ordinary vector quantization is better, but the difference is small.

〔Effect of the invention〕

As explained above, according to the vector quantization method of the present invention, one input vector is quantized in multiple systems using multiple codebooks, so the unit of the quantization code is divided, and as a result, the The probability that errors will occur in all divided codes during transmission is extremely small compared to the transmission error rate of normal quantized codes that are not divided. In other words, the range affected by a one-pit code error becomes smaller.

Therefore, damage to the decoded vector is reduced.

On the other hand, when there is no code error, the combination of output codes is determined so that the average of the representative vectors of each system minimizes the distortion with the input, so it is almost equivalent to the normal quantization of one system with the same amount of information. It can be expected to have good performance.

Furthermore, in addition to the advantages of the multi-system vector quantization method of the present invention against code errors, the storage capacity of the codebook can be significantly reduced, as shown in Tables ■ and Table ■, and there are It has the advantage of reducing the amount of search calculations.In addition, by narrowing down the search candidates to only those in the vicinity of the input vector in each codebook, there is almost no deterioration in performance.
It is possible to reduce the amount of calculations.

Therefore, by using the quantization method of the present invention for audio waveform encoding and image encoding, performance can be expected to improve, and it is particularly effective in applications where transmission path errors occur and information compression is required.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a conventional transmitting-side encoding device and receiving-side decoding device that perform vector quantization using one codebook, and FIG. 2 is a vector quantization device and its decoding device according to the present invention. 3 is a detailed block diagram of the vector quantization device of the present invention shown in FIG. 2, and FIG. 4 shows the configuration for calculating squared distance in the vector quantization device of FIG. 3. Block diagram, Figure 5 is the 3rd
FIG. 6 is a block diagram showing another configuration for calculating a squared distance in the embodiment shown in FIG. 3; FIG. 7 is a block diagram showing a configuration for calculating a weighted squared distance in the embodiment shown in FIG. Flowchart showing the procedure for creating two codebooks used in the vector quantization device by learning, Figure 8 is a graph showing the improvement of the codebook when learning is repeated according to the flowchart in Figure 7, Figures 9A and 9B Figure 10 is a diagram comparing the range of damage caused by code errors between the conventional vector quantization method and the vector quantization method of the present invention. Figure 11 is a graph comparing the effects of the vector quantization method of this invention with the prior art. Fig. 13 is a graph comparing the SNR for code errors of the position system shown in Fig. 12 with that when conventional vector quantization is used; A graph comparing spectrum distortion with respect to code errors when the present invention is applied to the quantization of the linear prediction parameters shown in the figure compared to when a conventional vector quantization method is used is shown. Fig. 1 Fig. 2, joo /2 (10 Fig. 8 J + provisional *C') Fig. 10 Fig. 11 Fig. 13 Error rate Fig. 14 Number of inverted bits

Claims (35)

[Claims] (1) An average vector of a set of a plurality of codebook storage means each having a predetermined number of representative vectors, and a representative vector selected from each of the plurality of codebook storage means for the input vector. distortion calculation means for calculating the distortion between the input vector and the input vector for a plurality of different sets of representative vectors; A multi-vector quantization device comprising: minimum distortion determining means for determining; and multiplexing means for multiplexing and outputting codes representing the determined representative vectors of the set. (2) The multi-vector quantization device according to claim 1, wherein the multiplexing means is a means for time-multiplexing each of the codes representing the representative vector. (3) The multi-vector quantization device according to claim 1, wherein the distortion calculation means is a means for calculating the square distance between the input vector and the average vector as the distortion. (4) The multi-vector quantization device according to claim 1, wherein the distortion calculation means is a means for calculating a weighted squared distance between the input vector and the average vector as the distortion. (5) The calculation means includes a subtraction means for calculating a vector of differences between the average vector and the input vector, and a sum of the squares of the respective elements of the difference vector calculated by the subtraction means. 2. The multi-vector quantization apparatus according to claim 1, further comprising square addition means for outputting the distortion as the distortion. (6) The distortion calculation means calculates, for each set of representative vectors selected one from each of the plurality of codebooks, the square sum of each element of the vector of the sum of the respective representative vectors of the set. table memory means for storing data corresponding to the sets; and inner product calculation means for calculating the inner product of the input vector and a representative vector selected one by one from each of the plurality of codebook storage means for the input vector. , and subtracting means for calculating the difference between the sum of each inner product from the inner product calculating means and the sum of squares corresponding to the selected set read from the table memory and outputting the difference as the distortion. Multi-vector quantizer. (7) The distortion calculation means includes a multiplication means that multiplies the input vector by a correspondingly inputted weight vector and outputs a weighted input vector, and a representative vector selected from each of the plurality of codebooks. For each set, table memory means stores a constant vector whose elements are squares of sums of mutually corresponding elements of respective representative vectors of the set, corresponding to the set; and the plurality of codebook storage means. first inner product calculation means for calculating the inner product of the representative vector of the set selected from the group and the weighted input vector from the multiplication means; and the constant read out from the table memory means in correspondence with the selected set. 2. The multiple vector according to claim 1, comprising: second inner product calculating means for calculating an inner product of a vector and the weight vector; and addition means for outputting the difference between the inner products from the first and second inner product calculating means as the distortion. Quantizer. (8) Claims 1 to 7, wherein two codebooks are provided.
The multi-vector quantization device according to any one of . (9) Each input vector u consists of k elements, and the plurality of codebook storage means each store N representative vectors x_j, j=0, 1,...,N-1, each consisting of k elements.
, and N representative vectors each consisting of k elements, y_m, m-0,1,...,N-1
2. The multi-vector quantization device according to claim 1, wherein Y codebooks having Y codebooks are respectively stored, k is a positive integer, and N is an integer of 2 or more. (10) The input vector u and the representative vector x_
Let each i-th element of j, y_m be u(i), x(i,
j) and y(i, m), the distortion calculating means calculates the following equation as the distortion for the representative vector x_j, y_m of the selected set (j, m): d′_j_,_m=▲mathematical formula, chemical formula, There are tables etc.▼
-2u(i) {x(i,j)+y(i,m)}+F(j
, m)...(a) F(j, m)=▲There are mathematical formulas, chemical formulas, tables, etc.▼{x
(i, j)+y(i, m)}...(b) The multi-vector quantization device according to claim 9. (11) The distortion calculation means calculates the representative vector x_j, y
The above formula (b) for all combinations (j, m) of __m
includes table memory means for storing calculated values of F(j, m) in correspondence with the combination (j, m), and the distortion calculation means stores the calculated values of F(j, m) in the selected set of representative vectors (j, m). 11. The multi-vector quantization device according to claim 10, wherein the calculation of equation (a) is performed by reading out the corresponding value of F(j, m) from said table memory means. (12) The i-th elements of the input weight vector w, the input vector u, and the representative vectors x_j, y_m are respectively expressed as w(i), u(i), x(i, j), and y(i
, m), the distortion calculating means calculates the selected set (j, m).
) for the representative vector x_j, y_m, the following equation d'_j_,_m=▲There are mathematical formulas, chemical formulas, tables, etc.▼
−2w(i)u(i) {x(i,j)+y(i,m)}
＋▲There are mathematical formulas, chemical formulas, tables, etc.▼w(i)F(i,
j, m)……(1) P(i, j, m)={x(i, j
)+y(i,m)}......Distortion d'_ defined by (2)
The multi-vector quantization device according to claim 9, wherein the multi-vector quantization device is means for calculating j_,_m. (13) The distortion calculation means is configured to calculate the selected representative vector x.
Claim 12, further comprising a table memory for storing a value obtained by pre-computing at least a part of the calculation of the constant vector F(i, j, m) expressed by the formula (b) for the set of _j, y_m.
The described multi-vector quantizer. (14) Claim 1, wherein the multiplexing means is means for frequency multiplexing each of the codes representing the representative vector.
The described multi-vector quantizer. (15) A multi-vector quantization method in which a plurality of samples of an input signal sequence are combined into one input vector, and each input vector is quantized, including: (a) a plurality of vectors each having a plurality of predetermined representative vectors; (b) calculating the distortion between the average vector of the set of selected representative vectors and the input vector; (c) step ( repeating a) and (b) for a plurality of different sets of representative vectors selected from the plurality of codebooks, and determining a set of representative vectors that gives the smallest distortion among the respective calculated distortions; (d) and multiplexing and outputting the respective codes representing the determined set of representative vectors. (16) The multi-vector quantization method according to claim 15, wherein a square distance between the input vector and the average vector is calculated as the distortion in the step (b). (17) The multi-vector quantization method according to claim 15, wherein a weighted squared distance between the input vector and the average vector is calculated as the distortion in the step (b). (18) Each said input vector u consists of k elements,
The plurality of codebooks include an 16. The multi-vector quantization method according to claim 15, wherein the Y codebook has representative vectors y_m, m=0, 1, . . . N-1, where k is a positive integer and N is an integer of 2 or more. (19) The input vector u and the representative vector x_
j, y_m, respectively, u(i), x(i
. Contains mathematical formulas, chemical formulas, tables, etc.▼
-2u(i) {x(i,j)+y(i,m)}+F(j
, m)...(a) F(j, m)=▲There are mathematical formulas, chemical formulas, tables, etc.▼{x
The multi-vector quantization method according to claim 18, wherein the calculation is performed as distortions d'_j_,_m defined by (i,j)+y(i,m)}...(b). (20) The step (b) is to calculate the constant F(j, m) defined by the above equation (b) using the equation (a) using a table of calculated values for all pairs (j, m) in advance. 20. The multi-vector quantization method according to claim 19, further comprising calculating the defined distortions d'_j_,_m. (21) The step (b) calculates the inner product of the input vector u and each of the representative vectors x_j and y_m, and calculates the sum of these inner products and the constant F(j, m) read from the table. 21. The multi-vector quantization method according to claim 20, wherein the difference between d'_j_,_m is calculated as the distortion d'_j_,_m. (22) The input weight vector w is obtained by dividing each first element of the input vector u and the representative vectors x_j, y_m into w(i), u(i), x(i, j), and y(
i, m), the step (b) is the selected set (j,
For the representative vectors x_j, y_m of
−2w(i)u(i) {x(i,j)+y(i,m)}
＋▲There are mathematical formulas, chemical formulas, tables, etc.▼w(i)F(i,
j, m) ... (a) F (i, j, m) = {x (i, j)
+y(i,m)}……(b) Distortion d′_j
The multi-vector quantization method according to claim 18, wherein _, _m are calculated. (23) The step (b) is the selected representative vector x_
The constant vector F (i, j, m) specified by the above equation (b) for the set of j, y_m is calculated in advance using a table of the results of at least a part of the calculation, and the constant vector F (i, j, m) is calculated in advance. 23. The multi-vector quantization method according to claim 22, further comprising calculating the distortions d'_j_,_m. (24) The calculation of the formula (a) in the step (b) involves the step of multiplying the input vector u by the weight vector w, and the inner product of the multiplication result and each of the representative vectors x_j and y_m. 23. The multi-vector quantization method according to claim 22, comprising the step of calculating . (25) The i-th elements of the input weight vector w, the input vector u, and the representative vectors x_j, y_m are respectively expressed as w(i), u(i), x(i, j), and y(i
, m), the step (b) is the selected set (j
, m) for the representative vectors x_j, y_m of
(i) {u(i)−τ・x(i,j)−τ・y(i,m
)}, where τ is an arbitrary positive constant. (26) In step (b), the distortion is expressed by the following equation d_j for the representative vectors x_j, y_m of the selected set (j, m).
＿、＿m=μ｜u−v＿j＿,＿m｜＾2+(1−μ)
{|u−x_j|＾2+|u−y_m|＾2}/4 Calculate the distortion d_j_,_m defined by v_j_,_m=(x_j+y_m,)/2, and μ is any arbitrary value of 0≦μ≦1. 19. The multi-vector quantization method according to claim 18, wherein the quantization method is a constant. (27) The step (b) calculates the distortion for the representative vectors x_j, y_m of the selected set (j, m) by the following formula ▲ Formula,
There are chemical formulas, tables, etc. Calculate the strain d_j_,_m specified by ▼, and calculate q(f|j) and q
19. The multi-vector quantization method according to claim 18, wherein (g|m) represents a probability that the codes j and m representing the representative vectors x_j and y_m will be mistaken as f and g, respectively, in a transmission path. (28) The step of creating a plurality of codebooks includes (a) a step of arbitrarily allocating a predetermined number of input sample vectors into a plurality of groups to create a plurality of initial codebooks; and (b) a number sufficiently larger than the predetermined number. a step of determining a set of representative vectors to which each of the learning vectors belongs by using the learning vectors as input vectors and sequentially quantizing them by the multi-vector quantization method using the plurality of initial codebooks; ) The contents of the initial codebooks other than any one of the plurality of initial codebooks are fixed, any one representative vector of the one initial codebook is regarded as a variable vector, and that one representative vector is assigned. The equation obtained by partially differentiating the sum of distortions of all the learning vectors included in the set of vectors with respect to the variable vector is set to 0, and the vector value obtained by solving that equation for the variable vector is set as a new representative vector. (d) repeating the step (c) for all other representative vectors of the one initial codebook and replacing them with new representative vectors, thereby changing the contents of the one initial codebook; and (e) repeating the steps (b), (c), and (d) for all other initial codebooks of the plurality of initial codebooks to update their contents. 16. The multi-vector quantization method according to claim 15. (29) The step of creating the plurality of codebooks is the step (b).
29. The multi-vector quantization method according to claim 28, further comprising the step of repeating , (c) and (d) a plurality of times for the same codebook. (30) The step of creating the plurality of codebooks is the step (b).
, (C), (D) and (E) a plurality of times. (31) The multi-vector quantization method according to claim 15, wherein the step (d) is a step of time-multiplexing and outputting each of the codes representing the determined set of representative vectors. (32) The multi-vector quantization method according to claim 15, wherein the step (d) is a step of frequency multiplexing and outputting each of the codes representing the representative vectors of the determined set. (33) The multi-vector quantization method according to claim 31 or 32, wherein the code representing each representative vector of the determined set is a number representing each representative vector. (34) The average vector is defined by the following equation. Weighted average vector v_j_,_m v_j_,_m={2^2^r^(^x^)x_j+2
^2^r^(^y^)y_m}/{2^2^r^(^x
^)+2^2^r^(^y^)}, and r(x) and r(y) are the transmission rates of codes representing the representative vectors x_j and y_m, respectively. method. (35) If the i-th element of the input vector u is expressed as u(i), and the g-th elements of the representative vectors x_j, y_m are expressed as x(g, j), y(g, m), then the step (
b) is the representative vector x_j of the selected set (j, m),
For y_m, calculate the strain d_j_,_m defined by the following formula ▲ There are mathematical formulas, chemical formulas, tables, etc. ▼ and h(i, g)
19. The multi-vector quantization method according to claim 18, wherein τ represents an element in row i and column g of a matrix on which the convolution product is performed, and τ is a parameter that minimizes the distortions d_j_,_m.