Near-Optimal Depth-Constrained CodesP. Gupta, B. Prabhakar, and S. Boyd
IEEE Transactions on Information Theory, 50(12):3294-3298, December 2004. This note considers an \(n\)-letter alphabet in which the \(i\)th letter is accessed with probability \(p_i\). The problem is to design efficient algorithm for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector \(q=(q_1^*, \ldots, q_n^*)\) in an appropriate convex set \(\mathcal S\), so as to minimize the relative entropy \(D(p\|q)\) over all \(q \in \mathcal S\). Methods from convex optimization give an explicit solution for \(q^*\) in terms of \(p\). We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes. |