$$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)$. Any rate $C-\varepsilon$ can be achieved by fixing a large-enough blocklength $n$ and associating each message $m\in \{1,\dots,2^{n(C-\varepsilon)}\}$ with a codeword $x^n_m\in \mathcal{X}^n$, each component of $x^n_m$ i.i.d. $\sim P^\ast_X$ where $P^\ast_X$ is the distribution that maximizes $I(X;Y)$. The distributions these codewords produce on the output alphabet $\mathcal{Y}^n$ are probably different enough from one another that any observed output $Y^n$ is only likely to have come from the true input $m$.

You can imagine choosing a codebook 'backwards' by instead building 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 necessary and sufficient conditions on $\{P_m\}_m$ that ensure decoding error probability $\to 0$ as $n$ grows?

  • $\begingroup$ interesting problem I think.. what is the underlying motivation? $\endgroup$ – user94040 Dec 20 '16 at 2:26
  • $\begingroup$ 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. $\endgroup$ – enthdegree Dec 20 '16 at 21:13
  • $\begingroup$ 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. $\endgroup$ – kodlu Dec 21 '16 at 4:34
  • $\begingroup$ 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. $\endgroup$ – 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.

This is a kind of unsatisfying answer since I am suspicious that you can come up with a channel that has a codebook that can be reliably decoded, but where the decoder has to do something different than this.

  • $\begingroup$ Thinking back I think there's a statement somewhere in John Gray's information theory book that says that no, the best decoder is actually of this form. Maybe this is a tautology in some way I can't see. No peace of mind until I find the reference... $\endgroup$ – enthdegree Jul 9 at 6:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.