In Part I of this two-part paper, we put forward the problem of secure network function computation.We investigated securely computing linear target functions with a wiretapper who can eavesdrop any edge subset up to a certain sizer, referred to as the security level, where the security function is the identity function, i.e., we need to prevent the source messages from being leaked to the wiretapper. The notion of this security is called source security. In the current Part II of the two-part paper, we consider another interesting model which is the same as the above one except that the security function is identical to the target function, i.e., we need to prevent the target function from being leaked to the wiretapper. The notion of this security is calledtarget-function security. We first prove a non-trivial upper bound on the secure computing capacity defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node for one use of the network. The upper bound obtained is applicable to arbitrary network topologies and arbitrary security levels. In particular, when the security levelris equal to 0, the upper bound reduces to the computing capacity without security consideration. This upper bound is always not less than the upper bound obtained in Part I for source security, which accords with the relation between the secure computing capacities for target-function security and source security. We further obtain a bound on the gap between the two upper bounds, and show that the gap between the two upper bounds can be unbounded. Furthermore, we present an algebraic framework for linear (function-computing) secure codes for the target-function-security model by proving two equivalent conditions for computability and target-function security, respectively. With this framework, we develop a construction of linear secure codes for the target-function-security model and thus obtain a lower bound on the secure computing capacity. In the same spirit, we also prove an equivalent algebraic condition for source security, and so obtain an algebraic framework for linear secure codes for the source-security model. With this, we not only generalize the code construction developed in Part I for the source-security model but also can present it in a more succinct and understandable way. In addition, motivated by the fact that a source-secure code is target-function-secure but not vice versa, we compare our code construction for the target-function-security model and the generalized code construction for the source-security model, and show that the codes constructed by the generalized code construction for source security are only a very special subclass of the codes constructed by the code construction for target-function security. Further, a considerably smaller field size can be used for our code construction for target-function security compared with the generalized code construction for source security.

In this paper, we consider code construction for the model of secure network function computation, where in a directed acyclic network, a sink node is required to correctly compute a linear function, regarded as the target function, of source messages generated at multiple source nodes; while a wiretapper, who can access any one edge subset up to a certain size$r$, referred to as the security level, is not allowed to obtain any information about a security function of the source messages. Here, we focus on an interesting and important case that the security function is identical to the target function, namely that we need to protect any information of the target function from being leaked to the wiretapper, which is called the target-function security. We prove an equivalent condition for targetfunction security for the existence of linear function-computing secure network codes from an algebraic point of view. With this, we develop a construction of linear function-computing secure network codes and thus obtain a lower bound on the secure computing capacity, defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node for one use of the network under the target-function-security constraint.

Network error control coding can be regarded as a generalization of classical algebraic coding. In particular, the minimum distance (in terms of the Hamming distance) in classical algebraic coding generalizes naturally to linear network error control coding. However, Yang and Yeung [1] surprisingly discovered that for a nonlinear network code, two different minimum distances are needed for characterizing its capabilities for error correction and error detection. In this paper, we further develop the research in this direction. Specifically, we introduce a distance and its refined version for joint error correction and detection and prove some of their basic properties, and study the relation between various distances for network error control. These results not only provide new insights into the error control capabilities of nonlinear network codes, but also enable linear network codes to be understood from a broader perspective.

In coding theory, codes are usually designed with a certain level of randomness to facilitate analysis and accommodate different channel conditions. However, the resulting random code constructed can be suboptimal in practical implementations. Represented by a bipartite graph, the Batched Sparse Code (BATS Code) is a randomly constructed erasure code that utilizes network coding to achieve near-optimal performance in wireless multi-hop networks. In the performance analysis in the previous research, it is implicitly assumed that the coded batches in the BATS code are independent. This assumption holds only asymptotically when the number of input symbols is infinite, but it does not generally hold in a practical setting where the number of input symbols is finite, especially when the code is constructed randomly. We show that dependence among the batches significantly degrades the code’s performance. In order to control the batch dependence through graphical design, we propose constructing the BATS code in a structured manner. A hardware-friendly structured BATS code called the Cyclic-Shift BATS (CS-BATS) code is proposed, which constructs the code from a small base graph using light-weight cyclic-shift operations. We demonstrate that when the base graph is properly designed, a higher decoding rate and a smaller complexity can be achieved compared with the random BATS code.

In this paper, we first explore the underlying mathematical structure of edge subsets on a finite directed acyclic graph in using a lattice-theoretic approach. We prove that a collection of edge subsets, depending on different conditions it satisfies, together with the corresponding “cut-separating” partial order, can form a meet-semilattice, a join-semilattice or a lattice. The bottom and top thus derived generalize the concept of the primary minimum cut introduced by Guang and Yeung (2018) and hence we provide a new way from the lattice-theoretic point of view to understand the primary minimum cut and its existence and uniqueness. The introduced concepts and obtained results regarded as a bridge connect graph theory and lattice theory, which appear to be of fundamental interest in graph theory, lattice theory, and even beyond. In addition, we consider linear network error correction (LNEC) coding when errors may occur on edges of a communication network of which the topology is known. In LNEC coding, the minimum required field size for the existence of LNEC codes, in particular LNEC maximum distance separable (MDS) codes which are regarded as a most important type of optimal codes, is an open problem not only of theoretical interest but also of practical importance. By applying the approach of the above edge-subset (semi-)lattice, we obtain an improved upper bound on the minimum required field size for the existence of LNEC (MDS) codes. We quantify the improvement over the existing results by both theoretical analysis and numerical simulations and thus show that the improvement is in general significant. The improved upper bound, which is graph-theoretic, depends only on the network topology and requirement of the error correction capability but not on a specific code construction. We also develop an efficient algorithm that can compute the bound in a linear time of the number of edges.

The proof of information inequalities and identities under linear constraints on the information measures is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). Building on our recent work (Guo et al., 2023), we developed in this paper an enhanced approach for solving this problem. Experimental results show that our new approach improves the time complexity by over 500 times compared with Guo et al. (2023) for the problem studied by Tian (2014).

The network coding enhances performance in network communications and distributed storage by increasing throughput and robustness while reducing latency. Batched sparse (BATS) codes are a class of capacity-achieving network codes, but their practical applications are hindered by their structure, computational intensity, and power demands of finite field (FF) operations. Most literature focuses on algorithmic-level techniques to improve the coding efficiency. Optimization with an algorithm/hardware co-designing approach has long been neglected. Leveraging the unique structure of BATS codes, we first present cyclic-shift BATS (CS-BATS), a hardware-friendly variant. Next, we propose a simple but effective bounded-value (BV) generator, to reduce the size of a finite field multiplier by up to 70%. Finally, we report on a scalable and resource-efficient field-programmable gate array (FPGA)-based network coding accelerator that achieves a throughput of 27 Gb/s, a speedup of more than 300 over software.

In this paper, we put forward the problem of secure network function computation under the function-security constraint. In this model, a target function, of which the inputs are generated at multiple source nodes as source messages, is required to be computed with zero error at a sink node over a network, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a target function of the source messages. The secure computing rate of a secure function-computing network code is the average number of times the target function can be securely computed per use of the network. However, characterizing this secure capacity with this general setup is overwhelmingly difficult. In this paper, we consider this secure model in which the target function and the security function are identical to be a linear function; and the wiretapper can eavesdrop any one edge subset up to a size$r$, referred to as the security level. We obtain a non-trivial upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. When$r=0$, the upper bound reduces to the computing capacity without security consideration. By applying the upper bound, we obtain an upper bound on the maximum security level such that the function can be securely computed with a positive rate, and fully characterize the secure computing capacity for a class of secure models. Finally, we prove that our upper bound is always larger than or equal to the upper bound previously obtained by Guang et al. on the secure computing capacity for source-security. This is consistent with the relation between the secure computing capacities for source-security and function-security.

