Elias delta coding

Elias delta code is a universal code encoding the positive integers developed by Peter Elias. 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 digit written in step 1 again, remove the leading bit and write down the remaining bits (Y).
4. Append the second binary digit (Y) to the first binary digit (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 (2^N' ) 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.

The code begins:

                                       Implied probability
 1 = 20 => N' = 0, N = 1 => 1             1/2
 2 = 21 + 0 => N' = 1, N = 2 => 0100      1/16
 3 = 21 + 1 => N' = 1, N = 2 => 0101       "
 4 = 22 + 0 => N' = 2, N = 3 => 01100     1/32
 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  1/256
 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 1/512
17 = 24 + 1 => N' = 4, N = 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 2^L, 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 2^N-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.

See also

• Elias gamma coding
• Elias omega coding

References

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2007)