US5546080A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Order-preserving, fast-decoding arithmetic coding arithmetic coding and compression method and apparatus
Assignee: International Business Machines Corp
•
Filing: 1994-01-03
•
Granted: 1996-08-13
•
Expires: 2014-01-03
Abstract
Abstract An efficient, fast-decoding, order-preserving, easily implementable, length-based (L-based) arithmetic coding method, apparatus, and manufacture for an m-ary alphabet {1, . . . , i, . . . , m} is provided. A coding method in accordance with the invention combines recursive division of intervals on a number line into sub-intervals whose lengths are proportional to symbol probability and which are ordered in lexical order with the constraint that probabilities be estimated as negative powers of two (1/2, 1/4, 1/8, etc.). As a consequence, the advantageous preservation of lexical order and computational efficiency are both realized. Also, a coding system in accordance with the invention is simple to implement, and high speed operation is achieved, because shifts take the place of multiplications. A coding apparatus in accordance with the invention preferably includes either a single decoding table to achieve fast decoding, or two decoding tables to achieve fast decoding as well as order preservation. The decoding process can conveniently be performed by constructing a decoding table for the C register. The C register is initialized with the leading bits of the codestring. The decoded symbol is the symbol i, i being the greatest integer that makes the C-register value greater than or equal to P(i).
Inventors
- 👤 Glen G. Langdon, Jr.
- 👤 Ahmad Zandi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 04:45
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
220 words
An apparatus for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the apparatus comprising: an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; means for encoding a symbol, the means for encoding including: (i) means for producing a numerical representation of the symbol, (ii) means for adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) means for left-shifting the sum to renormalize; and means for decoding a symbol from a code string, the means for decoding including: (i) means for identifying a coded symbol from at least one most significant bit of the code string, (ii) means for determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) means for obtaining the decoded symbol from the code string by means of the augend determined by the means for determining.
Claim 2
Independent Claim
220 words
An apparatus for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the apparatus comprising: an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; means for encoding a symbol, the means for encoding including: (i) means for producing a numerical representation of the symbol, (ii) means for adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) means for left-shifting the sum to renormalize; and means for decoding a symbol from a code string, the means for decoding including: (i) means for identifying a coded symbol from at least one most significant bit of the code string, (ii) means for determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) means for obtaining the decoded symbol from the code string by means of the augend determined by the means for determining.
Claim 3
Dependent Claim
40 words
An apparatus as recited in claim 1 wherein the means for decoding includes means for obtaining the decoded symbol from the identified coded symbol by identifying the largest cumulative probability whose value is less than that of the coded symbol.
Claim 4
Dependent Claim
35 words
An apparatus as recited in claim 1, wherein the means for decoding includes an inverse table containing respective decoded symbols which are addressible by respective index values which correspond with coded symbols of the alphabet.
Claim 5
Independent Claim
211 words
A method for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the method being for use with a coding and processing system including an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; the method comprising the steps of: encoding a symbol by: (i) producing a numerical representation of the symbol, (ii) adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) left-shifting the sum to renormalize; and decoding a symbol from a code string by: (i) identifying a coded symbol from at least one most significant bit of the code string, (ii) determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) obtaining the decoded symbol frown the code string by means of the augend determined in the step of determining.
Claim 6
Independent Claim
211 words
A method for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the method being for use with a coding and processing system including an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; the method comprising the steps of: encoding a symbol by: (i) producing a numerical representation of the symbol, (ii) adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) left-shifting the sum to renormalize; and decoding a symbol from a code string by: (i) identifying a coded symbol from at least one most significant bit of the code string, (ii) determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) obtaining the decoded symbol frown the code string by means of the augend determined in the step of determining.
Claim 7
Dependent Claim
38 words
A method as recited in claim 4 wherein the step of decoding includes obtaining the decoded symbol from the identified coded symbol by identifying the largest cumulative probability whose value is less than that of the coded symbol.
Claim 8
Dependent Claim
40 words
A method as recited in claim 4, wherein the step of decoding includes identifying a coded symbol using an inverse table containing respective decoded symbols which are addressible by respective index values which correspond with coded symbols of the alphabet.
Claim 9
Dependent Claim
268 words
A computer program product for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the computer program product being for use with a coding and processing system, the computer program product comprising: a computer-readable recording medium; means, recorded on the recording medium, for directing the coding and processing system to maintain an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; means, recorded on the recording medium, for directing the coding and processing system to encode a symbol by performing the steps of: (i) producing a numerical representation of the symbol, (ii) adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) left-shifting the sum to renormalize; and means, recorded on the recording medium, for directing the coding and processing system to decode a symbol from a code string by performing the steps of: (i) identifying a coded symbol from at least one most significant bit of the code string, (ii) determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) obtaining the decoded symbol from the code string by means of the augend determined by the step of determining.
Claim 10
Dependent Claim
268 words
A computer program product for coding and decoding symbols of an alphabet, the alphabet having a predetermined order for the symbols, the computer program product being for use with a coding and processing system, the computer program product comprising: a computer-readable recording medium; means, recorded on the recording medium, for directing the coding and processing system to maintain an augend table containing, for each respective symbol, a respective augend having a value related to a cumulative probability of all symbols of the alphabet which precede the respective symbol in the predetermined order, the cumulative probability being based on approximations, to negative powers of 2, of probabilities of the symbols of the alphabet which precede the respective symbol; means, recorded on the recording medium, for directing the coding and processing system to encode a symbol by performing the steps of: (i) producing a numerical representation of the symbol, (ii) adding the numerical representation to the augend whose value is related to the cumulative probability of the symbols which precede the symbol to be encoded, to produce a sum, and (iii) left-shifting the sum to renormalize; and means, recorded on the recording medium, for directing the coding and processing system to decode a symbol from a code string by performing the steps of: (i) identifying a coded symbol from at least one most significant bit of the code string, (ii) determining which of the augends of the augend table was added to the symbol to produce the coded symbol, and (iii) obtaining the decoded symbol from the code string by means of the augend determined by the step of determining.
Claim 11
Dependent Claim
56 words
A computer program product as recited in claim 7 wherein the means for directing to decode includes means, recorded on the recording medium, for directing the coding and processing system to obtain the decoded symbol from the identified coded symbol by identifying the largest cumulative probability whose value is less than that of the coded symbol.
Claim 12
Dependent Claim
54 words
A computer program product as recited in claim 7, wherein the means for directing to decode includes means, recorded on the recording medium, for directing the coding and processing system to maintain an inverse table containing respective decoded symbols which are addressible by respective index values which correspond with coded symbols of the alphabet.
References Cited (Backward Citations)
US3883847A
Cited
US4122440A
Cited
US4286256A
Cited
US4488143A
Cited
US4464650A
Cited
US4494108A
Cited
US4672539A
Cited
US4652856A
Cited
US4891643A
Cited
US4905297A
Cited
EP0350439A2
Cited
US4989000A
Cited
US4929946A
Cited
US5142283A
Cited
US5010344A
Cited
US5418532A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-13 | 2000-02-12 | 2000-08-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-13 | 2004-02-12 | 2004-08-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-13 | 2008-02-12 | 2008-08-13 | $7700.00 | Window Closed / Lapsed |