Symmetric multilevel diversity coding (SMDC) is a multi-source coding problem where the independent sources are ordered according to their importance. It was shown that sepa-rately encoding independent sources, referred to as superposition coding, is optimal. In this paper, an (L, s) sliding secure SMDC problem is considered, where$L$is the number of encoders and$s$is the security threshold, which means that each source$X$ais kept perfectly secure if no more than a -$s$encoders are accessible. It is shown that superposition coding is optimal for$s$= 1. The rate region for (L, s) = (3, 2) is characterized, which implies the suboptimality of superposition coding for the general problem. The main idea that joint coding can reduce rates is that we can use the previous source X a -1 as the secret key of X a. Based on this idea, a pseudo-superposition coding scheme is proposed to achieve the minimum sum rate, which uses superposition for the$s$sets of sources Xl, X2,‥ Xs-1, (Xs, Xs+1,”, XL). and joint encoding among Xs, Xs+1,”, XL.

The proof of information inequalities under linear constraints on the information measures is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). Building on our recent work [13], we develop in this paper an enhanced approach for solving this problem.

In this paper, we investigate the efficient transmisSion of sparse models in a distributed learning system. The system consists of multiple clients, each possessing a sparse local model, and a central server responsible for aggregating the clients' models. Our target is to characterize the tradeoff between communication cost and accuracy in transmissions from the clients to the server. We propose a compression scheme that concatenates a universal covering code and an optimal source code. The numerical results demonstrate an improvement in the communication cost over previous findings in [1]–[3] by comparing with a lower bound on the communication cost derived using a variant of a generalized Fano's inequality.

Recently, smart roadside infrastructure (SRI) has demonstrated the potential of achieving fully autonomous driving systems. To explore the potential of infrastructure-assisted autonomous driving, this paper presents the design and deployment of Soar, the first end-to-end SRI system specifically designed to support autonomous driving systems. Soar consists of both software and hardware components carefully designed to overcome various system and physical challenges. Soar can leverage the existing operational infrastructure like street lampposts for a lower barrier of adoption. Soar adopts a new communication architecture that comprises a bi-directional multi-hop I2I network and a downlink I2V broadcast service, which are designed based on off-the-shelf 802.11ac interfaces in an integrated manner. Soar also features a hierarchical DL task management framework to achieve desirable load balancing among nodes and enable them to collaborate efficiently to run multiple data-intensive autonomous driving applications. We deployed a total of 18 Soar nodes on existing lampposts on campus, which have been operational for over two years. Our real-world evaluation shows that Soar can support a diverse set of autonomous driving applications and achieve desirable real-time performance and high communication reliability. Our findings and experiences in this work offer key insights into the development and deployment of next-generation smart roadside infrastructure and autonomous driving systems.

In this paper, we put forward secure network function computation over a directed acyclic network. In such a network, a sink node is required to compute with zero error a target function of which the inputs are generated as source messages at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a security function of the source messages. The secure computing capacity for the above model is defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node with the given collection of wiretap sets and security function for one use of the network. The characterization of this capacity is in general overwhelmingly difficult. In the current paper, we consider securely computing linear functions with a wiretapper who can eavesdrop any subset of edges up to a certain size$r$, referred to as the security level, with the security function being the identity function. We first prove an upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. This upper bound depends on the network topology and security level. Furthermore, we obtain an upper bound and a lower bound on this bound, which are both in closed form. In particular, when the security level$r$is equal to 0, our upper bound reduces to the computing capacity without security consideration. Also, we discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. Furthermore, we obtain an equivalent expression of the upper bound by using a graph-theoretic approach, and accordingly we develop an efficient approach for computing this bound. On the other hand, we present a construction of linear function-computing secure network codes and obtain a lower bound on the secure computing capacity. By our code construction, for the linear function which is over a given finite field, we can always construct a (vector-) linear function-computing secure network code over the same field. We also give some sufficient conditions for the tightness of the lower bound in terms of the network topology. With this lower bound and the upper bound we have obtained, the secure computing capacity for some classes of secure models can be fully characterized. Another interesting case is that the security function is the same as the target function, which will be investigated in Part II of this paper.

We consider a generalized collision channel model for general multi-user communication systems, an extension of Massey and Mathys’ collision channel without feedback for multiple access communications. In our model, there are multiple transmitters and receivers sharing the same communication channel. The transmitters are not synchronized and arbitrary time offsets between transmitters and receivers are assumed. A "collision" occurs if two or more packets from different transmitters partially or completely overlap at a receiver. Our model includes the original collision channel as a special case.This paper focuses on reliable throughputs that are approachable for arbitrary time offsets. We consider both slot-synchronized and non-synchronized cases and characterize their reliable throughput regions for the generalized collision channel model. These two regions are proven to coincide. Moreover, it is shown that the protocol sequences constructed for multiple access communication remain "throughput optimal" in the generalized collision channel model. We also identify the protocol sequences that can approach the outer boundary of the reliable throughput region.

Proving linear inequalities and identities of Shannon’s information measures, possibly with linear constraints on the information measures, is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). In particular, an identity$f = 0$is verified by solving two LPs, one for$f \ge 0$and one for$f \le 0$. In this paper, we develop a set of algorithms that can be implemented by symbolic computation. Based on these algorithms, procedures for verifying linear information inequalities and identities are devised. Compared with LP-based algorithms, our procedures can produce analytical proofs that are both human-verifiable and free of numerical errors. Our procedures are also more efficient computationally. For constrained inequalities, by taking advantage of the algebraic structure of the problem, the size of the LP that needs to be solved can be significantly reduced. For identities, instead of solving two LPs, the identity can be verified directly with very little computation.

The problem of secure network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function f, of which the inputs are generated at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, obtains no information about the source inputs. The secure computing rate of a secure function-computing network code is the average number of times the target function can be securely computed for one use of the network. In the paper, we are interested in securely computing linear functions with the wiretapper who can eavesdrop any subset of edges up to a certain size r, referred to as the security level. We obtain an improved upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. When the security level r is equal to 0, our improved upper bound reduces to the computing capacity without security consideration. Furthermore, by applying the improved upper bound, we obtain a non-trivial upper bound on the maximum security level such that the function can be securely computed with a positive rate. We also present a lower bound on the secure computing capacity and give some sufficient conditions in terms of the network topology on the tightness of the lower bound. Together with the improved upper bound, the secure computing capacity for a class of security models can be fully characterized.

Proving linear inequalities and identities of Shannon’s information measures, possibly with linear constraints on the information measures, is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). In particular, an identity f = 0 is verified by solving two LPs, one for f ≥ 0 and one for f ≤ 0. In this paper, we develop a set of algorithms that can be implemented by symbolic computation. Based on these algorithms, procedures for verifying linear information inequalities and identities are devised. Compared with LP-based algorithms, our procedures can produce analytical proofs that are both human-verifiable and free of numerical errors. Our procedures are also more efficient computationally. For constrained inequalities, by taking advantage of the algebraic structure of the problem, the size of the LP that needs to be solved can be significantly reduced. For identities, instead of solving two LPs, the identity can be verified directly with very little computation.

BATched Sparse codes (BATS codes) are a class of random linear network code designed for wireless multi-hop networks with packet loss. The encoder of a BATS code generates batches where each batch contains a number of coded packets. As the outer code is a matrix generalization of the fountain code, the ordinary batch construction scheme relies on a degree distribution with a random packet sampling scheme. In practical applications, we want a batch construction scheme which achieves a high decoding rate at the destination. A natural question to ask is: Is there any batch construction scheme which achieves a higher decoding rate than the ordinary one? We give an affirmative answer to this question by formulating the batch construction scheme as a multi-armed bandit problem and solving it with a deep reinforcement learning method with the degree distribution as a guiding prior. The BATS code generated by our proposed method achieves a higher decoding rate with improved efficiency compared with the ordinary batch construction scheme.

