Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2003-01-15
2004-04-06
JeanGlaude, Jean (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
C341S050000
Reexamination Certificate
active
06717534
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data encoding device and a data decoding device.
2. Description of the Related Art
Basic technical concept for data compression may be embodied in Huffman encoding. In Huffman encoding, a letter with large occurrence frequency is assigned a shorter bit-length code. That is, respective letters are assigned individually recognizable codes such that a letter which occurs less frequently is assigned a longer bit-length code. This basic encoding method is described in detail in “The Data Compression Book, Second Edition” (written by M. Nelson, Jean-LoupGailly, translated by Takeshi Ogihara and Suguru Yamaguchi, published by K. K. Toppan, in March 1996) and is not described here.
In Huffman encoding, the data element (a unit for encoding) to code word (the minimum code unit) ratio is 1:1. That is, one data element correlates to one code word, and one code word correlates to one data element. When employing such an encoding method, correlation between a data element and a code word is generally defined in an encoding table.
In encoding utilizing an encoding table, assignment of code words to data elements can be achieved without much trouble when each encoding data in a series of encoding data is covered by a group of the relatively small number of kinds of data elements. However, for a case wherein a relatively large number of types of data elements are necessary to cover a series of encoding data, the assignment may not be easily achieved because any increase in the number of involved data elements leads to an increase of the number of code words which must be assigned, which in turn results in an enlarging the encoding table. For example, the encoding of twenty-six English alphabets (data elements) requires an encoding table which defines twenty-six code words, while encoding fifty Japanese syllabary characters requires an encoding table which defines fifty code words.
Increasing the number of code words also increases the amount of time and effort required to create a compatible encoding table, and the resulting encoding table will be relatively more difficult to install. Moreover, in an encoding method in which an encoding table is attached to encoded data, an enlarged encoding table may adversely affect the data compression rate.
In light of the above, in order to reduce the size of an encoding table without adversely affecting a compression rate, additional bit technology has conventionally been employed in the standard method promoted by the Joint Photographic Experts Group, or JPEG, which is an international standard image encoding method. In the following, an additional bit technology will be described, while referring to JPEG as an example.
Briefly, JPEG is a technology for compressing data by removing high frequency components in spatial frequency components of a pixel value in image data, such as photographs, and relies on the fact that there is only a small difference in a pixel value between adjacent pixels. During a process of compression, image data is segmented into image blocks each consisting of 8×8 pixels, for example, and frequency components in each image block are subjected to discrete cosine transformation, or DCT, to divide them into DC and AC components.
For DC components, a difference between adjacent image blocks is subjected to Huffman encoding. In Huffman encoding, difference values of DC components are put into groups before encoding. That is, a group of difference values is treated as a data element, or a unit of data encoding, and an encoding table defining correlation between each group and a code word is used in Huffman encoding.
Further, for accurate description of a difference value of each DC component (a current difference value), a difference between a current difference value and the minimum difference value (a group minimum value) which is assigned to the concerned group is added as an additional bit to a Huffman code word. The additional bit may be calculated as follows:
For
current
difference
value
smaller
than
0
(
<
0
)
(
additional
bit
)
=
(
current
difference
value
)
-
(
group
minimum
value
)
For
current
difference
value
equal
to
or
larger
than
0
(
≧
0
)
(
additional
bit
)
=
(
current
difference
value
)
+
(
group
minimum
value
)
+
M
-
1
wherein M is the number of types of data present in the group. This calculation, however, is theoretical. In actuality, a simplified version utilizing the characteristics of an encoding table is used.
In decoding, an encoding table which was referred to in encoding is again referred to in order to specify a relevant group based on a Huffman code word. Then, a difference value of the original DC component is obtained based on the group minimum value of the identified group and the additional bit.
As described above, according to an example of a conventional encoding technology, an encoding table using data groups and additional information (additional bit) for specifying particular data in a data group are utilized to ensure a smaller encoding table.
However, although the above-described conventional encoding technology which utilizes an encoding table using data groups and additional information can improve compression efficiency when occurrence frequencies of the respective data which constitute a group are substantially constant, the technology faces a difficulty when occurrence frequencies of the data are not constant. Problems often arise because improvement of compression efficiency in the latter case requires enlarging the size of the encoding table, and an enlarged coding table is more difficult to install.
In short, in a technology such as JPEG, in which values are grouped, even when it may be possible to handle situations wherein successive values are put into a single group, a situation wherein discrete values are placed in one group may face difficulty. That is, because it is expected in JPEG that a difference value of each DC component will be substantially zero, based on the assumption that a difference in pixel values of adjacent pixels is small, values which are closer to zero may have larger occurrence frequencies, and therefore should be assigned a shorter code word. In such a case, grouping may be possible such that values equal to or smaller than 3 be assigned the shortest code word. However, should values “0.8 to 1.2” have smaller frequency, the values may better e grouped into “0 to 0.8”, “0.8 to 1.2”, and “1.2 to 3” to attain h compression efficiency.
That is, presence of a peculiar value range, such as a value range without successiveness in terms of occurrence frequency or with difficulty in estimation of occurrence frequency, results in a need for increasing the number of data groups and thus entries to an encoding table. Creation and installation of such an enlarged encoding table are difficult to achieve.
SUMMARY OF THE INVENTION
The present invention was conceived in view of the above, and the present invention therefore advantageously provides an improved data encoding device and an improved data decoding device.
According to one aspect of the present invention, there is provided a data encoding device, comprising an encoding table for correlating a data element with a code word such that one data element is correlated with N number of code words and one code word is correlated with one data element, the data element serving as a unit of data encoding, N being an integer larger than zero; a retrieve unit for determining a data element corresponding to each of a series of enco
Fuji 'Xerox Co., Ltd.
JeanGlaude Jean
LandOfFree
Data encoding device and data decoding device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data encoding device and data decoding device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data encoding device and data decoding device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267908