Elias delta coding
|
|
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 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.
- Encode N with Elias gamma coding.
- Append the remaining N binary digits to this representation of N.
The code begins:
1 1 2 0100 3 0101 4 01100 5 01101 6 01110 7 01111 8 00100000 9 00100001 10 00100010 11 00100011 12 00100100 13 00100101 14 00100110 15 00100111 16 001010000 17 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.
See also: Elias gamma coding, Elias omega coding