Elias gamma coding
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.
Encoding
[edit]To code a number x ≥ 1:
- Let be the highest power of 2 it contains, so 2N ≤ x < 2N+1.
- Write out zero bits, then
- Append the binary form of , an -bit binary number.
An equivalent way to express the same process:
- Encode in unary; that is, as zeroes followed by a one.
- Append the remaining binary digits of to this representation of .
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 |
Decoding
[edit]To decode an Elias gamma-coded integer:
- Read and count 0s from the stream until you reach the first 1. Call this count of zeroes N.
- Considering the one that was reached to be the first digit of the integer, with a value of 2N, read the remaining N digits of the integer.
Uses
[edit]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.
Generalizations
[edit]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.
See also
[edit]- Elias delta (d) coding – universal code encoding positive integers
- Elias omega (?) coding – Universal code encoding positive integers
- Posit (number format) – Variant of floating-point numbers in computers
References
[edit]- ^ a b Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.
Further reading
[edit]- Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Lossless Compression Handbook. Elsevier. ISBN 978-0-12-620861-0.