World Library  
Flag as Inappropriate
Email this Article

Elias gamma coding

Article Id: WHEBN0000051761
Reproduction Date:

Title: Elias gamma coding  
Author: World Heritage Encyclopedia
Language: English
Subject: Entropy encoding, Data compression, Context tree weighting, Warped linear predictive coding, Log area ratio
Collection: Articles with Example C Code, Lossless Compression Algorithms, Numeral Systems
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Elias gamma coding

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.

Contents

  • Encoding 1
  • Decoding 2
  • Uses 3
  • Generalizations 4
  • References 5
  • See also 6

Encoding

To code a number:

  1. Write it in binary.
  2. Subtract 1 from the number of bits written in step 1 and prepend that many zeros.

An equivalent way to express the same process:

  1. Separate the integer into the highest power of 2 it contains (2N) and the remaining N binary digits of the integer.
  2. Encode N in unary; that is, as N zeroes followed by a one.
  3. Append the remaining N binary digits to this representation of N.

To represent a number x, Elias gamma uses 2 \lfloor \log_2(x) \rfloor + 1 bits[1]:199.

The code begins (the implied probability distribution for the code is added for clarity):

Number Encoding Implied probability
1 = 20 + 0 1 1/2
2 = 21 + 0 010 1/8
3 = 21 + 1 011 1/8
4 = 22 + 0 00100 1/32
5 = 22 + 1 00101 1/32
6 = 22 + 2 00110 1/32
7 = 22 + 3 00111 1/32
8 = 23 + 0 0001000 1/128
9 = 23 + 1 0001001 1/128
10 = 23 + 2 0001010 1/128
11 = 23 + 3 0001011 1/128
12 = 23 + 4 0001100 1/128
13 = 23 + 5 0001101 1/128
14 = 23 + 6 0001110 1/128
15 = 23 + 7 0001111 1/128
16 = 24 + 0 000010000 1/512
17 = 24 + 1 000010001 1/512

Decoding

To decode an Elias gamma-coded integer:

  1. Read and count 0s from the stream until you reach the first 1. Call this count of zeroes N.
  2. 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

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.

Generalizations

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.

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.

References

  1. ^ a b Elias, Peter (March 1975). "Universal codeword sets and representations of the integers".  
  • Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Lossless Compression Handbook. Elsevier.  

See also

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.