In network communication, the source often transmits messages at several different information rates within a session. How to deal with information transmission and network error correction simultaneously under different rates is introduced in this paper as a variable-rate network error correction problem. Apparently, linear network error correction maximum distance separable (MDS) codes are expected to be used for these different rates guaranteeing the maximal error-correcting capability. For this purpose, designing a linear network error correction MDS code based on the existing results for each information rate is an alternative solution, but it is inefficient due to its high complexity. In order to solve the problem more efficiently, we present the concept of variable-rate linear network error correction MDS codes preserving local encoding kernels, that is, these linear network error correction MDS codes of different rates have the same local encoding kernel at each internal node. Thus, each nonsource node always uses the same local kernel for coding, no matter what the rate is. Furthermore, we propose an approach to construct such a family of variable-rate network MDS codes and give an algorithm for efficient implementation. This approach economizes the storage space for each internal node, and saves resources and time for transmissions on networks. Moreover, the performance of our proposed algorithm is analyzed, including the field size, the time complexity, the encoding complexity at the source node, and the decoding methods. Finally, a random method is introduced for constructing such a family of variable-rate network MDS codes, and a lower bound on the success probability of this random method is given, which shows that this probability will approach to one as the base field size goes to infinity.

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to NEC, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed by Zhang in 2008, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear NEC. Motivated partly by the performance analysis of random linear network coding, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear NEC. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in a paper by Balli and colleagues, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at mostd.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well-known (and unsolved) index coding problem of information theory. We represent the problem by a bipartite demand graph. Uncoded transmission is optimal if and only if this graph is acyclic. Next, we define a code-constrained capacity region that restricts attention to any prespecified set of coding actions. A dynamic max-weight algorithm that acts over variable length frames is developed. The algorithm allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. A simple set of codes that exploit cycles in the demand graph are shown to be optimal for a class of broadcast relay problems.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well known (and unsolved) index coding problem of information theory. Rather than achieving the full capacity region, we develop a code-constrained capacity region, which restricts attention to a pre-specified set of coding actions. We develop a dynamic max-weight algorithm that allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. Further, we provide a simple set of codes based on cycles in the underlying demand graph. We show these codes are optimal for a class of broadcast relay problems.

The achievable information rate region problem of multisource multisink network coding for general acyclic networks with arbitrary transmission requirements has previously been studied, where inner and outer bounds on the region were derived in terms of Γ*, the fundamental region of entropy functions. In this paper, we derive the exact characterization of the achievable rate region in terms of entropic functions, thus closing the gap between the existing inner and outer bounds.

Interactive encoding and decoding with tree decoding (referred to simply as tree interactive encoding and decoding (TRIED)) is considered for the problem of lossless source coding with decoder only side information. A TRIED scheme is proposed and demonstrated that when applied to encode any conditionally Φ-mixing source of length n, its error probability decays polynomially with respect to n, average rate is around conditional entropy rate, and average computational complexity of encoding and decoding is O(n ln n).

