Exponential-Golomb coding


An exponential-Golomb code is a type of universal code. To encode any nonnegative 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.
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 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 :
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 −2x, while a positive integer x>0 is mapped to an odd integer 2x−1.
Exp-Golomb coding is also used in the Dirac video codec.

Generalization to order ''k''

To encode larger numbers in fewer bits, this can be generalized using a nonnegative integer parameter k. To encode a nonnegative integer x in an order-k exp-Golomb code:
  1. Encode ⌊x/2k⌋ using order-0 exp-Golomb code described above, then
  2. Encode x mod 2k in binary
An equivalent way of expressing this is:
  1. Encode x+2k−1 using the order-0 exp-Golomb code, then
  2. Delete k leading zero bits from the encoding result
x k=0k=1k=2k=3 x k=0k=1k=2k=3 x k=0k=1k=2k=3
011010010001000010110011000111001001020000010101000101100011000011100
10101110110011100011000011010111101001121000010110000101110011001011101
201101001101010120001101001110001000001010022000010111000110000011010011110
30010001011111011130001110001111001000101010123000011000000110010011011011111
40010101100100011001400011110001000000100100101102400001100100011010001110000100000
5001100111010011101150000100000001000100100110101112500001101000011011001110100100001
600111001000010101110160000100010001001000101000110002600001101100011100001111000100010
70001000001001010111111170000100100001001100101010110012700001110000011101001111100100011
800010010010100110001000018000010011000101000010110011010280000111010001111000010000000100100
900010100010110110101000119000010100000101010010111011011290000111100001111100010000100100101