An exponential-Golomb code (or just Exp-Golomb code) is a type of
universal code. To encode any
nonnegative integer
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
''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
High Efficiency Video Coding (HEVC), also known as H.265 and MPEG-H Part 2, is a video compression standard designed as part of the MPEG-H project as a successor to the widely used Advanced Video Coding (AVC, H.264, or MPEG-4 Part 10). In compa ...
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
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
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
See also
*
Elias gamma (γ) coding
*
Elias delta (δ) coding
*
Elias omega (ω) coding
*
Universal code
References
{{DEFAULTSORT:Exponential-Golomb Coding
Entropy coding
Numeral systems
Data compression