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 so that majority-rule decision will make the right choice.

Channel coding theorem

The channel capacity is achievable

To show that the channel capacity is achievable, we will demonstrate a transmission scheme that is guaranteed to have arbitrarily low error probability for sufficiently large $n$. The transmission scheme was selected primarily as a mathematical tool, and not as a guide for practical systems. The outline of the proof is as follows:

• We describe the transmission scheme which uses the input distribution $p_{X}(X)$ to generate a random codebook.
• We describe a decoding scheme which uses typical sets.
• We show that sufficiently large $n$ can be used to satisfy a desired upper bound in error probability.
• We conclude that $\max _{p(X)}I(X;Y)$ is achievable.

The receiver makes an error only if at least one of the following events occurs:

• The received codeword is not jointly typical with the transmitted codeword.
• Some other transmitted codeword is jointly typical with the received codeword.

By the AEP, the first event has probability at most $\epsilon$.

We cannot do better than the channel capacity

Because of the inherent stochasticity of the channel, each codeword $X^{n}$ gets received as a "diffuse" set of possible sequences $Y^{n}$. If we increase the blocklength, the AEP guarantees that these diffuse sets "harden," i.e., the sets will contain only typical sequences with high probability. This geometric intuition is useful because it makes it easy for us to see why we cannot use every codeword from ${\mathcal {X}}^{n}$: if we use slightly similar sequences $x_{1}^{n}$ and $x_{2}^{n}$, then the typical sets at the receiver may overlap and error-free decoding is not possible. Thus, if we can somehow collect codewords $X^{n}$ that are sufficiently different, then their output typical sets will not overlap with very high probability.

How many typical sets can we "pack" inside ${\mathcal {Y}}^{n}$? First, we observe that there are only $2^{nH(Y)}$ typical $n$-sequences in the output alphabet. Second, for a randomly chosen codeword $X^{n}$, there are $2^{nH(Y|X)}$ possible received sequences. The maximum number of codewords that we can use from $X^{n}$ is given by

${\frac {2^{nH(Y)}}{2^{nH(Y|X)}}}=2^{n(H(Y)-H(Y|X))}=2^{nI(X;Y)}$.

The best we can do for error-free transmission is to transmit $nI(X;Y)$ information bits over $n$ channel uses. Going beyond this limit will force the codeword "spheres" in $Y^{n}$ to overlap and thus result in an error probability that is bounded away from zero. This is true for any choice of $p(X)$, thus we have the following upper bound on the maximum rate

$R\leq \max _{p(X)}I(X;Y)$.

Together with the achievability bound, we can now say that for sufficiently large n, the maximum rate for error-free transmission over a channel $p(Y|X)$ is $\max _{p(X)}I(X;Y)$.