JPH07120960B2 - n-ary tree search vector quantizer - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a vector quantization coding apparatus for performing high-efficiency coding of signals.

[Prior art] FIG.
-10487 is a block diagram of the n-ary tree search vector quantizer, FIG. 4 is a detailed block diagram of the vector quantizer, and FIG. 5 is an explanatory diagram showing the relationship between the tree search and the index code. is there.

In FIG. 3, (1) is an average-value separated input vector, (2) is a vector quantizer of each stage, (3) is an output vector index, (4) is a codebook of each stage,
(5) is the amplitude gain, and in FIG. 4, (6) outputs the address (12) of the output vector to be sequentially read according to the output vector index (3) output from the vector quantizer (2) in the previous stage. Address counter, (7) multiplier, (8) inner product value, (9) maximum inner product detector, (1
0) is an amplitude gain latch that latches the inner product value as an amplitude gain, (11) is an index latch that latches the codebook address and outputs it as an index, and (13) is an adder. And the multiplier (7) form an arithmetic circuit.

Next, the operation will be described. In FIG. 3, the input vector (1) whose average value has been separated is a vector quantizer (2).
Quantization is performed as follows. First, the output vector is an n-ary (n is a power of 2) tree search. FIG. 5 shows a part of a binary tree and a quaternary tree as an example. The code of the index attached to the output vector of each node of the tree structure is determined as shown in FIG. 5, for example. The code of the quaternary tree in FIG. 5 (b) is shown in binary in the upper row and quaternary in the lower row. As can be seen from this figure, each time the number of stages in the n-ary tree structure increases by one, the code increases by log ₂ n bits (1 digit in the n-ary number) and the code is truncated by log ₂ n bits from the LSB. You can go up from the bottom to the top.

The input vector (1) whose average value is separated by searching the output vector codebook as described above up to the final stage is vector-quantized using the inner product as the distortion measure.
The tree search vector quantizer is represented by the connection of vector quantizers as shown in FIG. 3, and the vector quantizer at the m-th stage is represented by the block diagram of FIG. In FIG. 4, when the output vector index (3) is input from the (m-1) -th stage vector quantizer, the address counter (6) receives the input vector (1) based on the n-ary tree structure output vector. The address (12) of the output vector to be compared is output. When the output vector is read from the codebook (4), the product sum is calculated with the input vector (1). When the inner product value (8) of the vector thus obtained becomes the maximum with respect to the input vector, the maximum inner product detector (9) emits a strobe and the amplitude gain latch (10) has the inner product value (8). But the index latch (11)
The output vector address (12) is fetched into the address counter (6), and the value latched in the index latch (11) at the time when the address counter (6) finishes outputting all the output vector addresses (12) for the input vector (1). It is output as the output vector index (3) of m stages. When the m-th stage is the final stage, the amplitude gain (5) of the amplitude gain latch (10) is also output.

[Problems to be Solved by the Invention] Since the conventional n-ary tree search vector quantizer is configured as described above, it is necessary to have a number of vector dimension (K) multipliers for calculating the inner product. The adder that adds the products must also have K input terminals.

Further, the number of inner product operations in each stage must be performed by the number of times of the tree search (n times), and there is a problem that a maximum detector for detecting the maximum inner product value must be provided. .

The present invention has been made to solve the above problems, and an object thereof is to obtain an n-ary tree search vector quantizer which calculates an inner product with a small amount of hardware. It is an object to obtain an n-ary tree search vector quantizer that performs at high speed.

[Means for Solving the Problem] An n-ary tree search vector quantizer according to the present invention has all dimensions of a K-dimensional input vector obtained by blocking an input signal sequence into K units (K is an integer of 2 or more). And a one-dimensional multiplier for inputting the all-dimensional components of the output vector to be compared with the input vector for each dimension, and multiplying the input vector components of each dimension by all the dimensions. An arithmetic circuit having an accumulator that accumulates K multiplication results of the multiplier and outputs the result as an inner product is provided.

Further, the n-ary tree search vector quantizer according to the present invention is
A plurality of the arithmetic circuits for calculating the inner product of the output vector and the input vector in the same stage are provided, and the inner products output from the respective arithmetic circuits are input for comparison, and the output vector giving the maximum inner product is selected. It is equipped with a selector.

