Randomized source coding with limited common randomness

摘要

We study a Shannon-theoretic version of the so-called distribution preserving quantization problem. In this problem, a stationary and memoryless source is encoded under a distortion constraint with the additional requirement that the reproduction also be stationary and memoryless with a given law (which may be different from the source distribution). The encoder and decoder are stochastic and assumed to have access to common randomness which is independent of the source. Recent work has obtained the minimum achievable coding rate for a given distortion level under the assumption that unlimited common randomness is available. Here we consider the general case where the available common randomness may be limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. Connections with recent work by Cuff on distributed channel synthesis are also discussed.