Elias δ code or Elias delta code is a
universal code encoding the positive integers developed by
Peter Elias
Peter Elias (November 23, 1923 – December 7, 2001) 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. In 1955, Elias introdu ...
.
Encoding
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
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.
Encoding
To code a number ''x'' � ...
.
#Append the remaining ''N'' binary digits to this representation of ''N''+1.
To represent a number
, Elias delta (δ) uses
bits.
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
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.
Encoding
To code a number ''x'' � ...
] due to the
portion of the previous expression.
The code begins, using
instead of
:
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
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.
Encoding
To code a number ''x'' � ...
.
Example code
Encoding
void eliasDeltaEncode(char* source, char* dest)
Decoding
void eliasDeltaDecode(char* source, char* dest)
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
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
, 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
In coding theory, a zigzag code is a type of linear error-correcting code introduced by .. They are defined by partitioning the input data into segments of fixed size, and adding sequence of check bits to the data, where each check bit is the exc ...
, nor the
JPEG Zig-zag entropy coding).
See also
*
Elias gamma (γ) coding
*
Elias omega (ω) coding
*
Golomb-Rice code
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 ...
References
Further reading
* (NB. The Elias δ code coincides with Hamada's URR representation.)
{{Compression methods
Numeral systems
Lossless compression algorithms