Editing Arithmetic coding (section)

==History and patents==

Basic algorithms for arithmetic coding were developed independently by [[Jorma J. Rissanen]], at [[IBM Research]], and by Richard C. Pasco, a Ph.D. student at [[Stanford University]]; both were published in May 1976. Pasco cites a pre-publication draft of Rissanen's article and comments on the relationship between their works:<ref>{{cite thesis |type=PhD |last=Pasco |first=Richard Clark |date=May 1976 |title=Source coding algorithms for fast data compression |publisher=Stanford Univ|citeseerx=10.1.1.121.3377 }}</ref>
{{blockquote|
One algorithm of the family was developed independently by Rissanen [1976]. It shifts the code element to the most significant end of the accumulator, using a pointer obtained by addition and exponentiation. We shall now compare the alternatives in the three choices, and see that it is preferable to shift the code element rather than the accumulator, and to add code elements to the least significant end of the accumulator.}}

Less than a year after publication, IBM filed for a US [[patent]] on Rissanen's work. Pasco's work was not patented.

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" ([[Reasonable and non-discriminatory licensing|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 for 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 commercial software product may seem much less reasonable for a [[free software]] or [[Open-source software|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<ref>{{cite web|url=http://www.faqs.org/faqs/compression-faq/part1/section-17.html|title=What is JPEG?|website=comp.compression Frequently Asked Questions (part 1/3)}}</ref> although JPEG's arithmetic coding patents<ref>{{cite web |url=http://www.itu.int/rec/T-REC-T.81-200401-I!Cor1/dologin.asp?lang=e&id=T-REC-T.81-200401-I!Cor1!PDF-E&type=items |title=Recommendation T.81 (1992) Corrigendum 1 (01/04) |date=9 November 2004 |work=Recommendation T.81 (1992) |publisher=International Telecommunication Union |access-date=3 February 2011}}</ref> have expired due to the age of the JPEG standard (the design of which was approximately completed by 1990).<ref>{{cite book|title=JPEG Still Image Data Compression Standard|first1=W. B.|last1=Pennebaker|first2=J. L.|last2=Mitchell|publisher=Kluwer Academic Press|year=1992|isbn=0442012721}}</ref> [[JPEG XL]], as well as archivers like PackJPG, Brunsli and Lepton, that can losslessly convert Huffman encoded files to ones with arithmetic coding (or [[asymmetric numeral systems]] in case of JPEG XL), showing up to 25% size saving.

The JPEG [[image compression]] format's arithmetic coding algorithm is based on the following cited patents (since expired).<ref name="t81">{{cite web |title=T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES |url=https://www.w3.org/Graphics/JPEG/itu-t81.pdf |publisher=[[CCITT]] |date=September 1992 |access-date=12 July 2019}}</ref>

* {{US patent|4652856}} – ([[IBM]]) Filed 4 February 1986, granted 24 March 1987 – Kottappuram M. A. Mohiuddin, Jorma Johannes Rissanen – Multiplication-free multi-alphabet arithmetic code
* {{US patent|4905297}} – (IBM) Filed 18 November 1988, granted 27 February 1990 – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannes Rissanen – Arithmetic coding encoder and decoder system
* {{US patent|4935882}} – (IBM) Filed 20 July 1988, granted 19 June 1990 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders
* [https://patents.google.com/patent/JPH02202267A/en JP Patent 1021672] – ([[Mitsubishi Electric|Mitsubishi]]) Filed 21 January 1989, granted 10 August 1990 – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Coding system
* [https://patents.google.com/patent/JPH0834434B2/en JP Patent 2-46275] – (Mitsubishi) Filed 26 February 1990, granted 5 November 1991 – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Coding apparatus and coding method

Other patents (mostly also expired) related to arithmetic coding include the following.

* {{US patent|4122440}} – (IBM) Filed 4 March 1977, granted 24 October 1978 – Glen George Langdon, Jorma Johannes Rissanen – Method and means for arithmetic string coding
* {{US patent|4286256}} – (IBM) Filed 28 November 1979, granted 25 August 1981 – Glen George Langdon, Jorma Johannes Rissanen – Method and means for arithmetic coding utilizing a reduced number of operations
* {{US patent|4467317}} – (IBM) Filed 30 March 1981, granted 21 August 1984 – Glen George Langdon, Jorma Johannes Rissanen – High-speed arithmetic compression coding using concurrent value updating
* {{US patent|4891643}} – (IBM) Filed 15 September 1986, granted 2 January 1990 – Joan L. Mitchell, William B. Pennebaker – Arithmetic coding data compression/de-compression by selectively employed, diverse arithmetic coding encoders and decoders
* [https://patents.google.com/patent/JPS63281524A/en JP Patent 11782787] – ([[NEC]]) Filed 13 May 1987, granted 18 November 1988 – Michio Shimada – Data compressing arithmetic encoding device
* [https://patents.google.com/patent/JPS63314918A/en JP Patent 15015487] – ([[KDDI]]) Filed 18 June 1987, granted 22 December 1988 – Shuichi Matsumoto, Masahiro Saito – System for preventing carrying propagation in arithmetic coding
* {{US patent|4933883}} – (IBM) Filed 3 May 1988, granted 12 June 1990 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders
* {{US patent|4989000}} – (IBM) Filed 19 June 1989, granted 29 January 1991 – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Data string compression using arithmetic encoding with simplified probability subinterval estimation
* {{US patent|5099440}} – (IBM) Filed 5 January 1990, granted 24 March 1992 – William B. Pennebaker, Joan L. Mitchell – Probability adaptation for arithmetic coders
* {{US patent|5272478}} – ([[Ricoh]]) Filed 17 August 1992, granted 21 December 1993 – James D. Allen – Method and apparatus for entropy coding

Note: This list is not exhaustive. See the following links for a list of more US patents.<ref>{{cite web|url=http://www.faqs.org/faqs/compression-faq/part1/|website=comp.compression|title=Frequently Asked Questions}}</ref> The [[Dirac (codec)|Dirac codec]] uses arithmetic coding and is not patent pending.<ref>{{Cite web|url=https://lwn.net/Articles/272520/|title=Dirac video codec 1.0 released [LWN.net]|website=lwn.net}}</ref>

Patents on arithmetic coding may exist in other jurisdictions; see [[software patent]]s for a discussion of the patentability of software around the world.