Exponential-Golomb coding

An exponential-Golomb code (or just Exp-Golomb code) is a type of <a href="/facts/Universal_code_(data_compression)/9zn1cM2M">universal code</a>. To encode any <a href="/facts/Nonnegative_integer/u65og8JE">nonnegative integer</a> x using the exp-Golomb code:

<ol><li>Write down x+1 in binary</li>
<li>Count the bits written, subtract one, and write that number of starting zero bits preceding the previous bit string.</li></ol>
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
...<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

In the above examples, consider the case 3. For 3, x+1 = 3 + 1 = 4. 4 in binary is '100'. '100' has 3 bits, and 3-1 = 2. Hence add 2 zeros before '100', which is '00100'
Similarly, consider 8. '8 + 1' in binary is '1001'. '1001' has 4 bits, and 4-1 is 3. Hence add 3 zeros before 1001, which is '0001001'.
This is identical to the <a href="/facts/Elias_gamma_code/kcNSUnBg">Elias gamma code</a> of x+1, allowing it to encode 0.

Exponential-Golomb coding open-in-new

Exponential-Golomb coding