JPS6276931A - Data compressor - Google Patents

Abstract

PURPOSE:To attain a highly efficient data compression while using coded and decoded tables of a limited quantity by referring to one of coded or decoded tables to a data having a high frequency so as to apply coding or decoding and referring to plural tables to data having a low appearance frequency so as to apply coding or decoding. CONSTITUTION:The decoded data outputted from the 1st and 2nd decoded tables 6, 7 and a 4-bit code length data are selected for an output of any one table from a data selector 8 and a code length selector 9 respectively. Then as the decoded data, the result is outputted externally. Further, the selection signal comes from an identification flag F1 being an output of the 1st decoded table 6. Conversely, a data code requiring the two tables 2, 3 in case of the decoding selects the decoded data and the code length data of the 2nd decoded table 7 because the identification flag F1 of the 1st decoded table 6 is logical '1' by an OR gate OR.

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention relates to a data compression device that compresses data such as digital image data using Huffman encoding, and in particular, to a data compression device that achieves high compression efficiency. Regarding.

[Technical background of the invention]

2. Description of the Related Art Huffman encoding is known as a method for efficiently encoding data by utilizing statistical properties of binary data such as digital image data, such as data appearance frequency. The Huffman encoding method is a variable code length encoding method in which a code with a short code length is assigned to data that appears frequently, and a code with a long code length is assigned to data that appears less frequently.