This paper presents the first systematic study of the zero-error capacity regions of noisy networks. First, we consider two simple such networks, each consisting of a stationary memoryless multiple access channel with two binary inputs and one discrete output. There are two users in each network. Each of the two users transmits a message through the network, and the sink(s) of the network can decode both messages with zero error. A graph is used to represent the distinguishability of the inputs of the channel, and agraph setis used to represent the distinguishability of the inputs of the network. We show that for two networks represented by the same graph set, their zero-error capacity regions are the same. We list all the possible graph sets for the two networks and determine the zero-error capacity regions for some of these graph sets. Based on this result, we explore a relation between graph theory and set theory, and then redefine thecancellative pair of families of subsets. We further extend the problem formulation to a general network called theparallel network, which may consist of more than one channel with multiple inputs and multiple outputs.

In this paper, we put forward the model of secure network function computation. In this model, a target function, of which the inputs are generated at multiple source nodes, is required to be computed with zero error at a sink node over a network while being protected from a wiretapper who can access any one but not more than one wiretap set in a given collection of wiretap sets. The secure computing rate of a secure network code is the average number of times the target function can be securely computed with zero error for one use of the network. However, characterizing this secure capacity with this general setup is overwhelmingly difficult. In the paper, we only consider this secure model for linear functions with the wiretapper being able to eavesdrop any subset of edges in the network up to a certain size, referred to as the security level. We prove a non-trivial upper bound on the secure computing capacity. Also, we discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. We further present a lower bound by designing a secure network coding scheme. Both the upper and lower bounds are tight for some cases but not tight in general. Finally, by comparing the upper and lower bounds thus obtained, we can exactly characterize the secure computing capacity when network topology satisfies a certain condition.

Batched network coding (BNC) is a low-complexity solution to network transmission in multi-hop packet networks with packet loss. BNC encodes the source data into batches of packets. As a network coding scheme, the intermediate nodes perform recoding on the received packets belonging to the same batch instead of just forwarding them. A recoding scheme that may generate more recoded packets for batches of a higher rank is also called adaptive recoding. Meanwhile, in order to combat burst packet loss, the transmission of a block of batches can be interleaved. Stream interleaving studied in literature achieves the maximum separation among any two consecutive packets of a batch, but permutes packets across blocks and hence cannot bound the buffer size and the latency. To resolve the issue of stream interleaver, we design an intrablock interleaver for adaptive recoding that can preserve the advantages of using a block interleaver when the number of recoded packets is the same for all batches. We use potential energy in classical mechanics to measure the performance of an interleaver, and propose an algorithm to optimize the interleaver with this performance measure. Our problem formulation and algorithm for intrablock interleaving are also of independent interest.

Wireless relay network is a solution for transmitting information from a source node to a sink node far away by installing a relay in between. The broadcasting nature of wireless communication allows the sink node to receive part of the data sent by the source node. In this way, the relay does not need to receive the whole piece of data from the source node and it does not need to forward everything it received. In this paper, we consider the application of batched network coding, a practical form of random linear network coding, for a better utilization of such a network. The amount of innovative information at the relay which is not yet received by the sink node, called the innovative rank, plays a crucial role in various applications including the design of the transmission scheme and the analysis of the throughput. We present a visualization of the innovative rank which allows us to understand and derive formulae related to the innovative rank with ease.

We consider linear network error correction (LNEC) coding when errors may occur on the edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-known LNEC coding approaches. In LNEC coding, LNEC maximum distance separable (MDS) codes are a type of most important optimal codes. However, the minimum required field size for the existence of LNEC MDS codes is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we obtain an improved lower bound on the required field size by developing a graph-theoretic approach. The improvement over the existing results is in general significant. Furthermore, by applying the graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the capability of an LNEC code in terms of its minimum distance.

The discussion rate region in the multiterminal source model is the individual discussion rate required for generating a secret key of maximum rate. We give an explicit single-letter characterization of the discussion rate region for a large class of pairwise independent network (PIN) models. Besides, we also establish a sufficient condition for identifying whether a PIN model belongs to this class, which can be checked in strongly polynomial time. As a by-product, the discussion rate region reduces to a very simple expression for PIN model satisfying such condition.

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented.

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where security constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunity to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a set of particular security constraints, one of the proposed joint coding strategies can be used to construct a code that achieves the optimal rate region.

Proving or disproving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving more than a few random variables is difficult to be proved or disproved manually. In 1997, Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under the framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. The way to automatically find a shortest proof or a smallest counterexample is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming. Lastly, we propose a scalable algorithmic framework based on the alternating direction method of multipliers to accelerate solving a multitude of user-specific problems whose overall computational cost can be amortized with the number of users, and present its publicly-available software implementation for large-scale problems.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of I nodes. An (n, k, d, I) secure exact-repair regenerating code is an (n, k, d) exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters (n, k, d, I), the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound ℓ̂ on the number of wiretap nodes, and show that this bound is tight for the case k = d = n - 1.

In the paradigm of network coding, information-theoretic security is considered in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding for flexible pairs of information rate and security level with any fixed dimension (equal to the sum of rate and security level). We present a novel approach for designing a secure linear network code (SLNC) such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. We further develop a polynomial-time algorithm for efficient implementation and prove that there is no penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, by applying our approach as a crucial building block, we can construct a family of SLNCs that not only can be applied to all possible pairs of rate and security level but also share a common local encoding kernel at each intermediate node in the network.

Proving or disproving linear information theoretic inequalities is a fundamental task in information theory, and it has also been proved to be important in fields like cryptography and quantum communication theory. Manually proving information inequalities involving more than a few random variables can often be tedious or even intractable. In 1997, Yeung proposed a linear programming framework for verifying information inequalities, which was later extended to construct analytical proofs and disproofs. However, in practice this framework can be very slow for inequalities involving more than ten random variables, thus it is impossible to be applied to a wide range of practical problems. In this paper, we further extend this optimization-theoretic framework by reformulating the LPs and applying the Alternating Direction Method of Multipliers (ADMM) technique, where all the subproblems have closed-form solutions and thus can be solved efficiently. The proposed algorithm is also parallelizable so the performance can be further improved by running it on a GPU. An online web service is developed to allow users to prove or disprove their problem-specific inequalities without installing any software package or dependency.

BATS codes are a class of random linear network coding scheme which have close-to-optimal achievable rates, while adaptive recoding is a packet combining scheme which adds a boost to the throughput by adapting the packet combining at the relay to the random fluctuations in the number of erasures in individual batches. In this paper, we apply BATS code with adaptive recoding for the transmission on wireless relay network. In contrast to the existing adaptive recoding schemes, we propose a model which can make use of the broadcast nature of wireless communication to enhance the achievable rates via overhearing. We also optimize the packet efficiency, i.e., minimizing the average number of channel use for each input packet for a successful decoding.

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where secrecy constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunities to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a particular security configuration, one of the proposed joint coding strategies can be used to achieve the optimal sum rate.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are not only able to enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non-achievable, but whether it is asymptotically achievable or not remains open.

Massive Open Online Courses (MOOCs) have become an option for convenient access to education opportunities. However, the low completion rates remain a major challenge for MOOC teachers and providers. Meanwhile, very little has been known about learner experience in MOOC on Information Theory; which is a fundamental field of interest in engineering. This work-inprogress aims at promoting student completion rate in a MOOC on Information Theory by identifying effective strategies for individualized MOOC learning. In particular, the research-to-practice study takes place in a MOOC designed and taught by the third author. We established a learning experience model by extended an existing framework in the MOOC literature. We validated our model with empirical learning data collected from our own MOOC. We identified variables that predict student learning outcomes and completion. Our model enables us to further develop an Individualized Learning Path System that generates and selects the most suitable learning path for individual students.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. By applying this bound to the problem of computing a vector-linear function over a network, we are able to not only enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non achievable, but whether it is asymptotically achievable or not remains open.

