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:

  1. Write down x+1 in binary
  2. 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().

See also

References