Editing Elias omega coding (section)

{{Short description|Universal code encoding positive integers}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
'''Elias ω coding''' or '''Elias omega coding''' is a [[universal code (data compression)|universal code]] encoding the positive integers developed by [[Peter Elias]]. Like [[Elias gamma coding]] and [[Elias delta coding]], it works by prefixing the positive 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'''.

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

To encode a [[positive integer]] ''N'':
#Place a "0" at the end of the code.
#If ''N''&nbsp;= 1, stop; encoding is complete.
#Prepend the [[binary numeral system|binary]] representation of ''N'' to the beginning of the code. This will be at least two bits, the first bit of which is a 1.
#Let ''N'' equal the number of bits just prepended, minus one.
#Return to Step 2 to prepend the encoding of the new ''N''.

To decode an Elias omega-encoded positive integer:
#Start with a variable ''N'', set to a value of 1.
#If the next bit is a "0" then stop.  The decoded number is ''N''.
#If the next bit is a "1" then read it plus ''N'' more bits, and use that binary number as the new value of ''N''.  Go back to Step 2.