Search

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 a graph set is 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 the cancellative pair of families of subsets. We further extend the problem formulation to a general network called the parallel network, which may consist of more than one channel with multiple inputs and multiple outputs. [ABSTRACT FROM AUTHOR]

Most existing network communication systems, such as the Internet, are built around the TCP/IP protocol stack. However, TCP/IP cannot effectively support the upcoming network communication systems with more wireless communication links and higher requirements in terms of throughput, latency, and reliability. In this article, we introduce a general network communication protocol design based on batched network coding (BNC), which includes the existing framework as a special case and whose design can be guided by channel coding theory. BNC-based protocols can have significant throughput gain for single-hop or multihop wireless communications and provide better trade-off among throughput, latency and reliability. [ABSTRACT FROM AUTHOR]

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

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

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

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any $L\geq 2$ , where $L$ is the number of levels of the coding system. 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 principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for $L=5$. In this paper, for any fixed $L$ , we obtain in closed form a finite set of linear inequalities for characterizing 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 with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding. [ABSTRACT FROM AUTHOR]

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 $\ell $ nodes. An $(n,k,d,\ell)$ 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,\ell)$ , 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 $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

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

Let $X_{i}, i~\in 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 $X_{i}, i~\in 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 $X_{i}, i~\in 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). [ABSTRACT FROM AUTHOR]

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

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

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

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

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

Let \mathcal N=\1,\ldots ,n\ . The entropy function h of a set of n discrete random variables \{X_{i}:i\in \mathcal {N} \} is a 2^{n} -dimensional vector whose entries are \text h( \mathcal A)\triangleq H(X \mathcal A) , \mathcal A\subset \mathcal {N} , the (joint) entropies of the subsets of the set of n random variables with H(X_\emptyset )=0 by convention. The set of all entropy functions for n discrete random variables, denoted by , is called the entropy region for n . Characterization of \Gamma ^*n and its closure \overline {\Gamma ^*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 partition-symmetrical entropy functions. Let p=\ \mathcal N1,\ldots , \mathcal {Nt\} be a t -partition of \mathcal {N} . An entropy function \bf h is called p -symmetrical if for all {\mathcal{ A}},{\mathcal{ B}} \subset {\mathcal{ N}} , \text {h}({\mathcal{ A}}) = \text {h}({\mathcal{ B}}) whenever \mathcal A \cap \mathcal Ni = {\mathcal{ B}} \cap \mathcal Ni , i = 1, \ldots ,t . The set of all the p -symmetrical entropy functions, denoted by \Psi ^{*}_{p} , is called p -symmetrical entropy function region. We prove that \overline \Psi ^*p , the closure of \Psi ^{*}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. [ABSTRACT FROM AUTHOR]

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