Order-preserving, fast-decoding arithmetic coding arithmetic cod

Details Order-preserving, fast-decoding arithmetic coding arithmetic cod Order-preserving, fast-decoding arithmetic coding arithmetic cod

1994-01-03

1996-08-13

Hoff, Marc S.

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

341 51, H03M 730

Patent

active

055460801

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).

REFERENCES:
patent: 3883847 (1975-05-01), Frank
patent: 4122440 (1978-10-01), Langdon, Jr. et al.
patent: 4286256 (1981-08-01), Langdon, Jr. et al.
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4488143 (1984-12-01), Martin
patent: 4494108 (1985-01-01), Langdon, Jr. et al.
patent: 4652856 (1987-03-01), Mohiuddin et al.
patent: 4672539 (1987-06-01), Goertzel
patent: 4891643 (1990-01-01), Mitchell et al.
patent: 4905297 (1990-02-01), Langdon, Jr. et al.
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 4989000 (1991-01-01), Chevion et al.
patent: 5010344 (1991-04-01), Nagy
patent: 5142283 (1992-08-01), Chevion et al.
patent: 5418532 (1995-05-01), Lei
C. B. Jones, An Efficient Coding System for Long Source Sequences, IEEE Transactions on Information Theory, vol. IT-27, No. 3, pp. 280-291, May 1981.
J. Rissanen and K. M. Mohiuddin, A Multipiliction-Free Multialphabet Arithmetic Code, IEEE Transactions on Communications, vol. 37, No. 2 pp. 93-98, Feb. 1989.
E. N. Gilbert and E. F. Moore, Variable-Length Binary Encodings, BSTJ, vol. 38, pp. 933-967, 1959.
G. G. Langdon et al., A Simple General Binary Source Code, IEEE Trans, vol. IT-28, pp. 800-803, 1982.
G. G. Langdon, Augend-Based Arithmetic Codes and the Golomb Code, IBM Res. Rept. RJ7844, Nov. 1990.
J. Rissanen et al., Universal Modeling and Coding, IEEE Trans. on Information Theory, vol. IT-27, pp. 12-23, Jan. 1981.
Shannon, A Mathematical Theory of Communication, Bell Syst. Tech., Journal vol. 27, pp. 379-423 Jul. 1948.
R. G. Gallager, Variations on A Theme by Huffman, IEEE Trans. Infor. Theory, vol. IT-26, pp. 668-674, Nov. 1978.
G. G. Langdon, An Introduction to Arithmetic Coding, IBm J. Res. Develop., vol. 28, No. 2, pp. 135-149, Mar. 1984.
P. G. Howard et al., Image and Text Compression, Kluwer Academic Publishers, Kluwer Inter. Series in Engn. & Computer Science, pp. 85-112, 1992.
G. G. Langdon, Jr. et al., Compression of Black-White Images with Arithmetic Coding, IEEE Transactions on Communications, vol. COM-29, No. 6, ISSN 0090-6778, pp. 858-867, Jun. 1981.

Affiliated with

Also associated with

Rating

Order-preserving, fast-decoding arithmetic coding arithmetic cod does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Order-preserving, fast-decoding arithmetic coding arithmetic cod, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Order-preserving, fast-decoding arithmetic coding arithmetic cod will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1051651