Examples

Ex.1
$a - 10 \\ b - 01\\ c - 00\\ d - 111 \\ e - 110\\$ L=2/4+2/4+2/5+3(.15)+3(.15)=2.3

Ex.2
$a - 1\\ b - 0\\ c - 22 \\ d - 21\\ e - 20\\$ L=1/4+1/4+2/5+2(1.5)+2(1.5)=1.5

Ex.3
Code tree is incomplete!
We need to combine 3 at last step. So add DUMMIES
Grouping preference is
$x\rightarrow x-D+1 \rightarrow x-2D+2\rightarrow x-k(D-1)\rightarrow 1$
so $x-1=k(D-1) \rightarrow (x-1)$ is a multiple of (D-1) at last stage
Previous case x=6, x-1=5 not a multiple of D-1=2, so add 1 dummy.
L=.25+.25+2/5+2/10+3/10+3/10+0=1.7
Tree complete!

Extension

Code blocks of k source letters
Ex. a₁ a₂ a₃                 3 source letters K=3

$$\left. \begin{array}{l} Prob(a_1 a_1 a_1)=p_1^3\\ Prob(a_1 a... ...possibilities} \end{array} \right\} \mbox{ New source distrib}$$

Clearly,

$$H(X^3)\le\overline{R_3}\le H(X^3)+1$$

If n - letter blocks

$$H(X^n)\le \overline{R_n} \le H(X^n)+1$$

$$\Rightarrow \frac{H(X^n)}{n}\le \overline{R}=\frac{\overline{R}}{n} \le \frac{H(X^n)}{n} +\frac{1}{n}$$

So for sources with memory, $\overline{R}$ is bounded by H(X) the entropy rate.