Elias delta coding

Last updated December 06, 2024 • 2 min readFrom Wikipedia, The Free Encyclopedia

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

Encoding

To code a number X ≥ 1:

Let N = ⌊log₂X⌋; be the highest power of 2 in X, so 2^N ≤ X < 2^N+1.
Let L = ⌊log₂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 $x$ , Elias delta (δ) uses $\lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1$ bits.^[1]^: 200 This is useful for very large integers, where the overall encoded representation's bits end up being fewer [than what one might obtain using Elias gamma coding] due to the $\log _{2}(\lfloor \log _{2}(x)\rfloor +1)$ portion of the previous expression.

The code begins, using $\gamma '$ instead of $\gamma$ :

Number	N	N+1	δ encoding	Implied probability
1 = 2⁰	0	1	`1`	1/2

2 = 2¹ + 0	1	2	`0 1 0 0`	1/16
3 = 2¹ + 1	1	2	`0 1 0 1`	1/16

4 = 2² + 0	2	3	`0 1 1 00`	1/32
5 = 2² + 1	2	3	`0 1 1 01`	1/32
6 = 2² + 2	2	3	`0 1 1 10`	1/32
7 = 2² + 3	2	3	`0 1 1 11`	1/32

8 = 2³ + 0	3	4	`00 1 00 000`	1/256
9 = 2³ + 1	3	4	`00 1 00 001`	1/256
10 = 2³ + 2	3	4	`00 1 00 010`	1/256
11 = 2³ + 3	3	4	`00 1 00 011`	1/256
12 = 2³ + 4	3	4	`00 1 00 100`	1/256
13 = 2³ + 5	3	4	`00 1 00 101`	1/256
14 = 2³ + 6	3	4	`00 1 00 110`	1/256
15 = 2³ + 7	3	4	`00 1 00 111`	1/256

16 = 2⁴ + 0	4	5	`00 1 01 0000`	1/512
17 = 2⁴ + 1	4	5	`00 1 01 0001`	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⁴ + 3 = 19

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

Example code

Encoding

voideliasDeltaEncode(char*source,char*dest){IntReaderintreader(source);BitWriterbitwriter(dest);while(intreader.hasLeft()){intnum=intreader.getInt();intlen=0;intlengthOfLen=0;len=1+floor(log2(num));// calculate 1+floor(log2(num))lengthOfLen=floor(log2(len));// calculate floor(log2(len))for(inti=lengthOfLen;i>0;--i)bitwriter.outputBit(0);for(inti=lengthOfLen;i>=0;--i)bitwriter.outputBit((len>>i)&1);for(inti=len-2;i>=0;i--)bitwriter.outputBit((num>>i)&1);}bitwriter.close();intreader.close();}

Decoding

voideliasDeltaDecode(char*source,char*dest){BitReaderbitreader(source);IntWriterintwriter(dest);while(bitreader.hasLeft()){intnum=1;intlen=1;intlengthOfLen=0;while(!bitreader.inputBit())// potentially dangerous with malformed files.lengthOfLen++;for(inti=0;i<lengthOfLen;i++){len<<=1;if(bitreader.inputBit())len|=1;}for(inti=0;i<len-1;i++){num<<=1;if(bitreader.inputBit())num|=1;}intwriter.putInt(num);// write out the value}bitreader.close();intwriter.close();}

Generalizations

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).

Related Research Articles

Elias $code$ or 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.

In mathematics, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the least integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

<span class="mw-page-title-main">Euler's constant</span> Constant value used in mathematics

Euler's constant is a mathematical constant, usually denoted by the lowercase Greek letter gamma, defined as the limiting difference between the harmonic series and the natural logarithm, denoted here by $log$ :

Truncated binary encoding is an entropy encoding typically used for uniform probability distributions with a finite alphabet. It is parameterized by an alphabet with total size of number n. It is a slightly more general form of binary encoding when n is not a power of two.

In mathematics, the binary logarithm is the power to which the number $2$ must be raised to obtain the value $n$ . That is, for any real number $x$ ,

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands.

The AKS primality test is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

<span class="mw-page-title-main">Mertens function</span> Summatory function of the Möbius function

In number theory, the Mertens function is defined for all positive integers n as

In number theory, the integer square root (isqrt) of a non-negative integer $n$ is the non-negative integer $m$ which is the greatest integer less than or equal to the square root of $n$ ,

In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.

In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, called the modulus of the operation.

Elias ω coding or Elias omega coding is a universal code encoding the positive integers developed by Peter Elias. Like Elias gamma coding and Elias delta coding, it works by prefixing the positive integer with a representation of its order of magnitude in a universal code. Unlike those other two codes, however, Elias omega recursively encodes that prefix; thus, they are sometimes known as recursive Elias codes.

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 (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity.

In number theory, a narcissistic number in a given number base $is a number that is the sum of its own digits each raised to the power of the number of digits.$

In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.

Levenshtein coding is a universal code encoding the non-negative integers developed by Vladimir Levenshtein.

A non-integer representation uses non-integer numbers as the radix, or base, of a positional numeral system. For a non-integer radix β > 1, the value of

In mathematics, trailing zeros are a sequence of 0 in the decimal representation of a number, after which no other digits follow.

AN codes are error-correcting code that are used in arithmetic applications. Arithmetic codes were commonly used in computer processors to ensure the accuracy of its arithmetic operations when electronics were more unreliable. Arithmetic codes help the processor to detect when an error is made and correct it. Without these codes, processors would be unreliable since any errors would go undetected. AN codes are arithmetic codes that are named for the integers $and that are used to encode and decode the codewords.$

References

1 2 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.

Elias delta coding

Contents

Encoding

Example code

Encoding

Decoding

Generalizations

See also

Related Research Articles

References

Further reading