Zero-Error Capacity Regions of Noisy Networks
Qi Cao, Raymond W. Yeung · IEEE Transactions on Information Theory · 2022
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.