Elias delta coding
From Wikipedia, the free encyclopedia
Elias delta code is a universal code encoding the positive integers. To code a number:
- Write it in binary.
- Count the bits and write down that number of bits in binary (X).
- Use the binary digit written in step 1 again, remove the leading bit and write down the remaining bits (Y).
- Append the second binary digit (Y) to the first binary digit (X).
- 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:
- Separate the integer into the highest power of 2 it contains (2N' ) and the remaining N' binary digits of the integer.
- Encode N = N' + 1 with Elias gamma coding.
- 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 = 2² + 0 => N' = 2, N = 3 => 01100 1/32
5 = 2² + 1 => N' = 2, N = 3 => 01101 "
6 = 2² + 2 => N' = 2, N = 3 => 01110 "
7 = 2² + 3 => N' = 2, N = 3 => 01111 "
8 = 2³ + 0 => N' = 3, N = 4 => 00100000 1/256
9 = 2³ + 1 => N' = 3, N = 4 => 00100001 "
10 = 2³ + 2 => N' = 3, N = 4 => 00100010 "
11 = 2³ + 3 => N' = 3, N = 4 => 00100011 "
12 = 2³ + 4 => N' = 3, N = 4 => 00100100 "
13 = 2³ + 5 => N' = 3, N = 4 => 00100101 "
14 = 2³ + 6 => N' = 3, N = 4 => 00100110 "
15 = 2³ + 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:
- 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 N.
- 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.
[edit] See also
[edit] References
 |
This article does not cite any references or sources. (April 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed. |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
