A universal, operational theory of multi-user communication with fidelity criteria

Abstract

This thesis has two flavors: 1. A theory of universal multi-user communication with fidelity criteria: We prove the optimality of digital communication for universal multi-user communication with fidelity criteria, both in the point-to-point setting and in the multi-user setting. In other words, we prove a universal source-channel separation theorem for communication with a distortion criterion, both in the point-to-point setting and the multi-user setting. In the multi-user setting, the setting is unicast, that is, the sources which various users want to communicate to each other are independent of each other. The universality is over the medium of communication: we assume that the medium might belong to a family. Both in the point-to-point setting, we assume that codes can be random: the encoder might come from a family of deterministic codes and the decoder has access to the particular realization of the deterministic code, and finally, an average is taken over all these deterministic codes. In Shannon's theory, random-coding is a proof technique. However, in our setting, random codes are essential: universal source-channel separation does not hold if codes are not allowed to be random. This happens because we are asking the universal question. We also show the partial applicability of our results to the traditional wireless telephony problem. 2. An operational theory of communication with a fidelity criterion: We prove the source-channel separation theorem operationally: we rely only on definitions of channel capacity as the maximum rate of reliable communication and the rate-distortion function as the minimum rate needed to compress a source to within a certain distortion level. We do not rely on functional simplifications, for example, mutual information expressions for the proofs. By operational, we do not mean that what we are doing is "practically operational". The view that we have can also be viewed as a layered black-box view: if there is a black-box that is capable of one form of communication, then the black-box can be layered in order to accomplish another form of communication.