九州大学 システム情報科学府 情報理工学専攻 2018年8月実施 情報理論

https://runjp.com/docs/kyushu-university/ISEE/ist/2019/ist_201808_information_theory

---

【Question 1】

There is a discrete memoryless information source with an alphabet $\mathcal{X} = \{a, b, c, d\}$. The probability of occurrence $p(x)$ for each symbol $x \in \mathcal{X}$ is given in the table below. Note that $0 < \alpha \le \frac{1}{2}$.

x	a	b	c	d
$p(x)$	$\frac{\alpha}{2}$	$\frac{1-\alpha}{2}$	$\frac{1}{4}$	$\frac{1}{4}$

Answer the following questions:

(1) Find the entropy of this information source as a function of $\alpha$.

(2) Find one binary Huffman code for this information source when $0 < \alpha < \frac{1}{4}$.

(3) Find the average code length (the expected value of the code length) for the code in (2) as a function of $\alpha$.

(4) Find the average code length of a binary Huffman code for this information source when $\frac{1}{4} \le \alpha \le \frac{1}{2}$.

(5) Let $L(\alpha)$ be the average code length of a binary Huffman code for this information source. Draw a graph of $L(\alpha)$ for $\alpha \in (0, \frac{1}{2}]$.