Exponential-Golomb Coding
From WikiCoder
An exponential-Golomb code (or just Exp-Golomb code) is a type of universal code. To encode any positive integer x using the Exp-Golomb code:
- Write down x+1 in binary
- Count the bits written, subtract one, and write that number of starting zero bits preceding the previous bit string.
In essence, its a Unary Coding of how many bits, followed by the bits.
The first few values of the code are:
0 ⇒ 1 ⇒ 1 1 ⇒ 10 ⇒ 010 2 ⇒ 11 ⇒ 011 3 ⇒ 100 ⇒ 00100 4 ⇒ 101 ⇒ 00101 5 ⇒ 110 ⇒ 00110 6 ⇒ 111 ⇒ 00111 7 ⇒ 1000 ⇒ 0001000 8 ⇒ 1001 ⇒ 0001001 ...
This is identical to the Elias Gamma Coding of x+1, allowing it to encode 0.
Code Example
void write_ExpGolomb(unsigned val)
{
++val;
unsigned highest_bit_set = 32 - IntegerLog2(val);
write_bits(0, highest_bit_set-1);
if(highest_bit_set > 0) {
write_bits(val, highest_bit_set);
}
}
unsigned read_ExpGolomb()
{
int highest_bit_set = 0;
do {
++highest_bit_set;
} while(!read_bits(1));
unsigned val = read_bits(highest_bit_set) | (1<<highest_bit_set);
return val - 1;
}
See Finding integer log base 2 of an integer (aka the position of the highest bit set) for how to compute IntegerLog2().
