シャノンの雑音のある通信路符号化定理

**逆方向（$R > C \Rightarrow P_e \not\to 0$）。** ファノの不等式は、雑音のある出力が与えられたときの受信者のメッセージに関する残存不確実性を次のように抑える：$H(X\mid Y) \le 1 + P_e \log_2(n-1)$、ここで $n$ は可能なメッセージ数である。一方、通信路のデータ処理構造により各使用ごとに $I(X;Y) \le C$ が強制されるため、$N$ 回の通信路使用のブロック全体で受信者が抽出できる情報は高々 $NC$ ビットである。真のレートが $R > C$（1使用あたり）であれば、メッセージは $NR$ ビットのエントロピーを持つが、通信路はそのうち約 $NC < NR$ ビットしか提供しない。ファノの不等式は、$N$ が大きくなっても $P_e$ が $0$ から離れたままであることを強制する。なぜなら残存不確実性 $H(X\mid Y)$ を消し去ることができないからである。

**達成可能性の概略（$R < C \Rightarrow P_e \to 0$）。** 容量を達成する入力分布 $p(x)$ を固定し、長さ $N$ の符号語 $2^{NR}$ 個を $p(x)^N$ から独立にランダムに生成して符号帳を作る。復号の際、受信者は受信系列と同時典型的（統計的パターンが真の入力・出力対のように振る舞う）である唯一の符号語を探す。$R < C$ であるため、候補符号語の数（$2^{NR}$）は統計的に区別可能な通信路出力の数（$\approx 2^{NC}$）よりはるかに少なく、$N \to \infty$ のとき、送信されていない他の符号語が偶然受信系列と同時典型的に見える確率は $0$ に縮小し、復号誤り確率も、符号帳のランダムな選択について平均すると同様に縮小する — したがって、任意に小さい $P_e$ を達成する符号帳が少なくとも1つ存在するはずである。