The Full Wiki

More info on Elias gamma coding

Elias gamma coding: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

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.

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.

The code begins:

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

The implied probability distribution for the code is added for clarity.

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.

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.

Contents

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.

Example code

Encode

void eliasGammaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())     
    {
        int num = intreader.getInt();
        int l = log2(num);
        for (int a=0; a < l; a++)
            bitwriter.putBit(false); //put 0s to indicate how many bits will follow
        bitwriter.putBit(true);      //mark the end of the 0s
        for (int a=l-1; a >= 0; a--) //Write the bits as plain binary
        {
            if (num & 1 << a)
                bitwriter.putBit(true);
            else
                bitwriter.putBit(false);
        }
    }
    intreader.close();
    bitwriter.close();
}

Decode

void eliasGammaDecode(char* source, char* dest)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int numberBits = 0;
        while (!bitreader.getBit() && bitreader.hasLeft())
            numberBits++; //keep on reading until we fetch a one...
        int current = 0;
        for (int a=numberBits-1; a >= 0; a--) //Read numberBits bits
        {
            if (bitreader.getBit())
                current |= 1 << a;
        }
        current |= 1 << numberBits; //last bit isn't encoded!
 
        intwriter.putInt(current);
    }
}

External references

  • Peter Elias, "Universal codeword sets and representations of the integers", IEEE Trans. Information Theory 21(2):194-203, Mar 1975.
  • Khalid Sayood, Lossless Compression Handbook, Elsevier, 2003. Section 3.5.

See also

Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message