Optimal Codes With Limited Kraft Sum

The well-known Huffman algorithm is an elegant approach to solve the basic problem of finding the optimal code among those with Kraft sums smaller than or equal to 1. In this paper, an extended problem is investigated, where the Kraft sum of the usable codes is limited to a given real number γ, 0 <; γ <; 1. Unlike the case γ = 1 (i.e., Huffman coding), for γ <; 1, the Kraft sum of the optimal code is not necessarily equal to γ. However, we show that the Kraft sum of the optimal code lies in a finite set of rational numbers which depend on the value of γ. This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to γ´, where γ´ has a finite binary representation and 0 <; γ´ <; 1. To do so, the set of N-tuple codelength vectors with a specific Kraft sum γ´ is characterized. The binary representation of γ plays a fundamental role in all problems that arise for γ <; 1.