Introduction to arithmetic coding

The explanation of arithmetic coding has been simplified. Especially in this way, it seems that arithmetic coding first calculates the score representing the whole last node with infinite precision, and then converts this score into the final form at the end of coding. Many arithmetic encoders use numerical calculation with priority precision instead of trying to simulate infinite precision, because they know that the decoder can match and round the calculated fraction to the corresponding value under this precision. An example shows that a model should divide the interval [0, 1] into three parts and realize it with 8-bit precision. Note that since the precision is known, the range of binary values we can use is also known.

A process called renormalization makes finite precision no longer the limit of the number of characters that can be encoded. When all values in the range are reduced to a certain value, these values will be sent to the output data. Although the computer can handle the precision of many digits, the number of digits used in coding is less than their precision, so the existing data is shifted to the left and new data bits are added to the right to expand the available data range as much as possible. Note that this result appears in two of the previous three examples. Many different methods used in arithmetic coding are protected by American patents. Some of these patents are the key to the implementation of arithmetic coding algorithms defined in some international standards. In this case, these patents are usually used under a reasonable non-discriminatory (RAND) license agreement (at least as a strategy of the Standards Committee). In some famous cases (including some patents involving IBM), these licenses are free, while in other cases, a certain license fee is charged. The licensing agreement of RAND terms may not satisfy all users who intend to use this technology, because the cost is "reasonable" for a company that intends to produce proprietary software, but unreasonable for free software and open source software projects.

The famous company that has done a lot of pioneering work in the field of arithmetic coding and has many patents is IBM. Some analysts feel that the idea that there is no practical and effective arithmetic coding can be realized without infringing the patents owned by IBM and other companies is just a continuous urban legend in the field of data compression (especially when the effective arithmetic coding has been used for a long time and the original patents begin to expire). However, because the patent law does not provide a "clear boundary" test, it is always worried that the court will find a special application for patent infringement, and with the detailed review of the patent scope, it will be found that a bad ruling will bring great losses. However, the patent protection of these technologies has hindered their application. At least one important compression software, bzip2, deliberately stopped using arithmetic coding and switched to huffman encoding for fear of patent status.

The U.S. patents for arithmetic coding are listed below.

Patent 4,122,440-(IBM) was submitted on March 4, 1977 and approved on March 24, 1978 10 (now expired).

Patent No.4,286,256 —— (IBM) Approval Date 198 1 (may have expired).

Patent 4,467,365,438+07 —— (IBM) Date of approval: 265,438+0,65,438+August 0984 (possibly expired).

Patent No.4,652,856 —— (IBM) Approval Date1Feb. 4, 986 (may have expired)

Patent No.4,891,643-(IBM) was submitted on 1986/09/ 15 and was approved on1990/0102.

Patent No.4,905,297 —— (IBM) Approval Date1Feb. 27th, 990.

Patent No.4,933,883 —— (IBM) Approval Date 12, 1990.

Patent No.4,935,882 —— (IBM) Approval Date 19, 1990.

Patent 4,989,000-(? ) 1989/06/ 19 submitted,1991/0/29 approved.

Patent 5,099,440

Patent 5,272,478-(Ricoh)

Note: This list does not cover all patents. For more patent information, please refer to the following links.

The patent of arithmetic coding may exist in the judicial field of other countries. Please refer to the discussion on worldwide software patentability in Software Patents.