2 元対称通信路の通信路容量

反転確率 $p$ の 2 元対称通信路の容量 $C = 1 - h (p)$ を求められる。直列につないだ通信路の実質の反転確率（例: $2 p (1 - p)$ ）を求め、その容量を計算できる

前提

相互情報量（大学数学情報理論・符号理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学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 元対称通信路とは、0 か 1 を送ると、確率 $1 - p$ で正しく届き、確率 $p$ で反転して届く通信路です。この技能を使うと、その通信路で 1 回の使用あたり最大何ビットの情報を送れるか（通信路容量）を $C = 1 - h (p)$ で求められます。さらに、雑音のある通信路を中継して何段もつないだときに、全体が 1 つの 2 元対称通信路と同じになることを利用して、その容量も計算できます。

なぜそうしてよいのか

入力を $X$ 、出力を $Y$ とします。通信路容量は、入力の分布（ $P (X = 1) = a$ の $a$ ）を自由に選んだときの相互情報量の最大値 $C = max_{a} I (X; Y)$ として定義します。ここで 2 値エントロピー関数を $h (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ （ $0 lo g_{2} 0 = 0$ とする）と定めます。これは確率 $p$ で起こる事象 1 つ分の「表か裏か」のエントロピーです。

$I (X; Y) = H (Y) - H (Y ∣ X)$ を使います。 $X = 0$ と分かっていれば、 $Y$ は確率 $1 - p$ で 0、確率 $p$ で 1 なので $H (Y ∣ X = 0) = h (p)$ です。 $X = 1$ のときも同様に $h (p)$ です。よって入力の分布によらず $H (Y ∣ X) = h (p)$ となり、 $I (X; Y) = H (Y) - h (p)$ が成り立ちます。 $Y$ は 2 値なので $H (Y) \leq 1$ です。 $a = \frac{1}{2}$ とすると、 $P (Y = 1) = a (1 - p) + (1 - a) p = \frac{1}{2}$ となって $H (Y) = 1$ が実現します。したがって最大値は $C = 1 - h (p)$ です。

反転確率 $p_{1}, p_{2}$ の通信路を、雑音が互いに独立な状態で直列につなぐ場合を考えます。最終的に反転するのは「1 段目だけ反転」か「2 段目だけ反転」のときで、2 回反転すると元に戻ります。よって全体の反転確率は $q = p_{1} (1 - p_{2}) + (1 - p_{1}) p_{2}$ です。この値は入力が 0 でも 1 でも同じなので、全体は反転確率 $q$ の 2 元対称通信路になり、その容量は $1 - h (q)$ です。同じ $p$ の 2 段なら $q = 2 p (1 - p)$ となります。

手順

通信路全体の反転確率 $q$ を決める。1 段ならそのまま $q = p$ とする。独立な 2 段の直列なら $q = p_{1} (1 - p_{2}) + (1 - p_{1}) p_{2}$ （同じ $p$ なら $2 p (1 - p)$ ）とする。
2 値エントロピー $h (q) = - q lo g_{2} q - (1 - q) lo g_{2} (1 - q)$ を計算する（底は問題の指定に従い、ことわりがなければ 2）。
容量を $C = 1 - h (q)$ で求める。単位は 1 回の使用あたりのビット。
必要なら、容量を実現する入力は $P (X = 0) = P (X = 1) = \frac{1}{2}$ であることを確認する。

例題

反転確率 $\frac{1}{4}$ の 2 元対称通信路を 2 つ、雑音が独立になるように直列につなぐ（1 段目の出力をそのまま 2 段目の入力にする）。全体の通信路容量（ビット）を求めよ。

例題の解答

手順 1: 全体が反転するのは、ちょうど一方の段だけが反転するときである。よって反転確率は $q = 2 \cdot \frac{1}{4} \cdot \frac{3}{4} = \frac{3}{8}$ となる。

手順 2: 次の式で $h (q)$ を計算する。
$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} (3 - lo g_{2} 3) + \frac{5}{8} (3 - lo g_{2} 5) = 3 - \frac{3}{8} lo g_{2} 3 - \frac{5}{8} lo g_{2} 5$

手順 3: 容量は次のとおりである。
$C = 1 - h (\frac{3}{8}) = \frac{3}{8} lo g_{2} 3 + \frac{5}{8} lo g_{2} 5 - 2 \approx 0.046$

手順 4: この容量は、入力を 0, 1 等確率にしたときに達成される。参考までに、1 段だけなら $1 - h (\frac{1}{4}) \approx 0.189$ であり、直列にすると大きく減ることが分かる。

答え: $\frac{3}{8} lo g_{2} 3 + \frac{5}{8} lo g_{2} 5 - 2$

よくある誤り

直列 2 段の反転確率を $p^{2}$ や $2 p$ としてしまう誤り。2 回反転すると元に戻り、反転確率は「ちょうど 1 回反転」する確率なので、正しくは $q = 2 p (1 - p)$ である（例: $p = \frac{1}{4}$ なら $\frac{3}{8}$ ）。
直列の容量を各段の容量の積 $C_{1} C_{2}$ や $min (C_{1}, C_{2})$ としてしまう誤り。正しくは、全体の反転確率 $q$ を求めてから $1 - h (q)$ を計算する。例えば $p = \frac{1}{4}$ を 2 段つなぐと $1 - h (\frac{3}{8}) \approx 0.046$ であり、 $min = 0.189$ にはならない。
容量を $1 - p$ としてしまう誤り。 $1 - p$ は消失通信路の容量の形である。2 元対称通信路では、どのビットが誤ったか受信側に分からないため、正しくは $C = 1 - h (p)$ となる（ $p = \frac{1}{4}$ で $0.75$ ではなく約 $0.189$ ）。
$p > \frac{1}{2}$ で容量が小さくなる、または負になると考える誤り。 $h (p) = h (1 - p)$ なので $C (p) = C (1 - p)$ であり、例えば $p = 1$ なら $C = 1$ である（受信側で全ビットを反転すればよい）。容量が 0 になるのは $p = \frac{1}{2}$ のときだけである。また、 $h$ の対数を自然対数で計算すると単位がナットになってしまい、 $1 - h$ の「1」（ $= lo g_{2} 2$ ）と単位が合わなくなる。

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

入口の問題

この技能を使う問題

この技能の次に学べること

離散無記憶通信路の通信路容量（大学数学情報理論・符号理論）