Channel coding theorem

From Microlab Classes
Jump to navigation Jump to search

Channel capacity

Motivation

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

Example

Consider the following ternary-input ternary-output channel with input and output alphabet with the following conditional probability :

0.9 0.1 0
0.1 0.9 0
0 0 1

Here, it is clear that may have been due to or . Although we do not have any control over this channel (we cannnot change ), we do have control over , 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 as

.

In our example, our transmission strategy is to assign probabilities to each input symbol with complete knowledge of the channel . (If we do not know , 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 :

  • Always transmit .
  • Transmit or with 50-50 probability.
  • Transmit all symbols with equal probability, for all .

Checkpoint: Without calculating , argue that the first two transmission schemes are suboptimal.

Channel coding

In noisy channels, and so the mutual information is strictly less than the source entropy. 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

Channel coding theorem

The channel capacity is achievable

We cannot do better than the channel capacity

Random coding argument

Some examples