2004年7月5日分 略解

• クラフトの不等式を満足するが瞬時符号とならない符号の例をあげよ．
  • 例として、 A=0, B=01, C=011 という符号を設定した場合、 クラフトの不等式（p.75）: Σ_{i=1}^M 1/r^{g_i} = 1/2 + 1/4 + 1/8 = 7/8 ≦ 1 を満たす。 (記号の意味: 符号長 g_i の r元符号が M個ある.) しかし、 最初に「0」を受信した場合、全ての符号の可能性があり、 瞬時符号とならない。 また、決定木を適用した場合、全ての符号が leaf にならず、 node であることからも、この符号が瞬時符号ではないことが判る。
• (a) ハフマン符号を構成し，平均符号語長を求めなさい．
  • ハフマン符号の作成法は、教科書 p.82 を参照のこと．
  • 0 と 1 の置き方の違いで様々な（全４パターン）答えが考えられる。 一例として、s_1=0, s_2=10, s_3=11 が考えられる。
  • 平均符号長(p.77):
    L=Σ_{i=1}^M P(s_i)*{g_i} = 1/2 *1 + 3/10 * 2 + 1/5 *2 =1.5 [bit].
    (記号の意味: 符号長 g_i で生起確率 P(s_i) の符号が M 個ある.)
• (b) シャノン・ファノ符号を構成し，平均符号語長を求めなさい．
  • (a)と同様に、0 と 1 の置き方の違いで様々な (全4パターン) 答えが考えられる。
  • 一例として、s_1=1, s_2=01, s_3=00
  • 平均符号長は、
    L=Σ_{i=1}^M P(s_i)*{g_i} = 1/2 *1 + 3/10 * 2 + 1/5 *2 = 1.5[bit]
    

1. 池口 徹， 講義サポートページ
2. 情報理論及演習講義サポートページ
3. シラバス