Zero-Error Distributed Compression of Binary Arithmetic Sum
Xuan Guang, Ruze Zhang · IEEE Transactions on Information Theory · 2023
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.