[Operation] In the arithmetic circuit of the n-ary tree search vector quantizer according to the present invention, the components of all the dimensions of the input vector and the dimensions of the output vector to be compared with this input vector are calculated by one multiplier. And the input vector for each dimension, the vector components of the input dimensions are multiplied by all dimensions, and the accumulator accumulates K multiplication results of the multiplier to obtain the input vector. Calculate the dot product of the output vectors.

Further, in the n-ary tree search vector quantizer according to the present invention, the inner product operations of the same stage of the tree search are shared and executed by a plurality of arithmetic circuits, and the inner product output from each arithmetic circuit is output by the comparison selector. Input and compare to select the output vector that gives the maximum dot product.

[Embodiment] An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a detailed block diagram of a vector quantizer using an inner product operation showing an embodiment of the present invention. (1) is a K-dimensional (K is an integer of 2 or more) input vector in which an average value is separated. , (2) is the vector quantizer of each stage, (3) is the output vector index, (5) is the amplitude gain of the output vector in the final stage quantization with respect to the input vector, and (6) is the vector quantizer of the preceding stage ( An address counter that outputs the addresses of output vectors to be sequentially read according to the vector index (3) output by 2), (10) an amplitude gain latch that latches the inner product value as an amplitude gain, (11)
Is an index latch that latches the codebook address and outputs it as an index. (14) is the total of all the output vectors to be compared with all the dimensional components of the K-dimensional input vector (1) and this input vector (1). A multiplier for inputting the dimension components and for each dimension, and multiplying the input vector components of each dimension for all dimensions, (1
5) is an accumulator that accumulates K multiplication results of the multiplier (14) and outputs the result as an inner product, (16) is a comparator, (17)
Is a selector, (18) is a comparator, (19) and (20) are output vectors of nodes at each stage selected in the process of reaching the final stage of the tree search with the input vector (1) as an input. It is a codebook that stores an index code that is given in a predetermined relationship with an output vector. The multiplier (14) and the accumulator (15) form an arithmetic circuit, and the comparator (16), the selector (17), the comparator (18) and the amplitude gain latch (10) make a comparison selection. Make up a container.

Next, the operation will be described with reference to FIGS. 1, 3, and 5.

First, the mean-separated input vector (1) is quantized, but the output vector is an n-ary (n is a power of 2) tree search, and the inner product is vector-quantized using the distortion measure. As with the conventional n-ary tree search vector quantizer, the tree search vector quantizer is represented by the connection of vector quantizers as shown in FIG. The m-th stage vector quantizer can be represented by the block diagram of FIG.

In FIG. 1, first, in the input vector (1) whose average values have been separated, K signal sequences are input in series, that is, all the dimensional components of the input vector (1) are input for each dimension. Simultaneously with this input vector (1), the output vector index (3) output from the (m-1) th stage vector quantizer (2) is input. Then, the address counter (6) outputs the dimensional components of the output vector, which should be compared with the input vector (1) based on the n-ary tree structure, from the codebooks (19) and (20) for each dimension. Output the address to.

In this way, all-dimensional components of input vector (1) and
The all-dimensional components of the output vector to be compared with the input vector (1) are input to the multiplier (14) for each dimension, and the multiplier (14) outputs the multiplication result per signal sequence. Are sequentially output to the accumulator (15). Accumulator (1
5) is cleared immediately before the leading multiplication result of the K signal series is input, and the inner product value is calculated by accumulating the K multiplication results. A multiplier for computing this inner product,
The vector quantizer has, for example, two accumulators.

