$1$ Shannon code.

Consider the following method for generating a code for a random variable x that takes

on m values $\{1,2,$cdots,m$\}$ with probabilities p$\_(1),$p$\_(2),$cdots,p$\_($m$).$ Assume that the probabilities

are ordered so that p$\_(1)>=$p$\_(2)>=$cdots$>=$p$\_($m$).$ Define

F$\_($i$)=\backslash$sum$\_($k$=1)^($i$-1)$ p$\_($k$)$

the sum of the probabilities of all symbols less than i$.$ Then the codeword for i is the

number F$\_($i$)$in$[0,1]$ rounded off to l$\_($i$)$ bits, where l$\_($i$)=|$~log$((1)/($p$\_($i$)))$~$|.$

$($a$)$ Show that the code constructed by this process is prefix$-$free and that the average

length satisfies

l$\_($i$)=|$~log$((1)/($p$\_($i$)))$~$|$log$((1)/($p$\_($il$\_($ilog$((1)/($p$\_($i$)))+12^(-$l$\_($ip$\_($il$\_($i$)-1)).$F$\_($j$)$j$>$iF$\_($i$)2^(-$l$\_($i$))$F$\_($j$),$j$>$il$\_($j$)>=$l$\_($i$)$F$\_($i$)$l$\_($i$)(0\mathrm{.}5,0\mathrm{.}25,0\mathrm{.}125,0\mathrm{.}125)$H$($xL

Hints: Since l$\_($i$)=|$~log$((1)/($p$\_($i$)))$~$|,$ we have log$((1)/($p$\_($il$\_($ilog$((1)/($p$\_($i$)))+1$ and $2^(-$l$\_($ip$\_($il$\_($i$)-1)).$F$\_($j$)$

for j$>$i$,$ differs from F$\_($i$)$ by at least $2^(-$l$\_($i$)).$ The codeword for F$\_($j$),$j$>$i$,$ which has length

l$\_($j$)>=$l$\_($i$),$ differs from the codeword for F$\_($i$)$ at least once in the first l$\_($i$)$ places.

$($b$)$ Construct the code for the probability distribution $(0\mathrm{.}5,0\mathrm{.}25,0\mathrm{.}125,0\mathrm{.}125).$