この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

情報理論・符号理論の問題

難易度 3期末試験の応用レベル大学数学情報理論・符号理論

記号 $0, 1$ をそれぞれ確率 $\frac{3}{4}, \frac{1}{4}$ で、各時刻独立に出力する無記憶情報源 $X$ を考える。 $X$ の出力を $3$ 個ずつまとめたブロック（ $000, 001, \dots, 111$ の $8$ 通り）を $1$ つの記号とみなし、この $8$ 個の記号に対して $2$ 元ハフマン符号（符号記号は ${0, 1}$ ）を構成する。

このとき、元の情報源 $X$ の記号 $1$ 個あたりの平均符号長（ブロック $1$ 個あたりの平均符号長を $3$ で割ったもの）を求めよ。

この問題で使うもの

ハフマン符号（説明と入口の問題）
独立な試行と反復試行（説明と入口の問題）

この問題を解けるようになるまで（24 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まず $8$ 個のブロックそれぞれの確率を求め、 $\frac{1}{64}$ を単位とする整数の重みに直してからハフマンの手順を実行しましょう。

ヒント 2

重みは $27, 9, 9, 9, 3, 3, 3, 1$ です。最小の $2$ つを併合する操作を繰り返します。平均符号長は「併合で生じた節点の重みの総和」としても計算できます。

ヒント 3

最初の併合は $1 + 3 = 4$ 、次は $3 + 3 = 6$ 、その次は $4 + 6 = 10$ です。最終的な符号長は $1, 3, 3, 3, 5, 5, 5, 5$ となり、クラフトの和は $1$ になります。ここから平均符号長を計算し、最後に $3$ で割ります。

答えと解説

答えを見る

\frac{79}{96}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

ブロックの確率

各時刻の出力は独立なので、ブロックの確率は各記号の確率の積である。 $1$ を $k$ 個含むブロックの確率は $(\frac{3}{4})^{3 - k} (\frac{1}{4})^{k} = \frac{3 ^{3 - k}}{64}$ であり、そのようなブロックは $(k 3)$ 個ある。 $\frac{1}{64}$ を単位として重みで書くと
$27, 9, 9, 9, 3, 3, 3, 1$
となる（ $000$ が $27$ 、 $1$ を $1$ 個含む $3$ ブロックが $9$ 、 $1$ を $2$ 個含む $3$ ブロックが $3$ 、 $111$ が $1$ ）。

ハフマン符号の構成

重みの小さい $2$ つを繰り返し併合する。
- $1 + 3 = 4$ ：残りは $27, 9, 9, 9, 4, 3, 3$
- $3 + 3 = 6$ ：残りは $27, 9, 9, 9, 6, 4$
- $4 + 6 = 10$ ：残りは $27, 10, 9, 9, 9$
- $9 + 9 = 18$ ：残りは $27, 18, 10, 9$
- $9 + 10 = 19$ ：残りは $27, 19, 18$
- $18 + 19 = 37$ ：残りは $37, 27$
- $27 + 37 = 64$ ：根

根から木をたどると、各ブロックの符号長は次のようになる。
- $27$ （ $000$ ）：根 $64$ の子なので長さ $1$
- $9$ の $3$ 個： $18$ の子 $2$ 個と $19$ の子 $1$ 個で、いずれも長さ $3$
- $10$ は長さ $3$ の節点で、その子 $4, 6$ は長さ $4$ 、さらにその子 $1, 3, 3, 3$ はすべて長さ $5$

よって符号長は $1, 3, 3, 3, 5, 5, 5, 5$ である。

クラフトの不等式による確認

語頭符号であることを確かめると
$2^{- 1} + 3 \cdot 2^{- 3} + 4 \cdot 2^{- 5} = \frac{1}{2} + \frac{3}{8} + \frac{1}{8} = 1$
となり、クラフトの不等式を等号で満たす。ハフマン符号の符号木は、すべての内部節点がちょうど $2$ つの子をもつ完全な $2$ 分木なので、等号になるのは当然である。

平均符号長

ブロック $1$ 個あたりの平均符号長は
$L ˉ_{3} = \frac{27 \cdot 1 + 3 \cdot 9 \cdot 3 + ( 3 \cdot 3 + 1 ) \cdot 5}{64} = \frac{27 + 81 + 50}{64} = \frac{158}{64} = \frac{79}{32}$
である。

別の計算法として、併合で生じた節点の重みの和 $4 + 6 + 10 + 18 + 19 + 37 + 64 = 158$ を $64$ で割っても同じ値になる。

ハフマン符号は最適な語頭符号である。同順位の併合の選び方によって符号語は変わりうるが、平均符号長はつねに同じ値になる。

したがって、元の記号 $1$ 個あたりの平均符号長は
$\frac{L ˉ _{3}}{3} = \frac{79}{96} (\approx 0.823)$
である。

参考までに、エントロピーは $H (X) = - \frac{3}{4} lo g_{2} \frac{3}{4} - \frac{1}{4} lo g_{2} \frac{1}{4} \approx 0.811$ である。 $H (X) \leq \frac{79}{96} < H (X) + \frac{1}{3}$ が成り立ち、情報源符号化定理の評価と矛盾しない。

別解

ブロックの確率を $1/64$ を単位として表すと、 $000$ が $27$ 、 $001, 010, 100$ が各 $9$ 、 $011, 101, 110$ が各 $3$ 、 $111$ が $1$ である。

ハフマン法で、小さい 2 つを順に併合する。
1. $1 + 3 = 4$
2. $3 + 3 = 6$
3. $4 + 6 = 10$
4. $9 + 9 = 18$
5. $9 + 10 = 19$
6. $18 + 19 = 37$
7. $27 + 37 = 64$

ブロック 1 個あたりの平均符号長は、併合で作られた節点の重みの総和を $64$ で割った値に等しい。
$(4 + 6 + 10 + 18 + 19 + 37 + 64) /64 = 158/64 = 79/32$ である。

検算として符号長を具体的に割り当てる。 $000$ は長さ 2、 $001, 010, 100$ は長さ 3 が 2 つと長さ 4 が 1 つ、あるいは各 3 などに分かれうるが、平均は併合の和で一意に定まる。ここでは平均が $79/32 \approx 2.469$ であり、ブロックのエントロピー $3 H (1/4) \approx 2.434$ 以上で、 $+ 1$ 未満となり整合する。

元の情報源の記号 1 個あたりでは、 $79/32 \div 3 = 79/96 \approx 0.823$ ビットである。

情報理論・符号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題