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

Complete Channel Model

Previously, we showed a simple channel model that consists of the source, channel, and receiver. In modern communication systems, we add an encoder after the source and a decoder before the receiver. Figure 1 shows the complete channel model. The encoder is used to transform the source symbols into a code that suitable for the channel. The receiver decodes the received message coming out of the channel.

Figure 1: Complete channel model with the encoder added after the source and the decoder added before the receiver.

Let's bring back Bob and Alice into the scene again. This time let's use the complete channel model. Since most of our communication systems use binary representations, Bob needs to encode his data into binary digits before he sends it over the channel.

Let's look at a few examples. Suppose our source 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 is the encoding process. Let's add new definitions:

• The binary set $\{0,1\}$ are the code symbols.
• The encoded patterns $\{000,001,010,011,100,101,110,111\}$ are called the codewords. For example, $000$ is the codeword for the symbol $TTT$. $101$ is the codeword for $HTH$. In practice, we let some random variable $X$ have codewords as outcomes $\{x_{1},x_{2},x_{3},...,x_{n}\}$ associated with probabilities $\{P(x_{1}),P(x_{2}),P(x_{3}),...,P(x_{n})\}$. For example, $x_{1}=000$ is the codeword for $TTT$. Moreover, from our example, the source symbols are equiprobable and we have a direct mapping from source symbol to codeword (i.e., $s_{i}\rightarrow x_{i}$ ) then it follows that the codewords are equiprobable too: $P(x_{1})=P(x_{2})=P(x_{3})=P(x_{4})=P(x_{5})=P(x_{6})=P(x_{7})=P(x_{8})={\frac {1}{8}}$. The probability distribution of $X$ can change depending on the encoding scheme.
• We usually tabulate the encoding or mapping. We call this table the codebook. It's a simple look-up-table (LUT). Let's call the table below as codebook-1.

Codebook-1

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

The encoder looks at this table and encodes message before it gets into the channel. For example, suppose we want to send the message $TTTHHHTHTHTH$. The encoder uses codebook-1 to translate the source message into an encoded message: $000111010101$. Receivers should also know the same codebook-1 so that they can decode the message. For example, if the encoded message is $101011001110$, then we can decode the message as $HTHTHHTTHHHT$. Choosing the encoding where the $T\rightarrow 0$ and $H\rightarrow 1$ is simple. This encoding is arbitrary and it seems convenient for our needs. However, nothing stops us from encoding the source symbols with a different representation. For example, we can choose an encoding where $T\rightarrow 1$ and $H\rightarrow 0$. We can go for more complex ones like codebook-2 as shown below:

Codebook-2

Source Symbol	Codeword
TTT	01
TTH	001
THT	0001
THH	00001
HTT	000001
HTH	0000001
HHT	00000001
HHH	000000001

Where a source message $TTTHHHTHTHTH$ translates into $0100000000100010000001$. Codebook-2 can also decode an encoded message. For example, when we receive $00000010000100100000001$ we get $HTHTHHTTHHHT$. The choice of the encoding process is purely arbitrary. The question you might ask, is the coding scheme efficient?. One metric is the average code length defined as:

$L(X)=\sum _{i=1}^{n}P(x_{i})l_{i}$

Equation 1

Where $l_{i}$ is the code length of the codeword $x_{i}$. For example, the average code length of codebook-1 is:

$L(X)=8\cdot {\frac {1}{8}}\cdot 3=3$

The average code length of codebook-2 is:

$L(X)={\frac {1}{8}}\cdot 2+{\frac {1}{8}}\cdot 3+{\frac {1}{8}}\cdot 4+{\frac {1}{8}}\cdot 5+{\frac {1}{8}}\cdot 6+{\frac {1}{8}}\cdot 7+{\frac {1}{8}}\cdot 8+{\frac {1}{8}}\cdot 9=5.5$

$L(X)=8\cdot {\frac {1}{8}}\cdot 3=3$

The average code length of codebook-2 is:

$L(X)={\frac {1}{8}}\cdot 2+{\frac {1}{8}}\cdot 3+{\frac {1}{8}}\cdot 4+{\frac {1}{8}}\cdot 5+{\frac {1}{8}}\cdot 6+{\frac {1}{8}}\cdot 7+{\frac {1}{8}}\cdot 8+{\frac {1}{8}}\cdot 9=5.5$

