===========================================================================
CSC 310H                     Lecture 9 Summary                    Fall 2007
===========================================================================

------
Topics
------

 -  How many bits do we transmit?
 -  Comparison with block Huffman coding
 -  Stream code: send bits as they become available
 -  Arithmetic coding, take 2.
 -  References: section 6.2, lectures 7-8 from 2006 course by prof Roweis.

-----------------------------
How many bits do we transmit?
-----------------------------

 -  Once we establish that our N-symbol message is encoded as the interval
    [u,v), how big a bitstring b do we have to transmit?

 -  We want int(b) to be included in [u,v).

 -  Suppose b has k bits. Then the interval int(b) has length 2^{-k}.

 -  If you look at all intervals of length 2^{-k} of the form [0, 2^{-k}),
    [2^{-k}, 2*2^{-k}), [2*2^{-k}, 3*2^{-k}) and so on, one of them will
    be completely contained inside [u,v) whenever v-u >= 2*2^{-k}. Solving,
    we get k >= 1 + ln(1/(v-u)).

 -  Thus, k = 1 + ceil(ln(1/(v-u))) is good enough.

 -  Then, k < 2 + ln(1/(v-u))

 -  A block B of N symbols that has probability p_B = v - u gets encoded
    with less then 2 + ln(1/(v-u)) bits, so

        L' < sum_B{ p_B * (2 + ln(1/(v-u))) } = 2 + H(X^N)

 -  The per-symbol average codeword length becomes L = L'/N < H(X) + 2/N

 -  Thus, as in the case of Huffman coding, using large N we get close to
    the entropy.

------------------------------------
Comparison with block Huffman coding
------------------------------------

 1. Using the N-th extension

     a. We do NOT need to pre-compute codes for exponentially many N-tuples
        of symbols. This is a huge improvement.

     b. We still need the N-symbol look-ahead before we emit an encoding.

 2. We can easily change the probabilities that we are using, provided that
    the endocder and the decoder are doing the same thing, of course. For
    example, if after seeing a part of the input bit string on which we had
    started with probability of seeing a 0 as .9, we now want to use .8
    instead, we can simply start subdividing the intervals using the new
    proportion.

 3. We might have introduced a new problem, high precision floating point
    operations, which is used whenever intervals are being subdivided.

-----------------------------------------------
Stream code: send bits as they become available
-----------------------------------------------

Idea:

 -  The moment the interval [u,v) becomes completely contained inside
    [0, 1/2) = [0.0, 0.1), we know that no matter what symbols follow,
    the bit string we will end up sending will start with a 0.

 -  The encoder can, at this point, send the 0, and double the size of the
    interval [u,v) as [2*u,2*v).

 -  Similarly, when [u,v) becomes enclosed in [1/2, 1) = [0.1, 1.0), the
    encoder can send the bit 1 and double [u,v) and shift it back to [0,1)
    as [ 2*(u-1/2), 2*(v-1/2) ).

 -  It turns out that we will obtain huge improvements by sending bits as
    soon as they become available.

     -  We no longer need the N-symbol look-ahead.

     -  The size of the interval [u,v) can be maintained to be "large",
        and this will intuitively prevent floating-point arithmetic errors.

     -  In fact, we don't need to use an explicit block size any more! We
        can instead go through the entire message, compute the tiny
        interval inside [0,1) to which this message corresponds, and send
        a corresponding bit string.

-------------------------
Arithmetic coding, take 2
-------------------------

Algo:

    u <- 0
    v <- 1
    for every symbol a_{i_k} in turn
        r <- v-u
        u <- u + r*sum_{j=1}^{i_k-1}{p_j}
        v <- v + r*p_{i_k}
        while (u >= 1/2) or (v <= 1/2)
            if u >= 1/2
                send 1
                u <- 2*(u-1/2)
                v <- 2*(v-1/2)
            else if v <= 1/2
                send 0
                u <- 2*u
                v <- 2*v
            end if
        end while
    end for
    send enough final bits to specify a number inside [u,v)