# 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:
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):
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 (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 with k bits
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
Exp-Golomb-k coding examples :
| x | k=0 | k=1 | k=2 | k=3 | x | k=0 | k=1 | k=2 | k=3 | x | k=0 | k=1 | k=2 | k=3 |
| 0 | 1 | 10 | 100 | 1000 | 10 | 0001011 | 001100 | 01110 | 010010 | 20 | 000010101 | 00010110 | 0011000 | 011100 |
| 1 | 010 | 11 | 101 | 1001 | 11 | 0001100 | 001101 | 01111 | 010011 | 21 | 000010110 | 00010111 | 0011001 | 011101 |
| 2 | 011 | 0100 | 110 | 1010 | 12 | 0001101 | 001110 | 0010000 | 010100 | 22 | 000010111 | 00011000 | 0011010 | 011110 |
| 3 | 00100 | 0101 | 111 | 1011 | 13 | 0001110 | 001111 | 0010001 | 010101 | 23 | 000011000 | 00011001 | 0011011 | 011111 |
| 4 | 00101 | 0110 | 01000 | 1100 | 14 | 0001111 | 00010000 | 0010010 | 010110 | 24 | 000011001 | 00011010 | 0011100 | 00100000 |
| 5 | 00110 | 0111 | 01001 | 1101 | 15 | 000010000 | 00010001 | 0010011 | 010111 | 25 | 000011010 | 00011011 | 0011101 | 00100001 |
| 6 | 00111 | 001000 | 01010 | 1110 | 16 | 000010001 | 00010010 | 0010100 | 011000 | 26 | 000011011 | 00011100 | 0011110 | 00100010 |
| 7 | 0001000 | 001001 | 01011 | 1111 | 17 | 000010010 | 00010011 | 0010101 | 011001 | 27 | 000011100 | 00011101 | 0011111 | 00100011 |
| 8 | 0001001 | 001010 | 01100 | 010000 | 18 | 000010011 | 00010100 | 0010110 | 011010 | 28 | 000011101 | 00011110 | 000100000 | 00100100 |
| 9 | 0001010 | 001011 | 01101 | 010001 | 19 | 000010100 | 00010101 | 0010111 | 011011 | 29 | 000011110 | 00011111 | 000100001 | 00100101 |