Clearly, codebook-1 has a shorter code length than codebook-2. Let's introduce another metric called the coding efficiency. Coding efficiency is defined as:

$\eta ={\frac {H(S)}{L(X)}}$

Equation 2

Where $H(S)$ is the source entropy. The coding efficiency $\eta$ has a range of $0\leq \eta \leq 1$. If you recall our "go-to" interpretation of entropy, given some entropy $H(S)$ means we can represent $m=2^{H(S)}$ outcomes. Essentially, $H(S)$ is the minimum number of bits we can use to represent all outcomes of a source regardless of its distribution. Of course, a smaller coding length is desirable if we want to compress representations. For our simple coin flip example, $H(S)=3$. The efficiency of codebook-1 is $\eta ={\frac {3}{3}}=1$. Codebook-1 is said to be maximally efficient because it matches the minimum number of bits to represent the source symbols. The efficiency of codebook-2 is $\eta ={\frac {3}{5.5}}=0.5455$.

$L(X)$ should never be lower than $H(S)$. Otherwise, that doesn't make sense. How can you represent a data set that has $H(S)=3$ with $L(X)=2$? Something's wrong with your codebook if this happens.

Channel Rates and Channel Capacity

Let's bring back Bob and Alice into the scene again. When Bob sends his file to Alice, it takes a while before she gets the entire message because the channel has limited bandwidth. Bandwidth is the data rate that the channel supports. Let's define $C$ as the maximum channel capacity in units of bits per second (bits/s). We'll provide a quantitative approach later. Channels have different 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 is slower to communicate wirelessly. It is possible to transmit data to the channel at a much slower rate such that we are not utilizing the full capacity of the channel. We'd like to encode our source symbols into codewords that utilizes the full capacity of a channel. Shannon's source coding theorem says:

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

Take note that, $\epsilon$ in Shannon's statement is not the noise probability that we know. It's just a term that is used to indicate a small margin of error. In a nutshell, Shannon's source coding theorem says that we can calculate a maximum symbol rate (symbols/s) that utilizes the maximum channel rate $C$ while knowing the source entropy $H(S)$. Then, knowing this maximum symbol rate, we can find an encoding scheme that can get us close to this ideal rate. The maximum symbol rate is given by:

$R_{\textrm {max}}={\frac {C}{H(S)}}$

Equation 3

Let's look at a few examples to appreciate this.

Channel Rate Example 1: Three Coin Flips

Let's re-use the three coin flips example again. Suppose we want to send the three coin flip symbols over some channel that has a channel capacity $C=3$ bits/s (let's just say this is a given). We also know (from the above example) that we need a minimum of $H(S)=3$ bits per symbol to represent each outcome. This translates to:

$R_{\textrm {max}}={\frac {3\ {\textrm {bits/s}}}{3\ {\textrm {bits/symbols}}}}=1\ {\textrm {symbols/s}}$

If we are to utilize the maximum capacity of the channel, we need to encode the source symbols $\{TTT,TTH,THT,THH,HTT,HTH,HHT,HHH\}$ to its binary representation such that each binary digit in each codeword $x_{i}$ provides 1 bit of information . Luckily, codebook-1 does this because we have a coding efficiency of $\eta =1$. This result means that every binary digit of the codeword provides at least 1-bit of information. We are maximally efficient with this encoding. If you think about it, if we send 1 symbol/s to the channel and our encoding has 1 symbol (e.g., TTT) is 3 bits long then essentially we are able to send 3 bits/s to the channel. Since $C=3$ bits/s, then we are utilizing the entire maximum channel capacity.

From the above example, can we actually go beyond $R_{\textrm {max}}={\frac {C}{H(S)}}$ symbols/s? NO. Shannon explicitly said that "It is not possible to transmit at an average rate greater than $C/H$." This is the maximum symbol rate already.

Channel Rate Example 2: A 6-sided Die

This time, suppose we want to send the symbols of a fair 6-sided die on a channel that only has $C=1$ bits/s (this is a separate given). Such that $S$ has outcomes $\{1,2,3,4,5,6\}$. Of course, all outcomes are equiprobable with $P(s_{i})={\frac {1}{6}}$. From here, we can determined $H(S)=\log _{2}(6)=2.58$ bits/symbol. Therefore:

$R_{\textrm {max}}={\frac {1\ {\textrm {bits/s}}}{2.58\ {\textrm {bits/symbols}}}}=0.387$ symbols/s

Again, Shannon says that with a given $C$ and $H(S)$ we can only transmit at a maximum symbol rate of $R_{\textrm {max}}$ symbols/s. Now, let's think of an encoding scheme that suits our needs. For convenience, to represent 6 unique outcomes, we can use 3 bits to represent each outcome. Let's say we have codebook-3:

Codebook-3

Source Symbol	Codeword
1	000
2	001
3	010
4	011
5	100
6	101

The coding efficiency of codebook-3 used for the 6-die example is:

$\eta ={\frac {H(S)}{L(X)}}={\frac {2.58}{3}}=0.86$

Codebook-3 is not that efficient but it will suffice for now. Here, let's introduce the effective symbol rate $R_{X}$ due to the new encoding:

$R_{X}={\frac {\eta C}{H(S)}}$

Equation 4

Our encoding scheme affects how much data we're putting into the channel. If our coding efficiency isn't optimal $\eta \neq 1$ then we are only utilizing a fraction of the maximum capacity $C$. Hence we have the effective channel transmission rate $\eta C$ incorporated into our effective symbol rate $R_{X}$. Calculating $R_{X}$ for codebook-3 would give:

$R_{X}={\frac {0.86\cdot 1}{2.58}}=0.333$ symbols/s.

Observe that $R_{X}=0.333<R_{\textrm {max}}=0.387$. We are not even close to the maximum rate. Can we find a better encoding? How about this, suppose we create a composite symbol that consists of the three 6-sided die symbols. For example, we can let $111$ be one symbol, or we can let $555$ be another symbol. If we do so, then we have around $6\times 6\times 6=216$ unique possible outcomes for the new set of symbols. To represent 216 outcomes we need a minimum of 8 bits of code length (because $2^{8}=256$). So we can have codebook-4 as:

Codebook-4

Source Symbol	Codeword
111	0000_0000
112	0000_0001
113	0000_0010
...	...
665	1101_0110
666	1101_0111

The underscores are just there to separate the 4 bits for clarity. Codebook-4 looks really long but in practice, it's still small. So what changes? Since we have 8 bits per 3 symbols, the effective code length per symbol is $L(X)={\frac {8}{3}}$. Take note that all outcomes are equiprobable so dividing the 8 bits by 3 symbols is enough. This results in a coding efficiency of:

$\eta ={\frac {H(S)}{L(X)}}={\frac {2.58}{2.66}}=0.97$

Cool! We're much closer to being maximally efficient. Now, let's compute the new $R_{X}$ for codebook-4:

$R_{X}={\frac {\eta C}{H(S)}}={\frac {0.97}{2.58}}=0.376$ symbols/s.

Superb! The new $R_{X}=0.376$ is close to the maximum rate of $R_{\textrm {max}}=0.387$. The key trick was to create a composite symbols that consists of 3 of the original source symbols, then represent them with 8 binary digits of codewords.

In all of the discussions, we've only used different measures of information and channel rates. None of the discussions talked about a methodology of finding the best encoding scheme. This is because information theory does not tell us how to find the best encoder. It's just a measure. Keep that in mind!

Maximum Channel Capacity

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

This time, let's study how we can quantitatively determine the maximum channel capacity. In the last module, 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. $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 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$ while parametrizing the noise probability $\epsilon$. Figure 2 shows this plot. We can visualize $I(R,S)$ like a pipe while the noise parameter $\epsilon$ limits the flow of information. Figure 3 GIF shows the pipe visualization.

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

In communication theory, $I(R,S)$ is a metric for transmission rate. So the units are in bits/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. We can define the maximum channel capacity $C$ as:

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

Equation 5

We can re-write this as:

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

Equation 5

