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

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

難易度 1教科書の例題レベル大学数学情報理論・符号理論

情報源 $X$ は 4 個の記号 $a_{1}, a_{2}, a_{3}, a_{4}$ を、それぞれ次の確率で出力する。 $P (a_{1}) = \frac{2}{5}, P (a_{2}) = \frac{3}{10}, P (a_{3}) = \frac{1}{5}, P (a_{4}) = \frac{1}{10}$ 符号記号を ${0, 1, 2}$ とする 3 元語頭符号で $X$ の各記号を符号化するとき、1 記号あたりの平均符号長 $L ˉ = \sum_{i = 1}^{4} P (a_{i}) l_{i}$ （ $l_{i}$ は $a_{i}$ の符号語の長さ）の最小値を求めよ。

この問題で使うもの

D 元ハフマン符号（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

3 元ハフマン符号を作ります。その前に、記号数 $m$ が $m \equiv 1 (mod D - 1)$ を満たすかを確かめましょう。

ヒント 2

$m = 4$ 、 $D = 3$ なので、確率 $0$ のダミー記号を 1 個補って記号数を 5 にします。その後、確率の小さい 3 個ずつをまとめていきます。

ヒント 3

1 回目は $0, \frac{1}{10}, \frac{1}{5}$ をまとめて $\frac{3}{10}$ にします。残りの 3 個 $\frac{2}{5}, \frac{3}{10}, \frac{3}{10}$ をまとめると終わります。この結果から各記号の符号長を読み取りましょう。

答えと解説

答えを見る

\frac{13}{10}

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

解説を読む

3 元ハフマン符号を作ります。3 元ハフマン符号は、平均符号長が最小の 3 元語頭符号になります。

手順 1：ダミー記号を補う

$D = 3$ のハフマン符号では、確率の小さい順に 3 個ずつまとめていきます。1 回まとめるごとに記号は $D - 1 = 2$ 個減ります。最後にちょうど 1 個になるには、記号数 $m$ が $m \equiv 1 (mod 2)$ を満たす必要があります。

いまは $m = 4$ で、 $4 \equiv 0 (mod 2)$ です。そこで確率 $0$ のダミー記号 $d$ を 1 個補い、記号数を $5$ にします（ $5 \equiv 1 (mod 2)$ ）。

手順 2：小さい順に 3 個ずつまとめる

確率を小さい順に並べると
$P (d) = 0, P (a_{4}) = \frac{1}{10}, P (a_{3}) = \frac{1}{5}, P (a_{2}) = \frac{3}{10}, P (a_{1}) = \frac{2}{5}$
です。

1 回目：小さい 3 個 $d, a_{4}, a_{3}$ をまとめて、新しい記号 $b$ を作る。その確率は $0 + \frac{1}{10} + \frac{1}{5} = \frac{3}{10}$ である。
2 回目：残りは $a_{1} (\frac{2}{5}), a_{2} (\frac{3}{10}), b (\frac{3}{10})$ の 3 個である。これをまとめると確率 $1$ になり、終了する。

手順 3：符号語を割り当てる

2 回目にまとめた 3 個に $0, 1, 2$ を割り当てます。たとえば $a_{1} \to 0, a_{2} \to 1, b \to 2$ とします。 $b$ の中の 3 個には、 $b$ の符号語 $2$ の後ろに $0, 1, 2$ を付けます。
$a_{3} \to 20, a_{4} \to 21, d \to 22$
ダミー記号 $d$ は実際には出力されないので、符号語 $22$ は使いません。

したがって符号長は $l_{1} = 1, l_{2} = 1, l_{3} = 2, l_{4} = 2$ です。クラフトの不等式の左辺は $3^{- 1} + 3^{- 1} + 3^{- 2} + 3^{- 2} = \frac{8}{9} \leq 1$ となり、たしかに語頭符号が作れています。

手順 4：平均符号長を求める

$L ˉ = \frac{2}{5} \cdot 1 + \frac{3}{10} \cdot 1 + \frac{1}{5} \cdot 2 + \frac{1}{10} \cdot 2 = \frac{4}{10} + \frac{3}{10} + \frac{4}{10} + \frac{2}{10} = \frac{13}{10}$

（参考）ダミー記号を補わずに、まず $a_{4}, a_{3}, a_{2}$ をまとめ、残った 2 個をまとめるとどうなるかを見ます。このときは $l_{1} = 1$ 、 $l_{2} = l_{3} = l_{4} = 2$ となり、 $L ˉ = \frac{2}{5} + 2 \cdot \frac{3}{5} = \frac{8}{5}$ です。これは $\frac{13}{10}$ より大きいので、ダミー記号を補うことが必要だとわかります。

よって、平均符号長の最小値は $\frac{13}{10}$ です。

別解

3 元ハフマン符号が最適な語頭符号を与える。記号数 4 は、3 元の場合 $n \equiv 1 (mod 2)$ を満たさない（ $n = 3, 5, 7, \dots$ なら余りなく併合できる）ので、ダミー記号（確率 0）を 1 個加えて 5 記号にする。

確率は 0.4, 0.3, 0.2, 0.1, 0 である。
1 回目の併合: 確率の小さい 3 つ 0, 0.1, 0.2 を併合して 0.3 とする。
残りは 0.4, 0.3, 0.3 の 3 つである。
2 回目の併合: この 3 つを併合して 1 とする。

符号長は次のとおり。
- $a_{1}$ （0.4）: 長さ 1
- $a_{2}$ （0.3）: 長さ 1
- $a_{3}$ （0.2）と $a_{4}$ （0.1）: 長さ 2（ダミーも長さ 2）

平均符号長は $L ˉ = 0.4 \cdot 1 + 0.3 \cdot 1 + 0.2 \cdot 2 + 0.1 \cdot 2 = 0.7 + 0.6 = 1.3 = \frac{13}{10}$ 。

検算として、長さ $(1, 1, 2, 2)$ はクラフトの不等式 $3^{- 1} + 3^{- 1} + 3^{- 2} + 3^{- 2} = \frac{8}{9} \leq 1$ を満たす。
長さ $(1, 1, 1, x)$ は 3 つの語を長さ 1 に使うと $a_{4}$ の語が作れないので不可能である。
長さ 1 の語を 2 個以下にする場合、残りの長さは 2 以上になる。このとき最小は $0.4 + 0.3 + 0.2 \cdot 2 + 0.1 \cdot 2 = 1.3$ である。

よって最小値は $\frac{13}{10}$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題