Approximated multi-symbol arithmetic coding method and apparatus

Details Approximated multi-symbol arithmetic coding method and apparatus Approximated multi-symbol arithmetic coding method and apparatus

1995-12-11

1998-06-30

Young, Brian K.

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

H03M 700

Patent

active

057740810

ABSTRACT:
A method and apparatus for compressing and decompressing data is described. The most frequent symbols (A-Group.) are encoded using an Arithmetic Code, then the remainder of the symbols (H-Group) are first encoded using Huffman's algorithm (or any Prefix code) and then combined with the Arithmetic code resulting in a hybrid Arithmetic/Huffman code. After being encoded into a Huffman code, the H-Group symbols are made into a "super-symbol" which fits into an Arithmetic subinterval allocated to the symbols in the H-Group. The Arithmetic subintervals for the symbols in the H-Group preferably are a negative power of 2 (e.g., 1/2, 1/4, 1/16, 1/32, etc.) of the code space. Each such H-group subinterval has its own associated subset of H-group symbols comprising one Huffman code table that fits into that respective interval. Decoding in an AMSAC system first treats the code stream as Arithmetically encoded. Standard prior art Arithmetic decoding is performed until an interval assigned to the super-symbol(s) is encountered. The Arithmetic super-symbol for this interval is then processed to obtain the Prefix code by reversing the scaling and offsetting, if any, that was needed to fit the super-symbol into the assigned Arithmetic subinterval. The Prefix code is then decoded into the original symbol using standard prior art Prefix techniques.

REFERENCES:
patent: 5227789 (1993-07-01), Barry et al.
G.G. Langdon, "Adaptation to Binary Sources: Monte Carlo and Q Coder Approaches", IBM Research Journal, Nov. 1990.
R. B. Arps et al., "Control Characte Insertion Into Arithmeically Encoded Strings", IBM Technical Disclosure Bulletin, Sep. 1982, pp. 2051-2052.
D. R. Helman et al., "Statistics Collection For Compression Coding With Randomizing Feature", IBM Technical Disclosure Bulletin, Mar. 1982, p. 4917.
G. G. Langdon, "Embedding Prefix Codes Into Arithmetic Codes", IBM Technical Disclosure Bulletin, May 1984, pp. 5966-5969.
B. L. Marks, "Trimming Of Huffman Coding Tables", IBM Technical Disclosure Bulletin, Oct. 1979, p. 2106.
T. C. Bell et al., Text Compression, Prentice Hall, 1990, pp. 105-112.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., Vo. 40, No. 9, Sep. 1952, pp. 1098-1101.
G. G. Langdon, Jr. et al. "Hardware-Optimized Compression and the Skew Coder LSI Chip", Research Report, Computer Science, Feb. 6, 1992, pp. 1-17.
I. H. Witten et al., "Arithmetic Coding For Data Compression", Communications of the ACM, vol. 30, No. 6, Jun. 1987, pp. 520-540.
G. G. Langdon, Jr., "Compression of Black-White Images With Arithmetic Coding", IEEE Transactions On Communications, vol. COM-29, No. 6, Jun. 1981, pp. 858-867.

Affiliated with

Also associated with

Rating

Approximated multi-symbol arithmetic coding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Approximated multi-symbol arithmetic coding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximated multi-symbol arithmetic coding method and apparatus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1864443