Communications in Information and Systems

Volume 16 (2016)

Number 2

A randomized covering-packing duality between source and channel coding

Pages: 83 – 109

DOI: https://dx.doi.org/10.4310/CIS.2016.v16.n2.a1

Authors

Mukul Agarwal (Department of Electrical and Computer Engineering, Boston University, Boston, Massachusetts, U.S.A.)

Sanjoy Mitter (Laboratory for Information and Decision Systems, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Abstract

Let $b$ be a general channel, defined as a sequence of transition probabilities in the sense of Verdu and Han, over which the uniform $X$ source, denoted by $U$, is directly communicated to within distortion level $D$. The source $U$ puts uniform distribution on all sequences with type precisely $p_X$ as compared with the i.i.d. $X$ source which puts ‘most of’ its mass on sequences with type ‘close to’ $p_X$. A randomized covering-packing duality is established between source-coding and channel-coding by considering the source-coding problem (covering problem) of coding the source $U$ to within distortion level $D$ and the channel coding problem (packing problem) of reliable communication over $b$, thus leading to a proof of $C \geq R_U (D)$ where $C$ is the capacity of $b$ and $R_U (D)$ is the rate-distortion function of $U$. This also leads to an operational view of source-channel separation for communication with a fidelity criterion.

Full Text (PDF format)

Published 28 March 2017