Elias code or Elias gamma code is a universal code encoding positive integers developed by Peter Elias. [1]: 197, 199 It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
To code a number x ≥ 1:
An equivalent way to express the same process:
To represent a number , Elias gamma (γ) uses bits. [1]: 199
The code begins (the implied probability distribution for the code is added for clarity):
Number | Binary | γ encoding | Implied probability |
---|---|---|---|
1 = 20 + 0 | 1 |
1 |
1/2 |
2 = 21 + 0 | 1 0 |
0 1 0 |
1/8 |
3 = 21 + 1 | 1 1 |
0 1 1 |
1/8 |
4 = 22 + 0 | 1 00 |
00 1 00 |
1/32 |
5 = 22 + 1 | 1 01 |
00 1 01 |
1/32 |
6 = 22 + 2 | 1 10 |
00 1 10 |
1/32 |
7 = 22 + 3 | 1 11 |
00 1 11 |
1/32 |
8 = 23 + 0 | 1 000 |
000 1 000 |
1/128 |
9 = 23 + 1 | 1 001 |
000 1 001 |
1/128 |
10 = 23 + 2 | 1 010 |
000 1 010 |
1/128 |
11 = 23 + 3 | 1 011 |
000 1 011 |
1/128 |
12 = 23 + 4 | 1 100 |
000 1 100 |
1/128 |
13 = 23 + 5 | 1 101 |
000 1 101 |
1/128 |
14 = 23 + 6 | 1 110 |
000 1 110 |
1/128 |
15 = 23 + 7 | 1 111 |
000 1 111 |
1/128 |
16 = 24 + 0 | 1 0000 |
0000 1 0000 |
1/512 |
17 = 24 + 1 | 1 0001 |
0000 1 0001 |
1/512 |
To decode an Elias gamma-coded integer:
Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to compress data[ dubious – discuss] in which small values are much more frequent than large values.
Gamma coding is a building block in the Elias delta code.
Gamma coding does not code zero or negative integers. One way of handling zero is to add 1 before coding and then subtract 1 after decoding. Another way is to prefix each nonzero code with a 1 and then code zero as a single 0.
One way to code all integers is to set up a
bijection, mapping integers (0, −1, 1, −2, 2, −3, 3, ...) to (1, 2, 3, 4, 5, 6, 7, ...) before coding. In software, this is most easily done by mapping non-negative inputs to odd outputs, and negative inputs to even outputs, so the least-significant bit becomes an inverted
sign bit:
Exponential-Golomb coding generalizes the gamma code to integers with a "flatter" power-law distribution, just as Golomb coding generalizes the unary code. It involves dividing the number by a positive divisor, commonly a power of 2, writing the gamma code for one more than the quotient, and writing out the remainder in an ordinary binary code.