# Elias delta coding

**Elias δ code** or **Elias delta code** is a universal code encoding the positive integers developed by Peter Elias.^{[1]}^{:200}

## Contents

## Encoding[edit]

To code a number *X* ≥ 1:

- Let
*N*= ⌊log_{2}*X*⌋; be the highest power of 2 in*X*, so 2^{N}≤*X*< 2^{N+1}. - Let
*L*= ⌊log_{2}*N*+1⌋ be the highest power of 2 in*N*+1, so 2^{L}≤*N*+1 < 2^{L+1}. - Write
*L*zeros, followed by - the
*L*+1-bit binary representation of*N*+1, followed by - all but the leading bit (i.e. the last
*N*bits) of*X*.

An equivalent way to express the same process:

- Separate
*X*into the highest power of 2 it contains (2^{N}) and the remaining*N*binary digits. - Encode
*N*+1 with Elias gamma coding. - Append the remaining
*N*binary digits to this representation of*N*+1.

To represent a number , Elias delta (δ) uses bits.^{[1]}^{:200}

The code begins, using instead of :

Number | N | N+1 | δ encoding | Implied probability |
---|---|---|---|---|

1 = 2^{0} |
0 | 1 | `1` |
1/2 |

2 = 2^{1} + 0 |
1 | 2 | `0 1 0 ` |
1/16 |

3 = 2^{1} + 1 |
1 | 2 | `0 1 0 ` |
1/16 |

4 = 2^{2} + 0 |
2 | 3 | `0 1 1 ` |
1/32 |

5 = 2^{2} + 1 |
2 | 3 | `0 1 1 ` |
1/32 |

6 = 2^{2} + 2 |
2 | 3 | `0 1 1 ` |
1/32 |

7 = 2^{2} + 3 |
2 | 3 | `0 1 1 ` |
1/32 |

8 = 2^{3} + 0 |
3 | 4 | `00 1 00 ` |
1/256 |

9 = 2^{3} + 1 |
3 | 4 | `00 1 00 ` |
1/256 |

10 = 2^{3} + 2 |
3 | 4 | `00 1 00 ` |
1/256 |

11 = 2^{3} + 3 |
3 | 4 | `00 1 00 ` |
1/256 |

12 = 2^{3} + 4 |
3 | 4 | `00 1 00 ` |
1/256 |

13 = 2^{3} + 5 |
3 | 4 | `00 1 00 ` |
1/256 |

14 = 2^{3} + 6 |
3 | 4 | `00 1 00 ` |
1/256 |

15 = 2^{3} + 7 |
3 | 4 | `00 1 00 ` |
1/256 |

16 = 2^{4} + 0 |
4 | 5 | `00 1 01 ` |
1/512 |

17 = 2^{4} + 1 |
4 | 5 | `00 1 01 ` |
1/512 |

To decode an Elias delta-coded integer:

- Read and count zeros from the stream until you reach the first one. Call this count of zeros
*L*. - 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*+1, and subtract one to get*N*. - Put a one in the first place of our final output, representing the value 2
^{N}. - Read and append the following
*N*digits.

Example:

001010011 1. 2 leading zeros in 001 2. read 2 more bits i.e. 00101 3. decode N+1 = 00101 = 5 4. get N = 5 − 1 = 4 remaining bits for the complete code i.e. '0011' 5. encoded number = 2^{4}+ 3 = 19

This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding.

## Example code[edit]

### Encoding[edit]

```
void eliasDeltaEncode(char* source, char* dest)
{
IntReader intreader(source);
BitWriter bitwriter(dest);
while (intreader.hasLeft())
{
int num = intreader.getInt();
int len = 0;
int lengthOfLen = 0;
len = floor(log2(num)); // calculate 1+floor(log2(num))
lengthOfLen = floor(log2(len+1)); // calculate floor(log2(len))
for (int i = lengthOfLen; i > 0; --i)
bitwriter.outputBit(0);
for (int i = lengthOfLen; i >= 0; --i)
bitwriter.outputBit((len >> i) & 1);
for (int i = len-2; i >= 0; i--)
bitwriter.outputBit((num >> i) & 1);
}
bitwriter.close();
intreader.close();
}
```

### Decoding[edit]

```
void eliasDeltaDecode(char* source, char* dest)
{
BitReader bitreader(source);
IntWriter intwriter(dest);
while (bitreader.hasLeft())
{
int num = 1;
int len = 1;
int lengthOfLen = 0;
while (!bitreader.inputBit()) // potentially dangerous with malformed files.
lengthOfLen++;
for (int i = 0; i < lengthOfLen; i++)
{
len <<= 1;
if (bitreader.inputBit())
len |= 1;
}
for (int i = 0; i < len-1; i++)
{
num <<= 1;
if (bitreader.inputBit())
num |= 1;
}
intwriter.putInt(num); // write out the value
}
bitreader.close();
intwriter.close();
}
```

## Generalizations[edit]

Elias delta coding does not code zero or negative integers. One way to code all non negative integers is to add 1 before coding and then subtract 1 after decoding. One way to code all integers is to set up a bijection, mapping integers all integers (0, 1, −1, 2, −2, 3, −3, ...) to strictly positive integers (1, 2, 3, 4, 5, 6, 7, ...) before coding. This bijection can be performed using the "ZigZag" encoding from Protocol Buffers (not to be confused with Zigzag code, nor the JPEG Zig-zag entropy coding).

## See also[edit]

## References[edit]

- ^
^{a}^{b}Elias, Peter (March 1975). "Universal codeword sets and representations of the integers".*IEEE Transactions on Information Theory*.**21**(2): 194–203. doi:10.1109/tit.1975.1055349.

## Further reading[edit]

- Hamada, Hozumi (June 1983). "URR: Universal representation of real numbers".
*New Generation Computing*.**1**(2): 205–209. doi:10.1007/BF03037427. ISSN 0288-3635. Retrieved 2018-07-09. (NB. The Elias δ code coincides with Hamada's URR representation.)