Elias omega coding

Elias omega coding

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, Elias omega recursively encodes that prefix; thus, they are sometimes known as recursive Elias codes.

To code a number:
#Put a 'group' of "0" at the end of the representation.
#If the number to be encoded is 1, stop; if not, add the binary representation of the number as a 'group' to the beginning of the representation.
#Repeat the previous step, with the number of digits just written, minus 1, as the new number to be encoded.

The code begins:

Implied probability 1 0 1/2 2 10 0 1/8 3 11 0 " 4 10 100 0 1/64 5 10 101 0 " 6 10 110 0 " 7 10 111 0 " 8 11 1000 0 1/128 9 11 1001 0 " 10 11 1010 0 " 11 11 1011 0 " 12 11 1100 0 " 13 11 1101 0 " 14 11 1110 0 " 15 11 1111 0 " 16 10 100 10000 0 1/2048 17 10 100 10001 0 "

To decode an Elias omega-coded integer:
#Start with a variable "N", set to a value of 1.
#Read the first 'group', which will either be a single "0", or a "1" followed by "N" more digits. If it is a "0", it means the value of the integer is 1; if it starts with a "1", then "N" becomes the value of the group interpreted as a binary number.
#Read each successive group; it will either be a single "0", or a "1" followed by "N" more digits. If it is a "0", it means the value of the integer is "N"; if it starts with a "1", then "N" becomes the value of the group interpreted as a binary number.

Omega coding is used in applications where the largest encoded value is not known ahead of time, or to compress data in which small values are much more frequent than large values.

ee also

*Elias delta coding
*Elias gamma coding


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • 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 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… …   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

  • 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

  • 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… …   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

  • Prefix code — A prefix code is a code, typically a variable length code, with the prefix property : no code word is a prefix of any other code word in the set. A code with code words {0, 10, 11} has the prefix property; a code consisting of {0, 1, 10, 11} does …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Projet:Médecine/Index — Articles 0 9 1,2 dibromo 3 chloropropane · 112 (numéro d urgence européen) · 1935 en santé et médecine · 1941 en santé et médecine · 1er régiment médical · 2 iodothyronine déiodinase · 2,4,6 trichlorophénol · 2005 en santé et médecine · 2006 en… …   Wikipédia en Français

Share the article and excerpts

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