a variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. This class of codes is applied to speed up the decoding process, for the decoder can decode from both sides of th...
详细信息
a variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. This class of codes is applied to speed up the decoding process, for the decoder can decode from both sides of the compressed file simultaneously. In this paper, we study some basic properties of fix-free codes. We prove a sufficient and a necessary condition for the existence of fix-free codes, and we obtain some new upper bounds on the redundancy of optimal fix-free codes.
We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a ...
详细信息
We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost. (C) 2011 Elsevier B.V. All rights reserved.
作者：
Yekhanin, SMIT
Dept Elect Engn & Comp Sci Cambridge MA 02139 USA
A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. In a fix-free code, any finite sequence of codewords can be decoded in both directions, which can improve the rob...
详细信息
A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. In a fix-free code, any finite sequence of codewords can be decoded in both directions, which can improve the robustness to channel noise and speed up the decoding process. In this correspondence, we prove a new sufficient condition of the existence of fix-free codes and improve the upper bound on the redundancy of optimal fix-free codes.
A variable-length code is called a fix-free code if it is both prefix-free and suffix-free. In this paper, we consider some basic properties of fix-free codes. We obtain one lower and one upper bound on the redundancy...
详细信息
ISBN:
(纸本)9781424422463
A variable-length code is called a fix-free code if it is both prefix-free and suffix-free. In this paper, we consider some basic properties of fix-free codes. We obtain one lower and one upper bound on the redundancy of the optimal fix-free code. Comparing these bounds, we derive an upper bound on the length of the most likely source symbol in terms of its probability.
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...
详细信息
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. plays a fundamental role in all problems that arise for gamma < 1.
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 ar...
详细信息
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 with n symbols is less than 11/n + 0.11345 bits for n >32 . Some other upper bounds are also derived which are either suboptimal in some sense for small n or easily computable for large $n$ or 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.
暂无评论