0.13 Coding  (Page 10/22)

1. $N=4$ , $p\left(x_1\right)=0.5$ , $p\left(x_2\right)=0.25$ , $p\left(x_3\right)=p\left(x_4\right)=0.125$ . The total information is
   $$\sum _{i=1}^{4}I\left(x_i\right)=\sum _{i=1}^{4}log\left(\frac{1}{p\left(x_i\right)}\right)=1+2+3+3=9\text{bits}.$$
   The entropy of the source is
   $$H\left(x\right)=\frac{1}{2}·1+\frac{1}{4}·2+\frac{1}{8}·3+\frac{1}{8}·3=1.75\text{bits/symbol.}$$
2. $N=4$ , $p\left(x_i\right)=0.25$ for all $i$ . The total information is $I\left(x_i\right)=2+2+2+2=8$ . The entropy of the source is
   $$H\left(x\right)=\frac{1}{4}·2+\frac{1}{4}·2+\frac{1}{4}·2+\frac{1}{4}·2=2\text{bits/symbol.}$$

In Example [link] , messages of the same length from the first source give lessinformation than those from the second source. Hence, sources with the same number of symbols but different probabilitiescan have different entropies. The key is to design a system to maximize entropy since this will have the largest throughput, or largestaverage flow of information. But how can this be achieved?

First, consider the simple case in which there are two symbols in the alphabet, $x_1$ with probability $p$ , and $x_2$ with probability $1-p$ . (Think of a coin that is weighted so as to give heads with higher probability than tails.)Applying the definition [link] shows that the entropy is

This is plotted as a function of $p$ in [link] . For all allowable values of $p$ , $H\left(p\right)$ is positive. As $p$ approaches either zero or one, $H\left(p\right)$ approaches zero, which represent the symmetric cases in which either $x_1$ occurs all the time or $x_2$ occurs all the time, and no information is conveyed. $H\left(p\right)$ reaches its maximum in the middle, at $p=0.5$ . For this example, entropy is maximized whenboth symbols are equally likely.

The next result shows that an $N$ -symbol source cannot have entropy larger than $log\left(N\right)$ , and that this bound is achieved when all the symbols are equally likely.Mathematically, $H\left(x\right)\le log\left(N\right)$ , which is demonstrated by showing that $H\left(x\right)-log\left(N\right)\le 0$ . First,

since ${\sum }_{i=1}^{N}p\left(x_i\right)=1$ . Gathering terms, this can be rewritten

and changing the base of the logarithm (using $log\left(z\right)\equiv {log}_2\left(z\right)={log}_2\left(e\right)ln\left(z\right)$ , where $ln\left(z\right)\equiv {log}_e\left(z\right)$ ), gives

If all symbols are equally likely, $p\left(x_i\right)=1/N$ , then $\frac{1}{Np\left(x_i\right)}=1$ and $ln\left(\frac{1}{Np\left(x_i\right)}\right)=ln\left(1\right)=0$ . Hence $H\left(x\right)=log\left(N\right)$ . On the other hand, if the symbols are not equally likely, then the inequality $ln\left(z\right)\le z-1$ (which holds for $z\ge 0$ ) implies that

Rearranging [link] gives the desired bound on the entropy, that $H\left(x\right)\le log\left(N\right)$ . This says that, all else being equal, it is preferableto choose a code in which each symbol occurs with the same probability.Indeed, Example [link] provides a concrete source for which the equal probability case has higherentropy than the unequal case.

"Redundancy" showed how letters in the text of natural languages do not occur with equal probability. Thus,naively using the letters will not lead to an efficient transmission. Rather, the letters must be carefully translatedinto equally probable symbols in order to increase the entropy. A method for accomplishing this translation is given in "Source Coding" , but "Channel Capacity" examines the limits of attainable performance when transmitting symbols across a noisy (but otherwise perfect) channel.