Tu banner alternativo

Even–Rodeh coding

The topic of Even–Rodeh coding is a topic that has generated great interest in today's society. With the advancement of technology and globalization, Even–Rodeh coding has become a relevant topic that impacts different aspects of daily life. From Even–Rodeh coding person or event that has marked a before and after, to Even–Rodeh coding concept or trend that is currently in vogue, Even–Rodeh coding is something that deserves our attention and analysis. In this article, we will explore the various aspects of Even–Rodeh coding and its relevance in modern society.

Tu banner alternativo

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 8 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 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 100 1100 101011001001 0 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.
Wikious
Boobota
Sagapedia