Coding teaser: source coding

Channel Capacity

Make sure to read the Wiki page about the basics of a channel. Several discussions and interpretations are important for this chapter 😊.

Figure 1: $I(R,S)$ of a BSC with varying $p$ and parametrizing $\epsilon$.

Previously, we comprehensively investigated the measures of $H(R)$, $H(R|S)$, and $I(R,S)$ on a BSC. Recall that:

$I(R,S)=H(R)-H(R|S)$

If you think about it, $I(R,S)$ is a measure of channel quality. It tells us how much we can estimate the input from an observed output. In English, we said that $I(R,S)$ is a measure of the received information contained in the source information. Ideally if there is no noise, then $H(R|S)=0$ resulting in $I(R,S)=H(S)=H(R)$. We want this because this means all the information from the source gets to the receiver! When noise is present $H(R|S)\neq 0$, it degrades the quality of our $I(R,S)$ and the information about the receiver contained in the source is now being shared with noise. This only means one thing: we want $I(R,S)$ to be at maximum. From the previous discussion, we presented how $I(R,S)$ varies with $p$ and parametrizing the noise probability $\epsilon$. Figure 1 shows this plot (it's the same image from the last discussion). We can visualize $I(R,S)$ like a pipe that constricts the flow of information depending on the noise parameter $\epsilon$. Figure 2 GIF shows the pipe visualization.

Figure 2: Pipe visualization for $I(R,S)$

Let's modify our definition of $I(R,S)$ a bit. In communication theory, $I(R,S)$ is a metric for transmission rate. So the units is really in bits/second. Figure 1 demonstrates how much data can be transmitted per second. Interchanging between bits or bits/second might be confusing but for now, when we talk about channels (and also $I(R,S)$), let's use bits/s. Bits/s is also a measure of bandwidth. From the discussions, it is clear that we can define the maximum channel capacity $C$ as:

$C=\max(I(S,R))$

(1)

We can re-write this as:

$C=\max(H(R)-H(R|S))$

(1)

Here, $C$ is in units of bits/second. It tells us the maximum number of data that we can transmit per unit of time. Both $H(R)$ and $H(R|S)$ are affected by noise parameter $\epsilon$. In a way, noise limits $C$. For example, a certain $\epsilon$ can only provide a certain maximum $I(R,S)$. Looking at figure 1, when $\epsilon =0$ (or $\epsilon =1$) we can get a maximum $I(R,S)=1$ bits/s. When $\epsilon =0.25$ (or $\epsilon =0.75$) we can get a maximum $I(R,S)=0.189$ bits/s. These occur when $p=0.5$. We can prove this mathematically. Let's determine $C$ of a BSC given some $p$ and $\epsilon$.

$C=\max(H(R)-H(R|S))$

Since we know $H(R)$ follows the Bernoulli entropy $H_{b}(q)$ where $q=p+\epsilon -2\epsilon p$. Then we can just write:

$H(R)=H_{b}(q)=-q\log _{2}(q)-(1-q)\log _{2}(1-q)$

$\max(H(R))=1$ bits when $q=0.5$. Since $\epsilon$ is fixed depending on the channel, we can manipulate the input probability $p$ such that we can force $q=0.5$ and achieve the maximum $H(R)$. Hold on to this very important thought. We also know that $H(R|S)=H_{b}(\epsilon )$. Unfortunately, since $\epsilon$ is fixed then we can't immediately assume $H_{b}(\epsilon )=1$ not unless $\epsilon =0.5$. Therefore we can write $C$ as:

$C=\max(H_{b}(q)-H_{b}(\epsilon ))$

Leading to:

$C=1-H_{b}(\epsilon )$

(2)

Equation 2 shows how the maximum capacity is limited by the noise $\epsilon$. It describes the pipe visualization in figure 1. When $\epsilon =0$, $H_{b}(\epsilon )=0$ and our BSC can transmit $C=1.0$ bits/s of data. When $\epsilon =0.5$, $H_{b}(\epsilon )=1$, the noise entropy is at maximum and our channel can transmit $C=0$ bits/s. Clearly, we can't transmit data this way. Lastly, when $\epsilon =1$, then $H_{b}(\epsilon )=0$ again and we're back to transmitting $C=1$ bits/s.

Again, we can assume $\max(H_{b}(q))=1$ because we can transform the input to have a new probability distribution $p$ that maximizes $H_{b}(q)$! If we have the In fact, this is a prelude Shannon's source coding theorem:

"Let a source have entropy $H$ (bits per symbol) and a channel have a capacity $C$ (bits per second). Then it is possible to encode the output of the source in such a way as to transmit at the average rate $C/H-\epsilon$ symbols per second over the channel where $\epsilon$ is arbitrarily small. It is not possible to transmit at an average rate greater than $C/H$."

Note that the above statement only says that we can recode the source into something that can maximize the channel capacity. Also note that the $\epsilon$ is an arbitrary error. Not the noise probability. Figure 1 and our idea