It is well known thatsuperposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In this paper, we first obtain closed-form expressions of these uncountably many inequalities. Then we identify a finite subset of inequalities that is sufficient for characterizing the coding rate region. This gives an explicit characterization of the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast withL.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of l nodes. Under this security constraint, it has been shown that the optimal tradeoff curve has a single corner point for some (n, k, d, l). The focus of this paper is on finding parameters (n, k, d, l) whose associated tradeoff curve has this behavior. For k=d=n-1, we prove that the tradeoff curve has a single corner point if and only if l ≥ [[1/4](d-1)]. Previously, it was known that the tradeoff curve has a single corner point if l ≥ [(√d-1)2].

In the future communication applications, users may obtain their messages that have different importance levels distributively from several available sources, such as distributed storage or even devices belonging to other users. This scenario is the best modeled by the multilevel diversity coding systems (MDCS). To achieve perfect (information-theoretic) secrecy against wiretap channels, this paper investigates the fundamental limits on the secure rate region of the asymmetric MDCS (AMDCS), which include the symmetric case as a special case. Threshold perfect secrecy is added to the AMDCS model. The eavesdropper may have access to any one but not more than one subset of the channels but know nothing about the sources, as long as the size of the subset is not above the security level. The question of whether superposition (source separation) coding is optimal for such an AMDCS with threshold perfect secrecy is answered. A class of secure AMDCS (S-AMDCS) with an arbitrary number of encoders is solved, and it is shown that linear codes are optimal for this class of instances. However, in contrast with the secure symmetric MDCS, superposition is shown to be not optimal for S-AMDCS in general. In addition, necessary conditions on the existence of a secrecy key are determined as a design guideline.

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory.

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound.

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulas with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded.

Whether superposition (source separation) Is optimal for the asymmetric multilevel diversity coding systems (AMDCS) with perfect secrecy is answered in this paper by studying a non-trivial example. Threshold perfect secrecy is added to the AMDCS model. The eavesdropper may have access to any one but not more than one subset of the channels but can get nothing about the sources, as long as the size of the subset is not above the security level. The secure AMDCS (S-AMDCS) with five sources, four encoders and security level two is solved and it is shown that linear codes are optimal for this instance. However, in contrast with the secure symmetric multilevel diversity coding systems (S-SMDCS), superposition is shown to be not optimal for S-AMDCS in general from this counterexample.

Let Xi, i E V form a Markov random field (MRF) represented by an undirected graph G = (V, E), and V' be a subset of V. We determine the smallest graph that can always represent the subfield Xi, i E V' as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i E V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the minimum required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound. The graph-theoretic concepts introduced and the results obtained appear to be of fundamental interest in graph theory.

In conventional distributed storage exact repair problems, all sources are reconstructed when the decoder has access to a certain number of encoders (disks). So, the underlying reconstruction network is equivalent to a single-source problem. This paper considers a variant of the exact repair problem, where the underlying reconstruction network is the independent distributed source coding problem, a type of multi-source problem. As the first non-trivial case with two sources and three encoders, the storage-repair tradeoff regions are proved for all the 33 instances, and it is shown that binary codes are optimal.

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of nodes. In other words, the repair process is required to be secure. The focus of this paper is on such systems with 5 nodes. Specifically, we characterize the rate regions under secure repair for the (5, 3, 4) and (5, 4, 4) instances with 1 or 2 wiretap nodes. While characterizing the rate region of exact-repair regenerating codes remains open, our results indicate that the problem may be more tractable under the security constraint as described.

Let N = (1,..., n). The entropy function h of a set of n discrete random variables (Xi: i ∈ N ) is a 2n-dimensional vector whose entries are h(A) △ H(X ), A c N, the (joint) entropies of the subsets of the set of n random variables with H(XØ) = 0 by convention. The set of all entropy functions for n discrete random variables, denoted by Γn*, is called the entropy region for n. Characterization of Γn* and its closure Γn* are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider partitionsymmetrical entropy functions. Let p = (N1,..., Nt) be a t-partition of N. An entropy function his called p-symmetrical if for all A, B ⊂ N, h(A) = h(B) whenever |A∩Ni| = |B∩Ni|, i = 1,..., t. The set of all the p-symmetrical entropy functions, denoted by ψp*, is called p-symmetrical entropy function region. We prove that ψp*, the closure of ψp*, is completely characterized by Shannon-type information inequalities if and only if p is the 1-partition or a 2-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems.

We study the degrees of freedom (DoFs) of the multiple input multiple output (MIMO) multipair two-way distributed relay channel (mTDRC), where$K$pairs of users, each equipped with$M$antennas, exchange messages in a pairwise manner with the help of two geographically separated relay nodes, each with$N$antennas. We establish a general framework for the DoF analysis by combining the ideas of signal space alignment and interference neutralization. The proposed framework involves a joint design of user transmit beamformers, relay precoders, and user receive beamformers. Novel signal alignment techniques are proposed to reduce the number of linearly independent constraints for interference neutralization. Based on that, the original joint transceiver and relay design problem boils down to a problem solely on the design of the relay precoders. This problem is then solved utilizing recent development on the solvability of linear matrix equations. As a result, we derive an achievable DoF for the MIMO mTDRC with an arbitrary configuration of$(K,M,N)$. For$K=2$, the optimal DoF of the considered network is derived for$({M}/{N})\in (0, {1}/{2}) \cup (1,\infty )$by showing that the obtained achievable DoF meets a DoF upper bound. This result beats the state of the art by establishing the optimal DoF of the considered network in an extra range of$({M}/{N})\in (1,2)$. In addition, the achievable DoF obtained for$K=2$is much higher than the existing result in the range of$({M}/{N})\in ({11}/{16},1)$. Furthermore, we show that the optimal DoF of the considered network with$K\geq 3$is derived for$({M}/{N})\in (0, ({2K+\sqrt {2K}})/({4K^{2}-2K})) \cup ({3}/{2},\infty )$.

We study the degrees of freedom (DoF) of a distributed multi-input multi-output (MIMO) multiway relay channel (mRC) where two pairs of users, each equipped with M antennas, exchange messages in a pairwise manner with the help of two separated relay nodes, each with N antennas. We establish a general framework to derive achievable DoF based on linear signal processing. We show that, to achieve a certain DoF, a joint design of the user transmit beamforming, relay precoding, and user receive beamforming is required. We propose novel signal alignment techniques to reduce the number of linearly independent equations required for interference neutralization. Then, the original joint transceiver and relay design problem boils down to a problem solely on the design of the relay precoders. Based on recent developments on solving linear matrix systems, we determine the solution to the relay design problem and derive the corresponding achievable DoF. Our analysis reveals that the DoF of the considered network is achieved for equation, which is broader than the existing results by covering an extra range of M over N ∈ (1, 2).

We prove that by imposing a conditional mutual independence constraint and a marginalisation constraint, the almost entropic region can be completely characterised by Shannon-type information inequalities. Such a property is applied to obtain an explicit lower bound on the generalised Wyner common information.

In a point-to-point communication system, which consists of a sender, a receiver, and a set of noiseless channels, the sender wishes to transmit a private message to the receiver through the channels, which may be eavesdropped by a wiretapper. The set of wiretap sets is arbitrary. The wiretapper can access any one but not more than one wiretap set. From each wiretap set, the wiretapper can obtain some partial information about the private message, which is measured by the equivocation of the message given the symbols obtained by the wiretapper. The security strategy is to encode the message with some random key at the sender. Only the message is required to be recovered at the receiver. Under this setting, we define an achievable rate tuple consisting of the size of the message, the size of the key, and the equivocation for each wiretap set. We first prove a tight rate region when both the message and the key are required to be recovered at the receiver. Then, we extend the result to the general case when only the message is required to be recovered at the receiver. Moreover, we show that even if stochastic encoding is employed at the sender, the message rate cannot be increased.

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. Under the classical model, every node in a discrete memoryless network (DMN) incurs a unit delay, and the capacity region of the DMN satisfies the well-known cut-set outer bound. In this paper, we propose a generalized model for the DMN where some nodes may incur no delay. Under our generalized model, we obtain a new cut-set outer bound, which is proved to be tight for some two-node DMN and is shown to subsume an existing cut-set bound for the causal relay network. In addition, we establish under the generalized model another cut-set outer bound on the positive-delay region-the set of achievable rate tuples under the constraint that every node incurs a delay. We use the cut-set bound on the positive-delay region to show that for some two-node DMN under the generalized model, the positive-delay region is strictly smaller than the capacity region.

