Even-Rodeh coding

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

Encoding

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

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

To decode an Even-Rodeh-coded integer:

  1. Read 3 bits and store the value into N.
    • If the first bit read was 0 then stop. The decoded number is N.
    • If the first bit read was 1 then continue to step 2.
  2. Examine the next bit.
    • If the bit is 0 then read 1 bit and stop. The decoded number is N.
    • If the bit is 1 then read N bits, store the value as the new value of N, 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 1000 1/16
7 1110 1/16
8 10010000 1/256
15 10011110 1/256
16 101100000 1/512
2761 10011001010110010010 1/1,048,576

See also

References

  1. 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.
This article is issued from Wikipedia - version of the 6/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.