Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2003-02-27
2004-07-20
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
C382S247000, C708S205000
Reexamination Certificate
active
06765515
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a normalization processing method used on a coding algorithm of MQ-CODER, which is an arithmetic coding system, and an arithmetic coding/decoding apparatus of the MQ-CODER system.
This application claims priority of Japanese Patent Application No.2002-054574, filed on Feb. 28, 2002, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
As an arithmetic coding system, a coding system called MQ-CODER is known. This MQ-CODER is employed as an arithmetic coding system of JPEG2000 (ISO/IEC JTC 1/SC 29/WG1) or the like. This MQ-CODER coding/decoding algorithm is described in detail, for example, in the following literature:
“Next-Generation Image Coding System JPEG2000,” (Triceps) issued on Feb. 13, 2001; and
“JPEG2000 Part 1 Final Committee Draft Version 1.0,” (SO/IEC JTC 1/SC 29/WG1, JPEG2000 Editor Martin Boliek, Co-editors, Charilaos Christopoulos and Eric Majani) issued on Apr. 11, 2000.
With this MQ-CODER coding/decoding algorithm, renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) are carried out. Renormalization processing in coding (RENORME) is used for the processing on the final stage of LPS coding (CODELPS) and MPS coding (CODEMPS). LPS means less predominant symbol and MPS means more predominant symbol. Renormalization processing in decoding (RENORMD) is used for the processing on the final stage of decoding processing (DECODE). In decoding processing (DECODE), the processing may end without carrying out this renormalization processing in decoding (RENORMD) depending on the results of segmentation and selection processing, which is carried out before renormalization processing in decoding (RENORMD). Also in some cases in coding processing (ENCODE), the processing may end without carrying out renormalization processing in coding (RENORME).
Hereinafter, renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) will be described. The data contents of A, C, BP, B, B1 and CT referred to in renormalization processing in coding (RENORME) and renormalization processing in decoding (RENORMD) are the same as the data contents described in the foregoing literature. The following are the details of the data contents.
A is a value stored in an augend register. It is binary data with a 16-bit length.
C is a value stored in a code register. It is binary data with a 28-bit length.
BP is a pointer of a byte buffer.
B is data of a position indicated by BP of a byte buffer. It is binary data with an 8-bit length.
B1 is data of a position indicated by BP+1 of a byte buffer. It is binary data with an 8-bit length.
CT is a value of a free byte counter for counting free bits. It is binary data with a 4-bit length.
An arithmetic formula “X>>Y” means that right bit shift of binary data X by Y bits is carried out. An arithmetic formula “X<<Y” means that left bit shift of binary data X by Y bits is carried out. “0xXX . . . X” means binary data of hexadecimal expression. X represents hexadecimal numbers 0 to F.
FIG. 3
shows a processing flow of renormalization processing in coding (RENORME).
In renormalization processing in coding (RENORME), first, left bit shift of A and C by 1 bit is carried out and 1 is subtracted from CT (step S
11
).
Then, whether CT is 0 or not is judged (step S
12
). If CT is 0, subroutine processing of byteout processing (BYTEOUT) of step S
13
is carried out. When this subroutine of byteout processing (BYTEOUT) ends, the processing goes to step S
14
. If CT is not 0, the processing goes directly to step S
14
.
Next, arithmetic operation of (A&0x8000) is carried out and whether the result of this arithmetic operation is 0 or not is judged (step S
14
). That is, at step S
14
, whether MSB of A stored in an augend register is 1 or not is judged.
If the result of arithmetic operation at step S
14
is 0, the processing is repeated again from step S
11
. If the result of arithmetic operation is not 0, this flow ends.
In short, in this renormalization processing in coding (RENORME), left bit shift precessing of the value of A stored in the augend register is carried out until the value of A reaches 0x8000 or more.
FIG. 4
shows a processing flow of byteout processing (BYTEOUT) at step S
13
of the above-described renormalization processing in coding (RENORME).
In byteout processing (BYTEOUT), first, whether B is 0xFF or not is judged (step S
21
). If B is 0xFF, the processing goes to step S
27
. If B is not 0xFF, the processing goes to the next step S
22
.
Next, whether C is smaller than 0x8000000 or not is judged (step S
22
). If C is smaller than 0x8000000, the processing goes to step S
26
. If C is equal to or larger than 0x8000000, the processing goes to the next step S
23
.
Next, 1 is added to B (step S
23
).
Next, whether B is 0xFF or not is judged (step S
24
). If B is 0xFF, the processing goes to the next step S
25
. If B is not 0xFF, the processing goes to step S
26
.
Next, arithmetic operation of (C&0x7FFFFFF) is carried out and the result of this arithmetic operation is substituted in C (step S
26
). Then, the processing goes to step S
27
.
At step S
26
, 1 is added to BP and a value obtained by performing right bit shift of C by 19 bits is substituted in B. Then, arithmetic operation of (C&0x7FFFF) is carried out and its value is substituted in C. Then, 8 is substituted in CT.
At step S
27
, 1 is added to BP and a value obtained by performing right bit shift of C by 20 bits is substituted in B. Then, arithmetic operation of (C&07FFFFF) is carried out and its value is substituted in C. Then, 7 is substituted in CT.
In byteout processing (BYTEOUT), as the processing of step S
26
or step S
27
ends, the subroutine processing ends.
FIG. 5
shows a processing flow of renormalization processing in decoding (RENORMD).
In renormalization processing in decoding (RENORMD), first, whether CT is 0 or not is judged (step S
31
). If CT is 0, the processing goes to the subroutine of bytein processing (BYTEIN) of step S
32
. As this subroutine of bytein processing (BYTEIN) ends, the processing goes to step S
33
. If CT is not 0, the processing goes directly to step S
33
.
Next, left bit shift of A and C by 1 bit is carried out and 1 is subtracted from CT (step S
33
).
Then, arithmetic operation of (A&0x8000) is carried out and whether the result of this arithmetic operation is 0 or not is judged (step S
34
). That is, at step S
34
, whether MSB of A stored in an augend register is 1 or not is judged.
If the result of arithmetic operation at step S
34
is 0, the processing is repeated again from step S
31
. If the result of arithmetic operation is not 0, this flow ends.
In short, in this renormalization processing in decoding (RENORMD), left bit shift precessing of the value of A stored in the augend register is carried out until the value of A reaches 0x8000 or more.
FIG. 6
shows a processing flow of bytein processing (BYTEIN) at step S
32
of the above-described renormalization processing in decoding (RENORMD).
In bytein processing (BYTEIN), first, whether B is 0xFF or not is judged (step S
41
). If B is 0xFF, the processing goes to the next step S
42
. If B is not 0xFF, the processing goes to step S
45
.
Next, whether B1 is larger than 0x8F or not is judged (step S
42
). If B1 is larger than 0x8F, the processing goes to step S
43
. If B1 is equal to or smaller than 0x8F, the processing goes to the next step S
44
.
At step S
43
, 1 is added to BP, and C is added to a value obtained by performing right left bit shift of B by 9 bits. The result of this addition is substituted in C. Then, 7 is substituted in CT.
At step S
44
, 0xFF00 is added to C and the result of this addition is substituted in C. Then, 8 is substituted in CT.
At step S
45
, 1 is added to BP, and C is added to a value obtained by performing right left bit shift of B by 8 bits. The result of this addition is substituted in C. Then, 8 is substituted in CT.
In bytein processing (BYTEIN), as t
Frommer William S.
Frommer & Lawrence & Haug LLP
Wamsley Patrick
LandOfFree
Arithmetic coding/decoding apparatus of MQ-Coder system and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic coding/decoding apparatus of MQ-Coder system and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic coding/decoding apparatus of MQ-Coder system and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219949