Proving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving many random variables is difficult to be proved manually. In [1], Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under this framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality. The way to find a shortest proof is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming.

Consider a communication network represented by a directed graph G = (V, ε), where V is the set of nodes and 8 is the set of point-to-point channels in the network. On the network, a secure message M is transmitted, and there may exist wiretappers who want to obtain information about the message. In secure network coding, we aim to find a network code, which can protect the message against the wiretapper whose power is constrained. Cai and Yeung studied the model in which the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection A of all possible wiretap sets. In order to protect the message, the message needs to be mixed with a random key K. They proved tight fundamental performance bounds when A consists of all subsets of ε of a fixed size r. However, beyond this special case, obtaining such bounds is much more difficult. In this paper, we investigate the problem when A consists of arbitrary subsets of ε and obtain the following results: 1) an upper bound on H(M) and 2) a lower bound on H(K) in terms of H(M). The upper bound on H(M) is explicit, while the lower bound on H(K) can be computed in polynomial time when |A| is fixed. The tightness of the lower bound for the point-to-point communication system is also proved.

Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce batched sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks and certain multicast networks. For general multicast networks, under different optimization criteria, guaranteed decoding rates for the destination nodes can be obtained.

We investigate the data transmission problem in which a sequence of data is broadcast to a number of receivers via erasure channels with different erasure probabilities. Accordingly, the receivers wish to decode the data sequentially at different rates. We present a formulation of the problem and propose an optimal coding scheme. Our results can be employed in the streaming of a video clip by broadcasting, so that receivers with different bandwidths can play the video at different speeds. Specifically, receivers with sufficiently large bandwidth can play the video at normal speed, while others can play the video with pauses, or at a slower speed using time-scale modification. Our results completely characterize the fundamental tradeoff between the available bandwidth and the playback speed of the video.

Consider the entropy function region for discrete random variables Xi, i ϵ N and partition N into N1and N2with 0 ≤ |N1| ≤ |N2|. An entropy function h is called (N1, N2)-symmetrical if for all A, B ⊂ N, h(A) = h(B) whenever |A ∩ N1| = |B ∩N1|, i = 1,2. We prove that for |N1| = 0 or 1, the closure of the (N1, N2)-symmetrical entropy function region is completely characterized by Shannon-type information inequalities. Applications of this work include threshold secret sharing and distributed data storage, where symmetry exists in the structure of the problem.

In this paper, we show that the characterisation of all determinant inequalities for n × n positive definite matrices is equivalent to determining the smallest closed and convex cone containing all entropy functions induced by n scalar jointly Gaussian random variables. We have obtained inner and outer bounds on the cone by using representable functions and entropic functions. In particular, these bounds are tight and explicit for n ≤ 3, implying that determinant inequalities for 3 × 3 positive definite matrices are completely characterized by Shannon-type information inequalities.

In a point-to-point communication system which consists of a sender s, a receiver t and a set of noiseless channels, the senders wants to transmit a private message to the receiver t through the channels which may be eavesdropped by a wiretapper. The wiretapper can access any one but not more than one set of channels, which is referred to as a wiretap set. It is assumed that from each wiretap set, the wiretapper can obtain some partial information about the private message which is measured by the wiretapper's equivocation. The security strategy is to encode the message with some random key. Under these settings, we define an achievable rate tuple in terms of the message, the key and the wiretapper's equivocation, and prove a tight rate region of the rate tuples.

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. In this paper, we investigate the generalized discrete memoryless network (DMN) where some nodes may incur no delay. We call the capacity region of the generalized DMN under the constraint that every node incurs a delay the positive-delay region. We establish the cut-set outer bound on the positive-delay region. In addition, we use our cut-set outer bound to show that in some two-node generalized DMN, the positive-delay region is strictly smaller than the capacity region.

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. In the classical discrete memoryless network (DMN), every node incurs a delay. A well-known result for the classical DMN is the cut-set outer bound. In this paper, we generalize the model of the DMN in such a way that some nodes may incur no delay, and we obtain the cut-set outer bound for the generalized DMN.

In this paper, we propose an “arbitrarily varying channel” (AVC) approach to study the capacity of noncoherent transmission in a network that employs randomized linear network coding. The network operation is modeled by a matrix channel over a finite field where the transfer matrix changes arbitrarily from time-slot to time-slot but up to a known distribution over its rank. By extending the AVC results to this setup, we characterize the capacity of such a non-coherent transmission scheme and show that subspace coding is optimal for achieving the capacity. By imposing a probability distribution over the state space of an AVC, we obtain a channel which we called “partially arbitrarily varying channel” (PAVC). In this work, we characterize the “randomized” as well as the “deterministic” code capacity of a PAVC under the average error probability criterion. Although we introduce the PAVC to model the non-coherent network coding, this extension to an AVC might be of its own interest as well.

Contrary to the traditional method of information inequalities, in this paper, the entropy function region Γn* and its closure ̅Γn* are characterized via extreme rays of its outer bound polymatroidal region Γn. The characterization of Γ3* and the tightness of Γnas an outer bound on ̅Γn* are studied.

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.

We study the three-node point-to-point relay network which consists of two terminal nodes and one relay node between them and investigate practical network coding schemes for the network. The rate region achievable by the practical network coding schemes is obtained, and a procedure for constructing the linear network codes that achieve the rate pairs in the achievable rate region is presented. In addition, we show that the use of network coding rather than routing alone enlarges the achievable rate region, in particular increases the maximum equal-rate throughput.

We consider a two-way relay channel (TRC) in which two terminals exchange messages with the help of a relay between them. The two terminals transmit messages to the relay through the Multiple Access Channel (MAC) and the relay transmits messages to the two terminals through the Broadcast Channel (BC). We assume that the MAC and the BC do not interfere with each other, and each terminal receives signals only from the relay but not the other terminal. All the nodes are assumed to be full-duplex, which means that they can transmit and receive information at the same time. The TRC is said to be without feedback if each terminal node cannot use its previously received information for encoding its message. Otherwise, the TRC is said to be with feedback. We obtain an outer bound on the capacity region of the discrete memoryless TRC without feedback and prove that the outer bound is tighter than the cut-set outer bound. In addition, we show that using feedback can enlarge the capacity region of some discrete memoryless TRC.

Batched sparse (BATS) codes are proposed for transmitting a collection of packets through communication networks employing linear network coding. BATS codes generalize fountain codes and preserve the properties such as ratelessness and low encoding/decoding complexity. Moreover, the buffer size and the computation capability of the intermediate network nodes required to apply BATS codes are independent of the number of packets for transmission. It is verified theoretically for certain cases and demonstrated numerically for the general cases that BATS codes achieve rates very close to the capacity of linear operator channels.

Ten years ago, Ahlswede, Cai, Li, and Yeung refuted the folklore that information can be regarded as a commodity in network communication by means of an example now known as the butterfly network. The concept of network coding was formulated, and the fundamental max-flow-min-cut theorem for information flow was established. Since then, the work has generated much interest among many different research communities in engineering, mathematics, and natural science. This paper gives a historical account of the developments that led to this seminal work in network coding.

