Navigation
  • Home
  • Recent
  • Most Active
  • Popular
  • Blog
  • Credits
  • RSS
    		•
      Interaction
  • Register
  • Statistics
    		•
      Help
  • Suggestions
  • Contact Us
  • How to Edit
  • Help
    		•



    [Edit]


    Elias delta code is a universal code encoding the positive integers. To code a number:
      Write it in binary.
      Count the bits, remove the leading one, and write that number of starting bits in binary preceding the previous bit string.
      Subtract 1 from the number of bits written in step 2 and prepend that many zeros.

    An equivalent way to express the same process:
      Separate the integer into the highest power of 2 it contains (2N' ) and the remaining N binary digits of the integer.
      Append the remaining N binary digits to this representation of N.

    The code begins:
    1 = 20 => N' = 0, N = 1 => 1
    2 = 21 + 0 => N' = 1, N = 2 => 0100
    3 = 21 + 1 => N' = 1, N = 2 => 0101
    4 = 22 + 0 => N' = 2, N = 3 => 01100
    5 = 22 + 1 => N' = 2, N = 3 => 01101
    6 = 22 + 2 => N' = 2, N = 3 => 01110
    7 = 22 + 3 => N' = 2, N = 3 => 01111
    8 = 23 + 0 => N' = 3, N = 4 => 00100000
    9 = 23 + 1 => N' = 3, N = 4 => 00100001
    10 = 23 + 2 => N' = 3, N = 4 => 00100010
    11 = 23 + 3 => N' = 3, N = 4 => 00100011
    12 = 23 + 4 => N' = 3, N = 4 => 00100100
    13 = 23 + 5 => N' = 3, N = 4 => 00100101
    14 = 23 + 6 => N' = 3, N = 4 => 00100110
    15 = 23 + 7 => N' = 3, N = 4 => 00100111
    16 = 24 + 0 => N' = 4, N = 5 => 001010000
    17 = 24 + 1 => N' = 4, N = 5 => 001010001

    To decode an Elias delta-coded integer:
      Read and count zeroes from the stream until you reach the first one. Call this count of zeroes L.
      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 M.
      Put a one in the first place of our final output, representing the value 2M. Read and append the following M 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.

    See also: Elias gamma coding, Elias omega coding




        Elias delta coding
     
    Search more:
     

       
    Source Privacy License Download Contact Us Atlas
    Scientus.org Dictionary (Yet Another Wiki) RC : 1.39
    This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Elias delta coding". link