離散無記憶通信路の通信路容量

通信路行列から入力分布 $P (X = 1) = q$ の関数として $I (X; Y)$ を表し、微分して最大化することで $C = max_{P_{X}} I (X; Y)$ を求められる（消失通信路 $C = 1 - ε$ 、Z 通信路、消失と反転を含む通信路など）

前提

2 元対称通信路の通信路容量（大学数学情報理論・符号理論）
区間での最大・最小（数学II 微分法と積分法）

この技能までの道筋（75 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
エントロピー（大学数学情報理論・符号理論）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
重積分と累次積分（大学数学微分積分）
同時分布・周辺分布と独立性（大学数学確率・統計）
条件付き確率と乗法定理（数学A 場合の数と確率）
同時エントロピーと条件付きエントロピー（大学数学情報理論・符号理論）
相互情報量（大学数学情報理論・符号理論）
2 元対称通信路の通信路容量（大学数学情報理論・符号理論）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
区間での最大・最小（数学II 微分法と積分法）

説明

雑音のある通信路で、1 回の送信あたり最大で何ビットの情報を確実に送れるかを表す量が通信路容量 $C = max_{P_{X}} I (X; Y)$ です。入力が $0, 1$ の 2 値なら、入力分布は $q = P (X = 1)$ だけで決まります。そこで $I (X; Y)$ を $q$ の 1 変数関数として書き、区間 $0 \leq q \leq 1$ で最大化すれば $C$ が求まります。2 元対称通信路のように対称でない Z 通信路や、消失と反転の両方が起こる通信路でも、同じ手順で計算できます。

なぜそうしてよいのか

出力 $Y$ が入力 $X$ に応じてどう決まるかは、通信路行列（第 $x$ 行・第 $y$ 列が $P (Y = y ∣ X = x)$ の表）で与えられます。これは通信路が決めるもので、送り手には変えられません。送り手が選べるのは入力分布 $P (X = 1) = q, P (X = 0) = 1 - q$ だけです。相互情報量を $I (X; Y) = H (Y) - H (Y ∣ X)$ と分けると、 $q$ への依存の仕方が見えてきます。 $H (Y ∣ X) = (1 - q) H (Y ∣ X = 0) + q H (Y ∣ X = 1)$ で、各行のエントロピー $H (Y ∣ X = x)$ は通信路だけで決まる定数です。したがって $H (Y ∣ X)$ は $q$ の 1 次式になります。一方、出力分布 $P (Y = y) = (1 - q) P (Y = y ∣ X = 0) + q P (Y = y ∣ X = 1)$ も $q$ の 1 次式なので、 $H (Y)$ はそれを代入して計算できます。

