Lemma (Huffman)

Consider a source with alphabet $\mathcal{X}=\{a_{1},\cdots,a_{M}\}$ and symbol probabilities $p_{1},\cdots,p_{M}$ such that $$p_1\ge\cdots\ge p_M>0$$Consider the reduced source with alphabet $\mathcal{Y}$ obtained from $\mathcal{X}$ by combining the two least likely source symbols $a_{M-1}$ and $a_{M}$ into an equivalent symbol $a_{M-1,M}$ with probability $p_{M-1,M}$: $$\mathcal{Y}=\{a_{1},\cdots,a_{M-2},a_{M-1,M}\}$$Let $\mathcal{C}_{2}$, given by $f_{2}:\mathcal{Y}\to\{0,1\}^{*}$, be an optimal prefix code for the reduced source $\mathcal{Y}$. Now, construct a code $\mathcal{C}_{1}, \ f_{1}:\mathcal{X}\to\{0,1\}^{*}$, for the original source $\mathcal{X}$ as follows:

• The codewords for symbols $a_{1},\cdots,a_{M-2}$ are exactly the same as the corresponding codewords in $\mathcal{C}_{2}$:$$f_{1}(a_{i})=f_{2}(a_{i}), \ i=1,\cdots,M-2$$
• The codewords for symbols $a_{M-1}$ and $a_{M}$ are formed by appending a “0” and a “1”, respectively, to the codeword $f_{2}(a_{M-1,M})\in\mathcal{C}_{2}$ for symbol $a_{M-1,M}$:$$\begin{align*} f_{1}(a_{M-1})&=f_{2}(a_{M-1,M})0\\ f_{1}(a_{M})&=f_{2}(a_{M-1,M})1\\ \end{align*}$$Then $\mathcal{C}_{1}$ is an optimal prefix code for the original source $\mathcal{X}$.