For example, as shown in FIG. 5, data O to 15 are each 2-
When a data sequence with an appearance probability of 1 to 2-1 is encoded using the Huffman encoding method, as shown in FIG. 6, for example,
Data 0 is “0” in the binary conversion code, and data 1
5 is the binary conversion code “1111111111111
11'''. When data encoded using the Huffman encoding method is decoded, for example, as shown in FIG. 7, the encoded data "ooooooooooooooooo"
“011111111111111” becomes “O” when converted to original data, and encoded data “11111111”
1111111” becomes “15°” when converted to original data.

In other words, in a data compression device that uses an encoding or decoding table for encoding/decoding data, m types of current data (in encoding the original data shown in FIG. 5) 16) encoding tables are required, and 2rL (21 in order to decode the encoded data in FIG. 5) decoding tables are required for the maximum code length of n bits.

[Problems with background technology]

As mentioned above, in a data compression device that uses encoding or decoding tables for data encoding/decoding, the number of encoding tables is fixed, but the number of decoding tables depends on the statistics of the data series. The length depends on the maximum code length, which is determined by the characteristics of the code, so it changes depending on the encoded data. Here, if the maximum code length increases by 1 bit, the decoding table will be twice as necessary, and the maximum code length will depend greatly on the number of decoding tables. It can be said that coding everything is wasteful.

Therefore, as shown in Fig. 8, in the past, an upper limit was set for the maximum code length, that is, an upper limit of 4 bits in Fig. 8, on the premise that a limited number of encoding tables were used; For the current data 4 to 15, which have a code exceeding , an identification code is added to the data without being encoded. However, when attempting to compress data using such a limited number of encoding tables, it is necessary to set a limit on the code length, resulting in a decrease in compression efficiency.

[Purpose of the invention]

The present invention has been made based on the above circumstances, and its purpose is to provide a data compression device that enables highly efficient data compression while using a limited number of encoding tables and decoding tables. .

[Summary of the invention]

In order to achieve such an object, the present invention provides a data compression device that encodes or decodes data by a predetermined encoding method or decoding method using statistical properties of digital data generation. or using a decoding table,
Data that appears frequently is encoded or decoded by referring to one of the encoding or decoding tables mentioned above, and data that appears less frequently is encoded or decoded by referring to multiple of the encoding or decoding tables mentioned above. It is characterized by encoding or decoding.

[Embodiments of the invention]

A Huffman encoding circuit will be described below as an embodiment of the data compression apparatus according to the present invention with reference to FIG.

In FIG. 1, 1 is a data register, which holds original data sequences DO to D3 to be encoded. 2
is the first encoding table, which inputs the 4-bit data series DO to D3 from the data register 1, performs Huffman encoding on this input data series DO to D3 with 7 bits, and outputs a maximum code length of 7. Bit coded data CO to C6, 3-bit code length data LIO to LL2, and an identification flag Fl that indicates with 1 bit whether or not the code was successfully encoded.
This outputs the following.

3 is a second encoding table in which basically the same operation as the first encoding table 2 is performed, and based on the identification flag F1 of the output of the first encoding table 2, that is, the first encoding table The data that could not be encoded in step 2 is detected using the identification flag Fl, and the unencoded data DO~D3 is input, and this input data series DO~D3 is converted into a code with a maximum code length of 7.
A device that performs Huffman encoding on bits and outputs 7-bit encoded data 07 to C13, 3-bit code length data L20 to L22, and an identification flag F2 that indicates with 1 bit whether or not encoding was successful. It is.

1st. When the second encoding tables 2 and 3 are viewed as a single encoding table, the output codes are CO~C1
3, and the code length is 1. Second encoding table 2, 3
The final value is the value obtained by adding the code lengths output from the code length data L10 to LL2 and the code length data L2.
0 to L22 are added by an adder 4, and the total code length data LO to L3 is output. In addition, the identification flag F
1 and F2 are ORD) The overall identification flag F is ORed.
Obtain and output.

According to the above configuration, as shown in FIG.
6 are Huffman encoded with a maximum code length of 7 bits, so encoding can be performed using only the first encoding table 2. For example, for input of original data 6, encoded data CO to C6 are 1111110 and code length data L
IO~L12 is 1'1l (7) and identification flag F1 is 1
is output. Here, if the original data 7 to 15 are Huffman encoded, their maximum code length will exceed 7, so they will not be encoded in the first encoding table 2 and the identification flag F1 will be output as 0. do.

Then, the second encoding table 3 contains 7 to 1 of the original data.
5 is the current data 7 because the identification flag Fl is O.
.about.15 detects that it has not been encoded in the first encoding table 2. As a result, the second encoding table 3 inputs original data 7 to 15, and as shown in FIG.
~C13 is 1111110 and code length data L20~L
22 is output as 111(7), and the identification flag F1 is output as 1. Here, when 14.15 of the original data is Huffman encoded, its maximum code length exceeds 7, so it is not encoded using the second encoding table 3, and the identification flag F1 is
Outputs as 0.

Next, the decoding circuit in this embodiment will be explained with reference to FIG.

In FIG. 3, it is assumed that 5 is a code register that holds input code data, and the first bit of the code is located at the most significant bit.

The code data held in the code register 5 is stored in 1. It is separated into codes for the upper 7 bits created by the second encoding tables 2 and 3, and input to the first and second decoding tables 6 and 7, respectively.

1st. The second decoding table 6.7 contains 4 bits of decoded data and 4 bits of decoded data for input codes CO to C13, respectively.
Bit code length data, 1-bit identification flag Fl,
It outputs F2.

1st. The decoded data and 4-bit code length data output from the second decoding table 6.7 are selected by the data selector 8 and the code length selector 9, respectively, and the output of one of the tables is selected as the decoded data. The selection signal, which is output to the outside, is based on the identification flag F1 output from the first decoding table 6. In this case, if data can be encoded using only the first encoding table 2, that code can be decoded only using the first decoding table 6, and at that time, the identification flag F1 outputs 0. However, the output of the first decoding table 6 is selected as the decoded data and code length by the OR gate that receives the output of the identification flag F1. On the contrary, in a data code that requires two tables 2 and 3 during encoding, the identification flag F1 of the first decoding table 6 is 1 and the second decoding table 6 is The decoded data and code length data of conversion table 7 are selected.

According to the above configuration, as shown in FIG.
When the code 111111000000 is input,
The identification flag F1 of the first decoding table 6 becomes 1,
The decoded data and code length data of the second decoding table 7 are selected as the final decoding and code length outputs, and 8 and 9 are output as the decoding and code length outputs, respectively.

According to the present embodiment described above, the following effects are provided. That is, in the above embodiment, the first. The table capacity of the second table 2, 3 (or 6.7) is 8+8-16 for encoding and 16X16-25 for decoding.
It is 6. On the other hand, it is necessary to achieve the same compression efficiency for the original data O~15. For decoding, a decoding table capacity of 16384 is required.

In other words, according to this embodiment, in order to achieve data compression with the same efficiency, an encoding table of a fixed capacity is used,
Compared to the conventional method, decoding is possible with a decoding table capacity of 256+163841, that is, 1/64.

In the above embodiment, a case has been described in which two encoding tables are used, but it is also possible to use three or more encoding tables and a corresponding decoding table.

〔Effect of the invention〕

As described above, according to the present invention, a plurality of encoding or decoding tables are used, and frequently appearing data is encoded or decoded by referring to one of the encoding or decoding tables, By encoding or decoding data with low frequency of occurrence by referring to multiple encoding or decoding tables described above, highly efficient data can be generated while using a limited number of encoding tables and decoding tables. A data compression device that enables compression can be provided.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of a data compression device according to the present invention applied to encoding, FIG. 2 is a diagram for explaining the operation of the structure of FIG. 1, and FIG. 3 is a diagram showing the same implementation. A configuration diagram showing an example applied to decoding, FIG. 4 is a diagram for explaining the effect of the configuration in FIG. 6 is a diagram showing a Huffman encoding method, FIG. 7 is a diagram showing a decoding method of encoded data, and FIG. 8 is a diagram showing a conventional example. 1... Data register, 2, 3... first and second encoding table, 4... adder, 5... code register, 6.7... first and second decoding table, 8.・・・
Data selector, 9... code length selector. Applicant's representative Patent attorney Takehiko Suzue Figure 5 Figure 6 Figure 7 Figure 8

Claims (1)

[Claims] A data compression device that encodes or decodes data using a predetermined encoding or decoding method using the statistical properties of digital data generation, which uses multiple encoding or decoding tables to Data is encoded or decoded with reference to one of the above encoding or decoding tables, and data with low appearance frequency is encoded or decoded with reference to multiple of the above encoding or decoding tables. A data compression device characterized by decoding.