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

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

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

入力アルファベット ${0, 1}$ 、出力アルファベット ${0, 1, 2}$ の離散無記憶通信路を考える。入力 $X$ に対して、 $X$ と独立な雑音 $Z$ が $P (Z = 0) = P (Z = 1) = \frac{1}{2}$ で生じ、出力は通常の整数の和
$Y = X + Z$
で与えられる。入力分布を $P (X = 1) = q$ $(0 \leq q \leq 1)$ とする。この通信路の通信路容量 $C = max_{P_{X}} I (X; Y)$ を求めよ。ただし、対数の底は $2$ とし、単位はビットとする。

この問題で使うもの

離散無記憶通信路の通信路容量（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「離散無記憶通信路の通信路容量」の技能を使う。入力分布 $P (X = 1) = q$ とおき、 $I (X; Y) = H (Y) - H (Y ∣ X)$ を $q$ の関数で表して最大化する。

ヒント 2

$X$ がどちらの値でも $Y$ は $2$ 通りの値を確率 $\frac{1}{2}$ ずつとるので $H (Y ∣ X)$ は $q$ によらない。 $Y$ の分布は $P (Y = 0) = \frac{1 - q}{2}$ , $P (Y = 1) = \frac{1}{2}$ , $P (Y = 2) = \frac{q}{2}$ 。

ヒント 3

$H (Y ∣ X) = 1$ , $H (Y) = 1 + \frac{1}{2} h (q)$ となるので $I (X; Y) = \frac{1}{2} h (q)$ 。これを $q$ で微分し、 $h^{'} (q) = lo g_{2} \frac{1 - q}{q}$ の符号を調べる。

答えと解説

答えを見る

\frac{1}{2}

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

解説を読む

方針 $I (X; Y) = H (Y) - H (Y ∣ X)$ を $q$ の関数として表し、 $q$ で微分して最大値を求める。

手順 1：通信路行列 $Y = X + Z$ より
$P (Y = 0 ∣ X = 0) = P (Y = 1 ∣ X = 0) = \frac{1}{2}, P (Y = 1 ∣ X = 1) = P (Y = 2 ∣ X = 1) = \frac{1}{2}$
であり、それ以外の条件付き確率は $0$ である。

手順 2： $H (Y ∣ X)$ $X = 0$ のときも $X = 1$ のときも、 $Y$ は $2$ つの値を確率 $\frac{1}{2}$ ずつとるので $H (Y ∣ X = x) = 1$ である。よって
$H (Y ∣ X) = (1 - q) \cdot 1 + q \cdot 1 = 1.$

手順 3： $H (Y)$ 出力の分布は
$P (Y = 0) = \frac{1 - q}{2}, P (Y = 1) = \frac{1 - q}{2} + \frac{q}{2} = \frac{1}{2}, P (Y = 2) = \frac{q}{2} .$
したがって
$H (Y) = - \frac{1 - q}{2} lo g_{2} \frac{1 - q}{2} - \frac{1}{2} lo g_{2} \frac{1}{2} - \frac{q}{2} lo g_{2} \frac{q}{2} .$
$lo g_{2} \frac{1 - q}{2} = lo g_{2} (1 - q) - 1$ , $lo g_{2} \frac{q}{2} = lo g_{2} q - 1$ を使うと
$H (Y) = \frac{1 - q}{2} + \frac{1}{2} + \frac{q}{2} - \frac{1}{2} {(1 - q) lo g_{2} (1 - q) + q lo g_{2} q} = 1 + \frac{1}{2} h (q) .$
ここで $h (q) = - q lo g_{2} q - (1 - q) lo g_{2} (1 - q)$ である。

手順 4： $I (X; Y)$
$f (q) = I (X; Y) = H (Y) - H (Y ∣ X) = \frac{1}{2} h (q) .$

手順 5：微分して最大化 $0 < q < 1$ で
$h^{'} (q) = - lo g_{2} q - \frac{1}{lo g 2} + lo g_{2} (1 - q) + \frac{1}{lo g 2} = lo g_{2} \frac{1 - q}{q}$
なので $f^{'} (q) = \frac{1}{2} lo g_{2} \frac{1 - q}{q}$ である。 $0 < q < \frac{1}{2}$ では $\frac{1 - q}{q} > 1$ より $f^{'} (q) > 0$ 、 $\frac{1}{2} < q < 1$ では $f^{'} (q) < 0$ となる。よって $f (q)$ は $q = \frac{1}{2}$ で最大となる（端点 $q = 0, 1$ では $f = 0$ ）。
$C = f (\frac{1}{2}) = \frac{1}{2} h (\frac{1}{2}) = \frac{1}{2} \cdot 1 = \frac{1}{2} .$

（参考：出力 $Y = 1$ は入力について何も教えない「消失」と同じ役割をしており、この通信路は消失確率 $\frac{1}{2}$ の消失通信路と同じで、 $C = 1 - \frac{1}{2}$ と一致する。）

答え： $C = \frac{1}{2}$ ビット

別解

入力 $X = 0$ のとき $Y \in {0, 1}$ 、 $X = 1$ のとき $Y \in {1, 2}$ で、それぞれ確率 $1/2$ ずつである。

出力分布は $P (Y = 0) = \frac{1 - q}{2}$ 、 $P (Y = 1) = \frac{1}{2}$ 、 $P (Y = 2) = \frac{q}{2}$ となる。

出力エントロピーは
$H (Y) = - \frac{1 - q}{2} lo g_{2} \frac{1 - q}{2} - \frac{1}{2} lo g_{2} \frac{1}{2} - \frac{q}{2} lo g_{2} \frac{q}{2}$
$= \frac{1}{2} + \frac{1 - q}{2} + \frac{q}{2} + \frac{1}{2} h (q) = 1 + \frac{1}{2} h (q)$ 。
ここで $h (q) = - q lo g_{2} q - (1 - q) lo g_{2} (1 - q)$ は 2 値エントロピー関数である。

条件付きエントロピーは、どの $X$ に対しても $Z$ が一様なので $H (Y ∣ X) = H (Z) = 1$ である。

よって $I (X; Y) = H (Y) - H (Y ∣ X) = \frac{1}{2} h (q)$ 。これは $q = \frac{1}{2}$ で最大値 $\frac{1}{2}$ をとる。

検算： $q = 1/2$ のとき $Y$ の分布は $(1/4, 1/2, 1/4)$ で $H (Y) = 1.5$ 、 $I = 1.5 - 1 = 0.5$ となり一致する。

したがって $C = \frac{1}{2}$ ビットである。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題