こうして $I (q)$ は閉区間 $[0, 1]$ 上の連続関数になります（ $0 lo g 0 = 0$ と約束します）。連続関数なので最大値が存在し、「区間での最大・最小」の方法で求められます。微分には 2 値エントロピー関数 $h (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$ の導関数を使います。 $(lo g_{2} t)^{'} = \frac{1}{t l o g 2}$ から定数項が打ち消し合い、 $0 < t < 1$ で $h^{'} (t) = lo g_{2} \frac{1 - t}{t}$ となります。

例として消失確率 $ε$ の消失通信路を考えます。入力はそのまま届くか、確率 $ε$ で記号 $e$ （消失）に変わります。このとき $P (Y = e) = ε, P (Y = 0) = (1 - ε) (1 - q), P (Y = 1) = (1 - ε) q$ です。よって $H (Y) = h (ε) + (1 - ε) h (q)$ 、 $H (Y ∣ X) = h (ε)$ となり、 $I (q) = (1 - ε) h (q)$ です。これは $q = \frac{1}{2}$ で最大になり、 $C = 1 - ε$ が得られます。2 元対称通信路の $C = 1 - h (p)$ も同じ枠組みに入ります。ただし一般の通信路では、最適な $q$ が $\frac{1}{2}$ になるとは限りません。

手順

入力分布を $P (X = 1) = q, P (X = 0) = 1 - q (0 \leq q \leq 1)$ とおき、通信路行列 $P (Y = y ∣ X = x)$ を書き出す。
出力分布を求める： $P (Y = y) = (1 - q) P (Y = y ∣ X = 0) + q P (Y = y ∣ X = 1)$ 。これを使って $H (Y)$ を $q$ の式にする。
条件付きエントロピーを、各行のエントロピーを重み付けして求める： $H (Y ∣ X) = (1 - q) H (Y ∣ X = 0) + q H (Y ∣ X = 1)$ 。
$I (q) = H (Y) - H (Y ∣ X)$ を作り、 $0 < q < 1$ で微分する。 $h^{'} (t) = lo g_{2} \frac{1 - t}{t}$ と合成関数の微分を使い、 $I^{'} (q) = 0$ となる $q$ を求める。
増減表を作り、極値と端点の値 $I (0), I (1)$ を比べる。その最大値が $C$ になる。

例題

入力・出力がともに ${0, 1}$ の Z 通信路を考える。入力 $0$ は必ず $0$ として届く。入力 $1$ は確率 $\frac{1}{2}$ で $1$ として届き、確率 $\frac{1}{2}$ で $0$ に変わる。この通信路の通信路容量 $C$ （単位はビット、対数の底は 2）を求めよ。

例題の解答

【手順1】 $P (X = 1) = q$ とおく。通信路行列は、第 1 行（入力 0）が $(1, 0)$ 、第 2 行（入力 1）が $(\frac{1}{2}, \frac{1}{2})$ である。
【手順2】 $P (Y = 1) = q \cdot \frac{1}{2} = \frac{q}{2}$ なので、 $H (Y) = h (\frac{q}{2})$ 。
【手順3】 $H (Y ∣ X = 0) = 0$ 、 $H (Y ∣ X = 1) = h (\frac{1}{2}) = 1$ である。よって $H (Y ∣ X) = (1 - q) \cdot 0 + q \cdot 1 = q$ 。
【手順4】 $I (q) = h (\frac{q}{2}) - q$ となる。 $0 < q < 1$ で微分すると
$I^{'} (q) = \frac{1}{2} lo g_{2} \frac{1 - \frac{q}{2}}{\frac{q}{2}} - 1 = \frac{1}{2} lo g_{2} \frac{2 - q}{q} - 1.$
$I^{'} (q) = 0$ とおくと $lo g_{2} \frac{2 - q}{q} = 2$ 、つまり $\frac{2 - q}{q} = 4$ なので $q = \frac{2}{5}$ 。
【手順5】 $\frac{2 - q}{q} = \frac{2}{q} - 1$ は $q$ について減少するので、 $I^{'} (q)$ も減少する。よって $0 < q < \frac{2}{5}$ で $I^{'} > 0$ 、 $\frac{2}{5} < q < 1$ で $I^{'} < 0$ となり、 $q = \frac{2}{5}$ で極大かつ最大になる。端点の値は $I (0) = h (0) - 0 = 0$ 、 $I (1) = h (\frac{1}{2}) - 1 = 0$ である。最大値を計算すると
$h (\frac{1}{5}) = \frac{1}{5} lo g_{2} 5 + \frac{4}{5} lo g_{2} \frac{5}{4} = lo g_{2} 5 - \frac{8}{5}$
なので、 $I (\frac{2}{5}) = lo g_{2} 5 - \frac{8}{5} - \frac{2}{5} = lo g_{2} 5 - 2 (\approx 0.322)$ 。これは端点の値 $0$ より大きい。
したがって $C = lo g_{2} 5 - 2$ 。

答え: $lo g_{2} 5 - 2$

よくある誤り

最適な入力はいつも $q = \frac{1}{2}$ だと決めつける誤り。正しくは、微分して最大点を求める。上の Z 通信路では $I (\frac{1}{2}) = h (\frac{1}{4}) - \frac{1}{2} \approx 0.311$ で、真の最大値 $lo g_{2} 5 - 2 \approx 0.322$ （ $q = \frac{2}{5}$ ）より小さい。
$H (Y ∣ X)$ を行のエントロピーそのもの（例: $h (\frac{1}{2}) = 1$ ）としてしまう誤り。正しくは入力確率で重み付けして $H (Y ∣ X) = (1 - q) H (Y ∣ X = 0) + q H (Y ∣ X = 1) = q$ とする。
合成関数の微分で内側の微分を落とす誤り。 $\frac{d}{d q} h (\frac{q}{2}) = lo g_{2} \frac{2 - q}{q}$ とすると $q = \frac{2}{3}$ という誤った値が出る。正しくは $\frac{d}{d q} h (\frac{q}{2}) = \frac{1}{2} h^{'} (\frac{q}{2}) = \frac{1}{2} lo g_{2} \frac{2 - q}{q}$ 。
底を混同する誤り。 $h^{'} (t) = lo g \frac{1 - t}{t}$ （自然対数）と、ビット単位の $- 1$ を同じ式に混ぜてしまう例がある。すると $\frac{2 - q}{q} = e^{2}$ となって $q$ がずれる。正しくは、底 2 で $h^{'} (t) = lo g_{2} \frac{1 - t}{t}$ と統一するか、全体を自然対数で書き直してから微分する。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

離散無記憶通信路の通信路容量

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題