Levenshtein coding

Levenshtein coding

Levenshtein coding is a universal code encoding the non-negative integers developed by Vladimir Levenshtein.

The code of zero is "0"; to code a positive number:
#Initialize the step count variable "C" to 1.
#Write the binary representation of the number without the leading "1" to the beginning of the code.
#Let "M" be the number of bits written in step 2.
#If "M" is not 0, increment "C", repeat from step 2 with M as the new number.
#Write "C" "1" bits and a "0" to the beginning of the code.

The code begins: 0 0 1 10 2 110 0 3 110 1 4 1110 0 00 5 1110 0 01 6 1110 0 10 7 1110 0 11 8 1110 1 000 9 1110 1 001 10 1110 1 010 11 1110 1 011 12 1110 1 100 13 1110 1 101 14 1110 1 110 15 1110 1 111 16 11110 0 00 0000 17 11110 0 00 0001

To decode a Levenstein-coded integer:
#Count the number of "1" bits until a "0" is encountered.
#If the count is zero, the value is zero, otherwise
#Start with a variable "N", set it to a value of 1 and repeat "count minus 1" times:
#Read "N" bits, prepend "1", assign the resulting value to "N"

The Levenstein code of a positive integer is always one bit longer than the Elias omega code of that integer.

ee also

*Elias omega coding
*Log*

Sources

* [http://www.compression.ru/download/articles/int/levenstein_1968_on_the_redundancy_and_delay.pdf 1968 paper by V. I. Levenshtein] (in Russian)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Vladimir Levenshtein — Vladimir Iosifovich Levenshtein (en russe Владимир Иосифович Левенштейн, né en 1935) est un scientifique russe. Ses travaux portent en grande partie sur la théorie des codes. On lui doit notamment une notion de distance permettant de quantifier l …   Wikipédia en Français

  • 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

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Levenstein — Levenstein, Levenshtein is a surname and may refer to: * Jim Levenstein, a fictional character in the American Pie film series * Vladimir Levenshtein (born 1935), Russian scientist ** Levenshtein distance, a metric for comparing two strings or… …   Wikipedia

  • List of Russian IT developers — This list of Russian IT developers includes the famous hardware engineers, computer scientists and programmers from the Russian Empire, the Soviet Union and the Russian Federation. See also the Category:Russian computer scientists and… …   Wikipedia

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

Share the article and excerpts

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