Arithmetic Coding - US Patents

US Patents

A variety of specific techniques for arithmetic coding have historically been covered by US patents, although various well-known methods have since passed into the public domain as the patents have expired. Techniques covered by patents may be essential for implementing the algorithms for arithmetic coding that are specified in some formal international standards. When this is the case, such patents are generally available for licensing under what is called "reasonable and non-discriminatory" (RAND) licensing terms (at least as a matter of standards-committee policy). In some well-known instances (including some involving IBM patents that have since expired) such licenses were available free, and in other instances, licensing fees have been required. The availability of licenses under RAND terms does not necessarily satisfy everyone who might want to use the technology, as what may seem "reasonable" for a company preparing a proprietary software product may seem much less reasonable for a free software or open source project.

At least one significant compression software program, bzip2, deliberately discontinued the use of arithmetic coding in favor of Huffman coding due to the perceived patent situation at the time. Also, encoders and decoders of the JPEG file format, which has options for both Huffman encoding and arithmetic coding, typically only support the Huffman encoding option, which was originally because of patent concerns; the result is that nearly all JPEG images in use today use Huffman encoding although JPEG's arithmetic coding patents have expired due to the age of the JPEG standard (the design of which was approximately completed by 1990). There are some archivers like PackJPG, that can losslessly convert Huffman encoded jpegs to jpegs with arithmetic coding (with custom file name .pjg), showing up to 25% size saving.

Some US patents relating to arithmetic coding are listed below.

• U.S. Patent 4,122,440 — (IBM) Filed 4 March 1977, Granted 24 October 1978 (Now expired)
• U.S. Patent 4,286,256 — (IBM) Granted 25 August 1981 (Now expired)
• U.S. Patent 4,467,317 — (IBM) Granted 21 August 1984 (Now expired)
• U.S. Patent 4,652,856 — (IBM) Granted 4 February 1986 (Now expired)
• U.S. Patent 4,891,643 — (IBM) Filed 15 September 1986, granted 2 January 1990 (Now expired)
• U.S. Patent 4,905,297 — (IBM) Filed 18 November 1988, granted 27 February 1990 (Now expired)
• U.S. Patent 4,933,883 — (IBM) Filed 3 May 1988, granted 12 June 1990 (Now expired)
• U.S. Patent 4,935,882 — (IBM) Filed 20 July 1988, granted 19 June 1990 (Now expired)
• U.S. Patent 4,989,000 — Filed 19 June 1989, granted 29 January 1991 (Now expired)
• U.S. Patent 5,099,440 — (IBM) Filed 5 January 1990, granted 24 March 1992 (Now expired)
• U.S. Patent 5,272,478 — (Ricoh) Filed 17 August 1992, granted 21 December 1993 (Now expired)

Note: This list is not exhaustive. See the following link for a list of more patents. The Dirac codec uses arithmetic coding and is not patent pending.

Patents on arithmetic coding may exist in other jurisdictions, see software patents for a discussion of the patentability of software around the world.