Channel coding theorem

Channel capacity

Motivation

Formally, a channel is defined as a stochastic system which takes an input random variable $X$ and an output random variable $Y$ with a specified conditional probability distribution, $p(Y|X)$. Ideally, in a data transmission or storage systems, channels are noiseless which means that $X$ is completely determined by $Y$, which implies that $H(X|Y)=0$. However, most channels will exhibit some level of randomness and potentially one value $Y=y$ may come from more than one value of $X$. Thus, it is desired that the mutual information between $X$ and $Y$ is maximized.

Example

Consider the following ternary-input ternary-output channel with input and output alphabet ${\mathcal {X}}={\mathcal {Y}}=\{0,1,2\}$ with the following conditional probability $p(Y|X)$:

	$Y=0$	$Y=1$	$Y=2$
$X=0$	0.9	0.1	0
$X=1$	0.1	0.9	0
$X=2$	0	0	1

Here, it is clear that $Y=0$ may have been due to $X=0$ or $X=1$. Although we do not have any control over this channel (we cannnot change $p(Y|X)$), we do have control over $p(X)$, the input distribution. Our goal then is to select an input distribution (transmission strategy) so that the mutual information between the inputs and outputs is maximized. The maximum mutual information obtained in such a manner is defined as the channel capacity. For discrete memoryless channels, we define the channel capacity $C$ as

$C=\max _{p(X)}I(X;Y)$.

In our example, our transmission strategy is to assign probabilities to each input symbol $x\in \{0,1,2\}$ with complete knowledge of the channel $p(Y|X)$. (If we do not know $p(Y|X)$, we need to do some form of channel estimation, which out of our current scope in CoE 161.)

Let us say that this is your first time to do capacity calculations. You see the definition and think that maybe you can guess the right input distribution. After some thought, you came up with three candidate solutions for $p_{X}$:

• Always transmit $X=2$.
• Transmit $X=0$ or $X=1$ with 50-50 probability.
• Transmit all symbols with equal probability, $p(x)=1/3$ for all $x$.

Checkpoint: Without calculating $I(X;Y)$, argue that the first two transmission schemes are obviously suboptimal.

Channel coding

In noisy channels, $H(X|Y)>0$ and so the mutual information $I(X;Y)$ is strictly less than the source entropy$H(X)$. Even if we know the capacity-achieving input distribution, it is always possible to make mistakes if we inspect the channel outputs on a per-symbol basis. In this section, we introduce channel coding and see that by adding redundancy, we can control the probability of error.