World Library  
Flag as Inappropriate
Email this Article

Elias delta coding

Article Id: WHEBN0000051766
Reproduction Date:

Title: Elias delta coding  
Author: World Heritage Encyclopedia
Language: English
Subject: Elias coding, Exponential-Golomb coding, Elias gamma coding, Lossless compression algorithms, Prefix code
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Elias delta coding

Elias delta code is a universal code encoding the positive integers developed by Peter Elias.[1]:200 To code a number:

  1. Write it in binary.
  2. Count the bits and write down that number of bits in binary (X).
  3. Use the binary representation written in step 1 again, remove the leading bit and write down the remaining bits (Y).
  4. Append the second binary representation (Y) to the first binary representation (X).
  5. Count the bits written in step 2 (X), subtract 1 from that number 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 = N' + 1 with Elias gamma coding.
  3. Append the remaining N' binary digits to this representation of N.

To represent a number x, Elias delta uses \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1 bits.[1]:200

The code begins, using \gamma' instead of \gamma:

Number N' N Encoding Implied probability
1 = 20 0 1 1 1/2
2 = 21 + 0 1 2 0100 1/16
3 = 21 + 1 1 2 0101 "
4 = 22 + 0 2 3 01100 1/32
5 = 22 + 1 2 3 01101 "
6 = 22 + 2 2 3 01110 "
7 = 22 + 3 2 3 01111 "
8 = 23 + 0 3 4 00100000 1/256
9 = 23 + 1 3 4 00100001 "
10 = 23 + 2 3 4 00100010 "
11 = 23 + 3 3 4 00100011 "
12 = 23 + 4 3 4 00100100 "
13 = 23 + 5 3 4 00100101 "
14 = 23 + 6 3 4 00100110 "
15 = 23 + 7 3 4 00100111 "
16 = 24 + 0 4 5 001010000 1/512
17 = 24 + 1 4 5 001010001 "

To decode an Elias delta-coded integer:

  1. Read and count zeroes from the stream until you reach the first one. Call this count of zeroes L.
  2. Considering the one that was reached to be the first digit of an integer, with a value of 2L, read the remaining L digits of the integer. Call this integer N.
  3. Put a one in the first place of our final output, representing the value 2N-1. Read and append the following N-1 digits.

Example:

001010001
1. 2 leading zeros in 001
2. read 2 more bits i.e. 00101
3. decode N = 00101 = 5
4. get N' = 5 - 1 = 4 remaining bits for the complete code i.e. '0001'
5. encoded number = 24 + 1 = 17

This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding.

Contents

  • Example code 1
    • Encoding 1.1
    • Decoding 1.2
  • Generalizations 2
  • References 3
  • See also 4

Example code

Encoding

void eliasDeltaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        int len = 0;
        int lengthOfLen = 0;
        for (int temp = num; temp > 0; temp >>= 1)  // calculate 1+floor(log2(num))
            len++;
        for (int temp = len; temp > 1; temp >>= 1)  // calculate floor(log2(len))
            lengthOfLen++;
        for (int i = lengthOfLen; i > 0; --i)
            bitwriter.outputBit(0);
        for (int i = lengthOfLen; i >= 0; --i)
            bitwriter.outputBit((len >> i) & 1);
        for (int i = len-2; i >= 0; i--)
            bitwriter.outputBit((num >> i) & 1);
    }
    bitwriter.close();
    intreader.close();
}

Decoding

void eliasDeltaDecode(char* source, char* dest)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int num = 1;
        int len = 1;
        int lengthOfLen = 0;
        while (!bitreader.inputBit())     // potentially dangerous with malformed files.
            lengthOfLen++;
        for (int i = 0; i < lengthOfLen; i++)
        {
            len <<= 1;
            if (bitreader.inputBit())
                len |= 1;
        }
        for (int i = 0; i < len-1; i++)
        {
            num <<= 1;
            if (bitreader.inputBit())
                num |= 1;
        }
        intwriter.putInt(num);            // write out the value
    }
    bitreader.close();
    intwriter.close();
}

Generalizations

Elias delta coding does not code zero or negative integers. One way to code all non negative integers is to add 1 before coding and then subtract 1 after decoding. One way to code all integers is to set up a bijection, mapping integers all integers (0, 1, -1, 2, -2, 3, -3, ...) to strictly positive integers (1, 2, 3, 4, 5, 6, 7, ...) before coding.

References

  1. ^ a b Elias, Peter (March 1975). "Universal codeword sets and representations of the integers".  

See also

This article was sourced from Creative Commons Attribution-ShareAlike 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, E-Government 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 non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.