Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
1999-04-29
2001-02-13
Santamauro, Jon (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
C341S067000
Reexamination Certificate
active
06188338
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for data compression, and more particularly to a technique for data compression using Huffman coding.
2. Discussion of the Related Art
Generally, when communicating or storing data, data quantity can be reduced using data compression techniques. Huffman coding is a typical example of such data compression technique.
The Huffman code is a publicly known technique discussed in “Document Data Compression Algorithm Guide”, Uematsu, CQ Publishing Company, pp. 46-51, for example. Roughly speaking, in Huffman coding, data is compressed by assigning a short code to frequently generated symbols and a long code to symbols that are only occasionally generated. An example of Huffman code is shown in FIG.
8
.
The following are the two essential conditions for rendering Huffman codes effective:
(1)the appearance probability of each symbol is already known; and
(2)the appearance probability of each symbol is stationary. Condition (1) is based upon the fact that the generation of Huffman codes depends on the appearance probability of each symbol, and condition (2) is based upon the fact that Huffman coding uses a fixed code table. However, since it is necessary to perform a statistical process on the input data before coding in order to satisfy condition (1), the processing load becomes heavy. Also, condition (2) cannot be satisfied by general data.
In view of the above circumstances, a technique to update Huffman codes at appropriate intervals has been suggested, as is disclosed by Japanese Laid-Open Patent Application No. 7-7436, for example. With this method, condition (1) becomes unnecessary since codes are designed according to the statistics of the data coded immediately before. As for condition (2), a moderate variation is allowed since the optimum code is used at every updating interval.
FIGS. 9 and 11
are block diagrams respectively illustrating a coding apparatus and a decoding apparatus of the prior art.
As shown in
FIG. 9
, a data inputting unit
10
sends an input data
100
to a frequency counting unit
20
. The frequency counting unit
20
counts the appearance frequency of symbols contained in the input data
100
and outputs the result to a code assigning unit
40
as a frequency data
110
. The code assigning unit
40
generates a code word data
141
based upon the frequency data
110
and stores it in a code word memory
60
. A Huffman coder
70
performs a Huffman coding upon the input data
100
using the code word data
141
, and sends the resulting data to a code outputting unit
80
as a code data
151
. The code data outputting unit
80
outputs the code data
151
.
In
FIG. 11
, the parts similar to those in
FIG.9
have the same reference numbers and perform the same functions, and therefore are not discussed in detail.
A code data inputting unit
15
sends the code data
151
to a Huffman decoder
75
. The Huffman decoder
75
performs a Huffman decoding upon the code data
151
using the code word data
141
, and outputs the result to a data outputting unit
85
as the input data
100
. The data outputting unit
85
outputs the input data
100
to an external device.
FIGS. 10 and 12
are flow charts respectively illustrating the coding and decoding operations of the prior art.
As shown in
FIG. 10
, in step
10
, the frequency counting unit
20
counts each type of symbols contained in the input data
100
to obtain the frequency data
110
. In step
211
, it is determined whether the frequency data
110
satisfies a predetermined condition for the process of updating the code table at that time. If it does, the process proceeds to step
212
, and to step
30
if not. In step
212
, the code assigning unit
40
generates the Huffman code based upon the frequency data
110
to obtain the code word data
141
. In step
30
, the Huffman coder
70
performs a Huffman coding upon the input data
100
using the code word data
141
. In step
40
, it is determined whether any unprocessed input data
100
remains. The coding process is complete if there is no unprocessed input data
100
remaining. Otherwise, the process returns to step
10
.
In
FIG. 12
, the processes similar to those in
FIG. 10
have the same reference numbers and perform the same functions, and therefore are not discussed in detail.
In the above, the codes have the same initial value in the coding and decoding processes. General purpose codes or specially designed codes may also be used as input data. In the latter case, it is necessary to identify the code table to the decoding side by assigning the code table to the header of the code data.
The conditions for updating the code table in step
211
are arbitrary. Japanese Laid-Open Patent Application No. 7-7436, for example, is suggested particularly for application to moving image data, and the code table is updated for every frame.
The Huffman code generating algorithm in step
212
is publicly known and is discussed in “Document Data Compression Algorithm Guide”, Uematsu, CQ Publishing Company, for example, and therefore is not discussed here in detail. Generally, in a Huffman code generating algorithm, symbols are sorted by their appearance probabilities. Two symbols having low probabilities are combined to generate a new symbol. This process is repeated while codes are assigned to the symbols.
In the above discussed method, it is preferred that the code table be updated for every unit in which the distribution of the appearance probabilities of the input symbols is stationary. Therefore, updating intervals are preferred to be as short as possible, as long as sufficient statistics for presuming the distribution of the appearance probabilities of each symbol can be obtained. If the conditions are applied to static image data, similarities among the distribution of the appearance probabilities of each symbol cannot be expected, and therefore it becomes effective to update the code table within an image data.
The Huffman code generation of step
212
frequently uses a sorting process, and therefore shortening the updating intervals of the code table leads to an increase in the process load of the coding process.
A method disclosed by Japanese Laid-Open Patent Application No. 63-232626 aims to solve the above problem by generating a simplified Huffman code by rearranging the symbols in the appearance probability order and writing them in the code table prepared in advance. With this method, the process load of Huffman code generation is reduced since the sorting process is required only once.
The problem with this method, however, is that an efficient reduction of the code quantity is not assured. Even when the symbols are sorted in the appearance probability order, there are many possible distribution patterns of the appearance probabilities, and there is no assurance that the optimum codes will be generated.
SUMMARY OF THE INVENTION
The present invention has been made in view of the above circumstances and with an aspect to provide a coding method for easily generating an adaptive compressed code such as a Huffman code. Furthermore, the present invention has an aspect to provide an optimum coding technique when implementing on hardware.
A coding apparatus according to the present invention includes a data inputting element that inputs data containing a plurality of symbols to be coded, and a frequency counting element that counts an appearance frequency of each dominant symbol candidate previously selected from a set of symbols included in the input data, and a symbol selecting element that selects a dominant symbol from the dominant symbol candidates based upon the appearance frequency. The coding apparatus further includes a fixed code word storing element that stores a fixed code word, the fixed code word being predetermined according to a predicted appearance frequency of the corresponding symbol, a code assigning element that generates a new code word for the dominant symbol and a combined code word of a code word indicating that it is a no
Fuji 'Xerox Co., Ltd.
Oliff & Berridg,e PLC
Santamauro Jon
LandOfFree
Coding apparatus, decoding apparatus and methods applied... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Coding apparatus, decoding apparatus and methods applied..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding apparatus, decoding apparatus and methods applied... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2596122