Skip to main content
9 of 13
added 7 characters in body

Backwards random codebook generation

$$X \longrightarrow \fbox{$\phantom{\int}P_{Y|X}\phantom{\int}$}\longrightarrow Y$$

The information capacity of this channel is $\max_{P_X} I(X;Y)$, and it can be achieved by associating each message with a random codeword so that $m \mapsto x^n_m$ for $m=1,\dots,2^{n(I(X;Y)-\varepsilon)},$ with $x^n_i$ i.i.d. $\sim P^\ast_X$ where $P^\ast_X$ is the distribution that maximizes $I(X;Y)$. If you choose your codewords in this way with large enough $n$, then the output distributions they produce on $Y^n$ are nearly always different enough that the codeword $m$ can be distinguished accurately with high probability.

You can imagine choosing a codebook 'backwards' by choosing a collection of achievable output distributions: $$\{P_m\}_m\subset \{P: P = P_{Y^n|X^n}P_{X^n}\text{ for some }P_{X^n}\text{ over }\mathcal{X}^n\}$$

then when $m$ must be sent, input $X^n$ with a distribution such that $Y^n\sim P_m$

What are sufficient conditions on $\{P_m\}_m$ that ensure the decoding error probability $\to 0$ as $n$ grows?