Elias gamma coding
Elias gamma code is a
universal code encoding the positive integers. 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.
The code begins: 1 = 2
0 +
0 = 1 2 = 2
1 +
0 = 01
0 3 = 2
1 +
1 = 01
1 4 = 2
2 +
0 = 001
00 5 = 2
2 +
1 = 001
01 6 = 2
2 +
2 = 001
10 7 = 2
2 +
3 = 001
11 8 = 2
3 +
0 = 0001
000 9 = 2
3 +
1 = 0001
001 10 = 2
3 +
2 = 0001
010 11 = 2
3 +
3 = 0001
011 12 = 2
3 +
4 = 0001
100 13 = 2
3 +
5 = 0001
101 14 = 2
3 +
6 = 0001
110 15 = 2
3 +
7 = 0001
111 16 = 2
4 +
0 = 00001
0000 17 = 2
4 +
1 = 00001
0001To decode an Elias gamma-coded integer:#Read and count zeroes from the stream until you reach the first one. 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.
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 does not code zero or the 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.
*
Elias delta coding*
Elias omega coding
