Elias gamma coding

"Gamma encoding" redirects here. For the signal processing operation, see gamma correction.

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.

Encoding

To code a number x≥1:

  1. Let N=log2 x be the highest power of 2 it contains, so 2Nx < 2N+1.
  2. Write out N zero bits, then
  3. Append the binary form of x, an N+1-bit binary number.

An equivalent way to express the same process:

  1. Encode N in unary; that is, as N zeroes followed by a one.
  2. 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.[1]:199

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

Number Binary γ Encoding Implied probability
1 = 20 + 0 1 1 1/2
2 = 21 + 0 10 010 1/8
3 = 21 + 1 11 011 1/8
4 = 22 + 0 100 00100 1/32
5 = 22 + 1 101 00101 1/32
6 = 22 + 2 110 00110 1/32
7 = 22 + 3 111 00111 1/32
8 = 23 + 0 1000 0001000 1/128
9 = 23 + 1 1001 0001001 1/128
10 = 23 + 2 1010 0001010 1/128
11 = 23 + 3 1011 0001011 1/128
12 = 23 + 4 1100 0001100 1/128
13 = 23 + 5 1101 0001101 1/128
14 = 23 + 6 1110 0001110 1/128
15 = 23 + 7 1111 0001111 1/128
16 = 24 + 0 10000 000010000 1/512
17 = 24 + 1 10001 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.

Gamma coding is a building block in the Elias delta code.

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. In software, this is most easily done by mapping non-negative inputs to odd outputs, and negative inputs to even outputs, so the least-significant bit becomes an inverted sign bit:
\begin{cases}
x \mapsto 2x+1 & \mathrm{when~} x \geq 0 \\
x \mapsto -2x  & \mathrm{when~} x < 0 \\
\end{cases}

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

See also

This article is issued from Wikipedia - version of the Monday, December 15, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.