Exponential-Golomb coding

An exponential-Golomb code (or just Exp-Golomb code) is a type of universal code. To encode any nonnegative 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.

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
...

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 Elias gamma code of ''x''+1, allowing it to encode 0.

Extension to negative numbers

Exp-Golomb coding is used in the H.264/MPEG-4 AVC and H.265 High Efficiency Video Coding video compression standards, in which there is also a variation for the coding of signed numbers by assigning the value 0 to the binary codeword '0' and assigning subsequent codewords to input values of increasing magnitude (and alternating sign, if the field can contain a negative number):
0 ⇒ 0 ⇒ 1 ⇒ 1
1 ⇒ 1 ⇒ 10 ⇒ 010
−1 ⇒ 2 ⇒ 11 ⇒ 011
2 ⇒ 3 ⇒ 100 ⇒ 00100
−2 ⇒ 4 ⇒ 101 ⇒ 00101
3 ⇒ 5 ⇒ 110 ⇒ 00110
−3 ⇒ 6 ⇒ 111 ⇒ 00111
4 ⇒ 7 ⇒ 1000 ⇒ 0001000
−4 ⇒ 8 ⇒ 1001 ⇒ 0001001
...

In other words, a non-positive integer ''x''≤0 is mapped to an even integer −2''x'', while a positive integer ''x''>0 is mapped to an odd integer 2''x''−1.

Exp-Golomb coding is also used in the Dirac video codec.

Generalization to order ''k''

To encode larger numbers in fewer bits (at the expense of using more bits to encode smaller numbers), this can be generalized using a nonnegative integer parameter  ''k''. To encode a nonnegative integer ''x'' in an order-''k'' exp-Golomb code:
# Encode ⌊''x''/2^''k''⌋ using order-0 exp-Golomb code described above, then
# Encode ''x'' mod 2^''k'' in binary
An equivalent way of expressing this is:
# Encode ''x''+2^''k''−1 using the order-0 exp-Golomb code (i.e. encode ''x''+2^''k'' using the Elias gamma code), then
# Delete ''k'' leading zero bits from the encoding result

See also

* Elias gamma (γ) coding
* Elias delta (δ) coding
* Elias omega (ω) coding
* Universal code

References

{{DEFAULTSORT:Exponential-Golomb Coding
Numeral systems
Lossless compression algorithms