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

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

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

入力・出力のアルファベットがともに ${0, 1}$ で、ビット反転確率が $\frac{1}{4}$ の 2 元対称通信路（BSC）を考える。この通信路を 2 つ直列につなぎ、1 つ目の通信路の出力をそのまま 2 つ目の通信路の入力とする。2 つの通信路でのビット反転は互いに独立に起こるものとする。

1 つ目の通信路の入力 $X$ から 2 つ目の通信路の出力 $Z$ までを 1 つの通信路とみなしたとき、その通信路容量（1 回の使用あたり、単位はビット）を求めよ。ただし、対数の底は $2$ とする。

この問題で使うもの

2 元対称通信路の通信路容量（説明と入口の問題）
エントロピー（説明と入口の問題）
対数の定義と性質（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

2 つの BSC を直列につなぐと、全体もまた BSC になります。全体のビット反転確率を求めましょう。

ヒント 2

全体で反転が起こるのは、ちょうど一方の通信路で反転が起こるときです。BSC の容量は $C = 1 - h (p)$ です。

ヒント 3

全体のビット反転確率は $\frac{3}{8}$ です。 $h (\frac{3}{8})$ を $lo g_{2} 3, lo g_{2} 5$ で表しましょう。

答えと解説

答えを見る

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

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

解説を読む

1. 合成した通信路の遷移確率. $Z \neq = X$ となるのは、2 つの通信路のうちちょうど一方でビットが反転したときである（両方で反転すると元に戻る）。反転は独立なので
$P (Z \neq = X) = \frac{1}{4} \cdot \frac{3}{4} + \frac{3}{4} \cdot \frac{1}{4} = \frac{3}{8} .$
これは入力が $0$ でも $1$ でも同じなので、 $X$ から $Z$ への通信路はビット反転確率 $p = \frac{3}{8}$ の 2 元対称通信路である。

2. BSC の通信路容量. ビット反転確率 $p$ の BSC では
$I (X; Z) = H (Z) - H (Z ∣ X) = H (Z) - h (p) \leq 1 - h (p),$
ただし $h (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ 。等号は入力を一様分布にしたとき（このとき $Z$ も一様分布）に成り立つので、容量は $C = 1 - h (p)$ 。

3. 計算.
$h (\frac{3}{8}) = - \frac{3}{8} lo g_{2} \frac{3}{8} - \frac{5}{8} lo g_{2} \frac{5}{8} = - \frac{3}{8} (lo g_{2} 3 - 3) - \frac{5}{8} (lo g_{2} 5 - 3) = 3 - \frac{3}{8} lo g_{2} 3 - \frac{5}{8} lo g_{2} 5.$
よって
$C = 1 - h (\frac{3}{8}) = \frac{3}{8} lo g_{2} 3 + \frac{5}{8} lo g_{2} 5 - 2 (\approx 0.0456) .$
（1 つの BSC の容量 $1 - h (\frac{1}{4}) \approx 0.189$ より小さく、データ処理不等式と整合する。）

別解

2 つの BSC（反転確率 $p = \frac{1}{4}$ ）を直列につなぐと、 $X$ から $Z$ までは、ビットが反転するのは 2 回の反転のうちちょうど 1 回起こるときである。したがって実効的な反転確率は
$q = 2 p (1 - p) = 2 \cdot \frac{1}{4} \cdot \frac{3}{4} = \frac{3}{8} .$
これは反転確率 $q = \frac{3}{8}$ の BSC であり、容量は $C = 1 - h (q)$ （ $h$ は 2 値エントロピー関数）。
$h (\frac{3}{8}) = - \frac{3}{8} lo g_{2} \frac{3}{8} - \frac{5}{8} lo g_{2} \frac{5}{8} = - \frac{3}{8} (lo g_{2} 3 - 3) - \frac{5}{8} (lo g_{2} 5 - 3) = 3 - \frac{3}{8} lo g_{2} 3 - \frac{5}{8} lo g_{2} 5.$
よって
$C = 1 - h (\frac{3}{8}) = \frac{3}{8} lo g_{2} 3 + \frac{5}{8} lo g_{2} 5 - 2.$

検算: $lo g_{2} 3 \approx 1.58496$ , $lo g_{2} 5 \approx 2.32193$ より $0.375 \times 1.58496 + 0.625 \times 2.32193 \approx 0.59436 + 1.45121 = 2.04557$ 、 $C \approx 0.0456$ 。一方 $h (0.375) \approx 0.9544$ なので $1 - 0.9544 \approx 0.0456$ で一致する。なお 1 つの BSC の容量 $1 - h (1/4) \approx 0.189$ より小さく、データ処理不等式とも整合する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題