Return to Question

$$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?

$$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?

$$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 $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(I(X;Y)-\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?

$$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?

$$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 $m$ with a random 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(I(X;Y)-\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 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\}$$

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?

$$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 $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(I(X;Y)-\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?