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 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.

Example: repetition code

A simple way of error control is to employ repetition. In this scheme, we simply transmit the same symbol multiple times and decode the received sequence by taking the majority vote. For example, if we want to transmit the symbol 'a', we can use the channel 10 times which can possibly result in the sequence 'axaaaasdas', which contains 6 a's, one x, two s's, and one d. The receiver then decides that the transmitted symbol is 'a.'

Is it possible to make mistakes even with repetition? Yes! To see this, let us go back to the binary case and transmit binary symbols over a binary symmetric channel with crossover probability be the number of channel uses, and for simplicity, let us assume that $n$ is odd so that there is no possiblity of a tie in deciding between 0 and 1 as the transmitted symbol. We will make a decision error at the receiver if and only if the channel flips more than $(n-1)/2$ out of $n$ bits. The probability of this event is given by

$P({\hat {X}}\neq X)=\sum _{i={\frac {n+1}{2}}}^{n}\left({\begin{array}{c}n\\i\end{array}}\right)p_{e}^{i}(1-p_{e})^{n-i}$

Fortunately, we do not need to evaluate this to see that the receiver will decode correctly with high probability. By the asymptotic equipartition property, as long as we have sufficiently large $n$, the received sequence will be a typical $n$-sequence. For the BSC, the typical output sequence will consist of roughly $np_{e}$ errors. Since $p_{e}<1/2$, then there are fewer erroneous bits than correct bits for a sufficiently large blocklength.