Communications in Information and Systems
Volume 16 (2016)
A randomized covering-packing duality between source and channel coding
Pages: 83 – 109
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.