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 upperbound cannot be determined beforehand.
Contents

Encoding 1

Decoding 2

Uses 3

Generalizations 4

References 5

See also 6
Encoding
To code a number:

Write it in binary.

Subtract 1 from the number of bits written in step 1 and prepend that many zeros.
An equivalent way to express the same process:

Separate the integer into the highest power of 2 it contains (2^{N}) and the remaining N binary digits of the integer.

Encode N in unary; that is, as N zeroes followed by a one.

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 = 2^{0} + 0

1

1/2

2 = 2^{1} + 0

010

1/8

3 = 2^{1} + 1

011

1/8

4 = 2^{2} + 0

00100

1/32

5 = 2^{2} + 1

00101

1/32

6 = 2^{2} + 2

00110

1/32

7 = 2^{2} + 3

00111

1/32

8 = 2^{3} + 0

0001000

1/128

9 = 2^{3} + 1

0001001

1/128

10 = 2^{3} + 2

0001010

1/128

11 = 2^{3} + 3

0001011

1/128

12 = 2^{3} + 4

0001100

1/128

13 = 2^{3} + 5

0001101

1/128

14 = 2^{3} + 6

0001110

1/128

15 = 2^{3} + 7

0001111

1/128

16 = 2^{4} + 0

000010000

1/512

17 = 2^{4} + 1

000010001

1/512

Decoding
To decode an Elias gammacoded 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.
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.
ExponentialGolomb coding generalizes the gamma code to integers with a "flatter" powerlaw 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

^ ^{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 AttributionShareAlike 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, EGovernment 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 nonprofit organization.