## Duality between Source and Channel Coding

(Professor Kannan Ramchandran)
(DARPA) F30602-00-2-0538 and (NSF) CCR-0219722

We explore a mathematical characterization of the functional duality between classical source and channel coding, formulating the precise conditions under which the optimal encoder for one problem is functionally identical to the optimal decoder for the other problem. We then extend this functional duality to the case of coding with side information. We consider several examples which correspond to both discrete-valued and continuous-valued cases to illustrate our formulation.

Classical source coding under a rate-distortion (R-D) constraint and channel coding under a channel cost constraint have long been considered information-theoretic duals (this should not be confused for Lagrangian duality in optimization theory) of each other starting from Shannon's landmark paper in 1959. In the source coding (rate-distortion) problem, the goal is to find, for a given source distribution, the conditional distribution between the input source and the output reconstruction that minimizes the mutual information [1] between the two subjects to a target distortion constraint corresponding to a given distortion metric. In the channel coding (capacity-cost) problem, the goal is to find, for a given channel input-output conditional distribution, the channel input distribution that maximizes the mutual information between input and output subject to a target channel cost (or power) constraint corresponding to a channel cost metric. Cover and Thomas [1] point out that these two problems are information-theoretic duals of each other. This duality has also been exploited in the formulation of numerical optimization algorithms for the channel capacity and rate-distortion problems respectively using the Blahut-Arimoto algorithm. In [1] (see Sec 13.5), a packing versus covering interpretation of duality in Gaussian source and channel coding has been formulated to illustrate this duality. Indeed, some of the solutions to practical source coding (channel coding) have been inspired by solutions to channel coding (source coding): e.g., trellis-coded quantization in source coding has been inspired by trellis-coded modulation in channel coding.

We address the duality between source and channel coding with the objective of providing a mathematical characterization of their functional duality. To be specific, given an optimal source (channel) coding scheme (encoder and decoder), we detail the conditions under which such a scheme is a functional dual to a channel (respectively source) coding scheme (encoder and decoder), in the sense that the optimal encoder mapping for one problem is functionally identical to the optimal decoder mapping for the other problem. We show in the sequel that this functional duality is enabled through appropriate choices of metrics and constraints for the dual source (or channel) coding problem. Our inspiration for this formulation is derived from recent work by Gastpar et al. on the optimality conditions for uncoded communications [2]. We then extend these results to coding with side information and obtain the conditions under which the source and channel coding with side information are exact functional duals.

[1]
T. M. Cover and J. A. Thomas, Elements of Information Theory, New York: John Wiley and Sons, 1991.
[2]
M. Gastpar, B. Rimoldi, and M. Vetterli, "To Code or Not to Code," Proc. IEEE Int. Symp. Information Theory, Sorrento, Italy, June 2000.
1Professor, University of Michigan