Editing Elias delta coding

{{Use dmy dates|date=May 2019|cs1-dates=y}}
'''Elias δ code''' or '''Elias delta code''' is a [[Universal code (data compression)|universal code]] encoding the positive integers developed by [[Peter Elias]].<ref name="Elias"/>{{rp|200}}

== Encoding ==
To code a number ''X''&nbsp;≥ 1:
# Let ''N''&nbsp;= ⌊log<sub>2</sub> ''X''⌋; be the highest power of 2 in ''X'', so 2<sup>''N''</sup> ≤ ''X'' < 2<sup>''N''+1</sup>.
# Let ''L''&nbsp;= ⌊log<sub>2</sub> ''N''+1⌋ be the highest power of 2 in ''N''+1, so 2<sup>''L''</sup> ≤ ''N''+1 < 2<sup>''L''+1</sup>.
# 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<sup>''N''</sup>) 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 <math>x</math>, Elias delta (δ) uses <math>\lfloor \log_2(x) \rfloor  + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1</math> bits.<ref name="Elias"/>{{rp|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 <math>\log_2 (\lfloor \log_2(x) \rfloor +1)</math> portion of the previous expression.

The code begins, using <math>\gamma'</math> instead of <math>\gamma</math>:

{| class="wikitable"
! Number !! N !! N+1 !! δ encoding !! Implied probability
|-
| 1 = 2<sup>0</sup> || 0 || 1 || <code>1</code> || 1/2
|-
|colspan=5|
|-
| 2 = 2<sup>1</sup> + ''0'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''0''</code> || 1/16
|-
| 3 = 2<sup>1</sup> + ''1'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''1''</code> || 1/16
|-
|colspan=5|
|-
| 4 = 2<sup>2</sup> + ''0'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''00''</code> || 1/32
|-
| 5 = 2<sup>2</sup> + ''1'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''01''</code> || 1/32
|-
| 6 = 2<sup>2</sup> + ''2'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''10''</code> || 1/32
|-
| 7 = 2<sup>2</sup> + ''3'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''11''</code> || 1/32
|-
|colspan=5|
|-
| 8 = 2<sup>3</sup> + ''0'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''000''</code> || 1/256
|-
| 9 = 2<sup>3</sup> + ''1'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''001''</code> || 1/256
|-
| 10 = 2<sup>3</sup> + ''2'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''010''</code> || 1/256
|-
| 11 = 2<sup>3</sup> + ''3'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''011''</code> || 1/256
|-
| 12 = 2<sup>3</sup> + ''4'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''100''</code> || 1/256
|-
| 13 = 2<sup>3</sup> + ''5'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''101''</code> || 1/256
|-
| 14 = 2<sup>3</sup> + ''6'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''110''</code> || 1/256
|-
| 15 = 2<sup>3</sup> + ''7'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''111''</code> || 1/256
|-
|colspan=5|
|-
| 16 = 2<sup>4</sup> + ''0'' || 4 || 5 || <code>00&thinsp;1&thinsp;01 ''0000''</code> || 1/512
|-
| 17&nbsp;=&nbsp;2<sup>4</sup>&nbsp;+&nbsp;''1'' || 4 || 5 || {{nowrap|<code>00&thinsp;1&thinsp;01 ''0001''</code>}} || 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<sup>''L''</sup>, 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<sup>''N''</sup>.
#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<sup>4</sup> + 3 = 19

This code can be generalized to zero or negative integers in the same ways described in [[Elias gamma coding#Generalizations|Elias gamma coding]].

== Example code ==

=== Encoding ===
<syntaxhighlight lang="cpp">
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();
}
</syntaxhighlight>

=== Decoding ===
<syntaxhighlight lang="cpp">
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();
}
</syntaxhighlight>

== Generalizations ==<!-- This section is linked from [[Elias gamma coding]] -->
{{See also|Variable-length quantity#Zigzag encoding}}
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 [[Comparison of data serialization formats|"ZigZag" encoding from Protocol Buffers]] (not to be confused with [[Zigzag code]], nor the [[JPEG#Entropy coding|JPEG Zig-zag entropy coding]]).

== See also ==
* [[Elias gamma coding|Elias gamma (γ) coding]]
* [[Elias omega coding|Elias omega (ω) coding]]
* [[Golomb-Rice code]]

== References ==
{{Reflist|refs=
<ref name="Elias">{{cite journal |author-first=Peter |author-last=Elias |author-link=Peter Elias |title=Universal codeword sets and representations of the integers |journal=[[IEEE Transactions on Information Theory]] |volume=21 |issue=2 |pages=194–203 |date=March 1975 |doi=10.1109/tit.1975.1055349}}</ref>
}}

== Further reading ==
* {{cite journal |title=URR: Universal representation of real numbers |author-first=Hozumi |author-last=Hamada |journal=New Generation Computing |issn=0288-3635 |date=June 1983 |volume=1 |issue=2 |pages=205–209 |doi=10.1007/BF03037427 |s2cid=12806462 |url=https://www.researchgate.net/publication/220619145_URR_Universal_Representation_of_Real_Numbers<!-- https://link.springer.com/article/10.1007/BF03037427 --><!-- https://www.semanticscholar.org/paper/URR%3A-Universal-representation-of-real-numbers-Hamada/ae987cfad0b240d49245995421d0ec147ac72ae1 --> |access-date=2018-07-09}} (NB. The Elias δ code coincides with Hamada's URR representation.)

{{Compression methods}}

[[Category:Entropy coding]]
[[Category:Numeral systems]]
[[Category:Data compression]]