シャノンの通信路符号化定理
ウォルフォウィッツ(Wolfowitz)が1957年に証明した強逆定理(strong converse theorem)では、任意の有限の正の定数 A {\displaystyle A} について、
P e ≥ 1 − 4 A n ( R − C ) 2 − e − n ( R − C ) 2 {\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}
であることを示している。弱逆定理では、 n {\displaystyle n} を無限大に持って行くと、誤り率が0より大きな下界を持つことしか示していないのに対し、強逆定理では誤り率が1に近付くことを示している。このように、 C {\displaystyle C} は、完全に信頼できる通信とまったく信頼できない通信とをはっきりと分ける境界点になっている。
この達成可能性の証明は、漸近的等分配性(英語版)(AEP)を利用する証明のスタイルに従う。他のスタイルとして、誤り指数(英語版)を用いる情報理論の教科書もある。
どちらのタイプの証明でも、通信路を通じて使用される符号表がランダムに構成されているランダム符号化の論法を使う。これを用いることで解析が簡単になるが、それでもなお、通信路容量以下の任意のデータレートにおいて、誤り率が望むままに小さい符号が存在することを証明できる。
AEP関連の議論により、与えられた通信路について、長さ n {\displaystyle n} の情報源シンボル系列を X 1 n {\displaystyle X_{1}^{n}} 、長さ n {\displaystyle n} の通信路出力系列を Y 1 n {\displaystyle Y_{1}^{n}} とするとき、同時典型集合(jointly typical set)を以下のように定義できる。
A ε ( n ) = { ( x n , y n ) ∈ X n × Y n {\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}
2 − n ( H ( X ) + ε ) ≤ p ( X 1 n ) ≤ 2 − n ( H ( X ) − ε ) {\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}
情報理論において、シャノンの通信路符号化定理(シャノンのつうしんろふごうかていり、英語: noisy-channel coding theorem)とは、通信路の雑音のレベルがどのように与えられたとしても、その通信路を介して計算上の最大値までほぼエラーのない離散データ(デジタル情報)を送信することが可能であるという定理である。この定理は、1948年にクロード・シャノンによって発表されたが、これはハリー・ナイキストとラルフ・ハートレーの初期の仕事とアイデアに一部基づいていた。シャノンの第一基本定理(情報源符号化定理)に対してシャノンの第二基本定理とも言い、単にシャノンの定理とも言う。
上記の「計算上の最大値」を通信路容量(またはシャノン限界、シャノン容量とも)といい、特定の雑音レベルについて、通信路の理論上の最大情報転送速度である。