Elias delta code is a universal code

Universal code (data compression)

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...

 encoding the positive integers developed by Peter Elias

Peter Elias

Peter Elias was a pioneer in the field of information theory. Born in New Brunswick, New Jersey, he was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991....

. To code a number:

1. Write it in binary.
2. Count the bits and write down that number of bits in binary (X).
3. Use the binary representation written in step 1 again, remove the leading bit and write down the remaining bits (Y).
4. Append the second binary representation (Y) to the first binary representation (X).
5. 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:

1. Separate the integer into the highest power of 2 it contains (2^N' ) and the remaining N binary digits of the integer.
2. Encode N = N' + 1 with Elias gamma coding
   Elias gamma coding
   Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.-Encoding:To code a number:#Write it in binary....
   
   .
3. 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:

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 2^L, 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 2^N-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 = 2⁴ + 1 = 17

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

Encoding

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;
for (int temp = num; temp > 0; temp >>= 1) // calculate 1+floor(log2(num))
len++;
for (int temp = len; temp > 1; temp >>= 1) // calculate floor(log2(len))
lengthOfLen++;
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

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
}