Network error correction coding (NEC) has attracted a lot of attention in recent years because of its potential usefulness in network communications. Several kinds of errors may occur in communication networks using network coding. This includes random errors, erasures, and errors caused by attacks from malicious nodes. The main goal of the theory of NEC is to deal with these errors efficiently. Two kinds of network models have been considered in network coding theory: coherent and noncoherent networks. A network is called coherent if network characteristics are known to senders and receivers, and called noncoherent if they are unknown. Although both scenarios are theoretically interesting, the noncoherent network model fits better to the requirements in most applications. So far, there are two lines of research in the theory of NEC. One approach follows the classical method by representing messages by sequences and the other approach uses the theory of rank metric codes for network error correction by representing messages by subspaces. Following both approaches, basic theories have been developed. This includes the formulation of channel models, the characterization of error correction/detection capabilities for various kinds of errors, the derivation of bounds for NECs, the study of existence and constructions of optimal codes, the development of encoding and decoding techniques, and the design of code suitable for real applications. In this paper, we summarize some important contributions in this research direction.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ..., XNare encoded in a frame by frame manner, the encoder for each frame Xkcan use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i) }i=1∞. A novel computation approach is proposed to analytically characterize, numerically compute, and compare the minimum total rate of causal video coding Rc*(D1, ...,DN) required to achieve a given distortion (quality) level D1, ...,DN>; 0. Among many other things, the computation approach includes an iterative algorithm with global convergence for computing Rc*(D1, ...,DN) . The global convergence of the algorithm further enables us to demonstrate a somewhat surprising result (dubbed the more and less coding theorem)-under some conditions on source frames and distortion, the more frames need to be encoded and transmitted, the less amount of data after encoding has to be actually sent. With the help of the algorithm, it is also shown by example that Rc*(D1, ...,DN) is in general much smaller than the total rate offered by the traditional greedy coding method. As a by-product, an extended Markov lemma is established for correlated ergodic sources.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ? ? ? XNare encoded in a frame by frame manner, the encoder for each frame Xk, k = 1, ? ? ?, N, can use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i)}i=1?. A novel computation approach is proposed to analytically characterize and numerically compute the minimum total rate Rc(D1, ? ? ?, DN) required to achieve a given distortion (quality) level D1, ? ? ?, DN? 0. Specifically, we first show that for jointly stationary ergodic sources X1, X2, ? ? ?, XN, Rc(D1, ? ? ?, DN) is equal to the infimum of the nthorder total rate distortion function Rc,n(D1, ? ? ?, DN) over all n, where Rc,n(D1, ? ? ?, DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then present an iterative algorithm for computing Rc,n(D1, ? ? ?, DN) and demonstrate the convergence of the algorithm to the global minimum. The global convergence of the algorithm further enables us to establish a single-letter characterization of Rc(D1, ? ? ?, DN) in a novel way when the N sources are an independent and identically distributed vector source. Deep insights from the algorithm are also gained regarding how each frame should be encoded in order to achieve Rc(D1, ? ? ?, DN); it is demonstrated by example that Rc(D1, ? ? ?, DN) is in general much smaller than the total rate offered by the traditional greedy coding method by which each frame is encoded in a local optimum manner based on all information available to the encoder of the frame. In addition, a tight achievable rate distortion region is also derived.

Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.

In this paper, we study the error correction and detection capabilities of block codes for a general transmission system inspired by network error correction. For a given weight measure on the error vectors, we define a corresponding minimum weight decoder. Then we obtain a complete characterization of the capabilities of a block code for error correction and error detection. Our results imply that for a linear network code with the Hamming weight being the weight measure on the error vectors, the capability of the code is fully characterized by a single minimum distance. By contrast, for a nonlinear network code, two different minimum distances are needed for characterizing the capabilities of the code for error correction and for error detection. This leads to the surprising discovery that for a nonlinear network code, the number of correctable errors can be more than half of the number of detectable errors. We further define equivalence classes of weight measures with respect to a channel. Specifically, for any given code, the minimum distance decoders for two different weight measures are equivalent if the two weight measures belong to the same equivalence class.

In this paper, we study basic properties of linear network error correction codes, their construction and error correction capability for various kinds of errors. Our discussion is restricted to the single-source multicast case. We define the minimum distance of a network error correction code. This plays the same role as it does in classical coding theory. We construct codes that can correct errors up to the full error correction capability specified by Singleton bound for network error correction codes recently established by Cai and Yeung. We propose a decoding principle for network error correction codes, based on which we introduce two decoding algorithms and analyze their performance. We formulate the global kernel error correction problem and characterize the error correction capability of codes for this kind of error.

In this paper, we study the error correction capability of random linear network error correction codes (Z. Zhang, 2006). We derive bounds on the probability mass function of the minimum distance of a random network error correction code and the field size required for the existence of a network error correction code with a given degradation, which is the difference between the highest possible minimum distance in the Singleton bound and the minimum distance of the code. The main tool that we use to study these problems is an improved bound on the failure probability of random linear network codes that at one or more sinks, the source messages are not decodable. This problem was originally studied in T. Ho et al. (2006).

In this paper, we study the dynamic resource allocation problem for a class of time-varying wireless multicast networks with intra-multicast network coding. We provide distributed and dynamic cross-layer strategy to simultaneously achieve utility optimization and network stability under given power constraints. Our result shows when combined with Lyapunov drift technique for optimal flow control, "one shot" type of network codes, i.e., codes that restrict network coding within packets in a multicast that enter the network in the same timeslot, are sufficient to achieve performance optimality in this class of networks.

The capacity problem for general acyclic multi- source multi-sink networks with arbitrary transmission requirements has been studied by L. Song, et al (2003). Specifically, inner and outer bounds of the capacity region were derived respectively in terms of Gamman* and Gamma macrn*, the fundamental regions of the entropy function. In this paper, we show that by carefully bounding the constrained regions in the entropy space, we obtain the exact characterization of the capacity region, thus closing the existing gap between the above inner and outer bounds.

This paper summarizes our recent works on network error correction codes. We study basic properties of linear network error correction codes in the single source multicast case. We define the minimum distance of a network error correction code which plays the same role as it does in classical coding theory. We construct MDS codes and give sufficient conditions for its existence. We propose basic decoding algorithms and analyze their performance. We propose an improved upper bound for the failure probability of random network code and use it to analyze the performance of randomized network error correction codes [9], [10]. We study the possibility of decoding beyond error correction capability. We propose a hybrid network error correction coding systems. An extensive performance analysis of this coding system is reported in a separate paper.

Ignited by the pioneering work of Ahlswede et al on the characterization of the capacity region for single-source multicast networks, a number of works have been devoted to determining the capacity regions for more general networks. However, except a few interesting outer bounds that have been derived so far, the exact characterization is still restricted to rather simple networks. In this paper, we determine the capacity region for a more general class of networks called degree-2 K-pairs three-layer networks. The result suggests a characterization technique for more general multi-source multi-sink networks

In multi-source multi-sink network coding, messages across different sources are coded to increase the overall throughput. The various types of coded information in the network significantly complicate the determination of its capacity region. In this work, we derive explicit inner and outer bounds for acyclic multi-source multi-sink networks based on a cut-based network decomposition technique and a role-based information characterization technique. In particular, we derive a linear programming inner bound for regular K-pairs acyclic three-layer networks and a network sharing outer bound for arbitrary acyclic multi-source multi-sink networks. The techniques used in this paper reveal some of the basic mechanisms of multi-source multi-sink network coding

The max-flow min-cut bound is a fundamental result in the theory of communication networks, which characterizes the optimal throughput for a point-to-point communication network. The recent work of Ahlswede et al. extended it to single-source multisink multicast networks and Li et al. proved that this bound can be achieved by linear codes. Following this line, Erez and Feder as well as Ngai and Yeung proved that the max-flow min-cut bound remains tight in single-source two-sink nonmulticast networks. But the max-flow min-cut bound is in general quite loose (see Yeung, 2002). On the other hand, the admissible rate region of communication networks has been studied by Yeung and Zhang as well as Song and Yeung, but the bounds obtained by these authors are not explicit. In this work, we prove a new explicit outer bound for arbitrary multisource multisink networks and demonstrate its relation with the minimum cost network coding problem. We also determine the capacity region for a special class of three-layer networks.

In this paper, we investigate the rate-distortion performance of multiresolution encoding algorithms for successively refinable sources, including block codes and trellis codes. Our random coding arguments not only support the results of simulation-based experiments, such as tree structured vector quantization (TSVQ) and multistage trellis coded quantization (MSTCQ), but also provides some information theoretic considerations to understand the efficiency of such existing algorithms. In fact, the redundancy analysis that we developed is a practical generalization of the Shannon source coding theorem to the more concrete cases.

It is well known that trellis lossy source codes have better performance/complexity tradeoff than block codes, as shown by simulations. This makes the trellis coding technique attractive in practice. To get a better understanding of this fact, this paper studies the redundancy of trellis coding for memoryless sources and compares it with a similar result for block codes.

The synchronization recovery property of variable-length (VL) codes has been extensively studied. In the paper, the mean error propagation length (MEPL) and the variance of error propagation length (VEPL), which are the secondary performance criteria of a VL code, are introduced to measure the synchronization recovery capability of a VL code. For the same probability distribution, there exist many different VL codes which have the same redundancy as the Huffman code but quite different MEPLs and VEPLs. To find one of the VL codes which has the minimum MEPL is a very difficult problem. We present two design algorithms for finding minimum-redundancy VL codes with short MEPL and VEPL. These two algorithms are simple and have the property that the codewords are assigned one by one. The efficiency of the algorithms are tested extensively by comparing the algorithms with known construction methods available in literature. Actually, VL codes obtained by the two algorithms outperform almost all codes available.

Multiple description schemes for trellis coded vector quantizers are introduced. For these schemes, the Viterbi algorithm provides an optimal path for encoding and the design procedure utilizes the generalized Lloyd algorithm for suboptimal codebooks. The schemes are generalization of Jafarkhani and Throkh (see ICIP '98, Proceedings. of International Conference on Image Processing, vol.1, p.669-673,1998 and IEEE Transactions on Communications, vol.47, no.6, p.799-803, 1999) method in both temporal and spatial senses. A lower bound on rate-distortion region for more than three descriptions is given. The lower bound is a generalization of Ozarow's (1980) achievable region for a two channel and three description scheme.

Space-time convolutional codes have been shown to provide improved performance for high data rate transmission over fading channels through combined space diversity and coding gain. However, there are still some questions on how to design the codes in binary or discrete domain to achieve these gains in the complex domain of baseband-modulated signals. In this paper, we first consider the effect of minimum distance in the space-time codes, then propose a new efficient design method which is based on the upper and lower bounds of the coding gain. The simulation result shows that the new approach allows a fast search for optimal space-time convolutional codes for many practical problems.

Throughput bounds are attained for random channel access multichannel code-division multiple-access (CDMA) systems and spread slotted Aloha systems employing multiuser receivers. It is shown that the normalized throughput of these two systems reaches 1.0 exponentially fast in the region r/K0. The maximum throughput of the random channel access multichannel CDMA systems is found as K-/spl radic/(1-(1/M))KlogK-O(logK), where M is the number of channels in the system. The maximum throughput is reached when the average number of simultaneous users is r/sub m/=K-/spl radic/((1-(1/M))KlogK))+O(/spl radic/(K/logK)). The maximum throughput of the spread slotted Aloha systems is K-/spl radic/(KlogK)-O(log K). The maximum throughput is reached when the packet arrival of Poisson distribution has the arrival rate /spl lambda//sub m/=K-/spl radic/(KlogK)+O(/spl radic/(K/logK)).

The redundancy problem of universal lossy source coding at a fixed rate level is considered. Under some condition on the single-letter distortion measure, which implies that the cardinality K of the reproduction alphabet is not greater than the cardinality J of the source alphabet, it is shown that the redundancy of universally coding memoryless sources p by nth-order block codes of rate R goes like |(/spl part///spl part/R)d(p,R)|Kln n/2n+o(ln n/n) for all memoryless sources p except a set whose volume goes to 0 as the block length n goes to infinity, where d(p,R) denotes the distortion rate function of p. Specifically, for any sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes, where C/sub n/ is an nth-order block code at the fixed rate R, and any /spl epsiv/>0, the redundancy D/sub n/(C/sub n/,p) of C/sub n/ for p is greater than or equal to |(/spl part///spl part/R)d(p,R)|(K-/spl epsiv/)ln n/2n for all p satisfying some regular conditions except a set whose volume goes to 0 as n/spl rarr//spl infin/. On the other hand, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the rate R such that for any p satisfying some regular conditions, the super limit of D/sub n/(C/sub n/,p)|(ln n/n) is less than or equal to |(/spl part///spl part/R)d(p,R)|K/2.

A statistical characterization of the complexity function of the Verdu optimum multiuser detection (VOMD) algorithm is presented for a communication system employing a finite number of randomly accessed orthogonal channels and a finite number of simultaneous users. Multichannel code-division multiple-access (CDMA) systems are proposed. It is proved that the probability, in which the individual channel complexity is greater than A/sup r(1+/spl alpha/)/, approaches zero exponentially fast as the average number of simultaneous users in each channel increases, where A is the modulation alphabet size and /spl alpha/>0. When the number of simultaneous users is large, the complexity of applying the VOMD algorithm to each individual channel is negligible when compared with the complexity of applying the same algorithm directly to the traditional single-channel CDMA system supporting the same number of simultaneous users. The probability distribution of the joint complexity function of the aggregate system is found. It is shown that when the number of simultaneous users is large, the joint complexity function is negligible compared with applying the VOMD algorithm directly to the traditional single-channel CDMA system supporting the same number of simultaneous users. Therefore, a multichannel CDMA communication system can support a comparable population of simultaneous users to the traditional single-channel CDMA system of comparable bandwidth, while reducing the complexity of optimum multiuser detection to a practical level.

The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to finite-state decoders or trellis-structured decoders. When this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where /spl lambda/>0 and -/spl lambda/ are designated to be the slope of the rate distortion function R(D) of the source at some D; the quantity is close to R(D)+/spl lambda/D when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented; this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes. The resulting variable-rate trellis source codes are very efficient in low-rate regions. With k=8, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers; with k=8 and the number of states in the decoder=32, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, with k=8 and the number of states in the decoder=256, the mean-squared error encoding performance at the rates of a fraction of 1 bit/sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion rate function.

The redundancy problem of lossy source coding with abstract source and reproduction alphabets is considered. For coding at a fixed rate level, it is shown that for any fixed rate R>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the rate R such that the distortion redundancy of C/sub n/ (defined as the difference between the performance of C/sub n/ and the distortion rate function d(P, R) of P) is upper-bounded by |(/spl part/d(P,R))/(/spl part/R)| ln n/2n+o(ln n/n). For coding at a fixed distortion level, it is demonstrated that for any d>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C/sub n/}/sub n=1//sup /spl infin// of block codes at the fixed distortion d such that the rate redundancy of C/sub n/ (defined as the difference between the performance of C/sub n/ and the rate distortion function R(P,d) of P) is upper-bounded by (7ln n)/(6n)+o(ln n/n). These results strengthen the traditional Berger's (1968, 1971) abstract alphabet source coding theorem, and extend the positive redundancy results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997, and ibid., vol.42, p.803-21, 1996) on lossy source coding with finite alphabets and the redundancy result of Wyner (see ibid., vol.43, p.1452-64, 1997) on block coding of memoryless Gaussian sources.

The shortest common superstring problem and its extension to approximate matching are considered in the probability model where each string in a given set has the same length and letters of strings are drawn independently from a finite set. In the exact matching case, several algorithms proposed in the literature are shown to be asymptotically optimal in the sense that the ratio of the savings resulting from the superstring constructed by each of these algorithms, that is the difference between the total length of the strings in the given set and the length of the superstring, to the optimal savings from the shortest superstring approaches in probability to 1 as the number of strings in the given set increases. In the approximate matching case, a modified version of the shortest common approximate matching superstring problem is analyzed; it is demonstrated that the optimal savings in this case is given approximately by nlogn/I/sub l/(Q,Q,2D), where n is the number of strings in the given set, Q is the probability distribution governing the selection of letters of strings, I/sub l/(Q,Q,2D) is the lower mutual information between Q and Q with respect to 2D, and D/spl ges/0 is the distortion allowed in approximate matching. In addition, an approximation algorithm is proposed and proved asymptotically optimal.

Symmetrical multilevel diversity coding with independent data streams has been studied by Roche et al. (1992), and the admissible coding rate region was determined for the case of three levels. In particular, it was shown that coding by superposition is optimal, which means that optimality can be achieved by very simple coding. However, it is very difficult to generalize their proof to an arbitrary number of levels. In this paper, we use a new approach to study this problem, and we show that coding by superposition is optimal for symmetrical multilevel diversity coding in general. We also discuss how our result can be applied when the source consists of correlated data streams. The techniques we use are new in multiuser information theory, and our work sheds some light on the standing problem of characterizing those multilevel diversity coding systems for which coding by superposition is optimal.

Inspired by mobile satellite communications systems, we consider a source coding system which consists of multiple sources, multiple encoders, and multiple decoders. Each encoder has access to a certain subset of the sources, each decoder has access to certain subset of the encoders, and each decoder reconstructs a certain subset of the sources almost perfectly. The connectivity between the sources and the encoders, the connectivity between the encoders and the decoders, and the reconstruction requirements for the decoders are all arbitrary. Our goal is to characterize the admissible coding rate region. Despite the generality of the problem, we have developed an approach which enables us to study all cases on the same footing. We obtain inner and outer bounds of the admissible coding rate region in terms of /spl Gamma//sub N/* and /spl Gamma/~/sub N/*, respectively, which are fundamental regions in the entropy space defined by Yeung (1991). So far, there has not been a full characterization of /spl Gamma//sub N/*, so these bounds cannot be evaluated explicitly except for some special cases. Nevertheless, we obtain an alternative outer bound which can be evaluated explicitly. We show that this bound is tight for all the special cases for which the admissible coding rate region is known. The model we study in this paper is more general than all previously reported models on multilevel diversity coding, and the tools we use are new in multiuser information theory.

We present a general class of zero-error capacity problems with memory covering known cases such as coding for error correction and many new cases. This class can be incorporated into a model of channels with memory, which thus are shown to give a unification of a multitude of seemingly very different coding problems. We analyze a seemingly basic channel in this class.

For pt.II see ibid., vol.42, p.822-36 (1996). The Gold-washing data compression algorithm is an adaptive vector quantization algorithm with vector dimension n. In this paper, a redundancy problem of the Gold-washing data compression algorithm is considered. It is demonstrated that for any memoryless source with finite alphabet A and generic distribution p and for any R>0, the redundancy of the Gold-washing data compression algorithm with dimension n (defined as the difference between the average performance of the algorithm and the distortion-rate function D(p,R) of p) is upper-bounded by |/sub /spl delta/R///sup /spl delta//D(p,R)|((|A|+2/spl xi/+4 log n)/2n)+/spl sigma/(logn/n) where /sub /spl delta/R///sup /spl delta//D(p,R) is the partial derivative of D(p,R) with respect to R, |A| is the cardinality of A, and /spl xi/>0 is a parameter used to control the threshold in the Gold-washing algorithm. In connection with the results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997) on the redundancy of lossy source coding, this shows that the Gold-washing algorithm has the optimal convergence rate among all adaptive finite-state vector quantizers.

Given n discrete random variables /spl Omega/={X/sub 1/, /spl middot//spl middot//spl middot/, X/sub n/}, associated with any subset /spl alpha/ of (1, 2, /spl middot//spl middot//spl middot/, n), there is a joint entropy H(X/sub /spl alpha//) where X/sub /spl alpha//={X/sub i/:i/spl epsiv//spl alpha/}. This can be viewed as a function defined on 2/sup {1, 2, /spl middot//spl middot//spl middot/, n}/ taking values in (0, +/spl infin/). We call this function the entropy function of /spl Omega/. The nonnegativity of the joint entropies implies that this function is nonnegative; the nonnegativity of the conditional joint entropies implies that this function is nondecreasing; and the nonnegativity of the conditional mutual information implies that this function has the following property: for any two subsets /spl alpha/ and /spl beta/ of {1, 2, /spl middot//spl middot//spl middot/, n} H/sub /spl Omega//(/spl alpha/)+H/sub /spl Omega//(/spl beta/)/spl ges/H/sub /spl Omega//(/spl alpha//spl cup//spl beta/)+H/sub /spl Omega//(/spl alpha//spl cap//spl beta/). These properties are the so-called basic information inequalities of Shannon's information measures. Do these properties fully characterize the entropy function? To make this question more precise, we view an entropy function as a 2/sup n/-1-dimensional vector where the coordinates are indexed by the nonempty subsets of the ground set {1, 2, /spl middot//spl middot//spl middot/, n}. Let /spl Gamma//sub n/ be the cone in R/sup 2n-1/ consisting of all vectors which have these three properties when they are viewed as functions defined on 2/sup {1, 2, /spl middot//spl middot//spl middot/, n}/. Let /spl Gamma//sub n/* be the set of all 2/sup n/-1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. The question can be restated as: is it true that for any n, /spl Gamma/~/sub n/*=/spl Gamma//sub n/? Here /spl Gamma/~/sub n/* stands for the closure of the set /spl Gamma//sub n/*. The answer is "yes" when n=2 and 3 as proved in our previous work. Based on intuition, one may tend to believe that the answer should be "yes" for any n. The main discovery of this paper is a new information-theoretic inequality involving four discrete random variables which gives a negative answer to this fundamental problem in information theory: /spl Gamma/~*/sub n/ is strictly smaller than /spl Gamma//sub n/ whenever n>3. While this new inequality gives a nontrivial outer bound to the cone /spl Gamma/~/sub 4/*, an inner bound for /spl Gamma/~*/sub 4/ is also given. The inequality is also extended to any number of random variables.

Ahlswede has previously introduced an abstract correlated source (/spl Vscr//spl times//spl Wscr/,S) with outputs (/spl upsi/, /spl omega/)/spl isin/S/spl sub//spl Vscr//spl times//spl Wscr/, where persons P/sub /spl Vscr// and P/sub /spl Wscr// observe /spl upsi/ and /spl omega/, respectively. More recently, Orlitsky considered the minimal number C/sub m/ of bits to be transmitted in m rounds to "inform P/sub /spl Wscr// about /spl upsi/ over one channel." He showed that C/sub 2//spl les/4C/sub /spl infin//+3 and that in general C/sub 2/NOT/spl sim/C/sub /spl infin//. We give a simple example for C/sub 3/NOT/spl sim/C/sub /spl infin//. However, for the new model "inform P/sub /spl Wscr// over two channels", four rounds are optimal for this example-a result we conjecture in general. If both P/sub /spl Vscr// and P/sub /spl Wscr// are to be informed over two channels about the other outcome, we determine asymptotically the complexities for all sources. In our last model "inform P/sub /spl Vscr// and P/sub /spl Wscr// over one channel" for all sources the total number T/sub 2/ of required bits is known asymptotically and T/sub /spl infin// is bounded from below in terms of average degrees. There are exact results for several classes of regular sources. An attempt is made to discuss the methods of the subject systematically.

A new coding problem is introduced for a correlated source (X/sup n/,Y/sup n/)/sub n=1//sup /spl infin//. The observer of X/sup n/ can transmit data depending on X/sup n/ at a prescribed rate R. Based on these data the observer of Y/sup n/ tries to identify whether for some distortion measure /spl rho/ (like the Hamming distance) n/sup -1/ /spl rho/(X/sup n/,Y/sup n/)/spl les/d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X/sup n/ and Y/sup n/ are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X/sup n/ and Y/sup n/ are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory.

Corresponding to any lossless codeword length function l, three universal lossy data compression schemes are presented: one is with a fixed rate, another is with a fixed distortion, and a third is with a fixed slope. The former two universal lossy data compression schemes are the generalization of Yang-Kieffer's (see ibid., vol.42, no.1, p.239-45, 1995) results to the general case of any lossless codeword length function l, whereas the third is new. In the case of fixed-slope /spl lambda/>0, our universal lossy data compression scheme works as follows: for any source sequence x/sup n/ of length n, the encoder first searches for a reproduction sequence y/sup n/ of length n which minimizes a cost function n/sup -1/l(y/sup n/)+/spl lambda//spl rho//sub n/(x/sup n/, y/sup n/) over all reproduction sequences of length n, and then encodes x/sup n/ into the binary codeword of length l(y/sup n/) associated with y/sup n/ via the lossless codeword length function l, where /spl rho//sub n/(x/sup n/, y/sup n/) is the distortion per sample between x/sup n/ and y/sup n/. Under some mild assumptions on the lossless codeword length function l, it is shown that when this fixed-slope data compression scheme is applied to encode a stationary, ergodic source, the resulting encoding rate per sample and the distortion per sample converge with probability one to R/sub /spl lambda// and D/sub /spl lambda//, respectively, where (D/sub /spl lambda//, R/sub /spl lambda//) is the point on the rate distortion curve at which the slope of the rate distortion function is -/spl lambda/. This result holds particularly for the arithmetic codeword length function and Lempel-Ziv codeword length function. The main advantage of this fixed-slope universal lossy data compression scheme over the fixed-rate (fixed-distortion) universal lossy data compression scheme lies in the fact that it converts the encoding problem to a search problem through a trellis and then permits one to use some sequential search algorithms to implement it. Simulation results show that this fixed-slope universal lossy data compression scheme, combined with a suitable search algorithm, is promising.

Given n discrete random variables /spl Omega/={X/sub 1/,...,X/sub n/}, associated with any subset /spl alpha/ of {1,2,...,n}, there is a joint entropy H(X/sub /spl alpha//) where X/sub /spl alpha//={X/sub i/: i/spl isin//spl alpha/}. This can be viewed as a function defined on 2/sup {1,2,...,n}/ taking values in [0, +/spl infin/). We call this function the entropy function of /spl Omega/. The nonnegativity of the joint entropies implies that this function is nonnegative; the nonnegativity of the conditional joint entropies implies that this function is nondecreasing; and the nonnegativity of the conditional mutual information implies that this function is two-alternative. These properties are the so-called basic information inequalities of Shannon's information measures. An entropy function can be viewed as a 2/sup n/-1-dimensional vector where the coordinates are indexed by the subsets of the ground set {1,2,...,n}. As introduced by Yeng (see ibid., vol.43, no.6, p.1923-34, 1997) /spl Gamma//sub n/ stands for the cone in IR(2/sup n/-1) consisting of all vectors which have all these properties. Let /spl Gamma//sub n/* be the set of all 2/sup n/-1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. A fundamental information-theoretic problem is whether or not /spl Gamma/~/sub n/*=/spl Gamma//sub n/. Here /spl Gamma/~/sub n/* stands for the closure of the set /spl Gamma//sub n/*. We show that /spl Gamma/~/sub n/* is a convex cone, /spl Gamma//sub 2/*=/spl Gamma//sub 2/, /spl Gamma//sub 3/*/spl ne//spl Gamma//sub 3/, but /spl Gamma/~/sub 3/*=/spl Gamma//sub 3/. For four random variables, we have discovered a conditional inequality which is not implied by the basic information inequalities of the same set of random variables. This lends an evidence to the plausible conjecture that /spl Gamma/~/sub n/*/spl ne//spl Gamma//sub n/ for n>3.

The problem of redundancy of source coding with respect to a fidelity criterion is considered. For any fixed rate R>0 and any memoryless source with finite source and reproduction alphabets and a common distribution p, the nth-order distortion redundancy D/sub n/(R) of fixed-rate coding is defined as the minimum of the difference between the expected distortion per symbol of any block code with length n and rate R and the distortion rate function d(p,R) of the source p. It is demonstrated that for sufficiently large n, D/sub n/(R) is equal to -(/spl part///spl part/R)d(p,R) ln n/2n+o(ln n/n), where (/spl part///spl part/R)d(p,R) is the partial derivative of d(p,R) evaluated at R and assumed to exist. For any fixed distortion level d>0 and any memoryless source p, the nth-order rate redundancy R/sub n/(d) of coding at fixed distortion level d (or by using d-semifaithful codes) is defined as the minimum of the difference between the expected rate per symbol of any d-semifaithful code of length n and the rate-distortion function R(p,d) of p evaluated at d. It is proved that for sufficiently large n, R/sub n/(d) is upper-bounded by ln n/n+o(ln n/n) and lower-bounded by In n/2n+o(In n/n). As a by-product, the lower bound of R/sub n/(d) derived in this paper gives a positive answer to a conjecture proposed by Yu and Speed (1993).

This work examines the nearest neighbor encoding problem with an unstructured codebook of arbitrary size and vector dimension. We propose a new tree-structured nearest neighbor encoding method that significantly reduces the complexity of the full-search method without any performance degradation in terms of distortion. Our method consists of efficient algorithms for constructing a binary tree for the codebook and nearest neighbor encoding by using this tree. Numerical experiments are given to demonstrate the performance of the proposed method.

For the discrete memoryless channel (/spl chi/, y, W) we give characterizations of the zero-error erasure capacity C/sub er/ and the zero-error average list size capacity C/sub al/ in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not "single-letterize." Next we assume that /spl chi//spl sub/y and W(x|x)>0 for all x/spl isin//spl chi/, and we associate with W the low-noise channel W/sub /spl epsiv//, where for y/sup +/(x)={y:W(y|x)>0} W/sub /spl epsiv//(y|x)={1, if y=x and |y/sup +/(x)|=1 1-/spl epsiv/, if y=x and |y/sup +/(x)|>1 e/|y/sup +/(x)|-1, if y/spl ne/x. Our Theorem-2 says that as /spl epsi/ tends to zero the capacities C/sub er/(W/sub /spl epsi//) and C/sub al/(W/sub /spl epsi//) relate to the zero-error detection capacity C/sub de/(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C/sub oid/ for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C/sub oid/ equals the zero-error erasure capacity for transmission C/sub er/.

We consider a new problem in multiterminal source coding motivated by the following decentralized communication/estimation task. A firm's Chief Executive Officer (CEO) is interested in the data sequence {X(t)}/sub t=1//sup /spl infin// which cannot be observed directly, perhaps because it represents tactical decisions by a competing firm. The CEO deploys a team of L agents who observe independently corrupted versions of {X(t)}/sub t=1//sup /spl infin//. Because {X(t)} is only one among many pressing matters to which the CEO must attend, the combined data rate at which the agents may communicate information about their observations to the CEO is limited to, say, R bits per second. If the agents were permitted to confer and pool their data, then in the limit as L/spl rarr//spl infin/ they usually would be able to smooth out their independent observation noises entirely. Then they could use their R bits per second to provide the CEO with a representation of {X(t)} with fidelity D(R), where D(/spl middot/) is the distortion-rate function of {X(t)}. In particular, with such data pooling D can be made arbitrarily small if R exceeds the entropy rate H of {X(t)}. Suppose, however, that the agents are not permitted to convene, Agent i having to send data based solely on his own noisy observations {Y/sub i/(t)}. We show that then there does not exist a finite value of R for which even infinitely many agents can make D arbitrarily small. Furthermore, in this isolated-agents case we determine the asymptotic behavior of the minimal error frequency in the limit as L and then R tend to infinity.

A new on-line universal lossy data compression algorithm is presented. For finite memoryless sources with unknown statistics, its performance asymptotically approaches the fundamental rate distortion limit. The codebook is generated on the fly, and continuously adapted by simple rules. There is no separate codebook training or codebook transmission. Candidate codewords are randomly generated according to an arbitrary and possibly suboptimal distribution. Through a carefully designed "gold washing" or "information-theoretic sieve" mechanism, good codewords and only good codewords are promoted to permanent status with high probability. We also determine the rate at which our algorithm approaches the fundamental limit.

For pt.I see ibid., vol.42, no.3, p.803-21 (1996). Two versions of the gold-washing data compression algorithm, one with codebook innovation interval and the other with finitely many codebook innovations, are considered. The version of the gold-washing algorithm with codebook innovation interval k is a variant of the gold-washing algorithm such that the codebook is innovated once every k+1 source words during the process of encoding the entire source. It is demonstrated that when this version of the gold-washing algorithm is applied to encode a stationary, /spl phi/-mixing source, the expected distortion performance converges to the distortion rate function of the source as the codebook length goes to infinity. Furthermore, if the source to be encoded is a Markov source or a finite-state source, then the corresponding sample distortion performance converges almost surely to the distortion rate function. The version of the gold-washing algorithm with finitely many codebook innovations is a variant of the gold-washing algorithm in which after finitely many codebook innovations, the codebook is held fixed and reused to encode the forthcoming source sequence block by block. Similar results are shown for this version of the gold-washing algorithm. In addition, the convergence speed of the algorithm is discussed.

In this paper, a variant of address vector quantization (ADVQ) algorithm for image compression using conditional entropy lossless coding is presented. The motivation of the proposed approach is derived from Shannon's basic entropy concept that conditional entropy is less than joint entropy.

Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>

Multiple description source coding concerns situations in which the transmission of the source information is distributed over two data streams at rates R/sub 1/ and R/sub 2/, respectively. When both data streams are received, the decoder uses the combined data at rate R/sub 1/+R/sub 2/ to reconstruct the source information with average distortion d/sub 0/. If a communication breakdown prevents one of the data streams from reaching the receiver, the decoder has to base its reconstruction solely on the available data at rate either R/sub 1/ or R/sub 2/. This results in a higher distortion of either d/sub 1/ or d/sub 2/, respectively. The region /spl Rscr/ of all achievable quintuples (R/sub 1/, R/sub 2/, d/sub 0/, d/sub 1/, d/sub 2/) has been determined in the so-called "no excess rate" sum case defined by imposing the requirement R/sub 1/+R/sub 2/=R(d/sub 0/), where R(/spl middot/) is the rate-distortion function of the source. The case with excess rate sum, characterized by R/sub 1/+R/sub 2/>R(d/sub 0/), is challenging. We study in this paper a special case of it in which the requirements R/sub t/=R(d/sub t/), t=1, 2, are imposed; we refer to this as the "no excess marginal rate" case. The lower and upper bounds on d/sub 0/ we obtain are separated by only a tiny gap when evaluated for a binary equiprobable source and the Hamming distortion measure.>

The Backus-Gilbert (BG) method provides a signal recovery algorithm based on the moment information of a signal. In this work, we focus on a class of signals that can be well approximated with a multiresolution model, and propose a generalized BG method for signal recovery. A numerical experiment is given to demonstrate the performance of the generalized BG method.>

In this research, we consider a special class of band-limited signals which have a multiband structure in the frequency domain, and propose a new reconstruction algorithm to exploit the multiband feature of the underlying signals. The concept of the critical value is introduced to measure the performance of a reconstruction algorithm. We show analytically that the new algorithm performs better than the MMSE estimator for band-limited/multiband signals in terms of the critical value and region measure. Numerical examples are given for performance comparison of various methods.>

The generalized Lloyd algorithm plays an important role in the design of vector quantizers (VQ) and in feature clustering for pattern recognition. In the VQ context, this algorithm provides a procedure to iteratively improve a codebook and results in a local minimum that minimizes the average distortion function. We propose an efficient method to obtain a good initial codebook that can accelerate the convergence of the generalized Lloyd algorithm and achieve a better local minimum as well.>

The VLSI architecture for an adaptive vector quantizer is presented. The adaptive vector quantization method does not require a-priori knowledge of the source statistics and the pre-trained codebook. The codebook is generated on the fly and is constantly updated to capture local textual features of data. The source data are directly compressed without requiring the generation of codebook in a separate pass. The adaptive method is based on backward adaption without any side information. The speed of data compression by using the proposed adaptive method is much faster than that by using the conventional vector quantization methods. The algorithm is shown to reach the rate distortion function for memoryless sources. In image processing, most smooth regions are matched by the code vectors and most edge data are preserved by using the block-data interpolation scheme. The VLSI architecture consists of two move-to-front vector quantizers and an index generator. It explores parallelism in the direction of the codebook size and pipelining in the direction of the vector dimension. According to the circuit simulations using the popular SPICE program, the computation power of the move-to-front vector quantizer can reach 40 billion operations per second at a system clock of 100 MHz by using 0.8 /spl mu/m CMOS technology. It can provide a computing capability of 50 Mpixels per second for high-speed image compression. The proposed algorithm and architecture can lead to the development of a high-speed image compressor with great local adaptivity, minimized complexity, and fairly good compression ratio.>

Continuing earlier work (Ahlswede and Zhang, 1989) on write-efficient memories (WEM), the authors introduce new models, where several persons use the same storage device. At any time instant, exactly one of a prescribed set of users has access to the memory, but there is no protocol which determines the moving order. Among the constraints analyzed, the most interesting one is a complete privacy protection. While a user stores new data, he has to guarantee that those of the others do not get distorted. This leads to fascinating new coding problems. The authors provide several code constructions, as well as abstract performance bounds.>

Investigates the maximization of the differential entropy h(X+Y) of arbitrary dependent random variables X and Y under the constraints of fixed equal marginal densities for X and Y. We show that max[h(X+Y)]=h(2X), under the constraints that X and Y have the same fixed marginal density f, if and only if f is log-concave. The maximum is achieved when X=Y. If f is not log-concave, the maximum is strictly greater than h(2X). As an example, identically distributed Gaussian random variables have log-concave densities and satisfy max[h(X+Y)]=h(2X) with X=Y. More general inequalities in this direction should lead to capacity bounds for additive noise channels with feedback.>

Improved upper bounds for the size of radar arrays are found by using the window method. New general constructions and computer-searched examples are presented. The radar array problem is generalized to include arrays with sidelobes greater than 1.>

Let X and Y be two jointly distributed random variables. Suppose person P/sub X/, the informant, knows X, and person P/sub Y/, the recipient, knows Y, and both know the joint probability distribution of the pair (X,Y). Using a predetermined protocol, they communicate over a binary error-free channel in order for P/sub Y/ to learn X, whereas P/sub X/ may or may not learn Y. C/spl circ/m(X/spl verbar/Y) is the minimum number of bits required to be transmitted (by both persons) in the worst case when only m message exchanges are allowed. C/spl circ//spl infin/(X/spl verbar/Y) is the number of bits required when P/sub X/ and P/sub Y/ can communicate back and forth an arbitrary number of times. Orlitsky proved that for all (X,Y) pairs, C/spl circ//sub 2/(X/spl verbar/Y)/spl les/4C/spl circ//spl infin/(X/spl verbar/Y)+3, and that for every positive c and /spl isin/ with /spl isin/>

A new approach for the construction of systematic tEC/AUED codes is presented. These new constructions improve many values of the upper bound on the redundancy of the code for t=1 and 2.>

Some LYM-type inequalities are introduced to obtain a relationship between the parameters of t-error correcting/all unidirectional error-detecting codes of length n. As an application of these inequalities, new lower bounds on the redundancies of systematic tEC/AUED codes are derived and an extensive table is given.>

An adaptive method for lossy data compression and the associated VLSI architecture have been developed. This scheme does not require a-priori knowledge of the source statistics and codebook training. The codebook is generated on the fly and is constantly updated to capture local textual features of data. The algorithm is proven to reach rate distortion function for memoryless sources. The authors also propose a computing architecture which consists of a vector quantizer and an encoded-data generator. By using this method, a high-speed VLSI processor with good local adaptivity, less complexity and fair compression ratio can be achieved.>

The linear inequality method for covering codes is used to improve the lower bounds of t(n, k), the smallest covering radius of any (n, k) binary linear code. To make better use of the strength of this method, the relation between the covering radius of a code and the minimum distance of its dual code is studied. The authors obtained 65 improved lower bounds for t(n, k) within the range of n>

For Pt.I, see ibid., vol.37, no.3, p.573-82 (May 1991). The linear inequality method for covering codes is generalized. This method reduces the study of covering codes to the study of some local covering problems. One of these problems, the 1-3 covering system, is formulated and studied in detail. The results for this local covering problem lead to new linear inequalities satisfied by covering codes, which are used to obtain numerous new lower bounds on K(n, R) and t(n, k).>

Lower bounds for asymmetric single-error-correcting codes are derived. The codes are constructed by puncturing constant weight codes and by using a random coding argument.>

Recent results are extended on difference methods for the prediction of bandlimited signals, obtained by D.H. Mugler and W. Splettstosser (1986, 1987) and by D.H. Mugler (1990), are extended to generalized bandlimited signals defined by M. Zakai (1965) and A.J. Lee (1975, 1976). This makes the difference method applicable to a wider class of signals.>

The lower bounds on K(n,R), minimum number of codewords of any binary code of length n, and covering radius R are improved. A new technique combining the Hamming association scheme and the results of a classic problem of covering pairs by k-tuples is introduced. The new lower bounds are obtained by studying various linear inequalities satisfied by covering codes, and such an inequality is derived. The lower bounds for K(n,R) are studied for some special values of n and R, which serve as examples showing how the methods developed are applied to concrete cases.>

The author evaluates the limiting efficiencies e(-S) of burst-correcting array codes A(n/sub 1/,n/sub 2/, -s) for all negative readouts -s as n/sub 2/ tends to infinity and n/sub 1/ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s/sub i/ (1or=4/5 and e(-1)>or=2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1.>

A special case of the general discrete memoryless relay channel is studied. This channel consists of an input x, a relay output z, a channel output y, and a noiseless channel of capacity C/sub r/ allowing the relay sender to send additional information to the decoder. The channel is described by a collection of distributions (p(y, z mod x)). The decoder uses the channel output y and a function f(z) of the relay output at a rate no greater than C/sub r/ to recover the message. Some results on the capacity of the channel are obtained. >

Some results from classical estimation theory are extended to the case in which data must be communicated from several places where observations are made to the place where the estimate is generated. Particular emphasis is placed on determining how the variance of an unbiased estimator depends on the communication rates. Explicit result are given for Gaussian sources.>

An encoder whose input is a binary equiprobable memoryless source produces one output of rateR_{1}and another of rateR_{2}. LetD_{1}, D_{2}, and D_{0}, respectively, denote the average error frequencies with which the source data can be reproduced on the basis of the encoder output of rateR_{l}only, the encoder output of rateR_{2}only, and both encoder outputs. The two-descriptions problem is to determine the regionRof all quintuples(R_{1}, R_{2}, D_{1}, D_{2}, D_{0})that are achievable in thc usual Shannon sense. LetR(D)=1+D \log_{2} D+(1-D) \log_{2}(1-D)denote the error frequency rate-distortion function of the source. The "no excess rate case" prevails whenR_{1} + R_{2} = R(D_{0}), and the "excess rate case" whenR_{1} + R_{2} > R(D_{0}). Denote the section ofRat(R_{1}, R_{2}, D_{0})byD(R_{1} R_{2}, D_{0}) =\{(D_{1},D_{2}): (R_{1}, R_{2}, D_{1},D_{2},D_{0}) \in R}. In the no excess rate case we show that a portion of the boundary ofD(R_{1}, R_{2}, D_{0})coincides with the curve(\frac{1}{2} + D_{1}-2D_{0})(\frac_{1}_{2} + D_{2}-2D_{0})= \frac{1}{2}(1-2D_{0})^{2}. This curve is an extension of Witsenhausen's hyperbola bound to the caseD_{0} > 0. It follows that the projection ofRonto the(D_{1}, D_{2})-plane at fixedD_{0}consists of allD_{1} \geq D_{0}andD_{2} \geq D_{0}that lie on or above this hyperbola. In the excess rate case we show by counterexample that the achievable region of El Gamal and Cover is not tight.

Families of zero-error codes for the real binary adder channel with feedback that achieve high rate pairs are introduced. Two families of zero-error block codes are given for the case in which only one of the two senders receives feedback about the channel output. In the first of these families, the uninformed sender transmits at a rate of nearly one bit per symbol and the informed sender transmits slightly less that1/2bit per symbol. The second family is designed for the case in which the informed sender sends at or near one bit per symbol and the uninformed one sends nearly1/2bit per symbol. A family of zero-error codes is introduced, based on the Fibonacci recursion; these codes are readily implemented by means of a simple square-dividing strategy. The Fibonacci codes achieveR_{1}=R_{2}=\log_{2} [(1 + \sqrt{5})/2]in the limit of large block length. Time-sharing between members of these three code families is used to obtain an achievable rate region, or inner bound, to the zero-error capacity region for block coding. For the case in which the feedback is available to both senders, a variant of the Fibonacci difference equation is used to generate zero-error block codes with slightly higher asymptotic rateR_{1}=R_{2}=0.717.

Shannon's two-way channel problem has attracted the attention of information theorists for many years. In a classic paper Shannon gave both an outer and an inner bound to the capacity region of the two-way channel. Schalkwijk recently obtained an improvement to the inner bound for the Blackwell multiplying channel (BMC). We present the first improvements on Shannon's outer bound. Calculation shows that our results are close to optimum when applied to the BMC.

A memoryless binary equiprobable source produces one letter per second. Two people each are provided separately with private information about the source data at a rate of1/2bit per second. Suppose that by pooling their information they can produce a long-mn reconstruction of the source output that has arbitrarily small error frequency. We prove that then the least common asymptotic error frequency d that each can achieve without the other's help is(\sqrt{2}-1)/2=0.207. Since it had been shown previously that0.200 \leq d \leq 0.207, our result closes the so-called "007 gap." New analytical techniques introduced to effect the proof are of broader significance in multiuser information theory.