シャノンの通信路符号化定理
情報理論における他のいくつかの主要な結果と同様に、雑音のある通信路符号化定理の証明は、達成可能性の結果と、対応する逆定理の結果を含む。ここでの場合、これらの2つの構成要素は、雑音のある通信路を介して通信する際に可能なデータレートの集合の有界性を示す役割を果たし、また対応する逆定理は、これらの上下界がタイトであることを示している。
以下の概要は、情報理論の教科書で学習できる様々な証明スタイルのうちの一例に過ぎない。
通信路は無記憶であると仮定しているが、その遷移確率は送信者および受信者において既知の方法で離散時刻 i と共に変化する。
通信路容量は、
C = lim inf max p ( X 1 ) , p ( X 2 ) , . . . 1 n ∑ i = 1 n I ( X i ; Y i ) {\displaystyle C=\lim \inf \max _{p^{(}X_{1}),p^{(}X_{2}),...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})}
により与えられる。
最大値は、それぞれの通信路において通信路容量に達する確率分布において得られる。つまり、 C i {\displaystyle C_{i}} を時刻 i の通信路の通信路容量とすると、 C = lim inf 1 n ∑ i = 1 n C i {\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}} である。
下極限( lim inf {\displaystyle \lim \inf } )の部分は、 1 n ∑ i = 1 n C i {\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}} が収束しない場合に機能する。