Strong Functional Representation Lemma and Applications to Coding Theorems
Top Cited Papers
Open Access
- 16 August 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (11) , 6967-6978
Abstract
This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem.Keywords
All Related Versions
Funding Information
- Huawei Technologies
This publication has 35 references indexed in Scilit:
- Multiple description coding with many channelsIEEE Transactions on Information Theory, 2003
- The redundancy of source coding with a fidelity criterion. 1. Known statisticsIEEE Transactions on Information Theory, 1997
- Universal Almost Sure Data CompressionThe Annals of Probability, 1990
- New results in binary multiple descriptionsIEEE Transactions on Information Theory, 1987
- The discrete memoryless multiple-access channel with cribbing encodersIEEE Transactions on Information Theory, 1985
- Achievable rates for multiple descriptionsIEEE Transactions on Information Theory, 1982
- A coding theorem for the discrete memoryless broadcast channelIEEE Transactions on Information Theory, 1979
- The rate-distortion function for source coding with side information at the decoderIEEE Transactions on Information Theory, 1976
- Source coding with side information and a converse for degraded broadcast channelsIEEE Transactions on Information Theory, 1975
- Epsilon Entropy and Data CompressionThe Annals of Mathematical Statistics, 1971