Elias gamma coding

"Gamma encoding" redirects here; for the signal processing meaning, see gamma correction.

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:

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 (2^N) 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.

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 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.

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

• Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Lossless Compression Handbook. Elsevier. ISBN 978-0-12-620861-0.

See also

• Elias delta coding
• Elias omega coding