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

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

難易度 2教科書の演習問題レベル大学数学情報理論・符号理論

入力アルファベットが ${0, 1}$ 、出力アルファベットが ${0, 1, e}$ の離散無記憶通信路を考える。ここで $e$ は「消失」を表す記号である。入力 $X$ と出力 $Y$ の条件付き確率は、 $x \in {0, 1}$ に対して
$P (Y = x ∣ X = x) = \frac{5}{8}, P (Y = e ∣ X = x) = \frac{1}{4}, P (Y = 1 - x ∣ X = x) = \frac{1}{8}$
で与えられる。この通信路の通信路容量 $C = max_{P_{X}} I (X; Y)$ を求めよ。ただし、エントロピーと相互情報量の対数の底は $2$ とする（単位はビット）。

この問題で使うもの

離散無記憶通信路の通信路容量（説明と入口の問題）
エントロピー（説明と入口の問題）
相互情報量（説明と入口の問題）
対数の定義と性質（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$I (X; Y) = H (Y) - H (Y ∣ X)$ と分け、どちらが入力分布に依存するかを調べよう。

ヒント 2

$H (Y ∣ X)$ は入力分布によらない。 $P (Y = e) = \frac{1}{4}$ が常に一定であることに注目し、 $H (Y) = h (\frac{1}{4}) + \frac{3}{4} h (t)$ の形に書けることを使おう。

ヒント 3

$H (Y ∣ X) = \frac{11}{4} - \frac{5}{8} lo g_{2} 5$ であり、 $H (Y)$ は $P (X = 0) = \frac{1}{2}$ のとき最大で、そのとき $P (Y = 0) = P (Y = 1) = \frac{3}{8}$ となる。

答えと解説

答えを見る

\frac{5}{8} lo g_{2} 5 - \frac{3}{4} lo g_{2} 3

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

解説を読む

$P (X = 0) = a, P (X = 1) = 1 - a (0 \leq a \leq 1)$ とおく。 $I (X; Y) = H (Y) - H (Y ∣ X)$ を用いる。

$H (Y ∣ X)$ の計算　どちらの入力に対しても出力の条件付き分布は確率 $\frac{5}{8}, \frac{1}{4}, \frac{1}{8}$ の並べかえなので、
$H (Y ∣ X) = \frac{5}{8} lo g_{2} \frac{8}{5} + \frac{1}{4} lo g_{2} 4 + \frac{1}{8} lo g_{2} 8 = \frac{5}{8} (3 - lo g_{2} 5) + \frac{1}{2} + \frac{3}{8} = \frac{11}{4} - \frac{5}{8} lo g_{2} 5$
となり、これは $a$ によらない。よって $H (Y)$ を最大にすればよい。

$H (Y)$ の最大化　
$P (Y = e) = \frac{1}{4}, P (Y = 0) = \frac{5}{8} a + \frac{1}{8} (1 - a), P (Y = 1) = \frac{1}{8} a + \frac{5}{8} (1 - a)$
で、 $P (Y = 0) + P (Y = 1) = \frac{3}{4}$ は一定である。 $P (Y = 0) = \frac{3}{4} t$ とおくと
$H (Y) = h (\frac{1}{4}) + \frac{3}{4} h (t), h (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$
と書ける。 $h (t)$ は $t = \frac{1}{2}$ で最大値 $1$ をとり、 $t = \frac{1}{2}$ は $a = \frac{1}{2}$ のとき実現される。このとき $P (Y = 0) = P (Y = 1) = \frac{3}{8}$ で
$H (Y) = \frac{1}{4} lo g_{2} 4 + 2 \cdot \frac{3}{8} lo g_{2} \frac{8}{3} = \frac{1}{2} + \frac{3}{4} (3 - lo g_{2} 3) = \frac{11}{4} - \frac{3}{4} lo g_{2} 3.$

容量
$C = (\frac{11}{4} - \frac{3}{4} lo g_{2} 3) - (\frac{11}{4} - \frac{5}{8} lo g_{2} 5) = \frac{5}{8} lo g_{2} 5 - \frac{3}{4} lo g_{2} 3 \approx 0.262 ビット .$

別解

この通信路は、各入力に対する出力分布が互いの置換になっている対称な通信路である。 $I (X; Y) = H (Y) - H (Y ∣ X)$ で、 $H (Y ∣ X)$ は入力分布によらず一定である。 $H (Y)$ は入力が一様なとき最大になる（ $I$ は入力分布について凹で、 $0 \leftrightarrow 1$ の入れ替えに対して対称なため）。

条件付きエントロピー:
$H (Y ∣ X) = H (5/8, 1/4, 1/8) = \frac{5}{8} lo g_{2} \frac{8}{5} + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 = \frac{11}{4} - \frac{5}{8} lo g_{2} 5$ 。

入力が一様のとき、 $P (Y = 0) = P (Y = 1) = \frac{1}{2} (\frac{5}{8} + \frac{1}{8}) = \frac{3}{8}$ 、 $P (Y = e) = \frac{1}{4}$ 。よって
$H (Y) = 2 \cdot \frac{3}{8} lo g_{2} \frac{8}{3} + \frac{1}{4} \cdot 2 = \frac{3}{4} (3 - lo g_{2} 3) + \frac{1}{2} = \frac{11}{4} - \frac{3}{4} lo g_{2} 3$ 。

したがって
$C = H (Y) - H (Y ∣ X) = \frac{5}{8} lo g_{2} 5 - \frac{3}{4} lo g_{2} 3 = \frac{5 l o g _{2} 5 - 6 l o g _{2} 3}{8}$ 。

数値検算: $5 lo g_{2} 5 \approx 11.6096$ 、 $6 lo g_{2} 3 \approx 9.5098$ なので、差は $2.0999$ 、これを 8 で割って $C \approx 0.2625$ ビット。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題