Near-Optimal Depth-Constrained Codes

P. Gupta, B. Prabhakar, and S. Boyd

IEEE Transactions on Information Theory, 50(12):3294-3298, December 2004.
Precursor, Near-Optimal Routing Lookups with Bounded Worst Case Performance, appeared in Proceedings IEEE INFOCOM, 3:1184-1192, Tel Aviv, March 2000.

near_opt_depth_constr_codes.pdf
opt_routing.pdf

This note considers an -letter alphabet in which the 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 . We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.