Average length and entropy of a code from a probabilistic source I'm trying to do this exercise but I have some doubts.


  A binary memoryless source emits the symbols 0 and 1 with probability 0.8 and 0.2 respectively.
  It encodes three blocks messages: 000 is encoded with 0; any other xyz block with 1xyz.
  
  
  The obtained code is UD?
  It is instantaneous?
  Calculate the average length (binary symbol) of the code and compare that to the entropy of the source.
  


The code is UD and instantaneous.
I tried to calculate the average length and the entropy in this way:




The question marks indicate that I don't know how to go on to make the calculations.

Could someone help me?
Thanks a lot!



This is what I've done:

$p(000) = 0.8^3 = 0.512$

$p(001) = 0.8^2 + 0.2 = 0.84$

$p(010) = 0.8^2 + 0.2 = 0.84$

$p(011) = 0.8 + 0.2^2 = 0.84$

$p(100) = 0.8^2 + 0.2 = 0.84$

$p(101) = 0.8 + 0.2^2 = 0.84$

$p(110) = 0.8 + 0.2^2 = 0.84$

$p(111) = 0.2^3 = 0.008$

$\bar{l} = \sum_{i}^{ } l_i p(a_i) $
$        = 1\cdot p(000) + 4\sum_{x^{(3)}\neq 000}^{ } p(x^{(3)})$
$        = 0.512 + 4[3Pr(\#1=1) + 3Pr(\#1=2) + 1Pr(\#1=3)]$
$        = 0.512 + 4[3\cdot 0.2+3\cdot 0.2^2+0.2^3]=3.424$

$H(X) = -\sum_{i}^{ } p(a_i) \log_{2}p(a_i)$
$= -0.512 \log_{2} 0.512 -6(0.84 \log_{2} 0.84) -0.008 \log_{2} 0.008 = 1.81$

It's right? I think is not..



$p(000) = 0.8^3 = 0.512$

$p(001) = 0.8^2 \cdot 0.2 = 0.128$

$p(010) = 0.8^2 \cdot 0.2 = 0.128$

$p(011) = 0.8 \cdot 0.2^2 = 0.032$

$p(100) = 0.8^2 \cdot 0.2 = 0.128$

$p(101) = 0.8 \cdot 0.2^2 = 0.032$

$p(110) = 0.8 \cdot 0.2^2 = 0.032$

$p(111) = 0.2^3 = 0.008$

$\bar{l} = \sum_{i}^{ } l_i p(a_i) $
$        = 1\cdot p(000) + 4\sum_{x^{(3)}\neq 000}^{ } p(x^{(3)})$
$        = 0.512 + 4[3Pr(\#1=1) + 3Pr(\#1=2) + 1Pr(\#1=3)]$
$        = 0.512 + 4[3\cdot 0.2+3\cdot 0.2^2+0.2^3]=3.424$

$H(X) = -\sum_{i}^{ } p(a_i) \log_{2}p(a_i)$
$= -0.512 \log_{2} 0.512 -3(0.128 \log_{2} 0.128) -3(0.032 \log_{2} 0.032) -0.008 \log_{2} 0.008 = 2.16$

I don't know what else to do, I feel very stupid.
$\sum_{x\ne 000} p(x)$ is the probability of at least one 1 in the word. It's easy to break it according the number of ones ($\#1$) in $x$
$$=3 \Pr[\#1 =1] + 3\Pr[\#1=2] + 1\Pr[\#1=3]= 0.488$$

Which is indeed equal to $(1-(p_0)^3)$ as you wrote yourself.

The entropy is being computed similarly. Just plug in $\Pr(x)$ for any possible $x\in \{0,1\}^3$. BTW, your formula is written incorrectly (I assume it is a typo). Should be
$$ H(X) = -\sum_{a_i} p(a_i) \log_2(p(a_i)).$$