Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:
- Write it in binary.
- Count the bits and write down that number of bits in binary (X).
- Use the binary representation written in step 1 again, remove the leading bit and write down the remaining bits (Y).
- Append the second binary representation (Y) to the first binary representation (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.
To represent a number, Elias delta uses bits.
The code begins, using instead of :
| Number | N' | N | Encoding | Implied probability |
|---|---|---|---|---|
| 1 = 20 | 0 | 1 | 1 | 1/2 |
| 2 = 21 + 0 | 1 | 2 | 0100 | 1/16 |
| 3 = 21 + 1 | 1 | 2 | 0101 | " |
| 4 = 22 + 0 | 2 | 3 | 01100 | 1/32 |
| 5 = 22 + 1 | 2 | 3 | 01101 | " |
| 6 = 22 + 2 | 2 | 3 | 01110 | " |
| 7 = 22 + 3 | 2 | 3 | 01111 | " |
| 8 = 23 + 0 | 3 | 4 | 00100000 | 1/256 |
| 9 = 23 + 1 | 3 | 4 | 00100001 | " |
| 10 = 23 + 2 | 3 | 4 | 00100010 | " |
| 11 = 23 + 3 | 3 | 4 | 00100011 | " |
| 12 = 23 + 4 | 3 | 4 | 00100100 | " |
| 13 = 23 + 5 | 3 | 4 | 00100101 | " |
| 14 = 23 + 6 | 3 | 4 | 00100110 | " |
| 15 = 23 + 7 | 3 | 4 | 00100111 | " |
| 16 = 24 + 0 | 4 | 5 | 001010000 | 1/512 |
| 17 = 24 + 1 | 4 | 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 = 17This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding.