---
title: Range coding
slug: range-coding
qid: 
snapshot: enwiki-001302351303
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1302351303
tags: [109366297, 23118434, 23603337, 23837581, 29176270]
---

# Range coding

> [!note] Provenance
> Snapshot `enwiki-001302351303` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1302351303> · Licensed CC BY-SA 4.0

Range coding (or range encoding) is an entropy coding method defined by G. Nigel N. Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976. 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. After the expiration of the first (1978) arithmetic coding patent, 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.

Range coding (or range encoding) is an entropy coding method defined by G.&nbsp;Nigel&nbsp;N.&nbsp;Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976. 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. After the expiration of the first (1978) arithmetic coding patent, 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. int low = 0; int range = 100000; void Run() { Encode(0, 6, 10); // A Encode(0, 6, 10); // A Encode(6, 2, 10); // B Encode(0, 6, 10); // A Encode(8, 2, 10); // // emit final digits - see below while (range To finish off we may need to emit a few extra digits. The top digit of low is probably too small so we need to increment it, but we have to make sure we don't increment it past low+range . So first we need to make sure range is large enough. // emit final digits while (range One problem that can occur with the Encode function above is that range might become very small but low and low+range still have differing first digits. This could result in the interval having insufficient precision to distinguish between all of the symbols in the alphabet. When this happens we need to fudge a little, output the first couple of digits even though we might be off by one, and re-adjust the range to give us as much room as possible. For example, imagine the input stream has led the encoder to the right-open interval [59888, 60188), that is, low = 59888 and range = 300 . The trick is to narrow down the interval to [59888, 60000) = [59888, 59999], which allows the encoder to emit two of the left-most digits of low , and readjust the interval to [88800, 99999] = [88800, 100000), that is, low = 88800 and range = 100000 - low . The decoder will be following the same steps so it will know when it needs to do this to keep in sync. // this goes just before the end of Encode() above if (range Base 10 was used in this example, but a real implementation would just use binary, with the full range of the native integer data type. Instead of 10000 and 1000 you would likely use hexadecimal constants such as 0x1000000 and 0x10000 . Instead of emitting a digit at a time you would emit a byte at a time and use a byte-shift operation instead of multiplying by 10. Decoding uses exactly the same algorithm with the addition of keeping track of the current code value consisting of the digits read from the compressor. Instead of emitting the top digit of low you just throw it away, but you also shift out the top digit of code and shift in a new digit read from the compressor. Use AppendDigit below instead of EmitDigit . int code = 0; int low = 0; int range = 1; void InitializeDecoder() { AppendDigit(); // with this example code, only 1 of these is actually needed AppendDigit(); AppendDigit(); AppendDigit(); AppendDigit(); } void AppendDigit() { code = (code % 10000) * 10 + ReadNextDigit(); low = (low % 10000) * 10; range *= 10; } void Decode(int start, int size, int total) // Decode is same as Encode with EmitDigit replaced by AppendDigit { // adjust the range based on the symbol interval range /= total; low += start * range; range *= size; // check if left-most digit is same throughout range while (low / 10000 == (low + range) / 10000) AppendDigit(); // readjust range - see reason for this below if (range In order to determine which probability intervals to apply, the decoder needs to look at the current value of code within the interval [low, low+range) and decide which symbol this represents. void Run() { int start = 0; int size; int total = 10; InitializeDecoder(); // need to get range/total >0 while (start For the AABA example above, this would return a value in the range 0 to 9. Values 0 through 5 would represent A, 6 and 7 would represent B, and 8 and 9 would represent .
