JPH0324101B2 - - Google Patents

Abstract

PURPOSE:To improve the coding efficiency by setting a permissible distortion to a distortion decision circuit and applying variable length coding to an index signal of an output vector when the distance (distortion) between an input vector and an output vector is a permissible distortion or below during an output vector retrieval of minimum distortion so as to obtain a coded output. CONSTITUTION:A distortion d1 between an input vector (x) and an output vector y1 and a set permissible distortion dtheta are compared and when the relation of di<=Dtheta is reached, the retrieval is stopped. Then an index signal (i) of the output vector at that time is subject to variable length coding to obtain a coded output. thus, the coding efficiency is improved remarkably and high speed processing is attained.

Description

[Detailed Description of the Invention] [Industrial Application Field] This invention relates to a vector quantization encoder that blocks a plurality of input signal sequences and quantizes and encodes the blocks in a multidimensional signal space. .

[Conventional technology]

First, the principle of vector quantization will be briefly explained, and then a conventional vector quantization encoder will be explained.

K information source input signal sequences are put together into an input vector x = {x ₁ , x ₂ , . . . , x _K }. At this time, K
N representative points (i.e., output vectors) of the dimensional Euclidean signal space R ^K ( x R ^K ) y _i = {yi ₁ , yi ₂ ,
...y _iK } is set as Y={ y ₁ , y ₂ , ... y _N }.
Set the output vector yi as the representative point (e.g. center of gravity)
When each division of R ^K is defined as R ₁ , R ₂ , . . . , R _N , vector quantization Q is defined by the following equation.

Q: R ^K →Y...(1) Here, Ri=Q ^-1 (yi)={ x R ^K :Q( x )yi}...(2) _N ∪ ⁱ R _i =R ^K , Ri∩Rj= φ(i≠j)...(3) The above vector quantization Q is expressed as a cascade connection of encoding C and decoding D. The encoding C is the mapping of the set Y = { y ₁ , y ₂ , ..., y _N } of the output vectors of R ^K to the index set I = {1, 2, ..., N}, and the decoding D is This is mapping from I to Y.

That is, C: R ^K → I, D: I → Y...(4) Q=D・C...(5). In vector quantization, since the encoded output I is transmitted or recorded, the encoding efficiency is extremely high.

Vector quantization is the mapping of an input vector to the output vector yi that is the shortest distance (resulting in the least distortion). Specifically, if the distance (distortion) between the input and output vectors is d( x , yi ), then the following equation is obtained.

if d( x , yi )<d( x , yi ) for all j...(6) x−Ri, that is, x → yi ...(7) Set Y of output vectors yi as shown in Figure 3
can be obtained by clustering (selection of representative points and division of signal space are repeated until the sum of distortions is minimized) using an information source input signal sequence serving as a training model.

Figure 4 is a block diagram showing the configuration of a conventional vector quantization encoder. In the figure, 1 is an input vector register that holds blocks of input signal sequences, and 2 is a code table that creates addresses for the code table. Address counter, 3 is an output vector code table memory for storing output vectors, 4 is an output vector code table register for holding data read from this output vector code memory, 5 is an input vector register 1
6 is a parallel absolute value calculator that calculates the absolute value of the output of this parallel subtracter, and 7 is an absolute value distortion of the input/output vector. 8 is a minimum distortion detector that detects the output vector where the absolute value distortion of the input/output vector is the minimum, and 9 is the minimum distortion detector that minimizes the distortion based on the output signal of the minimum distortion detector 8. Each index latch holding an index of an output vector is shown.

Next, the operation will be explained. K input signal sequences of the encoder are collectively blocked and taken into an input vector register 1 as an input vector x = {x ₁ , x ₂ , . . . , x _K }. At this point, i=1, 2,
. . , N, the output vectors yi = {yi ₁ , yi _{2 ,} .
For each output vector yi , the parallel subtracter 5, parallel absolute value calculator 6, and absolute value distortion detector 7 calculate the absolute value distortion di of the input/output vector by the following calculation.

di=d( x , yi )= _K〓j | ^xj −yij| (8) Next, the minimum distortion detector 8 detects the output vector with the minimum absolute value distortion di. The minimum distortion d is d = min ⁱ d( x , yi ) = min ⁱ [ 〓 ^j | xj − yij |]
…(9). The minimum distortion detector 8 calculates the distortion d( x , yi ) of the output vector yi and the input vector x which are sequentially read from the output vector code table memory 3, and compares it with the past minimum value to detect the smaller value. When this is done, it is stored as a new minimum distortion, and a strobe signal is sent to the index latch 9 each time, and the index signal i, which is the code table address of the output vector, is taken into the index latch 9. In the above procedure, all output vectors yi (i=1~
N) Continues until readout completes full search. At this point, the index i of the output vector resulting in the minimum distortion remains in the index latch 9, and this becomes the encoded output.

The above is the full search vector quantization that constitutes the vector quantization encoder.
Quantization) section.

[Problem that the invention seeks to solve]

Since the conventional vector quantization encoder is configured as described above, the necessary number of bits for the encoded output is determined, and there is a problem that information cannot be compressed any further.