Here, $C$ is in units of bits/s. 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 the 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 2, when $\epsilon =0$ (or $\epsilon =1$) we can get a maximum $I(R,S)=1$ bits/s provided that the probability distribution of the symbols that get into the channel is $p=0.5$. When $\epsilon =0.25$ (or $\epsilon =0.75$) we can also get a maximum $I(R,S)=0.189$ bits/s when $p=0.5$. Let's determine $C$ of a BSC given some $p$ and $\epsilon$. Since we know $H(R)$ follows the Bernoulli entropy $H_{b}(q)$ where $q=p+\epsilon -2\epsilon p$. Then we can 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 a channel, we can manipulate the input probability $p$ of the source symbols that get into the channel such that we can force $q=0.5$ and achieve the maximum $H(R)$.

$p={\frac {0.5-\epsilon }{1-2\epsilon }}$

Interestingly, to achieve $q=0.5$ we simply need to set $p=0.5$ for any $\epsilon \neq 0.5$. The exception is when $\epsilon =0.5$ because that results in an absolute $I(R,S)=0$ and $p$ will be undefined (i.e., ${\frac {0}{0}}$). This result shows that for any $\epsilon \neq 0.5$ we can achieve maximum entropy for that given channel as long as we encode our source symbols to have $p=0.5$ before it gets into the channel! We can continue our derivation by writing $C$ as:

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

Leading to:

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

Equation 6

In equation 6, we can assume $\max(H_{b}(q))=1$ because we know we can achieve maximum entropy when we set $q=p=0.5$. Equation 6 shows how the maximum capacity is limited by the noise $\epsilon$. It describes the pipe visualization in figure 3. When $\epsilon =0$, $H_{b}(\epsilon )=0$ and our BSC has $C=1.0$ bits/s. When $\epsilon =0.5$, $H_{b}(\epsilon )=1$, the noise entropy is at maximum and our channel has $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 having $C=1$ bits/s.

The most important concept in determining maximum channel capacity is to use equation 5 for any channel model. Moreover, from our simple BSC derivation, we can see that in order to maximize the effective channel capacity, we need to encode our source symbols into codewords such that $p\rightarrow 0.5$ before it gets sent over the channel. This is the essence of the concept source coding where we encode the source to achieve maximum entropy. This is related to equation 4 where $\eta C$ tells us the effective channel rate assuming we have not encoded our source symbols to achieve $p=0.5$. If we have successfully achieved $p=0.5$ for the encoded codewords, then on average we utilize the maximum capacity $C$ (i.e., $\eta =1$).

Don't get mad, but despite having rigorous discussions about channels and noise, data compression assumes a noiseless channel. Phew! So much for going through the hard efforts.

Huffman Coding

The first two examples of encoding looked into source symbols that are equiprobable. First, we've shown that if $H(S)=L(X)\rightarrow \eta =1$, we can fully utilize the channel capacity. We've seen this in our three flips of a fair coin example. When $H(S)<L(X)\rightarrow 0<\eta <1$, we had to duplicate the source symbols to so that the effective code efficiency $\eta \approx 1$ and we can get closer to fully utilizing the channel. We're seeing a pattern that the closer our coding efficiency is to 1, we get closer to maximizing the channel capacity. However, what happens when the source symbols are not equiprobable?

Let's say we want to communicate the sum of two fair 6-sided die rolls. Our source alphabet $S$ contains symbols $\{2,3,4,5,6,7,8,9,10,11,12\}$. The source probability distribution is shown in the table below:

Source Symbol	Frequency	Probability
2	1	${\frac {1}{36}}$
3	2	${\frac {1}{18}}$
4	3	${\frac {1}{12}}$
5	4	${\frac {1}{9}}$
6	5	${\frac {5}{36}}$
7	6	${\frac {1}{6}}$
8	5	${\frac {5}{36}}$
9	4	${\frac {1}{9}}$
10	3	${\frac {1}{12}}$
11	2	${\frac {1}{18}}$
12	1	${\frac {1}{36}}$

What would be the best encoding for this source? The source entropy $H(S)=3.27$ bits. Let's say codebook-5 is a simple binary representation. Since there are $n=11$ outcomes, then using 4 bits for each codeword will suffice. Codebook-5 is shown below:

Codebook-5

Source Symbol	Codeword
2	0000
3	0001
4	0010
5	0011
6	0100
7	0101
8	0110
9	0111
10	1000
11	1001
12	1010

