例題集

ハフマン符号

知識・記憶レベル   難易度: ★★
ある信号の振幅値を5段階にわけ,0,1の2符号で符号化する.また,各振幅値を$(a, b, c, d, e)$の発生確率は以下のとおりである.このとき,次の問いにそれぞれ答えなさい. $P\{a\}=\frac{2}{32}, P\{b\}=\frac{3}{32}, P\{c\}=\frac{16}{32}, P\{d\}=\frac{7}{32}, P\{e\}=\frac{4}{32}$ (1)この情報源のエントロピーを求めなさい. (2)ハフマン符号化を行い符号化方法の図を示し,それぞれの段階の符号を答えなさい.
(1)エントロピー$H$は次のように求められる. \begin{eqnarray} H&=&\frac{2}{32}\log_2\frac{2}{32}-\frac{3}{32}\log_2\frac{3}{32}-\frac{16}{32}\log_2\frac{16}{32}\\ &&-\frac{7}{32}\log_2\frac{7}{32}-\frac{4}{32}\log_2\frac{4}{32}\\ &=&1.924 \cdots \\ &\approx&1.92 \ \mathrm{[bit/level]} \end{eqnarray} (2)ハフマン符号化の図は以下のようになる. %=image:/media/2014/08/27/140915025148377800.jpg: また,この図より,各段階の符号は以下のようになる. %=image:/media/2014/08/27/140915044767228100.jpg:各段階の符号