JPH04239225A - Variable-length encoding device - Google Patents

Abstract

PURPOSE:To constantly perform the optimum variable-length encoding by selecting a variable-length encoding table which has the minimum code length in an information amount evaluation circuit and encoding inputted information. CONSTITUTION:The values successively taken out from ROM 71 to 7N per piece of inputted information are provided to accumulators 81 to 8N, and the values obtained in the accumulators 81 to 8N are provided to a comparator 10 through registers 91 to 9N respectively. The comparator 10 discriminates a ROM from among the ROM 71 to 7N with the minimum value. The signals discriminated by the comparator 10 are provided to a selector 6 and the selection of ROM 51 to 5N is performed. The variable-length encoding table provided on the ROM 51 to 5N selected by the selector 6 is supplied to a variable-length encoding circuit 4 and the encoded signals are taken out to an output terminal 11.

Description

[Detailed description of the invention]

0001

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a variable length encoding device used for high efficiency encoding when digitally processing image signals, for example.

0002

[Prior Art] For example, in a high-efficiency encoding device for digitally processing an image signal, variable length encoding is performed to transmit generated information after encoding processing with a bit length corresponding to the amount of generated information. It is being said. In other words, the purpose of variable length encoding is to shorten the overall bit length by assigning codes with short code lengths to information that occurs frequently and codes with long code lengths to information that occurs less frequently. It is said that

[0003] In such variable length encoding, the table used for encoding is a type of table that predicts the probability of occurrence of input information according to the characteristics of the information to be processed, and determines the code length configuration accordingly. Only tables are provided. Therefore, when the probability of occurrence of input information matches the prediction, it is optimal (the overall bit length is the shortest). However, if the probability of occurrence of input information and the code length do not correspond, the overall bit length will be longer than in the optimal case. Under the worst conditions, it may become longer than the fixed length case.

By the way, when input information is divided into sets of a predetermined number of units, the frequency of occurrence of each piece of information in one set and the frequency of occurrence of each piece of information corresponding to this in another set are calculated. are not necessarily equal. This means that even if the variable length encoding table is optimal for a certain set, that table is not necessarily the optimal table for other sets.

[0005]

The problem to be solved is that in conventional variable length coding, only one type of table with a fixed code length configuration is generally provided. For this reason, it cannot be said that optimal variable length encoding is always performed.

[0006]

[Means for Solving the Problems] The present invention provides an information amount evaluation circuit comprising a plurality of variable length encoding tables, a code length table corresponding to these variable length encoding tables, an accumulator, a register, and a comparator; and a variable length encoding circuit that allocates variable length codes to input information according to a variable length encoding table, and the information amount evaluation circuit selects the variable length encoding table with the minimum code length and converts the input information into This is a variable length encoding device that performs encoding.

[0007]

[Operation] According to this, the variable length encoding table with the minimum code length is selected in the information amount evaluation circuit and the input information is encoded, so that optimal variable length encoding can always be performed. , it is possible to perform extremely highly efficient encoding.

[0008]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a block diagram of an example of a variable length encoding apparatus according to the present invention. In this figure, 1 is a terminal to which input information is supplied. Input information from this input terminal 1 is supplied to a variable length encoding circuit 4 through a delay compensation circuit 3 that compensates for delays in an information amount evaluation circuit 2, which will be described later. Also 5
1, 52, . . . , 5N are read-only memories (ROM) each forming a variable length encoding table. The variable length encoding tables provided in these ROMs 51, 52, . . . , 5N are supplied to the variable length encoding circuit 4 through the selector 6.

On the other hand, in the information amount evaluation circuit 2, the input information from the input terminal 1 is transferred to the ROMs 51, 52, . . .
a read-only memory (ROM) 71 that configures a code length table corresponding to a 5N variable length encoding table;
Commonly supplied to 72...7N. These ROM7
Values sequentially taken out for each input information from 1, 72...7N are supplied to accumulators (ACC) 81, 82...8N. The values obtained by the ACCs 81, 82...8N are supplied to the comparator 10 through registers 91, 92...9N, respectively. And ROM71, 72...7N where the value is the minimum in this comparator 10
(corresponding to the variable length encoding table of ROMs 51, 52, . . . 5N) is determined. In the information amount evaluation circuit 2, the input information from the input terminal 1 is processed for each predetermined block, and the comparator 10 makes a determination for each block, and the ACCs 81, 82, . . . , 8N are cleared.

The signal determined by the comparator 10 is supplied to the selector 6, and the ROM 51, 52...5N
A selection is made. Then, the variable length encoding table provided in the ROM 51, 52, . Note that the delay compensation circuit 3 compensates for the delay corresponding to the block processed by the above-mentioned information amount evaluation circuit 2. Further, the table selection information signal determined by the comparator 10 is taken out to the output terminal 12.

