Arithmetic Coding

In arithmetic coding, a message is encoded as a real number in an interval from one to zero.  Arithmetic coding typically has a better compression ratio than Huffman coding, as it produces a single symbol rather than several seperate codewords.   Arithmetic coding is a lossless coding technique.  There are a few disadvantages of arithmetic coding.  One is that the whole codeword must be received to start decoding the symbols, and if there is a corrupt bit in the codeword, the entire message could become corrupt.  Another is that there is a limit to the precision of the number which can be encoded, thus limiting the number of symbols to encode within a codeword.  There also exists many patents upon arithmetic coding, so the use of some of the algorithms also call upon royalty fees.

Here is the arithmetic coding algorithm, with an example to aid understanding.

  1. Start with an interval [0, 1), divided into subintervals of all possible symbols to appear within a message.  Make the size of each subinterval proportional to the frequency at which it appears in the message.  Eg:
    2. Symbol Probability Interval
    a 0.2 [0.0, 0.2)
    b 0.3 [0.2, 0.5)
    c 0.1 [0.5, 0.6)
    d 0.4 [0.6, 1.0)
  2. When encoding a symbol, "zoom" into the current interval, and divide it into subintervals like in step one with the new range.  Example: suppose we want to encode "abd".  We "zoom" into the interval corresponding to "a", and divide up that interval into smaller subintervals like before.  We now use this new interval as the basis of the next symbol encoding step.
    3. Symbol New  "a" Interval
    a [0.0, 0.04)
    b [0.04, 0.1)
    c [0.1, 0.102)
    d [0.102, 0.2)
  3. Repeat the process until the maximum precision of the machine is reached, or all symbols are encoded.  To encode the next character "b", we zuse the "a" interval created before, and zoom into the subinterval "b", and use that for the next step.  This produces:
    4. Symbol New "b" Interval
    a [0.102, 0.1216)
    b [0.1216, 0.151)
    c [0.151, 0.1608)
    d [0.1608, 0.2)

    And lastly, the final result is:

    Symbol New "d" Interval
    a [0.1608, 0.16864)
    b [0.16864, 0.1804)
    c [0.1804, 0.18432)
    d [0.18432, 0.2)
  4. Transmit some number within the latest interval to send the codeword.  The number of symbols encoded will be stated in the protocol of the image format, so any number within [0.1608, 0.2) will be acceptable.

To decode the message, a similar algorithm is followed, except that the final number is given, and the symbols are decoded sequentially from that.