In the paradigm of network coding, the nodes in a network are allowed to encode the information received from the input links. With network coding, the full capacity of the network can be utilized. In this paper, we propose a model, call the wiretap network, that incorporates information security with network coding. In this model, a collection of subsets of the channels in the network is given, and a wiretapper is allowed to access any one (but not more than one) of these subsets without being able to obtain any information about the message transmitted. Our model includes secret sharing in classical cryptography as a special case. We present a construction of secure linear network codes that can be used provided a certain graph-theoretic condition is satisfied. We also prove the necessity of this condition for the special case that the wiretapper may choose to access any subset of channels of a fixed size. The optimality of our code construction is established for this special case. Finally, we extend our results to the scenario when the wiretapper is allowed to obtain a controlled amount of information about the message.

In this work, we extend the notion of generalized Hamming weight for classical linear block codes to linear network codes by introducing the network generalized Hamming weight (NGHW) for a given network with respect to a fixed linear network code. The basic properties of NGHW are studied. We further show that NGHW can be used as a tool to characterize the security performance of a linear network code on a wiretap network. We also introduce the notion of network maximum distance separable code (NMDS code) by extending the notion of Maximum Distance Separable code in classical algebraic coding theory. We prove that NMDS codes play an important role in minimizing the information that an eavesdropper can obtain from the network.

A condition governing the possibility and impossibility of linear independence among the global encoding kernels of a linear network code is found. Based on this condition, we propose several alternative definitions of generic network codes, which give interpretations of such codes from different perspectives. We also present a unified framework for specifying and constructing different classes of linear network codes. Finally, using the insight obtained from the unified framework, we show that the proofs of some existing results regarding generic network codes can be greatly simplified.

Coherent network error correction is the error-control problem in network coding with the knowledge of the network codes at the source and sink nodes. With respect to a given set of local encoding kernels defining a linear network code, we obtain refined versions of the Hamming bound, the Singleton bound, and the Gilbert-Varshamov bound for coherent network error correction. Similar to its classical counterpart, this refined Singleton bound is tight for linear network codes. The tightness of this refined bound is shown by two construction algorithms of linear network codes achieving this bound. These two algorithms illustrate different design methods: one makes use of existing network coding algorithms for error-free transmission and the other makes use of classical error-correcting codes. The implication of the tightness of the refined Singleton bound is that the sink nodes with higher maximum flow values can have higher error correction capabilities.

We introduce variable-rate linear network coding for single-source finite acyclic network. In this problem, the source of a network transmits messages at different rates in different time sessions and every nonsource node in the network decodes the messages if possible. We propose two efficient algorithms for implementing variable-rate linear network coding under different circumstances.

Strong typicality, which is more powerful for theorem proving than weak typicality, can be applied to finite alphabets only, while weak typicality can be applied to countable alphabets. In this paper, the relation between typicality and information divergence measures is discussed. The new definition of information divergence measure in this paper leads to the definition of a unified typicality for finite or countably infinite alphabets which is stronger than both weak typicality and strong typicality. Unified typicality retains the asymptotic equipartition property and the structural properties of strong typicality, and it can potentially be used to generalize those theorems which are previously established by strong typicality to countable alphabets. The applications in rate-distortion theory and multisource network coding problems are discussed.

The relation between the Shannon entropy and variational distance, two fundamental and frequently-used quantities in information theory, is studied in this paper by means of certain bounds on the entropy difference between two probability distributions in terms of the variational distance between them and their alphabet sizes. We also show how to find the distribution achieving the minimum (or maximum) entropy among those distributions within a given variational distance from any given distribution. These results are applied to solve a number of problems that are of fundamental interest. For entropy estimation, we obtain an analytic formula for the confidence interval, solving a problem that has been opened for more than 30 years. For approximation of probability distributions, we find the minimum entropy difference between two distributions in terms of their alphabet sizes and the variational distance between them. In particular, we show that the entropy difference between two distributions that are close in variational distance can be arbitrarily large if the alphabet sizes of the two distributions are unconstrained. For random number generation, we characterize the tradeoff between the amount of randomness required and the distortion in terms of variation distance. New tools for non-convex optimization have been developed to establish the results in this paper.

In this paper, we study the linear multi-source network coding security problem in, without the assumption that all source messages have positive distributions. We obtain a necessary and sufficient security condition, which can be regarded as a generalization of the one in.

The Shannon information measures are well known to be continuous functions of the probability distribution for a given finite alphabet. In this paper, however, we show that these measures are discontinuous with respect to almost all commonly used "distance" measures when the alphabet is countably infinite. Such "distance" measures include the Kullback-Leibler divergence and the variational distance. Specifically, we show that all the Shannon information measures are in fact discontinuous at all probability distributions. The proofs are based on a probability distribution which can be realized by a discrete-time Markov chain with countably infinite number of states. Our findings reveal that the limiting probability distribution may not fully characterize the asymptotic behavior of a Markov chain. These results explain why certain existing information-theoretical tools are restricted to finite alphabets, and provide hints on how these tools can be extended to countably infinite alphabet.

We introduce the continuous time asynchronous channel as a model for time jitter in a communication system with no common clock between the transmitter and the receiver. We have obtained a simple characterization for an optimal zero-error self-synchronizable code for the asynchronous channel. The capacity of this channel is determined by both a combinatorial approach and a probabilistic approach. Our results unveil the somewhat surprising fact that it is not necessary for the receiver clock to resynchronize with the transmitter clock within a fixed maximum time in order to achieve reliable communication. This means that no upper limit should be imposed on the run lengths of the self-synchronization code as in the case of run-length limited (RLL) codes which are commonly used in magnetic recording.

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 prove the optimality of a secure network code we have previously constructed when the wiretapper can choose to access any subset of the channels of a fixed size. Specifically, we prove that the network code we constructed multicasts the maximum possible amount of information to the user nodes securely and uses the minimum amount of randomness to achieve the required security.

Consider a source network in which a finite alphabet source X = {Xi}i=0infinis to be encoded and transmitted, and another finite alphabet source Y = {Xi}i=0infincorrelated with X is available only to the decoder as side information. Traditionally, the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with the fact that the encoder does not have access to Y, implies that the encoder has to know the achievable rates before encoding. In this paper, we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assume that the encoder and decoder share a random database that is independent of both X and Y. A string matching-based (variable-rate) block coding algorithm with simple progressive encoding and joint typicality decoding is first proposed for the feedback source network. The simple progressive encoder does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources satisfying some mixing conditions, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes to the conditional entropy H(X | Y) of X given Y asymptotically, and at the same time the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically. The algorithm and the corresponding analysis results are then extended to the case where both X and Y are to be encoded separately, but decoded jointly. Finally, a universal decoding algorithm is proposed to replace the joint typicality decoding, and the resulting universal compression algorithm consisting of the simple progressive encoder and the universal decoding algorithm is further shown to be asymptotically optimal for the class of all jointly memoryless source-side information pairs (X,Y).

In this paper, we introduce a network multicast problem called the alternating multicast problem. In this problem, there is more than one multicast on the network, but only one of the multicasts can take place at any time. We propose an algorithm for constructing a linear network code which is static in the sense that the coding operations do not depend on the multicast. The code so constructed achieves the max-flow bound for each multicast, i.e., optimality is achieved when the base field is sufficiently large. An upper bound on the required field size for constructing the code is also obtained. We conjecture that a network code constructed by our algorithm can be converted into a network code for the associated simultaneous multicast problem, i.e., all the multicasts can take place at the same time. An example is presented to illustrate our conjecture.

We obtain a necessary and sufficient condition for the security of multi-source linear network codes by studying the algebraic structure of such codes. This condition is useful for analyzing the security of such linear network codes, and it applies in cases when the random keys do not necessarily have uniform distributions. This condition also shows that the security of a linear network code does not depend on the source distribution.

For two probability distributions with finite alphabets, a small variational distance between them does not imply that the difference between their entropies is small if one of the alphabet sizes is unknown. This fact, seemingly contradictory to the continuity of entropy for finite alphabet, is clarified in the current paper by means of certain bounds on the entropy difference between two probability distributions in terms of the variational distance between them and their alphabet sizes. These bounds are shown to be the tightest possible. The Lagrange multiplier cannot be applied here because the variational distance is not differentiable. We also show how to find the distribution achieving the minimum (or maximum) entropy among those distributions within a given variational distance from any given distribution. The results show the limitation of certain algorithms for entropy estimation. An upper bound is obtained for the rate-distortion function with respect to the error frequency criterion, and the minimal average complexity is determined for the generation of a probability distribution with a distortion criterion.

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.

