Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2000-09-11
2002-08-13
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S106000
Reexamination Certificate
active
06433709
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATION
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 11-257986, filed Sep. 10, 1999; the entire contents of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoding for variable length code words, and, more particularly, relates to a decoding method and a decoding apparatus for generating tables and detecting a code length of each code word after coding and for generating an address in the table in which decoded data items are stored, and also relates to a computer readable recording medium in which a decoding program is stored.
2. Description of the Related Art
There is a conventional decoding apparatus for decoding a variable length code word consisting of a definition part and a real data part, as shown in
FIG. 1
, for example. The definition part of the variable length code word includes the number of code words corresponding to each code length and decoded data items corresponding to each code word.
FIG. 1
is a block diagram showing a configuration of the conventional decoding apparatus.
As shown in
FIG. 1
, the conventional decoding apparatus comprises tables T
1
, T
2
, and T
3
, a buffer memory
11
for storing the real data part in the bit stream including variable length code words, a code word separation circuit
12
capable of separating one bit from the real data part stored in the buffer memory
11
, a comparator
13
for comparing an output data item from the code word separation circuit
12
with the data items stored in the table T
3
, and an addition circuit
14
for adding the output from the comparator
3
to an output data item obtained from the table T
2
.
The table T
1
stores the decoded data items included in the definition part that are arranged in smaller order of the codewords. The table T
2
stores the address to be used for searching the table T
1
, and the address indicates a memory field storing the decoded data item for the smallest value in code words having a same code length. In the table T
2
, the code length is used as index. The table T
3
stores the code word of the smallest value in code words having a same code length. In the table T
3
, the code length is also used as index.
There is a following conventional decoding method of decoding variable length code words in JPEG, for example.
At first, the tables T
1
to T
3
are generated by analyzing the definition (see
FIG. 2
) included in the head part of the bit stream.
FIG. 2
shows an example of the definition stored in the head part in which the number of code words having a code length
0
is zero, the number of code words having a code length
2
is two, the number of code words having a code length
3
is one, the number of code words having a code length
4
is two, and the number of code words having a code length
5
is two.
The generation methods of the tables T
1
to T
3
will be explained in detail.
At first, as shown in
FIG. 3
, the code (HUFFCODE(k)) corresponding to each code length (HUFFSIZE(k)) is obtained based on the number of code words. In the example shown in
FIG. 3
, the first code word (as the smallest code) in the code words having the code length
2
is determined as “00”, and the second code word is determined as “0” because the number of code words having the code length
2
is only two. Similarly, the first code (as the smallest code) in the code words having the code length
4
is determined as “1010”, and the second code is determined as “1011” because the number of code words having the code length
4
is also two. In this example, each code is expressed under the binary system. The decoded data item corresponding to each code word is separated from the head part and then stored in the table T
1
. In addition, as shown in
FIG. 4
, the smallest code word in code words having a same code length (namely, per same code length) is stored in the table T
3
according to each code length as index. Further, the first address in the table T
1
in which the decoded data items corresponding to the smallest code word in code words having a same code length are stored is stored in the table T
2
, as shown in FIG.
6
.
An actual decoding process that uses the tables T
1
, T
2
, and T
3
made by the above-described manner can be executed under the following procedures.
FIG. 7
is a flow chart showing the procedures of the conventional decoding method of decoding variable length code words. At first, the bit stream is stored in the buffer memory
11
in first-in order. The value “zero” is set to a register “temp” as an initial value, and the value “1” is set to a counter “i” as an initial value (Step S
301
).
The following operation is then performed by using the counter “i” that indicates a code length.
First, the first bit in the data stored in the buffer memory
11
is read and then added into the end of the register “temp”. Next, the comparator
13
compares the value of the register “temp” with the smallest code word T
3
(i) in code words having the code length “i” (where “i” is a positive integer) (Step S
303
).
The symbol “bits[i]” in
FIG. 7
indicates the “i-th” bit in the codes. Because the maximum code length in JPEG is
16
, these operations are repeated from i=1 to i=16 (Steps S
302
to S
305
). As a result, when it is firstly detected at Step S
303
in this repeating process that the value T
3
(i) is greater than the value of the register “temp”, the code length “leng” becomes “i−1” (Steps S
305
and S
306
). On the other hand, when “i” is not detected in the comparison at Step S
303
, the code length becomes
16
(Step S
305
and S
306
). Thereby, the code word is determined as the “leng” bits from the first bit to the “(i−1)−th” bit (see “leng=i−1 and word=bits[1:i−1]” at Step S
306
). Thus, the code word “word” is expressed by bits[1:i−1] in FIG.
7
.
Then, the address T
2
(leng) in the table T
1
indicating the smallest code word in the code words having the code length “leng” in the table T
1
by referring the table T
2
by using the code length “leng” as index. In addition, an offset (as a difference) from the smallest code word in the same code length can be obtained by subtracting the smallest code word T
3
(leng) having the same code length “leng” from the code word “word” (Step S
307
).
After this step S
307
, the value “addr” of the pointer (hereinafter referred to as pointer “addr”) is calculated by adding the offset “offs” to T
2
(leng) (Step S
308
). The table T
1
is searched by using this pointer in order to obtain the decoded data item corresponding to the code word “word” (Step S
309
).
For example,
FIG. 5
shows the value of each variable at Step S
303
when the first bit in the bit stream is “1011011011101101”. That is, the condition “tem T3(i)” is recognized at Step S
303
when “i”=5 (temp=10110). Thereby, “leng”=5−1=4 is calculated at Step S
306
. Because T3=“1010” when “leng”=4(see
FIG.4
), the offset “offs” becomes 1 (offs=1011−1010=1). The address “addr” of the decoded data item in the table T
1
can be calculated by adding this offset “offs” to the first address T
2
when i=4. The decoded data item is then obtained based on the address “addr”. As shown in
FIG. 6
, the decoded data item “data (V
4
,
1
)” stored in the table T
1
can be obtained by using a new index calculated by adding the offset “offs” to the first address obtained from the table T
2
.
By using the manner described above, the decoding for a code word is completed. When the decoding for the following code word is performed, the decoding apparatus eliminates the data item of the code length “leng” from the buffer memory
11
, or shifts the pointer to the first bit in the following code word to be decoded in order to point the first bit in the following code word.
However, in the conventional decoding appar
Jean-Pierre Peguy
Kabushiki Kaisha Toshiba
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
LandOfFree
Decoding method and decoding apparatus for variable length... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding method and decoding apparatus for variable length..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding method and decoding apparatus for variable length... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2891704