Categories
  • Entropy coding
    •   Encyclosphere.org ENCYCLOREADER
      supported by EncyclosphereKSF

    Even–Rodeh coding

    From Wikipedia - Reading time: 4 min

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

    Encoding[edit]

    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[edit]

    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[edit]

    • Elias omega (ω) coding

    References[edit]

    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 licensed under CC BY-SA 3.0.
    Original source: https://en.wikipedia.org/wiki/Even–Rodeh coding
    Status: article is cached
    Encyclosphere.org EncycloReader is supported by the EncyclosphereKSF