Even–Rodeh coding

Even–Rodeh code is a universal code encoding the non-negative integers developed by Shimon Even and Michael Rodeh.

Encoding

To code a non-negative integer in Even–Rodeh coding:

1. If is not less than 4 then set the coded value to a single <code>0</code> bit. Otherwise the coded value is empty.
2. If is less than 8 then prepend the coded value with 3 bits containing the value of and stop.
3. Prepend the coded value with the binary representation of .
4. Store the number of bits prepended in step 3 as the new value of .
5. Go back to step 2.

To decode an Even–Rodeh-coded integer:

1. Read 3 bits and store the value into .
2. * If the first bit read was <code>0</code> then stop. The decoded number is .
3. * If the first bit read was <code>1</code> then continue to step 2.
4. Examine the next bit.
5. * If the bit is <code>0</code> then read 1 bit and stop. The decoded number is .
6. * If the bit is <code>1</code> then read bits, store the value as the new value of , and go back to step 2.

Examples

See also

• Elias omega (ω) coding

References