In this paper, we present a refined version of the Singleton bound for network error correction, and propose an algorithm for constructing network codes that achieve this bound.

With respect to a given set of local encoding kernels defining a linear network code, refined versions of the Hamming bound, the Singleton bound and the Gilbert-Varshamov bound for network error correction are proved by the weight properties of network codes. This refined Singleton bound is also proved to be tight for linear message sets.

Strong typicality, which is more powerful for theorem proving than the weak typicality, can be applied to finite alphabet only, while weak typicality can be applied to both finite and countably infinite alphabets. In this paper, the relation between typicality and information divergence measures is discussed. This leads to the definition of a unified typicality for finite or countably infinite alphabet which is stronger than both weak typicality and strong typicality

Convolutional network coding deals with the propagation of a message pipeline through a cyclic network. We formulate a Convolutional network code by associating every pair of adjacent channels with a rational power series over the base field, called the local encoding kernel, and every channel with a concomitant global encoding kernel, which is a vector of rational power series. Given a complete set of local encoding kernels, a close-form formula is derived for calculating the global encoding kernels. A convolutional multicast is a convolutional network code that every qualified receiving node can decode the message. We offer a construction algorithm for a convolutional multicast as well as a decoding algorithm

It is well known that the Shannon information measures are continuous functions of the probability distribution when the support is finite. This, however, does not hold when the support is countably infinite. In this paper, we investigate the continuity of the Shannon information measures for countably infinite support. With respect to a distance based on the Kullback-Liebler divergence, we use two different approaches to show that all the Shannon information measures are in fact discontinuous at all probability distributions with countably infinite support

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network

This paper extends the part of the theory on linear network coding (S.-Y.R. Li et al., 2003) over an acyclic network. The extension also applies to "static linear network code" that is introduced by R. Koetter and M. Medard, (2003). Another objective is the rigorous clarification of fundamental concepts in linear network coding

Consider a source network in which a finite alphabet source X = {Xi}iinfin=0is to be encoded and transmitted, and another finite alphabet source Y = {Yi}iinfin=0available only to the decoder as the side information correlated with X. Traditionally the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with that the encoder does not have access to Y, necessitates that the encoder knows the achievable rates before encoding. In this paper we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assuming that the encoder and decoder share a random database that is independent of both X and Y, we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. This algorithm does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources which includes the class of all memoryless sources, the class of all aperiodic Markov sources, and a large class of finite-state sources as special subclasses, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically

We prove an inequality which governs the fundamental tradeoff between burstiness and delay in traffic shaping. Our result holds under very weak assumptions

This paper presents three approaches to explore the relation between the Shannon entropy and the von Neumann entropy. The first two approaches are based on the measurement of the quantum state, while the third approach is based on the preparation of the quantum state. Each of these approaches leads to an alternative definition of the von Neumann entropy.

Network coding theory shows that the multicast rate in a network can be increased if coding is allowed in the network nodes. Thus the capacity of a network with network coding is generally larger than that with routing alone. We quantify this gain in closed form for a class of networks called combination networks. From this result, it can readily be deduced that network coding gain can be unbounded.

Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Ko/spl uml/rner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using /spl epsiv/-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.

We introduce network error-correcting codes for error correction when a source message is transmitted to a set of receiving nodes on a network. The usual approach in existing networks, namely link-by-link error correction, is a special case of network error correction. The network generalizations of the Hamming bound and the Gilbert-Varshamov bound are derived.

We establish a one-to-one correspondence between information inequalities and group inequalities. The major implication of our result is that we can prove information inequalities by proving the corresponding group inequalities, and vice versa. By giving a group-theoretic proof for all Shannon-type inequalities, we suggest that new inequalities could be discovered by making use of the rich set of tools in group theory. On the other hand, via a non-Shannon-type information inequality discovered by Zhang and Yeung (1997), we obtain a new inequality in group theory whose meaning is yet to be understood.

We study the problem of source coding with multiple descriptions, which is described as follows. Let X be a discrete memoryless source. There are two encoders, Encoders 1 and 2, and three decoders, Decoders 0, 1, and 2. Encoders 1 and 2 describe the source X at respective rates R/sub 1/ and R/sub 2/. Decoder 1 receives the output of Encoder 1 only, and it can recover X with distortion D/sub 1/. Decoder 2 receives the output of Encoder 2 only, and it can recover X with distortion D/sub 2/. Decoder 0 receives the outputs of both Encoders 1 and 2, and it can recover X with distortion D/sub 0/. We show that if Decoder 2 (or Decoder 1) is required to recover a function of the source X perfectly in the usual Shannon sense, the El Gamal-Cover (1982) inner bound on the rate distortion region is tight. This finding subsumes the Rimoldi (1994) rate-distortion region for successive refinement of information, the Kaspi (1994) rate-distortion function when side information may be present at the decoder, and the El Gamal-Cover achievable rate region for multiple descriptions with deterministic distortion measures. We have also obtained a new outer bound on the rate-distortion region which enhances the outer bound due to Witsenhausen (1981) and Wyner. This new outer bound implies some interesting facts regarding the achievable rate-distortion vectors. Finally, we pose a multilevel diversity source coding problem for further study.

Upper bounds on the redundancy of Huffman codes have been extensively studied in the literature. Almost all of these bounds are in terms of the probability of either the most likely or the least likely source symbol. We prove a simple upper bound in terms of the probability of any source symbol.

We take the point of view that a Markov random field is a collection of so-called full conditional mutual independencies. Using the theory of I-measure, we have obtained a number of fundamental characterizations related to conditional mutual independence and Markov random fields. We show that many aspects of conditional mutual independence and Markov random fields have very simple set-theoretic descriptions. New insights into the structure of conditional mutual independence and Markov random fields are obtained. Our results have immediate applications in the implication problem of probabilistic conditional independency and relational database. We obtain a hypergraph characterization of a Markov random field which makes it legitimate to view a Markov random field as a hypergraph. Based on this result, we naturally employ the Graham reduction, a tool from relational database theory, to recognize a Markov forest. This connection between Markov random fields and hypergraph sheds some light on the possible role of hypergraph theory in the study of Markov random fields.

A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. This class of codes is applied to speed up the decoding process, for the decoder can decode from both sides of the compressed file simultaneously. We study some basic properties of fix-free codes. We prove a sufficient and a necessary condition for the existence of fix-free codes, and we obtain some new upper bounds on the redundancy of optimal fix-free codes.

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.

Write-efficient memories (WEMs) were introduced by Ahlswede and Zhang (1989) as a model for storing and updating information on a rewritable medium with cost constraints. We note that the research work of Justesen and Hoholdt (1984) on maxentropic Markov chains actually provide a method for calculating the capacity of WEM. By using this method, we derive a formula for the capacity of WEM with a double-permutation cost matrix. Furthermore, some capacity theorems are established for a special class of WEM called deterministic WEM. We show that the capacity of deterministic WEM is equal to the logarithm of the largest eigenvalue of the corresponding connectivity matrix, it is interesting to note that the deterministic WEM behaves like the discrete noiseless channels of Shannon (1948). By specializing our results, we also obtain some interesting properties for the maximization problem of information functions with multiple variables which are difficult to obtain otherwise. Finally, we present a method for constructing error-correcting codes for WEM with the Hamming distance as the cost function. The covering radius of linear codes plays an important role in the constructions.

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.

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.

