Elias omega coding

Elias ω coding or Elias omega coding is a <a href="/facts/Universal_code_(data_compression)/9zn1cM2M">universal code</a> encoding the positive integers developed by <a href="/facts/Peter_Elias/WVVQ1nKs">Peter Elias</a>. Like <a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a> and <a href="/facts/Elias_delta_coding/LoDaPWqx">Elias delta coding</a>, it works by prefixing the positive integer with a representation of its <a href="/facts/Order_of_magnitude/cWzRP2dM">order of magnitude</a> 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 <a href="/facts/Data_compression/gMFuY4FT">compress</a> data in which small values are much more frequent than large values.
To encode a <a href="/facts/Positive_integer/u65og8JE">positive integer</a> N:

<ol><li>Place a "0" at the end of the code.</li>
<li>If N = 1, stop; encoding is complete.</li>
<li>Prepend the <a href="/facts/Binary_numeral_system/a6JDSRPs">binary</a> representation of N to the beginning of the code. This will be at least two bits, the first bit of which is a 1.</li>
<li>Let N equal the number of bits just prepended, minus one.</li>
<li>Return to Step 2 to prepend the encoding of the new N.</li></ol>
To decode an Elias omega-encoded positive integer:

<ol><li>Start with a variable N, set to a value of 1.</li>
<li>If the next bit is a "0" then stop. The decoded number is N.</li>
<li>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.</li></ol>

Elias omega coding open-in-new

Elias omega coding