シャノンの通信路符号化定理
2 − n ( H ( Y ) + ε ) ≤ p ( Y 1 n ) ≤ 2 − n ( H ( Y ) − ε ) {\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}
2 − n ( H ( X , Y ) + ε ) ≤ p ( X 1 n , Y 1 n ) ≤ 2 − n ( H ( X , Y ) − ε ) } {\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}
2つの系列 X 1 n {\displaystyle {X_{1}^{n}}} と Y 1 n {\displaystyle Y_{1}^{n}} が上記で定義した同時典型集合の中にある場合、これらは同時典型(jointly typical)であるという。
ステップ
ランダム符号化の論法では、確率分布 Q から長さ n の符号語を 2 n R {\displaystyle 2^{nR}} 個ランダムに生成する。
この符号は送信者と受信者に公開される。