| Elias Delta Coding |
Article Index for Elias |
Shopping Coding |
Website Links For Elias |
Information AboutElias Delta Coding |
| CATEGORIES ABOUT ELIAS DELTA CODING | |
| numeration | |
| lossless compression algorithms | |
|
#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), substract 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'' with Elias Gamma Coding . #Append the remaining ''N''' binary digits to this representation of ''N''. The code begins: 1 = 20 => N' = 0, N = 1 => 1 2 = 21 + ''0'' => N' = 1, N = 2 => 010''0'' 3 = 21 + ''1'' => N' = 1, N = 2 => 010''1'' 4 = 22 + ''0'' => N' = 2, N = 3 => 011''00'' 5 = 22 + ''1'' => N' = 2, N = 3 => 011''01'' 6 = 22 + ''2'' => N' = 2, N = 3 => 011''10'' 7 = 22 + ''3'' => N' = 2, N = 3 => 011''11'' 8 = 23 + ''0'' => N' = 3, N = 4 => 00100''000'' 9 = 23 + ''1'' => N' = 3, N = 4 => 00100''001'' 10 = 23 + ''2'' => N' = 3, N = 4 => 00100''010'' 11 = 23 + ''3'' => N' = 3, N = 4 => 00100''011'' 12 = 23 + ''4'' => N' = 3, N = 4 => 00100''100'' 13 = 23 + ''5'' => N' = 3, N = 4 => 00100''101'' 14 = 23 + ''6'' => N' = 3, N = 4 => 00100''110'' 15 = 23 + ''7'' => N' = 3, N = 4 => 00100''111'' 16 = 24 + ''0'' => N' = 4, N = 5 => 00101''0000'' 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 REFERENCES |
|
|