- Elias delta coding
Elias delta code is a universal code encoding the positive integers. To code a number:
#Write it in binary.
#Count the bits and write down that number of bits in binary (X).
#Use the binary digit written in step 1 again, remove the leading bit and write down the remaining bits (Y).
#Append the second binary digit (Y) to the first binary digit (X).
#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:
#Separate the integer into the highest power of 2 it contains (2"N' ") and the remaining "N"' binary digits of the integer.
#Encode "N = N' + 1" withElias gamma coding .
#Append the remaining "N"' binary digits to this representation of "N".The code begins:
Implied probability 1 = 20 => N' = 0, N = 1 => 1 1/2 2 = 21 + "0" => N' = 1, N = 2 => 010"0" 1/16 3 = 21 + "1" => N' = 1, N = 2 => 010"1" " 4 = 2² + "0" => N' = 2, N = 3 => 011"00" 1/32 5 = 2² + "1" => N' = 2, N = 3 => 011"01" " 6 = 2² + "2" => N' = 2, N = 3 => 011"10" " 7 = 2² + "3" => N' = 2, N = 3 => 011"11" " 8 = 2³ + "0" => N' = 3, N = 4 => 00100"000" 1/256 9 = 2³ + "1" => N' = 3, N = 4 => 00100"001" " 10 = 2³ + "2" => N' = 3, N = 4 => 00100"010" " 11 = 2³ + "3" => N' = 3, N = 4 => 00100"011" " 12 = 2³ + "4" => N' = 3, N = 4 => 00100"100" " 13 = 2³ + "5" => N' = 3, N = 4 => 00100"101" " 14 = 2³ + "6" => N' = 3, N = 4 => 00100"110" " 15 = 2³ + "7" => N' = 3, N = 4 => 00100"111" " 16 = 24 + "0" => N' = 4, N = 5 => 00101"0000" 1/512 17 = 24 + "1" => N' = 4, N = 5 => 00101"0001" "
To decode an Elias delta-coded integer:
#Read and count zeroes from the stream until you reach the first one. Call this count of zeroes "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".
#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 = 24 + 1 = 17
This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding.
See also
*
Elias gamma coding
*Elias omega coding References
Wikimedia Foundation. 2010.