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. Existing research on network function computation explores two types of problems regarding block-length network codes and variable-length network codes. In this paper, we concentrate on an important class of variable-length network codes, namely uniquely-decodable network codes, whose computing rate is the maximum average expected number of bits transmitted on all edges in the network for computing the target function once with zero error. In the existing papers, lower bounds on the computing capacity of uniquely-decodable network codes have been proposed under certain constraints on either the network topology or the target function. By developing a novel graph coloring approach based on a cut-set strong partition, we obtain a general lower bound on the computing capacity of uniquely-decodable network codes, which is applicable to arbitrary network topologies, arbitrary information sources and arbitrary target functions. Furthermore, we show that this lower bound is a strict improvement over the previous results by applying this lower bound to the problem of computing an arithmetic sum over a diamond network.

In this paper, we consider the problem of zero-error network function computation. In a directed acyclic network, a single sink node requires to compute with zero error a function of source messages generated by multiple source nodes. We are interested in the information-theoretic computing capacity, which is defined as the average number of times that the function can be computed with zero error for one use of the network. The explicit characterization of the computing capacity in general is extremely challenging. The best known upper bound, applicable to arbitrary network topologies and arbitrary target functions, is the one proved by Guang et al. using the cut-set strong partition approach. This bound is tight for all previously considered network function computation problems whose computing capacities are known. In this paper, we focus on the model of computing the binary arithmetic sum over an asymmetric diamond network, which is of great importance to illustrate the combinatorial nature of network function computation problem. We first prove an upper bound of 1 on the computing capacity by using a linear programming approach, which rectifies an invalid upper bound previously proposed in the literature. However, this upper bound does not surpass the best known upper bound for this model, which is also equal to 1. Further, by developing a different graph coloring approach, we obtain an improved upper bound 3–1 0.822). We thus show that the best known upper bound by Guang et al. is not tight for this model. On the other hand, we present an explicit code construction, which implies a lower bound 6 0.815) on the computing capacity. Comparing the improved upper and lower bounds thus obtained, there exists a rough 0.007 gap between them.

In this paper, we put forward a model of zero-error distributed function compression system of two binary memoryless sources$X$and$Y$. In this model, there are two encoders$\mathbf {En1}$and$\mathbf {En2}$and one decoder$\mathbf {De}$, connected by two channels$(\mathbf {En1}, \mathbf {De})$and$(\mathbf {En2}, \mathbf {De})$with the capacity constraints$C_{1}$and$C_{2}$, respectively. The encoder$\mathbf {En1}$can observe$X$or$(X,Y)$and the encoder$\mathbf {En2}$can observe$Y$or$(X,Y)$according to the two switches${\mathbf {s}}_{1}$and${\mathbf {s}}_{2}$open or closed (corresponding to taking values 0 or 1). The decoder$\mathbf {De}$is required to compress the binary arithmetic sum$f(X,Y)=X+Y$with zero error by using the system multiple times. We use$({\mathbf {s}}_{1}{\mathbf {s}}_{2};C_{1}, C_{2}; f)$to denote the model in which it is assumed that$C_{1}\geq C_{2}$by symmetry. The compression capacity for the model is defined as the maximum average number of times that the function$f$can be compressed with zero error for one use of the system, which measures the efficiency of using the system. We fully characterize the compression capacities for all the four cases of the model$({\mathbf {s}}_{1}{\mathbf {s}}_{2};C_{1}, C_{2}; f)$for${\mathbf {s}}_{1}{\mathbf {s}}_{2}=00,01,10,11$. Here, the characterization of the compression capacity for the case$(01;C_{1},C_{2};f)$with$C_{1}>C_{2}$is highly nontrivial, where a novel graph coloring approach is developed. Furthermore, we apply the compression capacity for$(01;C_{1},C_{2};f)$to an open problem in network function computation that whether the best known upper bound of Guang et al. on computing capacity is in general tight. Up to now, we are not aware of any example for which this upper bound is not tight. By considering a network function computation model transformed from$(01;C_{1},C_{2};f)$with$C_{1}>C_{2}$, we give the answer that in general the upper bound of Guang et al. is not tight.

In this paper, we put forward the model of zero-error distributed function compression system of two binary memoryless sources X and Y as depicted in Fig. 1. In the model, there are two encoders En1 and En2 and one decoder De, connected by two channels with capacity constraints C1and C2, respectively. The encoder En1 can observe X or (X, Y), and the encoder En2 can observe Y or (X, Y). Here, we use two switches s1and s2open or closed (taking values 0 or 1) to represent whether En1 can observe Y and En2 can observe X, respectively. The decoder De is required to compress the binary arithmetic sum f(X, Y) = X + Y with zero error by using the system multiple times. We use (s1s2; C1, C2; f) to denote the model. The compression capacity is defined as the maximum average number of times that the function f can be compressed with zero error for one use of the system, which measures the efficiency for using the system. In the paper, the compression capacities for all the four models are fully characterized. Amongst them, the characterization of the compression capacity for (01; C1, C2; f) is very difficult. Toward this end, we develop a novel graph coloring approach in the converse part and the proof is highly nontrivial. Furthermore, we apply the compression capacity for (01; C1, C2; f) to the open problem in network function computation that whether the best known upper bound by Guang et al. on computing capacity is in general tight. This upper bound is always tight for all previously considered network function computation problems whose computing capacities are known. By considering equivalent network function computation models of (01; C1, C2; f), we give the answer that in general the upper bound of Guang et al. is not tight.