Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Patent
1986-09-15
1990-01-02
Shoop, Jr., William M.
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
341 51, 358426, H03M 730
Patent
active
048916439
ABSTRACT:
A data compression/de-compression system includes a first arithmetic coding encoder, characterized by a first set of encoding conventions, which encoder generates a code stream that points to an interval along a number line in response to decision event inputs. The code stream can be adjusted to point to the same interval as code streams generated by one or more other arithmetic coding encoders characterized by encoding conventions differing in some way from those in the first set. In a binary context, optimal hardware encoders increment or decrement the value of the code stream in response to each occurrence of a more probable decision event while optimal software so changes the code stream value for each occurrence of a less likely event. According to the invention, the code streams for optimal hardware encoders and optimal software encoders are made either identical or compatible to enable similar decoding for each. Identical or compatible code streams are obtained from encoders having different event sequence or symbol ordering along intervals on the number line. Moreover, various hardware and software decoders--with respective symbol ordering and other conventions--can be used in conjunction with encoders having respective conventions, wherein each decoder retrieves the same sequence of decisions for a code stream pointing to a given interval. In both encoding and decoding, the present invention overcomes finite precision problems of carry propagation and borrow propagation by handling data in bytes and bit stuffing at byte boundaries and by pre-borrowing as required.
REFERENCES:
patent: 4028731 (1977-06-01), Arps et al.
patent: 4122440 (1978-10-01), Langdon, Jr. et al.
patent: 4168513 (1979-09-01), Hains et al.
patent: 4259693 (1981-03-01), Aaron et al.
patent: 4286256 (1981-08-01), Langdon, Jr. et al.
patent: 4295125 (1981-10-01), Langdon, Jr.
patent: 4363036 (1982-12-01), Subramaniam
patent: 4369463 (1983-01-01), Anastassiou et al.
patent: 4462081 (1984-07-01), Lehan
patent: 4463342 (1984-07-01), Langdon, Jr. et al.
patent: 4467317 (1984-08-01), Langdon, Jr. et al.
patent: 4494108 (1985-01-01), Langdon, Jr. et al.
patent: 4516241 (1985-05-01), Farah et al.
patent: 4540973 (1985-09-01), Grallert
patent: 4558302 (1985-12-01), Welch
patent: 4577314 (1986-03-01), Chu et al.
patent: 4584561 (1986-04-01), Bernardson
patent: 4596024 (1986-06-01), Thomson
patent: 4633490 (1986-12-01), Goertzel et al.
J. Rissanen, G. G. Langdon, Jr.,-Arithmetic Coding, RJ2174, 1/88.
F. Barsi, P. Maestrini, Arithmetic Codes in Residue Number Systems, Digital Processes, 1978.
I. M. Boyarinov, G. A. Kabatyanskii, Iterative Arithmetic Independent-Error-Correcting Codes, Probl. Peredachi Inf. (USSR).
J. Rissanen-Combinatorial Coding, Conditional Entropy, and Distance for Sequences, Feb. 1975, RJ 1538.
G. N. N. Martin, Range Encoding: An Algorithm for Removing Redundancy from a Digitised Message.
J. Rissanen-Arithmetic Coding of Strings, Jun. 1975, RJ 1591.
J. Rissanen, G. G. Langdon, Jr., Arithmetic Coding, IBM Journal of Res. & Dev., vol. 23, No. 2.
F. Rubin, Arithmetic Stream Coding Using Fixed Precision Registers, IEEE, 11/79.
G. G. Langdon, Jr., J. J. Rissanen, Integer-Length Arithmetic Code for Conditional Binary Sources, IBM TDB, vol. 22, No. 10.
G. G. Langdon, Jr., Method for Carry-Over Control in a FIFO Arithmetic Code String, IBM TDB, vol. 23, No. 1, 6/80.
D. G. Abraham, Parallel Compression by Table Look-Up, IBM TDB, vol. 23, No. 7A, 12/80.
D. R. Helman, G. G. Langdon, Jr., J. J. Rissanen, Arithmetic Compression Code Control Parameter Approximation, IBM TDB, vol. 23, No. 11, 4/81.
G. G. Langdon, Jr., Apparatus Supporting Half-Duplexed Encoding/Decoding Action, IBM TDB, vol. 23, No. 11, 4/81.
G. G. Langdon, Jr., J. J. Rissanen, S. J. P. Todd, K. Y. Wong, Encryption Properties of Arithmetic Codes, IBM TDB, vol. 23, No. 11, 4/81.
R. B. Arps, G. G. Langdon, Jr., LIFO Arithmetic Compression Coding Method for Conditional Sources, IBM TDB, vol. 23, No. 11, 4/81.
G. G. Langdon, Jr., Tutorial on Arithmetic Coding, Computer Science Research Report, RJ3128, 5/6/81.
C. B. Jones, An Efficient Coding System for Long Source Sequences, IEEE, vol. 27, No. 3, 5/81.
G. G. Langdon, Jr., Table-Driven Decoder Involving Prefix Codes, IBM TDB, vol. 23, No. 12, 5/81.
G. G. Langdon, Jr., J. Rissanen, Compression of Black-White Images with Arithmetic Coding, IEEE, vol. 29, No. 6, 1981.
G. G. Langdon, Jr., J. J. Rissanen, Computational Speed Enhancement by Selective Precision in Arithmetic Code Operations, IBM TDB, vol. 24, No. 2, 7/81.
G. G. Langdon, Jr., Constrained Channel Coding Using a Reduced Number of Arithmetic String Coding Steps Per Cycle, IBM TDB, vol. 24, No. 8, 1/82.
G. G. Langdon, Jr., J. J. Rissanen, An Adaptive File Compression Algorithm, RJ3460, 4/23/82.
G. G. Langdon, Jr., S. J. P. Todd, General Unit-Time Arithmetic Codes for Constrained Channels, IBM TDB, vol. 25, No. 3A, 8/82.
G. G. Langdon, Jr., S. J. P. Todd, Augend Computation for Arithmetic Channel Codes, IBM TDB, vol. 25, No. 3A, 8/82.
R. B. Arps, J. M. Cheng, G. G. Langdon, Jr., Control Character Insertion Into Arithmetically Encoded Strings, IBM TDB, vol. 25, No. 4, 9/82.
G. G. Langdon, Jr., S. J. P. Todd, Method for Application of ECC to Constrained Channels, IBM TDB, vol. 25, No. 3A, 8/82.
G. G. Langdon, Jr., J. Rissanen, A Simple General Binary Source Code, IEEE, vol. 28, No. 5, 1982.
G. Nigel, N. Martin, G. G. Langdon, Jr., S. J. P. Todd, Arithmetic Codes for Constrained Channels, IBM J. Res. Dev., vol. 27, No. 2, 3/83.
S. J. P. Todd, G. G. Langdon, Jr., G. N. N. Martin, A General Fixed Rate Arithmetic Coding Method for Constrained Channels, IBM J. Res. Dev., vol. 27, No. 2, 3/83.
G. G. Langdon, Jr., A Note on the Ziv-Lempel Model for Compressing Individual Sequences, IEEE, 1983, vol. 29, No. 2.
G. G. Langdon, P. H. Siegel, S. Todd, Constrained Channel Coding with Spectral Null, IBM TDB, vol. 26, No. 5, 10/83.
G. G. Langdon, Jr., An Adaptive Run-Length Coding Algorithm, IBM TDB, vol. 26, No. 7B, 12/83.
G. G. Langdon, Jr., An Introduction to Arithmetic Coding, IBM J. Res. Develop., vol. 28, No. 2, 3/84.
D. Mahlab, Complexity of Data Compression Algorithms, IEEE (Israel), Mar. 1985.
H. Morita, K. Fujimoto, S. Kitada, S. Arimoto, On Efficiency of Binary Arithmetic Codes, Trans. Inf. Process. Soc. Jpn., vol. 25, No. 4, 1984.
Mitchell Joan L.
Pennebaker William B.
Block Marc A.
Dowd Thomas P.
International Business Machines - Corporation
Shoop Jr. William M.
Young Brian K.
LandOfFree
Arithmetic coding data compression/de-compression by selectively 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 data compression/de-compression by selectively, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic coding data compression/de-compression by selectively will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1386295