View source for 161-A3.1

* Activity: '''Mutual Information and Channel Capacity'''
* '''Instructions:''' In this activity, you are tasked to 
** Walk through the examples.
** Calculate the channel capacity of different channel models.
* Should you have any questions, clarifications, or issues, please contact your instructor as soon as possible.

== Example 1: Mutual Information ==
Given the following probabilities:

{| class="wikitable" style="text-align: center; width: 45%;"
|+ Table 1: <math>X</math>: Blood Type, <math>Y</math>: Chance for Skin Cancer
|-
! scope="col" | 
! scope="col" | A
! scope="col" | B
! scope="col" | AB
! scope="col" | O
|-
! scope="row" | Very Low
| 1/8
| 1/16
| 1/32
| 1/32
|-
! scope="row" | Low
| 1/16
| 1/8
| 1/32
| 1/32
|-
! scope="row" | Medium
| 1/16
| 1/16
| 1/16
| 1/16
|-
! scope="row" | High
| 1/4
| 0
| 0
| 0
|-
|}

To get the entropies of <math>X</math> and <math>Y</math>, we need to calculate the marginal probabilities:

{{NumBlk|::|<math>P_X = \{\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8}\}</math>|{{EquationRef|1}}}}
{{NumBlk|::|<math>P_Y = \{\tfrac{1}{4}, \tfrac{1}{4}, \tfrac{1}{4}, \tfrac{1}{4}\}</math>|{{EquationRef|2}}}}

And since:

{{NumBlk|::|<math>H\left(A\right)=\sum_{i=1}^n P\left(a_i\right)\cdot\log_2\left(\frac{1}{P\left(a_i\right)}\right)</math>|{{EquationRef|3}}}}

We get: 

{{NumBlk|::|<math>H\left(X\right) = \frac{1}{2}\log_2 2 + \frac{1}{4}\log_2 4 +\frac{1}{8}\log_2 8 +\frac{1}{8}\log_2 8 = \frac{7}{4}\,\mathrm{bits}=1.75\,\mathrm{bits}</math>|{{EquationRef|4}}}}
{{NumBlk|::|<math>H\left(Y\right) = \frac{1}{4}\log_2 4 + \frac{1}{4}\log_2 4 +\frac{1}{4}\log_2 4 +\frac{1}{4}\log_2 4 = 2\,\mathrm{bits}</math>|{{EquationRef|5}}}}

Calculating the conditional entropies using:

{{NumBlk|::|<math> H\left(X\mid Y\right)
=\sum_{i=1}^4 \sum_{j=1}^4 P\left(x_i, y_j\right)\cdot\log_2\left(\frac{P\left(y_j\right)}{P\left(x_i, y_j\right)}\right)=\frac{11}{8}\,\mathrm{bits}=1.375\,\mathrm{bits}</math>|{{EquationRef|6}}}}

{{NumBlk|::|<math> H\left(Y\mid X\right)
=\sum_{i=1}^4 \sum_{j=1}^4 P\left(x_i, y_j\right)\cdot\log_2\left(\frac{P\left(x_i\right)}{P\left(x_i, y_j\right)}\right)=\frac{13}{8}\,\mathrm{bits}=1.625\,\mathrm{bits}</math>|{{EquationRef|7}}}}

Note that <math>H\left(X\mid Y\right)\ne H\left(Y\mid X\right)</math>. Calculating the mutual information, we get:

{{NumBlk|::|<math>I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)=\frac{7}{4}-\frac{11}{8}=0.375\,\mathrm{bits}</math>|{{EquationRef|8}}}}

Or equivalently:

{{NumBlk|::|<math>I\left(X;Y\right)=H\left(Y\right)-H\left(Y\mid X\right)=2-\frac{13}{8}=0.375\,\mathrm{bits}</math>|{{EquationRef|9}}}}

Let us try to understand what this means:
* If we only consider <math>X</math>, we have the ''a priori'' probabilities, <math>P_X</math> for each blood type, and we can calculate the entropy, <math>H\left(X\right)</math>, i.e. the expected value of the information we get when we observe the results of the blood test.
* Will our expectations change if we do not have access to the blood test, but instead, we get to access (1) the person's susceptibility to skin cancer, and (2) the joint probabilities in Table 1? Since we are given more information, we expect one of the following:
** The uncertainty to be equal to the original uncertainty if <math>X</math> and <math>Y</math> are independent, since <math>H\left(X\mid Y\right)=H\left(X\right)</math>, thus <math>I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)=0</math>.
** A reduction in the uncertainty equal to <math>I\left(X;Y\right)</math>, due to the additional information given by <math>P\left(x_i, y_j\right)</math>.
** If <math>X</math> and <math>Y</math> are perfectly correlated, we reduce the uncertainty to zero since <math>H\left(X\mid Y\right) =H\left(X\mid X\right) = 0</math> and <math>I\left(X;Y\right)=H\left(X\right)</math>. 

== Example 2: A Noiseless Binary Channel ==
Consider transmitting information over a noiseless binary channel shown in Fig. 1. The input, <math>A=\{0, 1\}</math> has ''a priori'' probabilities <math>P\left(A=0\right)=\alpha</math> and <math>P\left(A=1\right)=1-\alpha</math>, and the output is <math>B=\{0,1\}</math>. Calculating the output probabilities:

{{NumBlk|::|<math>\begin{align}
P\left(B=0\right) 
& = P\left(B=0\mid A=0\right) \cdot P\left(A=0\right) + P\left(B=0\mid A=1\right) \cdot P\left(A=1\right) \\
& = 1 \cdot \alpha + 0 \cdot \left(1-\alpha\right) \\
& = \alpha \\
\end{align}</math>|{{EquationRef|10}}}}

{{NumBlk|::|<math>\begin{align}
P\left(B=1\right) 
& = P\left(B=1\mid A=0\right) \cdot P\left(A=0\right) + P\left(B=1\mid A=1\right) \cdot P\left(A=1\right) \\
& = 0 \cdot \alpha + 1 \cdot \left(1-\alpha\right) \\
& = 1-\alpha \\
\end{align}</math>|{{EquationRef|11}}}}

Thus, the entropy at the output is:

{{NumBlk|::|<math>H\left(B\right)=\alpha\log_2\frac{1}{\alpha} + \left(1-\alpha\right)\log_2\frac{1}{1-\alpha}=H\left(A\right)</math>|{{EquationRef|12}}}}

The conditional entropy, <math>H\left(B\mid A\right)</math> is then:

{{NumBlk|::|<math>\begin{align} H\left(B\mid A\right) = &\,\, \sum_{i=1}^n P\left(a_i\right) \sum_{j=1}^m P\left(b_j\mid a_i\right)\cdot\log_2\left(\frac{1}{P\left(b_j\mid a_i\right)}\right)\\
= &\,\, P\left(A=0\right)\cdot P\left(B=0\mid A=0\right)\cdot \log_2\frac{1}{P\left(B=0\mid A=0\right)} \\
& + P\left(A=0\right)\cdot P\left(B=1\mid A=0\right)\cdot \log_2\frac{1}{P\left(B=1\mid A=0\right)} \\
& + P\left(A=1\right)\cdot P\left(B=0\mid A=1\right)\cdot \log_2\frac{1}{P\left(B=0\mid A=1\right)} \\
& + P\left(A=1\right)\cdot P\left(B=1\mid A=1\right)\cdot \log_2\frac{1}{P\left(B=1\mid A=1\right)} \\
= &\,\, \alpha \cdot 1\cdot \log_2 1 \\
& + \alpha\cdot 0\cdot \log_2\frac{1}{0} \\
& + \left(1-\alpha\right)\cdot 0\cdot \log_2\frac{1}{0} \\
& + \left(1-\alpha\right)\cdot 1\cdot \log_2 1 \\
= &\,\, 0 \\
\end{align}</math>|{{EquationRef|13}}}}

Which is expected since <math>A</math> and <math>B</math> are perfectly correlated, and there is no uncertainty in <math>B</math> once <math>A</math> is given. Thus, the mutual information is:

{{NumBlk|::|<math>\begin{align}
I\left(A;B\right) & =H\left(B\right)-H\left(B\mid A\right) = H\left(B\right) \\
& = \alpha\log_2\frac{1}{\alpha} + \left(1-\alpha\right)\log_2\frac{1}{1-\alpha} \\
\end{align}</math>|{{EquationRef|14}}}}

To get the channel capacity, we get the maximum <math>I\left(A;B\right)</math> over all <math>\alpha</math>. Thus, we can take the derivative of the mutual information and set it equal to zero, to find the optimal <math>\alpha</math>. And noting that <math>\log_2 x = \tfrac{1}{\ln 2}\ln x</math>, we get:

{{NumBlk|::|<math>\begin{align}
\frac{\partial I\left(A;B\right)}{\partial \alpha} & = \frac{\partial}{\partial \alpha}\left( \alpha\log_2\frac{1}{\alpha} + \left(1-\alpha\right)\log_2\frac{1}{1-\alpha} \right) = 0\\
& = \frac{\partial}{\partial \alpha}\left(\frac{\alpha}{\ln 2}\ln\frac{1}{\alpha} + \frac{1-\alpha}{\ln 2}\ln\frac{1}{1-\alpha}\right) = 0\\
& = \frac{1}{\ln 2}\ln\frac{1}{\alpha} - \alpha\frac{1}{\alpha^2}\frac{\alpha}{\ln 2} - \frac{1}{\ln 2}\ln \frac{1}{1-\alpha} + \frac{1-\alpha}{\ln 2}\frac{1-\alpha}{\left(1-\alpha\right)^2} = 0\\
& = \ln\frac{1}{\alpha} - \ln\frac{1}{1-\alpha} = 0\\
\end{align}</math>|{{EquationRef|15}}}}

Thus, we can get <math>\alpha = 0.5</math>. This can also be seen from the plot of <math>I\left(A;B\right)</math> as a function of <math>\alpha</math> shown in Fig. 2. Therefore the channel capacity is:

{{NumBlk|::|<math>C = \max_{P\left(A\right)} I\left(A;B\right)= \left. I\left(A;B\right)\right|_{\alpha = 0.5} = 1\,\mathrm{bit/channel\,use}</math>|{{EquationRef|16}}}}

== Example 3: A Noisy Channel with Non-Overlapping Outputs ==


== Example 4: The Binary Symmetric Channel (BSC) ==

== Sources ==
* Yao Xie's [https://www2.isye.gatech.edu/~yxie77/ece587/Lecture2.pdf slides] on Entropy and Mutual Information