Multilevel diversity coding was introduced in recent work by Roche (1992) and Yeung (1995). In a multilevel diversity coding system, an information source is encoded by a number of encoders. There is a set of decoders, partitioned into multiple levels, with each decoder having access to a certain subset of the encoders. The reconstructions of the source by decoders within the same level are identical and are subject to the same distortion criterion. Inspired by applications in computer communication and fault-tolerant data retrieval, we study a multilevel diversity coding problem with three levels for which the connectivity between the encoders and decoders is symmetrical. We obtain a single-letter characterization of the coding rate region and show that coding by superposition is optimal for this problem. Generalizing to a symmetrical problem with an arbitrary number of levels, we derive a tight lower bound on the coding rate sum.

We present a framework for information inequalities, namely, inequalities involving only Shannon's information measures, for discrete random variables. A region in IR(2/sup n/-1), denoted by /spl Gamma/*, is identified to be the origin of all information inequalities involving n random variables in the sense that all such inequalities are partial characterizations of /spl Gamma/*. A product from this framework is a simple calculus for verifying all unconstrained and constrained linear information identities and inequalities which can be proved by conventional techniques. These include all information identities and inequalities of such types in the literature. As a consequence of this work, most identities and inequalities involving a definite number of random variables can now be verified by a software called ITIP which is available on the World Wide Web. Our work suggests the possibility of the existence of information inequalities which cannot be proved by conventional techniques. We also point out the relation between /spl Gamma/* and some important problems in probability theory and information theory.

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.

In a Diversity Coding System, an information source is encoded by a number of encoders. There are a number of decoders, each of which can access a certain subset of the encoders. We study a diversity coding problem in which there are two levels of decoders. The reconstructions of the source by decoders within the same level are identical, and are subject to the same distortion criterion. Our results imply a principle of superposition when the source consists of two independent data streams. Practical codes achieving zero error can easily be constructed for this special case. A class of open problems on this topic is also suggested.>

Let F be the fault of a system which takes value in /spl Omega/={f/sub i/}, and p/sub i/ be the known probability of occurrence of f/sub i/. Let T={t/sub j/} be a sufficient set of tests available for diagnosing the system, and c/sub j/ be the cost of t/sub j/. The number of possible responses for each test in T may be different. The author introduces the cost-entropy function as an information-theoretic lower bound on C/sub min/ the expected cost of an optimal testing tree. The author also obtains a universal upper bound of C/sub min/ when {p/sub i/} is unknown, and a refined upper bound on C/sub min/ when {p/sub i/} is known. The author's results are essential for developing heuristic strategies to search for optimal and suboptimal testing trees.>

The authors examine the behavior of a source subject to flow control by a credit manager. The source receives packets for transmission into a high-speed network according to a renewal process. The credit manager regulates the flow of data into the network by the following method. First, credit is generated at a fixed rate and is allowed to accumulate subject to an upper bound. Second, a packet is allowed to start transmission only if the accumulated credit is at least as large as the service time of the packet. Otherwise, the packet waits until the required amount of credit has been accumulated. Third, the credit bank is depleted at the onset of service by an amount which equals the service time. The main purpose of the credit manager is to smooth out the burstiness of the input process, thereby making it easier for the network to handle large amounts of data without undue delays, congestion, or buffer overflows. Despite the difficulty of this problem, the authors find the distributions of queue length, sojourn time, and interdeparture time by assuming a special structure for the service-time distribution and the credit bank. Numerical examples are included.>

The authors examine the behavior of a source subject to flow control by a credit manager. The source receives packets for transmission into a high speed network according to a renewal process. The credit manager regulates the flow of data into the network by the following method. First, credit is generated at a fixed rate and is allowed to accumulate, subject to an upper bound. Second, a packet is allowed to start transmission only if the accumulated credit is at least and as large as the service time of the packet. Otherwise, the packet waits until the required amount of credit has been accumulated. Third, the credit bank is depleted at the onset of service by an amount which equals the service time. The main purpose of the credit manager is to smooth out the burstiness of the input process, thereby making it easier for the network to handle large amounts of data without undue delays, congestion, or buffer overflows. Despite the difficulty of this problem, the distributions of queue length and sojourn time are found by assuming a special structure for the service time distribution and the credit bank. Numerical examples show that the algorithms can be used to solve practical problems.>

The underlying mathematical structure of Shannon's information measures was studied in a paper by R.W. Yeung (1991), and the I-Measure mu *, which is a signed measure defined on a proper sigma -field F, was introduced. The I-Measure is a natural extension of Shannon's information measures and is uniquely defined by them. They also introduced as a consequence the I-Diagram as a geometric tool for visualizing the relationship among the information measures. In general, an I-Diagram for n random variables must be constructed in n-1 dimensions. It is shown that for any finite collection of random variables forming a Markov chain, mu * assumes a very simple structure which can be illustrated by an I-Diagram in two dimensions, and mu * is a nonnegative measure.>

The author presents a new approach to understanding the underlying mathematical structure of Shannon's information measures, which provides answers to the following two questions for any finite number of random variables. (1) For any information-theoretic identity, is there a corresponding set-theoretic identity via the formal substitution of symbols? (2) For any set-theoretic identity, is there a corresponding information-theoretic identity and, if so, in what sense? The author establishes the analogy between information theory and set theory. Therefore, each information-theoretic operation can formally be viewed as a set-theoretic operation and vice versa. This point of view, which the author believes is of fundamental importance has apparently been overlooked in the past by information theorists. As a consequence the I-diagram, which is a geometrical representation of the relationship among the information measures, is introduced. The I-diagram is analogous to the Venn diagram in set theory. The use of the I-diagram is discussed.>

An alphabetic code for an ordered probability distribution (P/sub k/) is a prefix code in which P/sub k/ is assigned to the kth codeword of the coding tree in left-to-right order. This class of codes is applied to binary test problems. Several earlier results on alphabetic codes are unified and enhanced. The characteristic inequality for alphabetic codes that is analogous to the Kraft inequality for prefix codes is also derived. It is shown that if (P/sub k/) is in ascending or descending order, L/sub min,/ the expected length of an optimal alphabetic code, is the same as that of a Huffman code for the unordered distribution (P/sub k/). An enhancement of Gilbert and Moore's (1959) merging property of all optimal alphabetic code is proved. Two lower bounds and a new upper bound on the expected length of an optimal alphabetic code are also proven, and a simple method is proposed for constructing good alphabetic codes when optimality is critical.>

The concept of local redundancy is introduced, and it is shown that it is a simple but powerful tool for understanding the redundancy of a prefix code. Based on this concept, the redundancy of a prefix code when the structure of the code is partially known is proven. It is shown how this theorem can be used to obtain well-known lower bounds on R/sub Huff/, the redundancy of a Huffman code. The theorem is used to obtain a sequence of new lower bounds on R/sub Huff/ based on the Huffman procedure. A similar sequence of upper bounds on R/sub Huff/ is obtained. New lower and upper bounds on R/sub Huff/ when the two smallest probabilities of the source distribution are known are given as corollaries of these results.>

The problem of finding a binary prefix code of minimum average codeword length for a given finite probability distribution subject to the requirement that each codeword must end with a 1 is considered. Lower and upper bounds to the performance of the optimum code are derived; the lower bound is tight for certain probability distributions. An algorithm that generates an optimum code for any given distribution is described.>

The authors unify earlier investigations concerning the encoding of two correlated sources (X/sub k/), (Y/sub k/) by means of separate encoders. Decoding is done by a single decoder which receives the outputs from both encoders. The reconstruction of (X/sub k/) is required to be perfect in the usual Shannon sense. The authors determine the admissible rate region R (D), where D is the distortion of the reconstruction of (Y/sub k/). The binary Hamming case is investigated explicitly.>

When separate encoders are assigned to each of two correlated sources, it is in general true that the rate sum required is less when decoding is done by a single decoder than when separate decoders are used. However, if either encoder breaks down, system performance ordinarily degrades severely in the single-decoder case when one tries to recover the sources based solely on the output of the remaining encoder. The authors determine the admissible rate region for this situation, which is related to the multiple description problem. Some of the implications of the general result are unintuitive.>