シャノンの通信路符号化定理
正しくない系列Xが受信系列Yと同時典型である場合、誤りが発生する可能性がある。
符号の構成がランダムであることから、符号全体で平均した平均誤り率は、送信されたメッセージ番号に依存しないと仮定できる。従って、一般性を失うことなく、 W = 1 と仮定して良い。
同時AEPから、n を大きくすると、同時典型な X が存在しない確率は0に近付く。この誤り率は、上界として ε {\displaystyle \varepsilon } に限定できる。
また、同時AEPから、ある特定の X 1 n ( i ) {\displaystyle X_{1}^{n}(i)} とメッセージW = 1 から得られた Y 1 n {\displaystyle Y_{1}^{n}} とが同時典型である確率は ≤ 2 − n ( I ( X ; Y ) − 3 ε ) {\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}} である。
メッセージ1が送信されたときの受信系列と、メッセージiとが同時典型である事象として、次のように事象 E i {\displaystyle E_{i}} を定義する。
定義: E i = { ( X 1 n ( i ) , Y 1 n ) ∈ A ε ( n ) } , i = 1 , 2 , ... , 2 n R {\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}
定理 (Shannon, 1948):
1. 任意の無記憶通信路について、通信路容量
C = sup p X I ( X ; Y ) {\displaystyle \ C=\sup _{p_{X}}I(X;Y)}
は次の特性を持つ。任意の ε > 0 および R < C について、N が充分に大きい場合、ブロックエラーの最大確率が ≤ ε となるような、長さ N 、レート ≥ R の符号と復号アルゴリズムが存在する。
2. ビットの誤り率 pb が許容可能である場合、 R(pb) までのレートが達成可能である。ここで、
R ( p b ) = C 1 − H 2 ( p b ) {\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}}
であり、 H 2 ( p b ) {\displaystyle H_{2}(p_{b})} は二値エントロピー関数で、
H 2 ( p b ) = − [ p b log 2  p b + ( 1 − p b ) log 2  ( 1 − p b ) ] {\displaystyle H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]}
である。
3. 任意の pb について、 R(pb) より大きいレートは達成できない。