The present invention was made to solve these problems, and an object of the present invention is to provide a vector quantization encoder that can significantly improve encoding efficiency.

[Means for solving problems]

The vector quantization encoder according to this invention is
The full search vector quantization unit searches for an output vector that has the shortest distance (minimum distortion) relationship with the input signal vector, and also sets the distance (distortion) between the input vector and output vector obtained by this search. When the distance between the input and output vectors becomes less than or equal to the allowable distortion, the search operation of the full search vector quantizer is stopped,
Moreover, the index signal of the output vector at that time is variable-length coded by a variable-length coding circuit to obtain a coded output.

[Effect]

In this invention, the allowable distortion is set in the distortion determination circuit, and the index signal of the output vector is changed when the distance (distortion) between the input vector and the output vector becomes less than the allowable distortion during the search for the minimum distortion output vector. Encoding efficiency is improved by long encoding and obtaining encoded output.

〔Example〕

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. In the figure, 10 is a full search vector quantization unit (hereinafter referred to as FSVQ unit including the drawing), and 11 is a block diagram in which the absolute value distortion di is predetermined. A distortion determination circuit 12 determines whether the absolute value distortion di and the allowable distortion dθ have become less than or equal to the allowable distortion dθ, based on the output signal of the distortion determination circuit.
This is a variable length encoding circuit that performs variable length encoding on the index signal i of the output vector to obtain a encoded output at the time when dθ is reached.

FIG. 2 is a block diagram showing the detailed structure of the FSVQ unit 10 of this embodiment, and the same reference numerals as in FIG. 4 indicate the same elements. Furthermore, in place of the code table address counter 2 in FIG.
The difference is that the minimum distortion min _i di up to that point is output.

The operation of this embodiment configured as described above will be explained below.

First, the input signal sequence of the encoder is grouped into K blocks, and the input vector x = {x ₁ , x ₂ , . . .
x _K } is input to the FSVQ unit 10. In the FSVQ unit 10, the input vector x is taken into the input vector register 1, and the code table counter 13 with a reset function is sequentially counted up from i=1 to N, so that the output vector yi =
{yi, ₁ , yi, ₂ , ..., yi, _K } are read from the output vector code table memory 3 and latched into the output vector register 4 one after another.

Next, the parallel arithmetic unit 5, the parallel absolute value arithmetic unit 6, and the absolute value distortion detector 7 calculate the absolute value distortion di of the input vector x and each output vector yi , as expressed by the following equation.
di=d( x , yi )= _K〓j ⁼¹ |xj−yij| The minimum distortion detector 8 compares the above absolute value distortion di with the past minimum value, and when a smaller value is detected, it is set as a new It is output to the captured distortion determination circuit 11 as the minimum distortion. Also, each time a latch signal is sent to the index latch 9, the index signal i, which is the code table address of the output vector yi , is taken into the index latch 9 and output to the variable length encoding circuit 12. The above procedure is performed every time the count of the code table address counter 13 with a reset function is counted up from i=1 to N. compares it with a preset allowable distortion dθ, and when the relationship dθ≧di is established, it outputs an index latch signal to the variable length encoding circuit 12, causing it to take in the index signal i. Also, a reset signal is sent to the code table address counter 13 with a reset function to end counting and reset to i=1. The variable length encoding circuit 12 that has taken in the index signal i is
As an example of variable length encoding, all "0"s continuing from the most significant bit to the least significant bit of the index signal i are deleted to shorten the code length. This procedure is performed for all i's taken in, variable length coding is performed, and a coded output is obtained.

〔Effect of the invention〕

As explained above, this invention compares the distortion di of the input vector x and the output vector yi with the set allowable distortion dθ, stops the search when di≦dθ, and Since the index signal i is variable-length coded and output as a coded output, the coding efficiency is greatly improved, thereby achieving the effect of enabling high-speed processing.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing the configuration of an embodiment of the present invention, Fig. 2 is a block diagram showing the detailed structure of the main elements of the embodiment, and Fig. 3 shows the general principle of vector quantization. FIG. 4 is a block diagram showing the configuration of a conventional vector quantization encoder. 1... Input vector register, 2, 9... Code table address counter, 3... Output vector code table memory, 4... Output vector code table register, 5... Parallel subtractor, 6...
...Parallel absolute value calculator, 7...Absolute value distortion detector, 8
... Minimum distortion detector, 9 ... Index latch,
10... Full search vector quantization unit, 11... Distortion determination circuit, 12... Variable length encoding circuit. Note that the same reference numerals in each figure indicate the same or corresponding parts.

Claims (1)

[Claims] 1. In a system that performs vector quantization encoding of input signal vectors obtained by blocking each input signal sequence into multiple blocks, an output vector of each representative point is obtained by dividing a multidimensional signal space containing the input signal vector into multiple parts. a full search vector quantization unit that reads out the output vector from the input signal vector and searches for the output vector that has a minimum distortion relationship with the input signal vector; a distortion determination circuit that determines whether the following has occurred and generates a significant signal; and a variable length code that encodes the index signal of the output vector into a variable length code at the time when the distortion determination circuit generates a significant signal to obtain a coded output. A vector quantization encoder comprising: an encoding circuit.