Codebook-5 has $L(X)=4$ and therefore the coding efficiency $\eta ={\frac {H(S)}{L(X)}}=0.8175$. Clearly this won't maximize the channel. Oh no! What should we do then? This is where we introduce one of the well-known compression methods: The Huffman Coding.

The Huffman coding is a lossless compression. The encoding has this interesting property where frequent symbols map to short codewords, while rare symbols map to long codewords. In fact, Huffman codes says that we can have an average code length of $L(X)$ that's within a unit of $H(X)$ then that means we'll have $\eta \approx 1$.

Huffman Coding Example 1

Let's consider another example before we show you the magic of the Huffman coding on our two-die roll scenario. Suppose we have a source alphabet $S$ with outcomes $\{a,b,c,d,e\}$ and probability distribution:

Source Symbol	Probability
a	0.05
b	0.25
c	0.37
d	0.22
e	0.11

Huffman coding has the following steps:

1. Arrange all symbols in ascending order of their probability (or frequency). Let each symbol be a single leaf node.

2. Consider the bottom two nodes.

• Combine these two nodes to form a composite node.
• The probability of the composite node is the sum of its components.
• Make sure that the lower probability component is on the left of the composite node, while the higher probability component is on the right.
• If the components have the same probability, you can select either to be on the left or right.

3. Repeat step 1 and 2 with the new composite node as part of the list. Do this until we are left with 1 node.

• When you reach step 2 and a composite node has the same probability with another node (probably a composite node too), the node with the longer path takes the left side.

4. Write the Huffman codes starting from the top of the tree down to the root of the symbol.

• The top is the MSB (most-significant bit)
• The root of the tree are the LSB (least-significant bit)

Figure 4 shows a step-by-step process of reconstructing the tree of our example.

Figure 4: Huffman coding step-by-step process for example 1.

Just to explicitly explain the Huffman coding process:

1. We re-arranged elements $\{a,b,c,d,e\}$ to $\{a,e,d,b,c\}$ in ascending order of probabilities.

2. We combined the lowest two ($a$ and $e$) to form the composite node $ae$ whose probability is $P(ae)=P(a)+P(e)=0.16$. We don't need to re-arrange because the elements are still in ascending order even with the composite node $ae$.

3. We combined $ae$ with $d$ to get composite node $aed$ with $P(aed)=P(ae)+P(d)=0.38$. We need to re-arrange the nodes in ascending order.

4. We combined $b$ and $c$ to get composite node $bc$ with $P(bc)=P(b)+P(c)=0.62$. We need to re-arrange the nodes in ascending order.

5. We reached the last tree so we just combined the composite nodes $aed$ and $bc$. We should get $P(aedbc)=P(aed)+P(bc)=1.00$ if we did the Huffman code correctly. All left arrows are tagged with 0s while all right arrows are tagged with 1s. We can get the Huffman codes for all symbols from this tree. You can actually swap the directions for 1s and 0s, but for our example, all left arrows use 0s while all right arrows use 1s.

The top of the tree will be the MSB (left-most bit) while the bottom of the tree will be the LSB (right-most bit). For example, to get the Huffman code for $a$ we have (from the top of the tree) $0\rightarrow 0\rightarrow 0=000$. To get $d$ we have $0\rightarrow 1=01$. Simple right? We can generate a new codebook for our example.

Codebook for Huffman coding example 1

Source Symbol	Codeword
a	000
b	10
c	11
d	01
e	001

The cool part about Huffman coding is that codewords are uniquely decodable. This means that for every codeword, we can immediately tell the symbol it's pertaining to. We'll get back to this in the next module. For example, if the we received an encoded message $110010100101000001100111$ we can decode it as $cededaebdc$. We can calculate the average code length for this one. Recall that:

$L(X)=P(x_{i})l_{i}$

Therefore, we have:

$L(X)=(0.05)(3)+(0.25)(2)+(0.37)(2)+(0.22)(2)+(0.11)(3)=2.16$

If we send these encoded symbols across a channel according to the probability distribution of each symbol, we would have $L(X)=2.16$ on average. The entropy $H(S)$ is:

