Introduction to Rangecoding

1. Combinatorics

Suppose we have a bit string with n0 0s and n1 1s in it. If its the only information we know about that string, that means that all the strings with n0 0s and n1 1s are equiprobable.
And we know from combinatorics that there're (n0+n1)!/n0!/n1! such strings.
So for compact encoding of the string, we just have to store its number among strings having the same stats.

2. Enumeration-based coding

One simple way to perform such an enumeration is recurrent:

C(n0,n1) = (n0+n1)!/n0!/n1!

for strings with first bit:
0 - use interval 0..C(n0-1,n1)-1
1 - use interval C(n0-1,n1)..C(n0,n1)-1

(Accidentally, C(n0-1,n1)+C(n0,n1-1)=C(n0,n1))

s[i] = i'th bit of the string
a(s,x) = Sum( s[i], i=0..x-1 ) // count of 1s in string prefix
code(s) = Sum( s[i]*C(n0-(i+1-a(s,i)),n1-a(s,i)), i=0..n0+n1-1 )

low = 0
range = C(n0,n1)
for bit in s[] {
  rnew = range*n0/(n0+n1); // C(n0-1,n1)
  if( bit==1 ) {
    n1--; low += rnew; range -= rnew; // range*n1/(n0+n1)
  } else {
    n0--; low += 0; range = rnew; 
  }
}

3. Rangecoding

To use a limited precision for the low register in the loop described above, we can output and discard the bits which won't be modified anymore.
(range precision is always much easier to control, as its value only decreases).

Basically, low can be always represented in the form:

{0}{N x 1}{k-bit mantissa}

  {0}{N x 1}{k-bit mantissa}
+           {k-bit range}
----------------------------
  {1}{N x 0}{k-bit new mantissa}

  {0}{N x 1}{k-bit mantissa}
+           {k-bit range}
----------------------------
  {0}{N x 1}{k-bit new mantissa}

That's how the plain arithmetic coding works, but memory i/o is bytewise on the modern platforms, so its not quite efficient to use bits there.
And in fact bits are not any special there, as we can use any positional base-b numeral system instead.

{0..b-2}{N x b-1}{k-digit mantissa}

4. Carryless coding

All this stuff with variable-length low representation is certainly not quite simple, but there's a possible workaround - we can always forcibly cut down the range (thus adding some redundancy) so that low+range<b^k would be always true.

Also, the redundancy can be significantly reduced by using a higher precision for low than for range (low only requires addition, so its easy). For example, see CLR (clr.cdr in coders6a.rar),

However, a considerable inconvenience of carryless coding is the requirement for symmetrical processing in decoding, which makes a carryless decoder fairly complex comparing to "normal" (with carries).

But then, there's a somewhat more exotic alternative to usual carryless implementations - instead of cutting range down little by little, we can make the overflows rare enough by extending the low, like explained above, and then just set range to a minimal value (like 1), thus effectively flushing the coder. The benefit of this is that decoder implementation becomes simpler than in usual carryless, and faster. (see CLRF, crlf.cdr in coders6c2.rar),