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

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

$2$ つの通信路を縦続接続した次の通信路を考える。

第 $1$ 段：入力 $X \in {0, 1}$ を受け取り、確率 $\frac{3}{4}$ でそのまま、確率 $\frac{1}{4}$ で反転した値 $Z \in {0, 1}$ を出力する（2 元対称通信路）。
第 $2$ 段： $Z$ を受け取り、確率 $\frac{2}{3}$ で $Y = Z$ をそのまま出力し、確率 $\frac{1}{3}$ で消失記号 $Y = e$ を出力する（2 元消失通信路）。

第 $2$ 段で消失が起こるかどうかは、 $X$ や第 $1$ 段の反転とは独立に決まるものとする。入力 $X$ から出力 $Y \in {0, 1, e}$ までを $1$ つの離散無記憶通信路とみなしたとき、その通信路容量 $C = P_{X} max I (X; Y)$ を求めよ。ただし、エントロピーと相互情報量の対数の底は $2$ とする（単位はビット）。

この問題で使うもの

離散無記憶通信路の通信路容量（説明と入口の問題）
2 元対称通信路の通信路容量（説明と入口の問題）
エントロピー（説明と入口の問題）
同時エントロピーと条件付きエントロピー（説明と入口の問題）
相互情報量（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず $X$ から $Y$ への遷移確率を求めましょう。 $P (X = 0) = a$ とおき、 $I (X; Y) = H (Y) - H (Y ∣ X)$ を計算します。

ヒント 2

「消失か否か」と「消失しなかったときの値」に分けて、エントロピーのグループ化を使いましょう。 $H (Y) = h (1/3) + \frac{2}{3} h (r)$ （ $r = P (Z = 0)$ ）となります。

ヒント 3

$I (X; Y) = \frac{2}{3} (h (r) - h (1/4))$ となるので、 $r = \frac{1}{2}$ のとき最大です。あとは $h (1/4)$ を $lo g_{2} 3$ で表しましょう。

答えと解説

答えを見る

\frac{1}{2} lo g_{2} 3 - \frac{2}{3}

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

解説を読む

2 値エントロピー関数を $h (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$ $(0 \leq t \leq 1)$ と書く。入力分布を $P (X = 0) = a, P (X = 1) = 1 - a$ $(0 \leq a \leq 1)$ とおく。

$X$ から $Y$ への遷移確率 消失は確率 $\frac{1}{3}$ で、 $X$ や反転とは独立に起こる。消失しないとき（確率 $\frac{2}{3}$ ）、 $Y$ は $Z$ に等しい。よって
$P (Y = x ∣ X = x) = \frac{2}{3} \cdot \frac{3}{4} = \frac{1}{2}, P (Y = 1 - x ∣ X = x) = \frac{2}{3} \cdot \frac{1}{4} = \frac{1}{6}, P (Y = e ∣ X = x) = \frac{1}{3} .$

条件付きエントロピー $X = x$ を固定すると、 $Y$ が消失かどうかで $2$ 段階に分けられる。まず「消失か否か」が確率 $\frac{1}{3}, \frac{2}{3}$ で決まり、消失しなかったときは確率 $\frac{3}{4}, \frac{1}{4}$ で $x, 1 - x$ になる。エントロピーのグループ化（連鎖律）により
$H (Y ∣ X = x) = h (\frac{1}{3}) + \frac{2}{3} h (\frac{1}{4})$
で、これは $x$ によらない。したがって $H (Y ∣ X) = h (\frac{1}{3}) + \frac{2}{3} h (\frac{1}{4})$ 。

出力のエントロピー $r = P (Z = 0) = \frac{3}{4} a + \frac{1}{4} (1 - a)$ とおくと、
$P (Y = e) = \frac{1}{3}, P (Y = 0) = \frac{2}{3} r, P (Y = 1) = \frac{2}{3} (1 - r) .$
同じくグループ化により
$H (Y) = h (\frac{1}{3}) + \frac{2}{3} h (r) .$

相互情報量
$I (X; Y) = H (Y) - H (Y ∣ X) = \frac{2}{3} (h (r) - h (\frac{1}{4})) .$
$h (r) \leq 1$ で、等号は $r = \frac{1}{2}$ のときに成り立つ。 $r = \frac{1}{4} + \frac{1}{2} a$ なので、 $r = \frac{1}{2}$ となるのは $a = \frac{1}{2}$ （一様入力）のときである。よって
$C = \frac{2}{3} (1 - h (\frac{1}{4})) .$

$h (1/4)$ の計算
$h (\frac{1}{4}) = \frac{1}{4} lo g_{2} 4 + \frac{3}{4} lo g_{2} \frac{4}{3} = \frac{1}{2} + \frac{3}{4} (2 - lo g_{2} 3) = 2 - \frac{3}{4} lo g_{2} 3.$
したがって
$C = \frac{2}{3} (\frac{3}{4} lo g_{2} 3 - 1) = \frac{1}{2} lo g_{2} 3 - \frac{2}{3} (\approx 0.126 ビット) .$

（参考：これは、2 元対称通信路の容量 $1 - h (\frac{1}{4})$ に、消失しない確率 $\frac{2}{3}$ を掛けた値になっている。）

別解

第 2 段の消失は $X$ や第 1 段の反転と独立なので、全体の通信路は次のように読める。確率 $\frac{2}{3}$ で $Z$ がそのまま出力され、確率 $\frac{1}{3}$ で消失記号 $e$ が出力される。

消失が起こったかどうかは $Y$ から分かる。この事象を $E$ とすると、 $E$ は $X$ と独立である。したがって
$I (X; Y) = I (X; E) + I (X; Y ∣ E) = 0 + \frac{2}{3} I (X; Z) + \frac{1}{3} \cdot 0 = \frac{2}{3} I (X; Z)$ 。

$I (X; Z)$ は 2 元対称通信路（誤り確率 $\frac{1}{4}$ ）の相互情報量である。その最大値は一様入力 $P_{X} = (\frac{1}{2}, \frac{1}{2})$ で達成され、 $1 - h (\frac{1}{4})$ に等しい。この入力は $I (X; Z)$ の最大化を与えるので、 $I (X; Y)$ の最大化も与える。

$h (\frac{1}{4}) = - \frac{1}{4} lo g_{2} \frac{1}{4} - \frac{3}{4} lo g_{2} \frac{3}{4} = \frac{1}{2} + \frac{3}{4} (2 - lo g_{2} 3) = 2 - \frac{3}{4} lo g_{2} 3$ 。

よって $1 - h (\frac{1}{4}) = \frac{3}{4} lo g_{2} 3 - 1$ であり、
$C = \frac{2}{3} (\frac{3}{4} lo g_{2} 3 - 1) = \frac{1}{2} lo g_{2} 3 - \frac{2}{3} \approx 0.1258$ ビット。

検算： $h (\frac{1}{4}) \approx 0.8113$ なので $\frac{2}{3} (1 - 0.8113) = \frac{2}{3} \times 0.1887 \approx 0.1258$ となり、上の値と一致する。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる