Elias delta coding

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" with Elias 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.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Elias omega coding — is a universal code encoding the positive integers. Like Elias gamma coding and Elias delta coding, it works by prefixing the integer with a representation of its order of magnitude in a universal code. Unlike those other two codes, however,… …   Wikipedia

  • Elias gamma coding — Elias gamma code is a universal code encoding positive integers. It is used most commonly when coding integers whose upper bound cannot be determined beforehand. To code a number: #Write it in binary. #Subtract 1 from the number of bits written… …   Wikipedia

  • Elias coding — is term used for one of two types of lossless coding schemes used in digital communications:* Shannon Fano Elias coding, a precursor to arithmetic coding, in which probabilities are used to determine codewords; * Universal coding using one of… …   Wikipedia

  • Delta encoding — Not to be confused with Elias delta coding. Delta encoding is a way of storing or transmitting data in the form of differences between sequential data rather than complete files; more generally this is known as data differencing. Delta encoding… …   Wikipedia

  • Exponential-Golomb coding — An Exponential Golomb code (or just Exp Golomb code) of order k is a type of universal code, parameterized by a whole number k. To encode a nonnegative integer in an order k exp Golomb code, one can use the following method: # Take the number in… …   Wikipedia

  • Huffman coding — Huffman tree generated from the exact frequencies of the text this is an example of a huffman tree . The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits, as opposed of 288 bits if 36… …   Wikipedia

  • Adaptive Huffman coding — (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one pass encoding and …   Wikipedia

  • Modified Huffman coding — is used in fax machines to encode black on white images (bitmaps). It combines the variable length codes of Huffman coding with the coding of repetitive data in run length encoding. External links Modified Huffman coding from UNESCO . Archived… …   Wikipedia

  • NegaFibonacci coding — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Universal code (data compression) — In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”