Elias gamma coding
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Elias \gamma code or Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper bound cannot be determined beforehand.
Elias \gamma code or Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper bound cannot be determined beforehand.
Encoding
To code a number x ≥ 1: Let N = \lfloor \log_2 x \rfloor be the highest power of 2 it contains, so 2 N ≤ x < 2 N+1 . Write out N zero bits, then Append the binary form of x , an (N+1) -bit binary number. An equivalent way to express the same process: Encode N in unary; that is, as N zeroes followed by a one. Append the remaining N binary digits of x to this representation of N . To represent a number x , Elias gamma (γ) uses 2 \lfloor \log_2(x) \rfloor + 1 bits. The code begins (the implied probability distribution for the code is added for clarity):
Decoding
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 2 N , read the remaining N digits of the integer.
Uses
Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to compress data in which small values are much more frequent than large values. Gamma coding can be more size efficient in those situations. For example, note that, in the table above, if a fixed 8-bit size is chosen to store a small number like the number 5, the resulting binary would be 00000101 , while the γ-encoding variable-bit version would be 00 1 01 , needing 3 bits less. On the contrary, bigger values, like 254 stored in fixed 8-bit size, would be 11111110 while the γ-encoding variable-bit version would be 0000000 1 1111110 , needing 7 extra bits. Gamma coding is a building block in the Elias delta code.
See also
References
Further reading
Text derived from https://en.wikipedia.org/w/index.php?oldid=1285268729 under CC BY-SA 4.0; modifications have been made.