Let $x\in \mathcal{X}$ be a symbol from an input alphabet, let $p(y|x)$ be a conditional probability distribution corresponding to a discrete memoryless channel and let $y\in\mathcal{Y}$ be an output alphabet. Given that the channel has capacity $C$, is it true that one can compress any $n-$bit output to $nC$ bits with error in the compression vanishing as $n\rightarrow\infty$?

The motivation for this comes from the reverse Shannon theorem established in Section IV of https://arxiv.org/pdf/quant-ph/0106052.pdf. To simulate a channel, Alice applies the channel locally and then transfers the output to Bob. She does this in a clever way such that only $2^{nC}$ bits of communication is actually required.

I was wondering if her protocol is equivalent to compressing the channel output and sending it over to Bob.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.