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$\gamma $,$0<\gamma <1$. Unlike the case$\gamma =1$(i.e., Huffman coding), for$\gamma <1$, the Kraft sum of the optimal code is not necessarily equal to$\gamma $. 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$\gamma $. This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to$\gamma '$, where$\gamma '$has a finite binary representation and$0<\gamma '<1$. To do so, the set of$N$-tuple codelength vectors with a specific Kraft sum$\gamma '$is characterized. The binary representation of$\gamma $plays a fundamental role in all problems that arise for$\gamma <1$.

Dominant codelength sequences for reversible variable length codes (RVLCs) have been recently introduced and studied as a means to looking into optimal RVLCs. However, obtaining the dominant sequences for RVLCs is computationally challenging. In this paper, we consider a special subset of all RVLCs, namely, the sequentially-constructible (SC) RVLCs, for which the dominant sequences can be obtained with less computational complexity. Of course, this time saving is achieved at the cost of losing the optimality. However, it is shown that the dominant sequences for SC RVLCs provide acceptable performance in terms of the redundancy. Specifically, it is seen that the worst case penalty in using the optimal SC RVLCs with respect to the optimal RVLCs is at most 2/9 bit per symbol for alphabet size of up to 16. While obtaining the dominant sequences of SC RVLCs is relatively faster, it will still become challenging as the search space of the relevant branch-and-bound algorithm gets larger, when the source alphabet size increases. In order to further reduce the time complexity, we propose an alternative approach to a table of SC RVL codelength sequences, which avoids the branch-and-bound algorithm. It is shown that the codes obtained by this approach perform almost as well as the SC dominant sequences. Specifically, for an alphabet size of up to 21, the redundancy of this approach is, at most, 2/19 bit more than the optimal SC RVLCs.

Bidirectional decoding improves the error resilience of the fix-free codes, which is important in some applications like video coding. However, in general, two separate decoders must be designed for forward and backward decoding and hence, the cost of decoding is almost doubled. For the symmetric fix-free codes, although the forward and backward decoders are the same, the redundancy could be much greater than the case of asymmetric fix-free codes. In this paper, a class of fix-free codes, called weakly symmetric, is studied. A code is weakly symmetric if the reverse of each codeword itself is a codeword. This imposes a much weaker constraint on the codewords than what is necessitated by the symmetric codes, i.e., each codeword must be equal to its reverse. We show that the forward and backward decoders of a weakly symmetric fix-free code are essentially the same. In addition, it is shown that two significant sufficient conditions for the existence of asymmetric fix-free codes are also applicable to the case of weakly symmetric fix-free codes. As a result, we conclude that for any memoryless source, the redundancy of the optimal weakly symmetric fix-free code is at most 1.0817 bits. Moreover, it can be only 0.8 bit greater than the redundancy of the Huffman code in the worst case. In summary, weakly symmetric fix-free codes can be regarded as an option by which one can to some extent achieve the low redundancy of asymmetric fix-free codes and the low-cost bidirectional decoding of symmetric fix-free codes, simultaneously.

One of the most important challenges in the context of fix-free codes is proving the$ {{ 3}\over { 4}}$-conjecture, which guarantees the existence of fix-free codewords of lengths$\ell _{1},\ell _{2},\ldots, \ell _{N}$if$\sum _{i=1}^{N}2^{-\ell _{i}}\leq {{ 3}\over { 4}}$. Although this conjecture has not become a theorem yet, some researchers have proved the problem with some extra constraints on the codelengths. One of those, we call it Yekhanin's constraint, is$\sum _{i:\ell _{i}-\lambda \leq 1}2^{-\ell _{i}}\geq {{ 1}\over { 2}}$, where$\lambda =\min _{k}\ell _{k}$. In this paper, it is shown that such a constraint is not so restrictive. We prove that almost 93.8% of the$N$-tuple codelength vectors with Kraft sum$ {{ 3}\over { 4}}$do satisfy Yekhanin's constraint. One can optimistically interpret this result as almost 93.8% of the road of proving the$ {{ 3}\over { 4}}$-conjecture is paved.