# Backwards random codebook generation

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

The information capacity of this channel is $C=\max_{P_X} I(X;Y)$, and it can be achieved by associating each message $m$ with a codeword $x^n_m\in \mathcal{X}^n$ with each codeword component 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, then as long as $n$ is large and the total number of messages $m$ is less than $2^{n(C-\varepsilon)}$, then the distributions the codewords produce on the output alphabet $\mathcal{Y}^n$ are nearly always different enough that the message $m$ can be recovered with high probability from the output $Y^n$.

You can imagine choosing a codebook 'backwards' by choosing a collection of attainable 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\}$$

When $m$ must be sent, input $X^n$ distributed so that the output $Y^n$ is distributed like $P_m$

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

• interesting problem I think.. what is the underlying motivation? – user94040 Dec 20 '16 at 2:26
• It came up when trying to find the information capacity of a situation where one transmitter is broadcasting to a collection of receivers that can't see each other's receptions directly, but can only conference a certain amount of information to all the others. – enthdegree Dec 20 '16 at 21:13
• I think standard the word you want for searching the information theory literature is "broadcast" a certain amount of information to all the others. The issue with the question's wording is that it omits motivating and background information meaning one doesn't know the full context. Other key phrases would be multiuser information theory or network information theory. – kodlu Dec 21 '16 at 4:34
• While I am not an expert in this area, the book by Csizsar and Korner, namely "Information Theory:Discrete Memoryless Channels", 2nd Edition, Cambridge, is a good place to start. In particular, there is a taxonomy of network problems in the beginning of Part III, Multi-terminal systems. – kodlu Dec 21 '16 at 4:39

A sufficient condition for $\{P_1,\dots, P_{M_n}\}\subset \operatorname{Hull}\{P_{Y^n|X^n=x^n}| x^n\in \mathcal{X}^n\}$ to be a working codebook is that it has some $c>0$ where taking $Y_m\sim P_m$ for each $m$, then for any $\ell\!\neq\! m$ we have: $$\mathbb{P}(P_m(Y_m) \leq c\cdot P_{\ell}(Y_m))=\mathcal{o}(1/M_n).$$
Then the following will be a working decoder: "Decide $m$ was sent if $\mathbb{P}(P_m(Y_m)>c\cdot P_{\ell}(Y_m))$ for each $\ell\neq m$." For $c=1$ this is just a maximum likelihood decoder.