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: If is not less than 4 then set the coded value to a single 0 bit. Otherwise the coded value is empty. If is less than 8 then prepend the coded value with 3 bits containing the value of and stop. Prepend the coded value with the binary representation of . Store the number of bits prepended in step 3 as the new value of . Go back to step 2.

To decode an Even–Rodeh-coded integer: Read 3 bits and store the value into . If the first bit read was 0 then stop. The decoded number is . If the first bit read was 1 then continue to step 2. Examine the next bit. If the bit is 0 then read 1 bit and stop. The decoded number is . If the bit is 1 then read bits, store the value as the new value of , and go back to step 2.

Examples

Number Encoding Implied probability 0 000 1/8 1 001 1/8 2 010 1/8 3 011 1/8 4 100 0 1/16 5 101 0 1/16 6 110 0 1/16 7 111 0 1/16 8 100 1000 0 1/256 9 100 1001 0 1/256 ︙ 15 100 1111 0 1/256 16 101 10000 0 1/512 ︙ 2761 1/1,048,576 ︙

Even–Rodeh coding

Bron en licentie