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

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

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

入力アルファベット ${0, 1}$ 、出力アルファベット ${0, 1, e}$ の離散無記憶通信路を考える。入力 $X = x$ （ $x \in {0, 1}$ ）に対して、出力 $Y$ は
$P (Y = x ∣ X = x) = \frac{1}{2}, P (Y = e ∣ X = x) = \frac{1}{4}, P (Y = 1 - x ∣ X = x) = \frac{1}{4}$
で定まる（ $e$ は消失を表す記号である）。この通信路の通信路容量（ $1$ 回の使用あたり、単位はビット）を求めよ。対数の底は $2$ とする。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$I (X; Y) = H (Y) - H (Y ∣ X)$ を使い、 $H (Y ∣ X)$ が入力分布によらないことに注目しましょう。

ヒント 2

$P (X = 0) = a$ として出力の分布を $a$ で表すと、 $P (Y = e)$ は $a$ によらず一定になります。 $H (Y)$ が最大になるのは $P (Y = 0) = P (Y = 1)$ のときです。

ヒント 3

$H (Y ∣ X) = \frac{3}{2}$ で、 $a = \frac{1}{2}$ のとき出力の分布は $(\frac{3}{8}, \frac{3}{8}, \frac{1}{4})$ になります。

答えと解説

答えを見る

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

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

解説を読む

通信路容量は $C = max_{P_{X}} I (X; Y)$ 、 $I (X; Y) = H (Y) - H (Y ∣ X)$ である。

$H (Y ∣ X)$

どちらの入力に対しても出力の条件付き分布は確率 $(\frac{1}{2}, \frac{1}{4}, \frac{1}{4})$ の並べかえなので、入力分布によらず
$H (Y ∣ X) = H (\frac{1}{2}, \frac{1}{4}, \frac{1}{4}) = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{4} \cdot 2 = \frac{3}{2} .$

$H (Y)$ の最大化

$P (X = 0) = a$ （ $0 \leq a \leq 1$ ）とすると
$P (Y = 0) = \frac{1}{2} a + \frac{1}{4} (1 - a) = \frac{1}{4} + \frac{1}{4} a, P (Y = 1) = \frac{1}{2} - \frac{1}{4} a, P (Y = e) = \frac{1}{4} .$
$P (Y = e)$ は $a$ によらず $\frac{1}{4}$ であり、 $P (Y = 0) + P (Y = 1) = \frac{3}{4}$ で一定なので、 $H (Y)$ は $P (Y = 0) = P (Y = 1) = \frac{3}{8}$ 、すなわち $a = \frac{1}{2}$ のとき最大になる（ $H (Y)$ は $a$ の凹関数で、 $a \leftrightarrow 1 - a$ の入れかえで対称なため）。このとき
$H (Y) = 2 \cdot \frac{3}{8} lo g_{2} \frac{8}{3} + \frac{1}{4} lo g_{2} 4 = \frac{3}{4} (3 - lo g_{2} 3) + \frac{1}{2} = \frac{11}{4} - \frac{3}{4} lo g_{2} 3.$

通信路容量

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

（別の見方: 確率 $\frac{1}{4}$ で消失し、消失しなかったとき（確率 $\frac{3}{4}$ ）の条件付きビット反転確率は $\frac{1/4}{3/4} = \frac{1}{3}$ である。よって $C = \frac{3}{4} (1 - h (\frac{1}{3}))$ 、 $h (\frac{1}{3}) = lo g_{2} 3 - \frac{2}{3}$ より $C = \frac{3}{4} (\frac{5}{3} - lo g_{2} 3)$ となり一致する。）

答えは $\frac{5}{4} - \frac{3}{4} lo g_{2} 3$ である。

別解

この通信路は、行ごと・列ごとの確率の並びが入れ替えで一致する対称な通信路なので、容量は入力を一様分布 $P (X = 0) = P (X = 1) = \frac{1}{2}$ にしたときの相互情報量 $I (X; Y) = H (Y) - H (Y ∣ X)$ で与えられる。

一様入力のとき $P (Y = 0) = P (Y = 1) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{4} = \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} lo g_{2} 4 = \frac{3}{4} (3 - lo g_{2} 3) + \frac{1}{2} = \frac{11}{4} - \frac{3}{4} lo g_{2} 3.$
$H (Y ∣ X) = H (\frac{1}{2}, \frac{1}{4}, \frac{1}{4}) = \frac{1}{2} \cdot 1 + 2 \cdot \frac{1}{4} \cdot 2 = \frac{3}{2}$ 。したがって
$C = \frac{11}{4} - \frac{3}{4} lo g_{2} 3 - \frac{3}{2} = \frac{5}{4} - \frac{3}{4} lo g_{2} 3 \approx 0.0613 ビット .$
検算（別の方法）: 消失確率 $\frac{1}{4}$ の消失通信路と、残りの $\frac{3}{4}$ で誤り確率 $\frac{1/4}{3/4} = \frac{1}{3}$ の 2 元対称通信路を合成したものとみなせるので、 $C = \frac{3}{4} (1 - h (\frac{1}{3}))$ 。 $h (\frac{1}{3}) = lo g_{2} 3 - \frac{2}{3}$ なので $C = \frac{3}{4} (\frac{5}{3} - lo g_{2} 3) = \frac{5}{4} - \frac{3}{4} lo g_{2} 3$ で一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題