Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Patent
1996-02-29
1999-02-02
Young, Brian
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
341 67, H03M 742
Patent
active
058671145
ABSTRACT:
A method and apparatus are disclosed for performing data compression on raw uncompressed data. The method develops a semi-adaptive modeler that sub-divides the length of an input data file into blocks of fixed size. The blocks are then sub-divided into sub-blocks in which the frequencies of the symbols are mapped to occupy the whole frequency space. The modeler is then used to develop a reduced complexity implementation of arithmetic coding, whereby, the time consuming divide operation used in computing the symbols' true probabilities is replaced by a simple shift operation. The reduced complexity arithmetic coder is referred to as approximate arithmetic coder. The modeler and the approximate arithmetic coder are then used in a multi-step data compression system that employs a ZL coder. The multi-step method results in high efficiency data compression systems that are ideal for real time operations and are better suited for network communications or data storage systems. The method overcomes many of the difficulties found in the prior art and generally achieves better compression ratios.
REFERENCES:
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5227789 (1993-07-01), Barry et al.
patent: 5235613 (1993-08-01), Brown et al.
patent: 5293379 (1994-03-01), Carr
Ziv J. and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977, pp. 337-343.
Witten I. H. et al., "Arithmetic Coding for Data Compression", Comm. ACM, 30, No. 6, pp. 520-540, Jun. 1987.
Moffat A., "Linear Time Adaptive Arithmetic Coding", IEEE Trans. Info. Theory, vol. 36, No. 2, pp. 401-406, Mar. 1990.
Welch T. A, "A Technique for High-Performance Data Compression", IEEE Computer, pp. 8-19, Jun. 1984.
Barbir A., "A New Fast Approximate Arithmetic Coder", 28th IEEE SSCT, Baton Rouge, LA , Mar. 31-Apr. 2, 1996.
Nelson M., The Data Compression Book, 1992, pp. 123-148, M & T Books, 115 West 18th Street, New York, New York 10011.
Howard P.G. and J.S. Vitter, "Analysis of Arithmetic Coding for Data Compression", Proceeding Data Compression Conference, pp. 3-12, Apr. 8-11, 1991.
Neal R.M., "Fast Arithmetic Cding Using Low-Precision Division", Manuscript, 1987.
Ziv J. and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding", IEEE Transactions on Information Theory, vol. IT-24, pp. 530-536, Sep., 1978.
Huffman D. A., "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., pp. 1098-1101 (date unknown).
Rissanen J.J., "Generalized Kraft Inequality and Arithmetic Coding", IBM Journal Research Development, May 1976, pp. 198-203.
Harris John D.
Jean-Pierre Peguy
Mitel Corporation
Young Brian
LandOfFree
Method and apparatus for performing data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1121190