Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2001-08-13
2003-05-20
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S050000, C341S051000, C709S246000
Reexamination Certificate
active
06567019
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a data processing apparatus and method for processing a variable length code with carry signals.
BACKGROUND OF THE INVENTION
Generally, an arithmetic unit in an arithmetic coding unit generates a variable length code each time the arithmetic coding of one symbol is performed, and generates a carry signal such as a carry signal and a borrow signal depending on the contents of computation. At this time, because the code has a variable length, code length information for indicating the length of the generated code is outputted at the same time. The length of the variable length code is between 0 and a certain value N. The value N depends on register length in the arithmetic coding unit, called an augend register or a code interval register (hereinafter referred to as A register).
Typical arithmetic coding systems include the JBIG system standardized by the JBIG (Joint Bi-level Image Experts Group) that is an agent of the ITU (International Telecommunications Union), and the Q-coder proposed by IBM Corporation. In the following description, the arithmetic coding system will not be limited to a specific one, assuming that general arithmetic coding is used. However, technical terms may be used inevitably for convenience of explanation because terms and concepts are not popular, and in this case, the JBIG that is a standard system will be applied.
Whether or not the value of the A register is within a predetermined range is checked (it is usually considered that the value falls within a predetermined range if the value of the most significant bit of this register A is ‘1’) each time arithmetic coding of one symbol is performed, and if the value falls within the range, nothing is done and then arithmetic coding is performed for a next symbol. In this case, the generated code length is 0 bit. In contrast, if the value does not fall within the range, shift processing is performed so that the value of the A register falls within the predetermined range, and at the same time shift processing is performed for a cord register (hereinafter referred to as C register) being a register based on which codes are generated. This is usually referred to as normalization processing (hereinafter referred to as shift processing or normalization processing).
At this time, a shifted bit number is a generated code length, and information shifted out from the C register is a code. Specific examples are shown in
FIGS. 1A
to
1
F.
FIGS. 1A
to
1
F show values of the arithmetic register before and after shift processing. Assume that the lengths of the A register and C register are N+1 bits, respectively, and the values of the respective registers immediately after arithmetic coding (before shift processing) are those shown in FIG.
1
A. In this case, it is determined that the value falls within a predetermined range because the most significant bit of the A register is ‘1’, and thus shift processing is not performed (FIG
1
B), and the generated code length is 0 bit.
Then, assume that the values of the respective registers immediately after arithmetic coding are those shown in FIG.
1
C. In this case, it is determined that the value does not fall within a predetermined range because the most significant bit of the A register is ‘0’, and thus shift processing is performed. For this shift processing, left shifting is carried out until the most significant bit of the A register becomes ‘1’. In the example shown in FIG
1
C, 5-bit left shifting is performed. This 5-bit shifting is also performed for the C register. Thus, a 5-bit code of “10100” is shifted out from the C register, and this code is outputted as a code. When such 5-bit shifting is performed, ‘0’ is added to the lower five bits of the respective registers. As a result, the values of the respective registers after shift processing are those as shown in FIG.
1
D.
Then, assume that the values of the respective registers immediately after arithmetic coding are those in FIG.
1
E. In this case, the value of the A register is the minimum, and the generated code is a N-bit code (upper N bits of the C register). If the value of the A register is smaller than this value, the value equals to ‘0’, and there is no possibility that the most significant bit is ‘1’ with any bit shifting, leading to a breakdown of shift processing. The values of respective registers after shift processing in
FIG. 1E
are those as shown in FIG.
1
F.
In the above description, relationship between the values of registers for use in arithmetic computation and the codes and code lengths generated for the values has been shown.
If information generated in the computation unit is only a variable length code and code length information, the process is simple. If the variable length codes are concatenated seamlessly, and are then cut by a predetermined length, a code of fixed length can be outputted.
A Huffman encoder that is one type of encoders for entropy coding outputs only a variable code and code length information, and thus a code of fixed length can be obtained only with the aforesaid processing. What performs such processing is generally called a (length fixation) packing circuit, and has been used for many years as with the Huffman code. One example of the packing circuit is shown in
FIG. 2
for reference.
FIG. 2
shows the configuration of a general packing circuit for length fixation. The packing circuit shown in
FIG. 2
accepts variable length codes of 0 to 15 bits, couple the codes and output them in 16 bits.
In
FIG. 2
, reference numeral
201
denotes a terminal for inputting variable length codes of 0 to 15 bits, reference numeral
202
denotes a terminal for inputting code length information of 4 bits, reference numeral
203
denotes an adder for adding inputted code length information to the bit number of codes remaining in the packing circuit, reference numeral
204
denotes a carry output of the adder
203
, reference numeral
205
denotes lower a 4-bit output of the adder
203
, reference numeral
206
denotes a D flip-flop for latching the carry output
204
, reference numeral
207
denotes a 4-bit D flip-flop for latching the lower 4-bit output
205
of the adder
203
, reference numeral
208
denotes an output signal of the D flip-flop
206
, reference numeral
210
denotes a barrel shifter for shifting an input variable length code, reference numeral
211
denotes a coupler for concatenating the code remaining in the packing circuit to the input variable length code, reference numeral
212
denotes a 30-bit D flip-flop for latching the codes concatenated by the coupler
211
, and reference numeral
213
denotes a shifter for shifting by 16 bits the concatenated code outputted from the D flip-flop
212
.
Operations of the packing circuit shown in
FIG. 2
will be briefly described below.
First, a hold value of the D flip-flop
207
is cleared to zero by initialization processing. Then, a first variable length code is inputted from the terminal
201
, and is sent straightly to the coupler
211
without being shifted by the barrel shifter
210
, and the input variable length code is at the head of the concatenated code. If the code length of this variable length code is S bits, code length information of the value S is inputted to the terminal
202
at the inputting of the variable length code. The code length information is latched in the D flip-flop
207
via the adder
203
. Thereby, the first variable length code of S bits is captured in the packing circuit.
Then, assume that a variable length code of T bits is inputted. The variable length code inputted from the terminal
201
is shifted by S bits by the barrel shifter
210
, and is sent to the coupler
211
. The coupler
211
couples the T-bit variable length code shifted by S bits to the rear of the first inputted S-bit variable length code, and newly generates a concatenated code of (S+T) bits. The concatenated code is latched in the D flip-flop
212
. On the other hand, the value T being code information is inputted in the terminal
202
LandOfFree
Data processing apparatus and method 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 processing apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3076620