Golomb Coding
Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.
Contents
Rice Coding
Rice coding (invented by Robert F. Rice) denotes using a subset of the family of Golomb codes to produce a simpler (but possibly suboptimal) prefix code. Rice used this set of codes in an adaptive coding scheme; "Rice coding" can refer either to that adaptive scheme or to using that subset of Golomb codes. Whereas a Golomb code has a tunable parameter that can be any positive integer value, Rice codes are those in which the tunable parameter is a power of two. This makes Rice codes convenient for use on a computer since multiplication and division by 2 can be implemented more efficiently in binary arithmetic.
Rice was motivated to propose this simpler subset due to the fact that geometric distributions are often varying with time, not precisely known, or both, so selecting the seemingly optimal code might not be very advantageous.
Rice coding is used as the entropy encoding stage in a number of lossless image compression and audio data compression methods.
Overview
Golomb coding uses a tunable parameter to divide an input value into two parts: , the result of a division by , and , the remainder. The quotient is sent in Unary Coding, followed by the remainder in Truncated Binary Coding. When Golomb coding is equivalent to Unary Coding.
Example
, r can be encoded using Truncated Binary Encoding on bits
q | r | Encoded value | |
---|---|---|---|
0 | 0 | 0 | 000 |
1 | 0 | 1 | 001 |
2 | 0 | 2 | 010 |
3 | 0 | 3 | 0110 |
4 | 0 | 4 | 0111 |
5 | 1 | 0 | 1000 |
6 | 1 | 1 | 1001 |
7 | 1 | 2 | 1010 |
8 | 1 | 3 | 10110 |
9 | 1 | 4 | 10111 |
10 | 2 | 0 | 11000 |
Example Code
Rice Coding
void write_Rice(unsigned val, unsigned bits)
{
// Write the quotient via Unary Coding
write_bits(0, val >> bits);
write_bits(1, 1);
// Write the remainder via Truncated Binary Coding
write_bits(val & ((1<<bits)-1), bits);
}
unsigned read_Rice(unsigned bits)
{
// Read the quotient from Unary Coding
unsigned value = 0;
do {
++value;
} while(!read_bits(1));
// Read the remainder and put the two together.
return (value << bits) | read_bits(bits);
}
Golomb Coding
void write_Golomb(unsigned value, unsigned divisor)
{
unsigned quotient = value / divisor;
unsigned remainder = value - quotient * divisor;
// Write the quotient as Unary Coding
write_bits(0, quotient);
write_bits(1, 1);
// Write the remainder
write_bits(remainder, IntegerLog2(divisor));
}
unsigned read_Golomb(unsigned divisor)
{
// Read the quotient as Unary Coding
unsigned quotient = 0;
do {
++quotient;
} while(!read_bits(1));
// Read the remainder and put them together
return (quotient * divisor) + read_bits(IntegerLog2(divisor));
}
References
See Finding integer log base 2 of an integer (aka the position of the highest bit set) for how to compute IntegerLog2().