Editing Range coding (section)

'''Range coding''' (or '''range encoding''') is an [[entropy coding]] method defined by G.&nbsp;Nigel&nbsp;N.&nbsp;Martin in a 1979 paper,<ref name=compressconsult>[http://www.compressconsult.com/rangecoder/#download G.&nbsp;Nigel&nbsp;N.&nbsp;Martin, ''Range encoding: An algorithm for removing redundancy from a digitized message''], Video & Data Recording Conference, [[Southampton]], UK, July 24–27, 1979.</ref> which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976.<ref>"Source coding algorithms for fast data compression" Richard Clark Pasco, Stanford, CA 1976</ref> Given a stream of symbols and their probabilities, a range coder produces a space-efficient stream of bits to represent these symbols and, given the stream and the probabilities, a range decoder reverses the process.

Range coding is very similar to [[arithmetic coding]], except that coding is done with digits in any base, instead of with bits, and so it is faster when using larger bases (e.g. a [[byte]]) at small cost in compression efficiency.<ref>"[http://people.xiph.org/~tterribe/notes/range.html On the Overhead of Range Coders]", Timothy B. Terriberry, Technical Note 2008</ref> After the expiration of the first (1978) arithmetic coding patent,<ref>{{US patent|4122440}} — (IBM) Filed March 4, 1977, Granted 24 October 1978 (Now expired)</ref> range coding appeared to clearly be free of patent encumbrances. This particularly drove interest in the technique in the [[open source]] community. Since that time, patents on various well-known arithmetic coding techniques have also expired.