The main advantage of usingasymmetricfix-free codes is the possibility ofbidirectional decodingwhich can improve decoding speed and error resilience. However, the cost of these benefits is higher redundancy and the need to design two different decoders.Symmetricfix-free codes have the same forward and backward decoders but the redundancy of an optimal code can be unlimited. Withweakly symmetricfix-free (WSF) codes, the forward and backward decoders are the same and the redundancy of the optimal WSF code for an arbitrary source is limited to 1.0817 bits in the worst case. In this paper, we show that this redundancy is much less on average, i.e., the average redundancy of an optimal WSF code is at most 0.1241 bits for alphabet sizes larger than 32. TheA*-based search algorithm is modified to obtain the optimal WSF code for the average distribution of monotone sources withnsymbols forn≤ 64. Based on these optimal codes and a new code product operator, some suboptimal WSF codes with many codewords are obtained. Then upper bounds on the average redundancy of optimal WSF codes are derived for arbitrarily largen. These bounds are almost the same as those derived recently for asymmetric fix-free codes. This result encourages the use of WSF codes to take advantage of the same forward and backward decoders and the low redundancy.

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.

The tight lower bound on the redundancy of optimal prefix-free codes in terms of a given symbol probability (not necessarily the largest or the smallest one) has been derived in the literature. The first goal of this paper is to derive the tight lower bounds in terms of j (j > 1) known symbol probabilities of the source using some properties of Kullback-Leibler distance. Since fix-free codes are special prefix-free codes (for which no codeword is a suffix of the other codewords), it is clear that all lower bounds on the redundancy of optimal prefix-free codes are also valid for fix-free ones. Accordingly, the second question of the paper is on the tightness of the derived lower bounds for optimal fix-free codes. It is proven that these lower bounds are tight for optimal fix-free codes if j ≤ 3, and are not tight for j ≥ 4. Also, it is shown that the tight lower bound in terms of the probability of the most likely symbol is the same for optimal prefix-free and optimal fix-free codes.

The problem of designing a fixed code for encoding all monotone sources with a large alphabet size n is studied. It is proved that if the code-lengths of a code sequence are of order O(log n), then the redundancy for almost all monotone sources with n symbols is very close to that for a specific distribution, so-called average distribution. Noting this point, for any large alphabet size n, a new code with a very simple structure is proposed whose redundancy is close to that of the Huffman code for almost all monotone sources with alphabet size n.

For each alphabet size up to 30, a symmetric reversible variable length code (RVLC) is determined which is most likely to be optimal in average codeword length. It is shown that these codes are optimal for more than half of all the possible sources.

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$.

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 this paper, the difference between the redundancy of the optimal asymmetric/symmetric fix-free code, and that of the optimal prefix-free code is considered as the penalty of benefiting from the desired properties of fix-free codes. This penalty is studied from different perspectives. In particular, it is shown that the average penalty of asymmetric fix-free codes is less than 0.21 bit per symbol. Moreover, it is proved that when the source alphabet size is sufficiently large, for almost all sources, the penalty is less than or equal to 0.182 bit per symbol. Regarding symmetric fix-free codes, it is shown that the average penalty tends to infinity as the source alphabet size increases.

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.

Applying a fast over-segmentation algorithm to image and working on a region-based graph (instead of the pixel-based graph) is an efficient approach to reduce the computational complexity of graph-based image segmentation methods. Nevertheless, some undesirable effects may arise if the conventional cost functions, such as Ncut, AverageCut, and MinCut, are employed for partitioning the region-based graph. This is because these cost functions are generally tailored to pixel-based graphs. In order to resolve this problem, we first introduce a new class of cost functions (containing Ncut and AverageCut) for graph partitioning whose corresponding suboptimal solution can be efficiently computed by solving a generalized eigenvalue problem. Then, among these cost functions, we propose one that considers the size of regions in the partitioning procedure. By simulation, the performance of the proposed cost function is quantitatively compared with that of the Ncut and AverageCut.

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.

The performance of optimal prefix-free encoding for memoryless sources with a large alphabet size is studied. It is shown that the redundancy of the Huffman code for almost all sources with a large alphabet size$n$is very close to that of the average distribution of the monotone sources with$n$symbols. This value lies between 0.02873 and 0.02877 bit for sufficiently large$n$.

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.

In order to determine how suboptimal the Shannon code is, one should compare its performance with that of the optimal code, i.e., the corresponding Huffman code, in some sense. It is well known that in the worst case the redundancy of both the Shannon and Huffman codes can be arbitrarily close to 1. Beyond this worst case viewpoint, very little is known. In this paper, we compare the performance of these codes from an average point of view. The redundancy is considered as a random variable on the set of all sources with n symbols and its average is evaluated. It is shown that the average redundancy of the Shannon code is very close to 0.5 bits, whereas the average redundancy of the Huffman code is less than n-1(1+ln n)+0.086 bits . It is also proven that the variance of the redundancy of the Shannon code tends to zero as n increases. Therefore, for sources with alphabet size n, the redundancy of the Shannon code is approximately 0.5 bits with probability approaching 1 as n→ ∞.

