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)