A balanced code with r check bits and k information bits is a binary code of length k+r and cardinality 2/sup k/ such that each codeword is balanced; that is, it has [(k+r)/2] 1's and [(k+r)/2] 0's. This paper contains new methods to construct efficient balanced codes. To design a balanced code, an information word with a low number of 1's or 0's is compressed and then balanced using the saved space. On the other hand, an information word having almost the same number of 1's and 0's is encoded using the single maps defined by Knuth's (1986) complementation method. Three different constructions are presented. Balanced codes with r check bits and k information bits with k/spl les/2/sup r+1/-2, k/spl les/3/spl times/2/sup r/-8, and k/spl les/5/spl times/2/sup r/-10r+c(r), c(r)/spl isin/{-15, -10, -5, 0, +5}, are given, improving the constructions found in the literature. In some cases, the first two constructions have a parallel coding scheme.

Binary prefix codes with the constraint that each codeword must end with a "1" have been recently introduced by Berger and Yeung (1990). We analyze the performance of such codes by investigating their average codeword length. In particular, we show that a very simple strategy permits the construction of a "1"-ended binary prefix code whose average codeword length is less than H+1 for any discrete source with entropy H. We also prove a tight lower bound on the optimal average codeword length in terms of H and of the minimum letter probability of the source. Finally, we discuss the problem of finding an optimum feasible code.>

Some limitations are given on the redundancy of D-ary codes with maximal codeword length L. An upper bound that improves on a previous result of E.N. Gilbert (1971) is given. It is then shown that the redundancy of these constrained codes is very close to that of the unconstrained Huffman codes when the number of codewords N is such that ND/sup 1-L/ becomes negligible. A tight bound is given on the redundancy when only the most likely probabilities are known. In the binary case, a tight lower bound is given on the redundancy when only the least likely probability is known.>

The problem of constructing statistically synchronizable codes over arbitrary alphabets and for any finite source is considered. It is shown how to efficiently construct a statistically synchronizable code whose average codeword length is within the least likely codeword probability from that of the Huffman code for the same source. Moreover, a method is given for constructing codes having a synchronizing codeword. The method yields synchronous codes that exhibit high synchronizing capability and low redundancy.>

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p/sub 1/ of the most likely source letter is provided. For large values of p/sub 1/, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived.>

Upper and lower bounds are obtained for the redundancy of binary Huffman codes for a memoryless source whose least likely source letter probability is known. Tight upper bounds on redundancy in terms of the most and least likely source letter probabilities are provided.>

An ambiguous point in the paper by Apostolico and Fraenkel (see ibid., vol.IT-33, no.2, p.238-45, March 1987) is clarified. New codes that have better asymptotic performances and better synchronization capability are introduced.>

Immutable codes, which have recently been introduced as a tool for preventing undesirable changes of data recorded over write-once memories, are considered. The have the property that any change of recorded information over such memories can be detected. A fast algorithm for testing whether a variable-length code is immutable is presented. The complexity of the algorithm is O(L/sup 2/), where L is the sum of the codeword lengths.>

Bounds on the redundancy of Huffman codes in terms of the probability p/sub 1/ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2/sup l+1/+1)or=2. It is shown that the new bounds are the tightest possible for these intervals.>

The authors consider statistically synchronizable variable-length codes, i.e. codes that admit decoders able to self-synchronize with high probability if the input sequence of code symbols is long enough. They show that a necessary and sufficient condition for the existence of a statistically self-synchronizing decoder and, therefore, for a code to be statistically synchronizable, is that the code has a synchronizing sequence. They also give a decision procedure to test whether a code has a synchronizing sequence. Finally, they specialize the procedure to obtain a simple and efficient algorithm to test the statistical synchronizability property of prefix codes.>

Upper bounds on the entropy of a countable integer-valued random variable are furnished in terms of the expectation of the logarithm function. In particular, an upper bound is derived that is sharper than that of P. Elias (ibid., vol.IT-21, no.2, p.194-203, 1975), for all values of E/sub p/(log). Bounds that are better only for large values of E/sub p/ than the previous known upper bounds are also provided.>

New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 \leq P_{1} \leq 0.4is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1}is the only known probability is presented. The improved bound is the tightest possible for1/3 \leq P_{1} \leq 0.4. Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1}andP_{N}are known.

Proof is given that no regular or synchronizable universal codeword sets can achieve optimality. Some asymptotic properties of a remarkable class of regular codeword sets related to the Fibonacci representation of integers are also obtained.

A multivalued encoding is a variable length coding system in which more than one codeword may correspond to each source symbol. The properties of unique decipherability, decipherability with finite delay, and synchronizability for multivalued encodings are characterized. In particular, the property, of unique decipherability is considered, and a recent conjecture about decipherability with finite delay is proved to be true. The notion of a synchronizable multivalued code is also introduced, and a necessary. and sufficient condition for a multivalued code to be synchronizable is provided. Some auxiliary results are also obtained.

A simple and complete analysis is given for establishing whether a code is uniquely decipherable, has finite delay, or is synchronizable. The conditions are based on certain combinatorial properties of the codewords and are such that for a finite code there exists an effective procedure for testing the properties in question.