$H(S)=-0.05\log _{2}(0.05)-0.25\log _{2}(0.25)-0.37\log _{2}(0.37)-0.22\log _{2}(0.22)-0.11\log _{2}(0.11)\approx 2.078$ bits

Therefore the coding efficiency for this example would be $\eta ={\frac {H(S)}{L(X)}}={\frac {2.078}{2.16}}=0.96$ which is really close to being maximally efficient. Cool right? If we just represent each outcome with 3 binary digits (because there are 5 outcomes so we need $m=2^{3}=8$), then $L(X)=3$ and the coding efficiency for a straight-forward binary coding would be $\eta ={\frac {H(S)}{L(X)}}={\frac {2.078}{3}}=0.69$. Huffman coding rules!

Huffman Coding Example 2

Just to make sure you have sufficient practice, let's try a different probability distribution for the same symbols:

Source Symbol	Probability
a	0.1
b	0.3
c	0.4
d	0.1
e	0.1

Figure 5 shows the Huffman coding process and steps.

Figure 5: Huffman coding for example 2.

1. We still re-arrange the symbols according to probability. In case the probabilities are the same, we can re-arrange them in any other way. However, sometimes it's more convenient to re-arrange them in alphabetical order of the symbol names. Or sometimes the symbol indices. It's entirely up to you.

2. Combine the lowest two: $e$ and $d$ to get $ed$ with $P(ed)=P(e)+P(d)=0.2$. Then re-arrange.

3. Combine the lowest two: $a$ and $ed$ to get $aed$ with $P(aed)=P(a)+P(ed)=0.3$. If a composite node has the same probability with other composite or base nodes, make sure the composite node with the highest depth stays on the left.

4. Combine $aed$ with $b$ to get $aedb$ with $P(aedb)=P(aed)+P(b)=0.6$. Re-arrange for the last node.

5. Last node should add up to 1. From here we tag all left arrows with 0s and all right arrows with 1s. We can construct our new codebook.

Codebook for Huffman coding example 2

Source Symbol	Codeword
a	100
b	11
c	0
d	1011
e	1010

The codebook for this example gives us an average codelength of:

$L(X)=(0.1)(3)+(0.3)(2)+(0.4)(1)+(0.1)(4)+(0.1)(4)=2.1$

While the source entropy would be:

$H(S)=-0.1\log _{2}(0.1)-0.3\log _{2}(0.3)-0.4\log _{2}(0.4)-0.1\log _{2}(0.1)-0.1\log _{2}(0.1)\approx 2.046$

Resulting in a coding efficiency of:

$\eta ={\frac {H(S)}{L(X)}}={\frac {2.046}{2.10}}=0.97$

Still a much better coding efficiency that using a direct 3-bit binary representation because $\eta ={\frac {H(S)}{L(X)}}={\frac {2.046}{3}}=0.682$.

Huffman Coding Example 3

Going back to our 2-die roll example, we can use Huffman coding to get codebook 6:

Codebook-6

Source Symbol	Codeword
2	00101
3	1000
4	000
5	011
6	110
7	111
8	101
9	010
10	1001
11	0011
12	00100

Codebook-6 is just one table. Sometimes we may swap the direction of arrows. Moreover, sometimes when we end up having components of the same probabilities, we may have swapped them in a different direction. Regardless, the Huffman codes generate a mapping that is uniquely decodable. Codebook-6 has an average code length of $L(X)=3.31$. The two 6-sided die rolls has a source entropy of $H(S)=3.27$ bits/s. Therefore $\eta ={\frac {H(S)}{L(X)}}={\frac {3.27}{3.31}}=0.99$. That is superbly close to a maximal coding efficiency. Lastly, if you observe all the Huffman encoding examples, all frequent symbols have shorter code lengths while all rare symbols have longer codelengths. This is a cool data compression algorithm.

Summary

For this chapter, we summarize our learnings:

• We covered the complete model for a channel while introducing components like encoder and decoder.
• We introduced new definitions: code symbols, codewords, codebooks, coding efficiency, maximum channel capacity, and effective channel rates.
• We had a sneak peak of the source coding theorem.
• We derived a quantitative measure of channel capacity for BSC.
• Lastly, we studied the Huffman coding and appreciated how cool it is.

Have fun doing the lab exercises 😃