That is, for example, when a tree search is performed using a quaternary tree shown in FIG. 5 (b), first, in the first inner product calculation, one of the multipliers (14) and accumulators (15) sets the index to 00. The inner product (# 0) with the corresponding output vector is calculated, and the inner product (# 1) with the output vector corresponding to the index 01 is calculated by the other multiplier (14) and accumulator (15). This 2
The two inner products are compared by the first stage comparator (16), and the larger one is selected by the selector (17). #
The larger inner product of 0 and # 1 is compared with the inner product stored in the amplitude gain latch (10) by the second comparator (18), but only when the inner product is calculated for the first time The larger value of # 0 and # 1 is stored in the amplitude gain latch (10) regardless of the value of the gain latch (10).

Next, in the second inner product calculation, one of the multipliers (14),
The accumulator (15) calculates the inner product (# 2) with the output vector corresponding to the index 10, and the other multiplier (1
4), the accumulator (15) calculates the inner product (# 3) with the output vector corresponding to the index 11, and the selector (17) selects the larger value as in the first time. Here, a comparison is made with the value stored in the amplitude gain latch (10) in the first inner product calculation, and the larger one is stored in the amplitude gain latch (10).

That is, at this time point, the maximum inner product value of # 0 to # 3 is stored in the amplitude gain latch (10). The output vector to be multiplied when calculating these inner products is divided into two codebooks (19) and (20) and stored in advance.
For example, the codebook (19) stores output vectors corresponding to the indexes 00 and 10, and the codebook (20) stores output vectors corresponding to the indexes 01 and 11 in advance.

Further, the index is taken into the index latch (11) at the same time as the inner product value is stored in the amplitude gain latch (10). The index at this time is the value of the address counter + the output of the comparator (16). In this way, when the address counter (6) finishes outputting all the output vector addresses to be compared, the index latch (11)
The value captured in is output as the output vector index (3). When the m-th stage is the final stage, the value of the amplitude gain latch (10) is also output.

Further, other embodiments of the present invention will be described below with reference to the drawings.

FIG. 2 is a detailed block diagram of a vector quantizer using an inner product calculation showing another embodiment of the present invention. (1) is a K-dimensional (K is an integer of 2 or more) input in which an average value is separated. Vector, (2) vector quantizer of each stage, (3) output vector index, (4) codebook of each stage,
(5) is an amplitude gain, (6) is an address counter that outputs the address (12) of the output vector to be sequentially read according to the output vector index (3) output by the vector quantizer (2) in the previous stage, (8 ) Is an inner product value, (9) is a maximum inner product detector, (10) is an amplitude gain latch that latches the inner product value as an amplitude gain, (11) is an index latch that latches the address (12) and outputs it as an index, ( 14) is a multiplier and (15) is an accumulator.

Next, the operation will be described.

When the input vector (1) separated from the average value is quantized, the output vector is an n-ary (n is a power of 2) tree search, and the inner product is vector quantized using a distortion measure,
The tree search vector quantizer is represented by the connection of vector quantizers as shown in FIG. 3, like the conventional n-ary tree search vector quantizer. The m-th stage vector quantizer can be represented by the block diagram of FIG.

In FIG. 2, first of all, an input vector (1) whose average values have been separated has K signal sequences input in series, that is, all dimensional components of the input vector (1) are input for each dimension. At the same time as this input vector (1), the output vector index (3) is input from the (m−1) th stage vector quantizer, and the address counter (6) is called the input vector (1) based on the n-ary tree structure. The address (12) is output so that the components of all dimensions of the output vector to be compared are output from the codebook (4) for each dimension.

In this way, all-dimensional components of input vector (1) and
The all-dimensional components of the output vector to be compared with the input vector (1) are input to the multiplier (14) for each dimension, and the multiplier (14) outputs the multiplication result per signal sequence. Are sequentially output to the accumulator (15). Accumulator (1
5) is cleared immediately before the leading multiplication result of the K signal series is input, and the inner product value is calculated by accumulating the K multiplication results.

When the inner product value (8) of the vector thus obtained becomes maximum with respect to the input vector (1), the maximum inner product detector (9) emits a strobe and the inner product value is stored in the amplitude gain latch (10). (8) When the output vector address (12) is taken into the index latch (11) and the address counter (6) has finished outputting all the output vector addresses (12) for the input vector (1), the deindex latch ( The value captured in 11) is output as the output vector index (3) of the mth stage. When the m-th stage is the final stage, the value of the amplitude gain latch (10) is also output.

In the above embodiment, the case of quaternary tree search is shown, but n
If it is a progression tree (n is a power of 2), it may not be a quadtree. Further, although FIG. 1 of the above-mentioned embodiment shows the case where the number of multipliers and accumulators for performing the inner product operation is two, the number is not limited as long as it is plural.

In the above embodiment, two codebooks are provided, one of which stores the output vector corresponding to the indexes 00 and 01, and the other of which stores the output vectors corresponding to the indexes 01 and 11; It suffices that the number of is the same as the number of multipliers and accumulators for performing the inner product operation,
The output vectors stored in the codebook may be in any combination.

EFFECTS OF THE INVENTION As described above, according to the present invention, all-dimensional components of a K-dimensional input vector obtained by blocking the inner product calculation for every K input signal sequences (K is an integer of 2 or more). And one-dimensional multiplier of the output vector to be compared with this input vector for each dimension, and one multiplier for multiplying the input vector components of each dimension by all dimensions.
By accumulating K multiplication results of this multiplier and performing the calculation with an accumulator that outputs the result as an inner product, the inner product can be calculated by one multiplier and accumulator.
There is an effect that the inner product can be calculated with a small amount of hardware.

Further, according to the present invention, a plurality of the arithmetic circuits for calculating the inner product of the output vector and the input vector of the same stage are provided, and the inner products output from the respective arithmetic circuits are input to perform comparison to obtain the maximum inner product. Since the comparison selector for selecting the output vector to be provided is provided, the inner product operations of the same stage of the tree search can be shared and executed by the plurality of operation circuits.
There is an effect that the inner product calculation can be performed at high speed.

[Brief description of drawings]

FIG. 1 is a detailed block diagram of a vector quantizer using an inner product operation which constitutes an n-ary tree search vector quantizer according to an embodiment of the present invention, and FIG. 2 is a vector showing another embodiment of the present invention. A detailed block diagram of the quantizer, FIG. 3 is a block diagram of the n-ary tree search vector quantizer, and FIG.
FIG. 5 is a detailed block diagram of a vector quantizer using an inner product operation that constitutes a forward tree search vector quantizer, and FIG. 5 is an explanatory diagram showing the relationship between a tree search and an index code. (1)
Is an input vector separated from the average value, (2) is a vector quantizer of each stage, (3) output vector index, (4)
Is a codebook of each stage, (5) is an amplitude gain, (6) is an address counter that sequentially outputs read addresses (12) according to the output vector index of the previous-stage quantizer,
(7) is a multiplier, (8) is an inner product value, (9) is a maximum inner product detector, (10) is an amplitude gain latch, (11) is an index latch, (13) is an adder, and (14) is a multiplication. , (15) is accumulator, (16), (18) is comparator, (17) is selector, (1
9) and (20) are codebooks in which output vectors are stored. In the drawings, the same reference numerals indicate the same or corresponding parts.

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Internal reference number FI technical display location H04N 1/41 Z 7/24

Claims (2)

[Claims] 1. K input signal sequences (K is an integer of 2 or more)
The output vector of the node at each stage selected in the process of reaching the final stage of the tree search with the K-dimensional vector blocked for each input as an input, and the index code given in a predetermined relationship with this output vector An n-ary tree search codebook (n is a power of 2) to be stored is input, the input vector and the index code are input, and the n-ary tree search codebook is tree-searched and read based on the index code. The inner product of the output vector of the next stage and the input vector is calculated by the arithmetic circuit, and the index code of the output vector giving the maximum inner product is sequentially output to the final stage, and the output vector of the output vector giving the maximum inner product is given at the final stage. In the n-ary tree search vector quantizer which outputs the maximum inner product value at that time together with the index code as the amplitude gain, Input all-dimensional components of the input vector and all-dimensional components of the output vector to be compared with the input vector into the circuit for each dimension, and input all the vector components of the input dimensions. An n-ary tree search vector quantizer comprising one multiplier for multiplying by dimension and an accumulator for accumulating K multiplication results of the multiplier and outputting the result as an inner product. . 2. A plurality of the arithmetic circuits for calculating the inner product of the output vector and the input vector in the same stage are provided, and the inner products output from the respective arithmetic circuits are input for comparison.
The n according to claim 1, further comprising a comparison selector for selecting an output vector that gives a maximum inner product.
Progressive tree search vector quantizer.