Loading AI tools
Universal encoding scheme for positive integers From Wikipedia, the free encyclopedia
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.