Therefore, according to this device, the information amount evaluation circuit (2) determines the variable length encoding table (R
OM51, 52...5N) is selected (selector 6) and the input information (input terminal 1) is encoded (variable length encoding circuit 4), so it is possible to always perform optimal variable length encoding. This makes it possible to perform extremely highly efficient encoding.

Furthermore, FIG. 2 is a block diagram of an example of a decoding device. In this figure, signals corresponding to the signals taken out to the above-mentioned output terminals 11 and 12 are supplied to input terminals 21 and 22. A signal from this input terminal 21 is supplied to a variable length decoding circuit 23. Further, 31, 32, . . . , 3N are read-only memories (ROM) that constitute variable length decoding tables corresponding to the variable length encoding tables provided in the ROMs 51, 52, . . . , 5N, respectively. The variable length decoding tables provided in these ROMs 31, 32, . . . , 3N are supplied to the selector 24. Further, a signal from the input terminal 22 is supplied to the selector 24 through the register 25. Then, the variable length decoding table provided in the ROM 31, 32, .

[0013]Decoding is performed in this manner. Note that in decoding, the table selection information signal can be made unnecessary by selecting the one with the least contradiction from among the decoding tables decoded using all the decoding tables. However, this table selection information signal is a signal with a small number of bits, about 3 bits, so that the configuration of the decoding device can be extremely simplified.

FIG. 3 shows an example of a variable length encoding table. In the figure, the quantization level of the input information is -1
For cases of 016 to +1016, two examples of variable length encoding tables are shown in code length configurations. In this figure, Table 1 is selected when the frequency of occurrence of the quantization level of input information being 0 is extremely high. Further, Table 2 is selected when the quantization level of the input information is frequently in the range of -2 to +2.

Furthermore, an information-theoretic explanation will be added regarding the principle of the present invention. Now, an information source consisting of M types of reports is expressed as S, and the elements of S are expressed using information source symbols (s1, s
2...sM). In this case, information source S to N
The average amount of information I when reports occur is

It is expressed as [Equation 1]. Here, p(si) is the number of reports with si out of N reports as ni.

[Math 2] It is.

Next, divide the N pieces of occurrence information into two sets,
Separate into N1 notifications and N2 notifications. If the average information amount of the former is I1 and that of the latter is I2, then

It is expressed as [Equation 3]. Here, N1 +N2 = N, and p1
(si) and p2 (si) are the frequencies of occurrence of notification si among N1 and N2 notifications, respectively. Therefore

[Math 4] There is a relationship.

Next, p1 (si) and p2 (si
), the following inequality holds true.

[Math 5] Therefore, the following inequality also holds true for the average information amount I.

[Math 6]

This inequality shows that the average amount of information can be smaller if N1 and N2 pieces are encoded separately than when N pieces are encoded all at once. That is, it means that it is more efficient to perform encoding according to each occurrence information probability individually than to perform encoding all at once.

This shows the advantage of performing optimal encoding for each predetermined number as a unit, as shown in the present invention. Therefore, in the present invention, for this optimization, a coding table with a plurality of code length configurations is provided, and information amount evaluation is performed.

[0020]

[Effects of the Invention] According to the present invention, the variable length encoding table with the minimum code length is selected in the information amount evaluation circuit and the input information is encoded, so that optimal variable length encoding is always performed. This has made it possible to perform extremely highly efficient encoding.

[Brief explanation of the drawing]

FIG. 1 is a configuration diagram of an example of a variable length encoding device according to the present invention.

FIG. 2 is a configuration diagram of an example of the decoding device.

FIG. 3 is a diagram for explaining the same.

[Explanation of symbols]

1 Input terminal to which input information is supplied 2 Information amount evaluation circuit 3 Delay compensation circuit 4 Variable length encoding circuits 51, 52...5N Read-only memory 6 for variable length encoding table Selectors 71, 72... 7N Code length table read-only memory 81, 82...8N Accumulator 91, 92...
...9N Register 10 Comparator 11 Encoding output terminal 12 Table selection information output terminal

Claims (1)

[Claims] [Claim 1] A plurality of variable length encoding tables and code length tables corresponding to these variable length encoding tables;
It consists of an information evaluation circuit consisting of an accumulator, a register, and a comparator, and a variable length encoding circuit that assigns a variable length code to input information according to the variable length encoding table, and the minimum code length is achieved in the information evaluation circuit. A variable length encoding device that selects the variable length encoding table to encode the input information.