Elias delta coding

<h2 id="encoding">Encoding</h2>
To code a number X ≥ 1:

<ol><li>Let N = ⌊log2 X⌋; be the highest power of 2 in X, so 2N ≤ X < 2N+1.</li>
<li>Let L = ⌊log2 N+1⌋ be the highest power of 2 in N+1, so 2L ≤ N+1 < 2L+1.</li>
<li>Write L zeros, followed by</li>
<li>the L+1-bit binary representation of N+1, followed by</li>
<li>all but the leading bit (i.e. the last N bits) of X.</li></ol>
An equivalent way to express the same process:

<ol><li>Separate X into the highest power of 2 it contains (2N) and the remaining N binary digits.</li>
<li>Encode N+1 with <a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a>.</li>
<li>Append the remaining N binary digits to this representation of N+1.</li></ol>
To represent a number 
 
 
 
 x
 
 
 {\displaystyle x}
 
, Elias delta (δ) uses 
 
 
 
 ⌊
 
 log
 
 2
 
 
 ⁡
 (
 x
 )
 ⌋
 +
 2
 ⌊
 
 log
 
 2
 
 
 ⁡
 (
 ⌊
 
 log
 
 2
 
 
 ⁡
 (
 x
 )
 ⌋
 +
 1
 )
 ⌋
 +
 1
 
 
 {\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}
 
 bits.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>: 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 <a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a>] due to the 
 
 
 
 
 log
 
 2
 
 
 ⁡
 (
 ⌊
 
 log
 
 2
 
 
 ⁡
 (
 x
 )
 ⌋
 +
 1
 )
 
 
 {\displaystyle \log _{2}(\lfloor \log _{2}(x)\rfloor +1)}
 
 portion of the previous expression.
The code begins, using 
 
 
 
 
 γ
 ′
 
 
 
 {\displaystyle \gamma '}
 
 instead of 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
:

<table><tbody><tr><th>Number</th><th>N</th><th>N+1</th><th>δ encoding</th><th>Implied probability</th></tr><tr><td>1 = 20</td><td>0</td><td>1</td><td>1</td><td>1/2</td></tr><tr><td colspan="5"></td></tr><tr><td>2 = 21 + 0</td><td>1</td><td>2</td><td>0 1 0 0</td><td>1/16</td></tr><tr><td>3 = 21 + 1</td><td>1</td><td>2</td><td>0 1 0 1</td><td>1/16</td></tr><tr><td colspan="5"></td></tr><tr><td>4 = 22 + 0</td><td>2</td><td>3</td><td>0 1 1 00</td><td>1/32</td></tr><tr><td>5 = 22 + 1</td><td>2</td><td>3</td><td>0 1 1 01</td><td>1/32</td></tr><tr><td>6 = 22 + 2</td><td>2</td><td>3</td><td>0 1 1 10</td><td>1/32</td></tr><tr><td>7 = 22 + 3</td><td>2</td><td>3</td><td>0 1 1 11</td><td>1/32</td></tr><tr><td colspan="5"></td></tr><tr><td>8 = 23 + 0</td><td>3</td><td>4</td><td>00 1 00 000</td><td>1/256</td></tr><tr><td>9 = 23 + 1</td><td>3</td><td>4</td><td>00 1 00 001</td><td>1/256</td></tr><tr><td>10 = 23 + 2</td><td>3</td><td>4</td><td>00 1 00 010</td><td>1/256</td></tr><tr><td>11 = 23 + 3</td><td>3</td><td>4</td><td>00 1 00 011</td><td>1/256</td></tr><tr><td>12 = 23 + 4</td><td>3</td><td>4</td><td>00 1 00 100</td><td>1/256</td></tr><tr><td>13 = 23 + 5</td><td>3</td><td>4</td><td>00 1 00 101</td><td>1/256</td></tr><tr><td>14 = 23 + 6</td><td>3</td><td>4</td><td>00 1 00 110</td><td>1/256</td></tr><tr><td>15 = 23 + 7</td><td>3</td><td>4</td><td>00 1 00 111</td><td>1/256</td></tr><tr><td colspan="5"></td></tr><tr><td>16 = 24 + 0</td><td>4</td><td>5</td><td>00 1 01 0000</td><td>1/512</td></tr><tr><td>17 = 24 + 1</td><td>4</td><td>5</td><td>00 1 01 0001</td><td>1/512</td></tr></tbody></table>
To decode an Elias delta-coded integer:

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

This code can be generalized to zero or negative integers in the same ways described in <a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a>.

<h2 id="example-code">Example code</h2>
<h3>Encoding</h3>
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 = 1 + floor(log2(num));  // calculate 1+floor(log2(num))
        lengthOfLen = floor(log2(len)); // 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();
}

<h3>Decoding</h3>
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();
}

<h2 id="generalizations">Generalizations</h2>
See also: <a href="/facts/Variable-length_quantity/403RnSeL">Variable-length quantity § Zigzag encoding</a>
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 <a href="/facts/Bijection/j4gTuTmW">bijection</a>, 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 <a href="/facts/Comparison_of_data_serialization_formats/YGkeqybD">"ZigZag" encoding from Protocol Buffers</a> (not to be confused with <a href="/facts/Zigzag_code/CeQQI12Y">Zigzag code</a>, nor the <a href="/facts/JPEG/HQ8QS3uB">JPEG Zig-zag entropy coding</a>).

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma (γ) coding</a></li>
<li><a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega (ω) coding</a></li>
<li><a href="/facts/Golomb-Rice_code/bUyW4uLN">Golomb-Rice code</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Hamada, Hozumi (June 1983). <a href="https://www.researchgate.net/publication/220619145_URR_Universal_Representation_of_Real_Numbers">"URR: Universal representation of real numbers"</a>. New Generation Computing. 1 (2): 205–209. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF03037427">10.1007/BF03037427</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0288-3635">0288-3635</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12806462">12806462</a>. Retrieved 2018-07-09. (NB. The Elias δ code coincides with Hamada's URR representation.)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="/wiki/Peter_Elias" target="_blank">/wiki/Peter_Elias</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Peter_Elias" target="_blank">/wiki/Peter_Elias</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Elias delta coding open-in-new

Elias delta coding