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

1. The obtained code is UD?
2. It is instantaneous?
3. 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.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. May 20, 2016 at 23:53

$\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)).$$

• Thank for the reply. How did you get 0.488? May 21, 2016 at 6:53
• @four can you tell what is $p_0$? May 21, 2016 at 14:45
• $p_0$ is the probability of the sequence $000$. I don't understand how I should calculate it, I just know that $p(0) = 0.8$, then $p(000)$ is $0.8^3$ or $3*0.8$ or something else? May 21, 2016 at 14:51
• @four, Actually $p_0$ is the probability of seeing a "0", which is 0.8 as you say. The probability for seeing 000 is $p(000)=p_0^3$. This should fully answer your question. May 21, 2016 at 14:53
• Thanks for your patience. I modified the main message with the steps I did to solve the exercise. Could you tell me if I have done in the right way? May 21, 2016 at 15:31