Coding teaser: source coding

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

Channel Rates and Improved Channel Model

Let's bring back Bob and Alice into the scene again. If you recall the story of Bob and Alice, bob wants to send a file to Alice but it will take long due to the limited bandwidth of the channel. When we say bandwidth, the channel can only send a maximum amount of bits per second. Let's define $C$ as the maximum channel rate in units of bits/s. Channels have different maximum rates because of their physical limitations and noise. For example, an ethernet bandwidth can achieve a bandwidth of 10 Gbps (gigabits per second), while Wifi can only achieve at a maximum of 6.9 Gbps. It really is slower to communicate wirelessly.

Since most of our communication systems use binary representations, Bob has to convert his data into binary digits before he sends it over the channel. Let's look at a few examples. Suppose our alphabet $S$ has the symbols of all combinations of flipping three fair coins. Then our symbols would be $\{TTT,TTH,THT,THH,HTT,HTH,HHT,HHH\}$. Bob needs to map each symbol into a binary representation such that $\{TTT,TTH,THT,THH,HTT,HTH,HHT,HHH\}\rightarrow \{000,001,010,011,100,101,110,111\}$. This mapping is called an encoding process. Let's add new definitions:

• The binary set $\{0,1\}$ are the code symbols.
• The mapping set $\{TTT,TTH,THT,THH,HTT,HTH,HHT,HHH\}$ are called the codewords. For example, $000$ is the codeword for the symbol $TTT$. $101$ is the codeword for $HTH$.
• We usually tabulate the encoding or mapping. We call this table the codebook. It's a simple look-up-table (LUT).

Source Symbol	Codeword
TTT	000
TTH	001
THT	010
THH	011
HTT	100
HTH	101
HHT	110
HHH	111

Channel Capacity

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