It is shown that efficient reversible variable length codes (RVLCs) with numerous codewords can be obtained if suboptimal RVLCs for the average distributions of monotone sources with relatively small alphabet sizes are multiplied by some fixed-length codes. Employing these RVLCs, the best known upper bounds on the average redundancy of optimal RVLC are almost halved. In particular, it is proved that the average redundancy of optimal RVLC for sources withnsymbols is less than 11/n+0.11345 bits forn> 32. Some other upper bounds are also derived which are either suboptimal in some sense for smallnor easily computable for largenor descriptive of asymptotic behavior. Moreover, we prove that the penalty of using optimal RVLC instead of Huffman code is less than 0.0848 bits for almost all sources with sufficiently large alphabet size. These results provide stronger evidence that, overall, the cost of benefiting from the desired properties of RVLC is not significant in terms of the redundancy.

In the context of fix-free codes, the most important and immediate consequence of the 3/4-conjecture (if it is proven), is that the redundancy of an optimal binary fix-free code never exceeds 1 bit, as with the optimal prefix-free codes, i.e. Huffman codes. In this paper, this bound on the redundancy is proven without requiring the conjecture to be true. To do so, we use two known sufficient conditions for the existence of binary fix-free codes to derive an improved upper bound on the redundancy of an optimal fix-free code in terms of the largest symbol probability.

In order to investigate the cost of employing fix-free codes instead of the well-established prefix-free codes, some upper bounds on the redundancy of the optimal fix-free codes and their difference with the corresponding Huffman codes are presented. Unlike the conventional approach, which is based on some Shannon-like suboptimal codes, we examine the redundancy of a better Huffman-like code. An algorithm is proposed for deriving optimal binary codeword lengths with Kraft-sum [5/8] for a given probability distribution. The existence of a fix-free code with such codelengths is guaranteed by Yekhanin's theorem. It is shown that the redundancy of this fix-free code is, at most, 0.8 bit greater than that of the Huffman code and does not exceed [8/3]-log3 ≅ 1.0817 bits. This upper bound is [4/3]-log[5/3] ≅0.5964 bit less than the best known one. If the [3/4]-conjecture is proved sometime in the future, the presented upper bound on the redundancy of the optimal fix-free codes (i.e., 1.0817) will be improved by only [5/3]-log3 ≅ 0.0817 . In addition to these general bounds, all known upper bounds in terms of the largest, the smallest, and an arbitrary given symbol probability are substantially improved.