Question

We use Huffman's algorithm to obtain an encoding of alphabet $\left\{a,b,c\right\}$with frequencies ${\mathbf{f}}_{\mathbf{a}}\mathbf{,}{\mathbf{f}}_{\mathbf{b}}\mathbf{,}{\mathbf{f}}_{\mathbf{c}}$. In each of the following cases, either give an example of frequencies $\mathbf{(}{\mathbf{f}}_{\mathbf{a}}\mathbf{,}{\mathbf{f}}_{\mathbf{b}}\mathbf{,}{\mathbf{f}}_{\mathbf{c}}\mathbf{)}$that would yield the specified code, or explain why the code cannot possibly be obtained (no matter what the frequencies are).

(a) Code:$\left\{0,10,11\right\}$

(b) Code:$\left\{0,1,00\right\}$

(c) Code:$\left\{10,01,00\right\}$

Short answer

1. The code$\left\{0,10,11\right\}$ can be obtained for frequencies$20,30$ and 50.
2. Code $\left\{0,1,00\right\}$cannot be obtained from any of the frequencies, because the tree obtained is not a full binary tree
3. Code $\left\{10,01,00\right\}$cannot be obtained from any of the frequencies, because the tree obtained is not a full binary tree.

Step-by-step solution

Huffman Encoding

Huffman encoding is done by following a path from the root to leaf of a full binary tree. Every left node of the tree is represented as 0 and every right node of the tree is represented as 1.

(a)

Determine the full binary tree of {0,10,11}

Let ${\mathrm{f}}_{\mathrm{a}}=50,\hspace{0.33em}{\mathrm{f}}_{\mathrm{b}}=20,\hspace{0.33em}{\mathrm{f}}_{\mathrm{c}}=30$. Prefix free encoding of these frequencies is:

The tree obtained is a full binary tree. Therefore, the frequencies $(50,20,30)$yield the codelocalid="1657259801818" $\left\{0,10,11\right\}.$

(b)

Determine the full binary tree of{0,1,00} 

Prefix free encoding for the given code word is:

The tree obtained is not a full binary tree. Also, it violates an important property:

A codeword cannot be prefix of another codeword. Here, codeword of $\mathrm{a}\left(0\right)$ is the prefix of codeword of$\mathrm{c}\left(00\right)$ Therefore, the no frequencies can yield the code $\left\{0,1,00\right\}$.

(c)

Determine the full binary tree of {10,01,00}

Prefix free encoding for the given codeword is:

The tree obtained is not a full binary tree. Thus, no frequencies can yield such a code.

Hence, the codeword$\left\{0,10,11\right\}$ can only be yielded from the alphabets.