The Shannon code is a very simple suboptimal scheme for computing prefix-free codelengths for a given memoryless source. A recursive version of the well-known Shannon code (RSh) is investigated in this paper. It has a redundancy which never exceeds that of the Shannon code. Unlike the Huffman code, the RSh code and its variations can be directly applied to sources with an infinitely countable alphabet. The average redundancy, taken over the set of all n-tuple distributions, is considered as a criterion for code comparisons. For n>;40, the average redundancy is approximately 0.14 bits for the RSh code, compared to approximately 0.5 and 0.03 bits for the Shannon and Huffman codes, respectively. For large n, a constrained version of the RSh code, called CRSh, has an average redundancy of only 0.07 bits for unsorted symbol probabilities. If the symbol probabilities are sorted in descending order, then a very simple modification of the RSh algorithm results in a code which is near-optimal from the average redundancy point of view.

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.

A greedy scheme called Greedy Codeword Assignment Scheme (GCAS) is proposed to assign D-ary codewords to the given code-lengths ¿1,¿2,...,¿n, so that they satisfy the fix-free property. This scheme guarantees that a D-ary fix-free code can be obtained whenever ¿i=1nD-¿¿ ¿(D), where ¿(D) is equal to 5/8 for D even and very close to 5/8 for D odd. This result can be regarded as an extension of Yekhanin's theorem on the existence of binary fix-free codes. In the special case D=2 , the greediness of GCAS enables us to prove that if mini ¿i= 2, the inequality ¿i=1n2-¿i¿ 21/32 implies the existence of a binary fix-free code with code-lengths ¿1,¿2,...,¿n.

Recently, a linear programming (LP) decoder has been introduced for binary linear codes. Although the performance of an LP decoder has a close relationship with the form of the parity check matrix (or equivalently with the Tanner graph) of the code, there is no clear approach to choosing a suitable form for LP decoding. In this paper, we focus on the class of cyclic codes, and show that the cyclic structure of the code can be used to expand the parity check matrix and obtain a low redundancy form which is suitable for LP decoding. Performance results are given which demonstrate the effectiveness of the proposed algorithm.

For a given memoryless information source, the Huffman code is the optimal prefix-free code in the sense of redundancy. Generally, the length of each codeword in the Huffman code is a function of all symbol probabilities p1, p2, ..., pn. In contrast, with the best known suboptimal code, i.e., the Shannon code, the length of the i-th codeword (i.e. [- log pi]) is a function of only pi. In this paper, two recursive versions of the Shannon code (RYY and RSh) are proposed which have redundancy which lies between that of the Huffman code and the Shannon code. In particular, the redundancy is not greater than that of the Shannon code and the i-th codeword length does not depend on pi+1, pi+2, ..., pn. In order to evaluate the overall performance of the proposed codes, their redundancy is considered as a random variable on the set of all sources with n symbols. An algorithm for generating random n-tuple distributions is derived and the expected value of the redundancy of the resulting codes is estimated. Recently, it was proven that the average redundancy of the Shannon code is around 0.5 bits. Simulation shows that for n > 20 the average redundancy of the proposed codes are about 0.1 and 0.06, while it is approximately 0.03 for the Huffman code.

The problem of selecting a code for finite monotone sources with N symbols is considered. The selection criterion is based on minimizing the average redundancy (called Minave criterion) instead of its maximum (i.e., Minimax criterion). The average probability distribution PNmacr, whose associated Huffman code has the minimum average redundancy, is derived. The entropy of the average distribution (i.e., H(PNmacr)) and the average entropy of the monotone distributions (i.e., H(PNmacr)) are studied. It is shown that both logN-H(PNmacr) and logN-H(PNmacr) are asymptotically equal to a constant (sime0.61). Therefore, there is only a negligible penalty (at most 1.61 bits/symbol) in using a simple fixed-length code with respect to the optimal code. An efficient near-optimal encoding technique is also proposed. The consequences of the two approaches, i.e., Minave and Minimax, are compared in terms of their associated distributions and associated codes. In order to evaluate the average performance of the Minimax code, we prove that the informational divergence of the average distribution and Minimax distribution asymptotically grows as -2.275+loglogN

The minimax distribution PFNdefined by the probabilities pi,FN= 1/lambdaN(i-1)(i-1)/iiplays an important role in the context of encoding finite monotone sources with unknown probabilities. The Shannon code for this distribution is a suboptimal minimax code. The average performance of this suboptimal code is considered in this paper. In order to evaluate the average performance of the minimax code, we compare it with the minave code which minimizes the average redundancy over all monotone sources with N symbols. To achieve this, we study the informational divergence of the minave and minimax distributions and prove that it asymptotically grows as -2.275+log log N. The log log N degradation in average performance should not be regarded as a drawback of the minimax code because the minimum average codeword length over the class of monotone sources grows as log N, which asymptotically dominates log log N

In this paper, the average probability distribution P~/sup N/~ of equiprobable finite monotone sources, where N is the number of symbols, is derived and some properties of this distribution are investigated. The associated Huffman code has the minimum redundancy in the average sense. An efficient suboptimal encoding technique is proposed. We show that log N -H(P~/sup N/~) is a constant asymptotically, and consequently there is a negligible penalty (asymptotically) in using a fixed length code. The length of the shortest codeword should be modified such that lim/sub N/spl rarr//spl infin// l/sub N//l/sub 1/=2. This limit cannot be a constant for minimax and universal codes such as the /spl omega/ and /spl delta/ codes. These properties are also shown to hold when the number of symbols is unknown but bounded.