Search

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability. [ABSTRACT FROM AUTHOR]

Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of $m$ -variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables $m$ , which improve upon the known bounds for any $m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any $m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of $m$ -variate monomials whose restriction to an arbitrary line in ${\mathbb {F}}_{q}^{m}$ is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables $m$ is fixed and the alphabet size $q=2^\ell $ is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

With the prevalence of orthogonal frequency-division multiplexing (OFDM) in many standards, e.g., IEEE 802.11, IEEE 802.16, DVB-T, and DVB-T2, a number of variant modulation schemes based on OFDM have been proposed, which resort to signal sparsity to further enhance spectral efficiency and mitigate the high peak-to-average ratio (PAPR) problem. Among these variants, OFDM with subcarrier number modulation (OFDM-SNM) has been proven to be efficient for simple communication systems with low constellation modulation orders and limited decoding capability. To rigorously verify the performance advantages of OFDM-SNM, we present the study of OFDM-SNM in this paper from the information-theoretic perspective. In particular, we determine an upper bound on the mutual information of OFDM-SNM in closed form by using the log sum inequality. Also, we analyze the optimal pattern utilization probabilities (PUPs) for OFDM-SNM by channel-dependent coding and propose an easy-to-implement iterative algorithm to approach the optimal PUPs. Moreover, considering the practical achievability, we propose a Huffman coding based achievable PUP vector construction scheme to obtain the achievable PUPs and the corresponding achievable rate. We carry out numerical simulations to verify the effectiveness of this study and illustrate the efficiency of the obtained PUPs in comparison with several benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the update bandwidth in distributed storage systems (DSSs). The update bandwidth, which measures the transmission efficiency of the update process in DSSs, is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated. This paper contains the following contributions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth (MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irregular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code redundancy and the minimum update bandwidth. Fourth, we introduce explicit code constructions of MR-MUB codes and MUB codes with the smallest code redundancy. Fifth, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes. Last, we construct a class of $(n = k + 2, k)$ vertical maximum-distance separable (MDS) array codes that can achieve all of the minimum code redundancy, the minimum update bandwidth and the optimal repair bandwidth of irregular array codes. [ABSTRACT FROM AUTHOR]

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉ + O(log log n) redundancy bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth’s balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit. [ABSTRACT FROM AUTHOR]

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder’s sequence X differs from the decoder’s sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size. [ABSTRACT FROM AUTHOR]

In this paper, we present a variable-length binary code for permutations of degree n, where n is a power of 2. The Lehmer code and its variants provide a bijection between permutations and the indexes in lexicographic ordering. They provide compression of permutations approaching Shannon bound at the expense of structural information. The variable-length code proposed in this paper has asymptotically optimal compression capability while preserving structural information of permutations. In other words, the code encodes the way a permutation is organized, and is optimal in the sense that the ratio of average codeword length and the entropy of permutations approaches 1 as n tends to infinity. The encoding and decoding are efficient. Like the Lehmer code and other enumerative codes, it is not necessary to construct look-up tables. The code is complete and satisfies the prefix condition. Furthermore, the codeword length indicates how “well shuffled” a permutation is. Permutations with longer codewords seem more “random.” An enumeration method of the variable-length code is also given by using T. Cover’s enumerative coding scheme and Schalkwijk code. This gives a different indexing from the Lehmer code. This work can be extended to the case of arbitrary $n$ in a straightforward way. [ABSTRACT FROM AUTHOR]

We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived. [ABSTRACT FROM AUTHOR]

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 codelengths 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$. [ABSTRACT FROM AUTHOR]

This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem. [ABSTRACT FROM AUTHOR]

A central question in the classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and independent identically distributed (i.i.d.) compression rate of the Shannon entropy of the source. In this paper, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated with the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length, and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here, we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in the quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Furthermore, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation. [ABSTRACT FROM AUTHOR]

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider, we have two sources with known discrete distributions, and we wish to find codes that maximize the success probability that the two source outputs are represented in $L$ bits or less. A good practical use for this problem is a table with two-field entries that is stored in a memory of a fixed width $L$ . Such tables of very large sizes are common in network switches/routers and in data-intensive machine-learning applications. After defining the problem formally, we solve it optimally with an efficient code-design algorithm. We also solve the problem in the more constrained case where a single code is used in both fields (to save space for storing code dictionaries). For both code-design problems we find decompositions that yield efficient dynamic-programming algorithms. With the help of an empirical study we show the success probabilities of the optimal codes for different distributions and memory widths. In particular, this paper demonstrates the superiority of the new codes over existing compression algorithms. [ABSTRACT FROM AUTHOR]

Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with p\max \geq 1 /2, where p\max is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$ -bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4$ . [ABSTRACT FROM AUTHOR]

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$ . [ABSTRACT FROM PUBLISHER]

Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper, we introduce and compare several techniques to store prefix codes. Let N be the sequence length and n be the alphabet size. Then, a naive storage of an optimal prefix code uses \mathcal O \hspace -.5ex \left ( n\log n \right ) bits. Our first technique shows how to use \mathcal O \hspace -.5ex \left ( n\log \log (N/n) \right ) bits to store the optimal prefix code. Then, we introduce an approximate technique that, for any 0<\epsilon <1/2 , takes {\mathcal {O} \hspace {-.5ex} \left ({ {n \log \log (1 / \epsilon )} }\right )} bits to store a prefix code with an average codeword length within an additive \epsilon of the minimum. Finally, a second approximation takes, for any constant c > 1 , \vphantom {\sum ^{R^{R}}}\mathcal {O}(n^{1 / c} \log n) bits to store a prefix code with an average codeword length at most c$ times the minimum. In all cases, our data structures allow encoding and decoding of any symbol in {\mathcal {O} \hspace {-.5ex} \left ({ {1} }\right )} time. We experimentally compare our new techniques with the state of the art, showing that we achieve sixfold-to-eightfold space reductions, at the price of a slower encoding (2.5–8 times slower) and decoding (12–24 times slower). The approximations further reduce this space and improve the time significantly, up to recovering the speed of classical implementations, for a moderate penalty in the average code length. As a byproduct, we compare various heuristic, approximate, and optimal algorithms to generate length-restricted codes, showing that the optimal ones are clearly superior and practical enough to be implemented. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

This paper presents lossless prefix codes optimized with respect to a payoff criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm, which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and scalar parameter. The payoff criterion considered encompasses a tradeoff between maximum and average codeword length; it is related to a payoff criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length payoff criterion subject to a limited length constraint. A special case of the first related payoff is connected to coding problems involving source probability uncertainty and codeword overflow probability, whereas the second related payoff compliments limited length Huffman coding algorithms. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter q, 0 < q < 1. By encoding pairs of symbols, it may be possible to reduce the redundancy penalty of symbol-by-symbol encoding, while preserving the simplicity of the encoding and decoding procedures typical of Golomb codes and their variants. It is shown that optimal codes for these so-called two-dimensional (2-D) geometric distributions are parameter singular, in the sense that a prefix code that is optimal for one value of the parameter q cannot be optimal for any other value of q. This is in sharp contrast to the one-dimensional (1-D) case, where codes are optimal for positive-length intervals of the parameter q. Thus, in the 2-D case, it is infeasible to give a compact characterization of optimal codes for all values of the parameter q, as was done in the 1-D case. Instead, optimal codes are characterized for a discrete sequence of values of q that provides good coverage of the unit interval. Specifically, optimal prefix codes are described for q = 2^-1/k\;(k \geq 1), covering the range q \geq 1 \over 2, and q = 2^-k\;(k > 1), covering the range q < 1 \over 2. The described codes produce the expected reduction in redundancy with respect to the 1-D case, while maintaining low-complexity coding operations. [ABSTRACT FROM PUBLISHER]

This paper presents new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources according to various nonlinear codeword length objectives. Like the most well-known redundancy bounds for minimum average redundancy coding—Huffman coding—these are in terms of a form of entropy and/or the probability of an input symbol, often the most probable one. The bounds here, some of which are tight, improve on known bounds of the form L\in [H,H+1), where H is some form of entropy in bits (or, in the case of redundancy objectives, 0) and L is the length objective, also in bits. The objectives explored here include exponential-average length, maximum pointwise redundancy, and exponential-average pointwise redundancy (also called d^th exponential redundancy). The first of these relates to various problems involving queueing, uncertainty, and lossless communications; the second relates to problems involving Shannon coding and universal modeling. Also explored here for these two objectives is the related matter of individual codeword length. [ABSTRACT FROM AUTHOR]

Given a discrete memoryless source X, it is well known that the expected codeword length per symbol Ln (X) of an optimal prefix code for the extended source Xn converges to the source entropy as n approaches infinity. However, the sequence Ln (X) need not be monotonic in n, which implies that the coding efficiency cannot be increased by simply encoding a larger block of source symbols (unless the block length is appropriately chosen). As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is useful to know when an increase in the block length guarantees a decrease in the expected codeword length per symbol. While this paper does not provide a complete answer to that question, we give some properties of Ln (X) and obtain for each n ≥ 1 and nondyadic p1n (p1 is the probability of the most likely source symbol) an integer k* for which Lkn (X) < Ln(X) for all k ≥ k*, implying that the coding efficiency of encoding blocks of length kn is higher than that of encoding blocks of length n for all k ≥ k*. This question is simpler in part because Lkn (X) ≤ Ln (X) is guaranteed for all ≥ 1 and k ≥ 1, but our results distinguish scenarios where in- creasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar. [ABSTRACT FROM AUTHOR]

Whereas Huffman coding finds a prefix code minimizing mean codeword length for a given finite-item probability distribution, quasiarithmeric or quasilinear coding problems have the goal of minimizing a generalized mean of the form φ-1 (Σipiφ(li)), where li denotes the length of the ith codeword, pi denotes the corresponding probability, and φ is a monotonically increasing cost function. Such problems, proposed by Campbell, have a number of diverse applications. Several cost functions are shown here to yield quasiarithmetic problems with simple redundancy bounds in terms of a generalized entropy. A related property, also shown here, involves the existence of optimal codes: For ‘well-behaved’ cost functions, optimal codes always exist for (possibly infinite-alphabet) sources having finite generalized entropy. An algorithm is introduced for finding binary codes optimal for convex cost functions. This algorithm, which can be extended to other minimization utilities, can be performed using quadratic time and linear space. This reduces the computational complexity of a problem involving minimum delay in a queue, allows combinations of previously considered problems to be optimized, and greatly expands the set of problems solvable in quadratic time and linear space. [ABSTRACT FROM AUTHOR]

We show that verifying a given prefix code for optimality requires Ω(n log n) time, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting. [ABSTRACT FROM AUTHOR]

Two sufficient conditions are given for the existence of binary fix-free codes (i.e., both prefix-free and suffix-free). Let L be a finite multiset of positive integers whose Kraft sum is at most 3/4. It is shown that there exists a fix-free code whose codeword lengths are the elements of L if either of the following two conditions holds. 1) The smallest integer in L is at least 2, and no integer in L, except possibly the largest one, occurs more than 2min(L)-2 times. ii) No integer in L, except possibly the largest one, occurs more than twice. The results move closer to the Ahlswede-Balkenhol-Khachatrian conjecture that Kraft sums of at most 3/4 suffice for the existence of fix-free codes. [ABSTRACT FROM AUTHOR]

We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions. [ABSTRACT FROM AUTHOR]

In the first part of this paper, we tackle the case where a variable length-to-block Tunstall code is used to encode the wrong source (miscoding). It turns out that, exactly as happens in the case with Huffman coding, the asymptotic excess rate is given by the informational divergence between the probability distribution ruling the source and the probability distribution for which the Tunstall code had been devised. We also prove asymptotic equality between the individual rate of a codeword and the corresponding self-information. This allows us to bound the maximal and the minimal length in a Tunstall tree. In the second part of the paper we study the case where the probability distribution of the source changes in time. If this happens, it is necessary to frequently update the current code, to ensure that the optimality conditions concerning its rate are met. This coding procedure is known as adaptive coding. We propose some schemes for adaptive Tunstall coding, based on the structure of the coding tree, on the "ordering property", analogous to Gallager's (1978) sibling property of the Huffman code, and on the "Tunstall regions", analogous to the attraction regions due to Longo and Galasso (1982). [ABSTRACT FROM PUBLISHER]