Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Even–Rodeh coding
open-in-new
<h2 id="encoding">Encoding</h2> <p>To code a <a href="/facts/Non-negative_integer/u65og8JE">non-negative integer</a> N in Even–Rodeh coding: </p> <ol><li>If N is not less than 4 then set the coded value to a single 0 bit. Otherwise the coded value is empty.</li> <li>If N is less than 8 then prepend the coded value with 3 bits containing the value of N and stop.</li> <li>Prepend the coded value with the <a href="/facts/Binary_numeral_system/a6JDSRPs">binary</a> representation of N.</li> <li>Store the number of bits prepended in step 3 as the new value of N.</li> <li>Go back to step 2.</li></ol> <p>To decode an Even–Rodeh-coded integer: </p> <ol><li>Read 3 bits and store the value into N. <ul><li>If the first bit read was 0 then stop. The decoded number is N.</li> <li>If the first bit read was 1 then continue to step 2.</li></ul></li> <li>Examine the next bit. <ul><li>If the bit is 0 then read 1 bit and stop. The decoded number is N.</li> <li>If the bit is 1 then read N bits, store the value as the new value of N, and go back to step 2.</li></ul></li></ol> <h2 id="examples">Examples</h2> <table><tbody><tr><th>Number</th><th>Encoding</th><th>Implied probability</th></tr><tr><td>0</td><td>000</td><td>1/8</td></tr><tr><td>1</td><td>001</td><td>1/8</td></tr><tr><td>2</td><td>010</td><td>1/8</td></tr><tr><td>3</td><td>011</td><td>1/8</td></tr><tr><td colspan="3"></td></tr><tr><td>4</td><td>100 0</td><td>1/16</td></tr><tr><td>5</td><td>101 0</td><td>1/16</td></tr><tr><td>6</td><td>110 0</td><td>1/16</td></tr><tr><td>7</td><td>111 0</td><td>1/16</td></tr><tr><td colspan="3"></td></tr><tr><td>8</td><td>100 1000 0</td><td>1/256</td></tr><tr><td>9</td><td>100 1001 0</td><td>1/256</td></tr><tr><td colspan="3">︙</td></tr><tr><td>15</td><td>100 1111 0</td><td>1/256</td></tr><tr><td colspan="3"></td></tr><tr><td>16</td><td>101 10000 0</td><td>1/512</td></tr><tr><td colspan="3">︙</td></tr><tr><td>2761</td><td>100 1100 101011001001 0</td><td>1/1,048,576</td></tr><tr><td colspan="3">︙</td></tr></tbody></table> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega (ω) coding</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Even, Shimon; Rodeh, Michael (April 1978). "Economical encoding of commas between strings". Communications of the ACM. 21 (4): 315–317. doi:10.1145/359460.359480. <a href="/wiki/Shimon_Even" target="_blank">/wiki/Shimon_Even</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>