Elias delta coding

related topics
{math, number, function}
{@card@, make, design}

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

An equivalent way to express the same process:

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 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.

<

See also

References

Full article ▸

related documents
Product of rings
Abelian category
Column vector
Sum rule in differentiation
Category of sets
Complete category
Brun's constant
Endomorphism
Hamiltonian path problem
Characteristic subgroup
Mutual recursion
Double precision
Inverse functions and differentiation
Sharp-P
Baire category theorem
AVL tree
Sophie Germain prime
Inequation
Kleene star
Axiom of union
Additive function
Random sequence
Up to
Zero divisor
Normal morphism
Lagged Fibonacci generator
Identity matrix
Blum Blum Shub
Identifier
Row and column spaces