シャノンの定理とは
シャノンの定理とは、誤りの生じる（雑音のある）通話路であっても、誤りのない情報の伝送速度を、通話路容量に近づけられることを示した定理です。
通話路の容量を $C$ 、情報伝達速度を $R$ とすると、任意に小さい誤り確率 $\epsilon$ で送れる符号化が存在することを示しています。
$$R=C-\epsilon , \epsilon\gt0$$
シャノンの定理を簡単に導く
通信路の入力側につながれた情報源の１秒当たりのエントロピーを $H(X)$、送信信号の不確定度を表すエントロピーを $H_Y(X)$ とした場合、情報伝達速度 $R$ は以下で表されます。尚、$H_Y(X)$ は情報の「あいまい度」と呼ばれています。
$$R=H(X)-H_Y(X)$$
文字の種類が $k$、文字数が $N$ の文字系列のエントロピーを $H=\log_2{k}$ とすると、文字列の総数は以下になります。
$$k^N=2^{HN}$$
これより、送信信号（入力）の文字列の総数は $2^{H(X)N}$ となります。この中から確実に送信できるのは、情報伝達速度分である $2^{RN}$ と言うことができ、その確率は、
$$\frac{2^{RN}}{2^{H(X)N}}=2^{[R-H(X)]N}=2^{-H_Y(X)N} -①$$
そうでない確率は次のように表されます。
$$1-2^{-H_Y(X)N} -②$$
１つの受信信号に対する送信信号（文字数列）の候補の数は、情報のあいまい度 $H_Y(X)$ により $2^{H_Y(X)N}$ となります。この中に１つだけ①の確率で現れる文字数列があればよいので、そうでない（２つ以上現れる）確率 $P$ は②により以下で表されます。
$$P=(1-2^{-H_Y(X)N})^{2^{H_Y(X)N}-1}$$
この確率 $P$ は、２つの異なる送信信号に対して、同じ受信信号が発生してしまう確率になります。
ここで、が十分に長い文字数列（$N\gg1$）を仮定とすると、$2^{-H_Y(X)N}\ll1$ より、テイラー展開することができて、
$$P\cong 1-2^{-H_Y(X)N}\cdot 2^{H_Y(X)N}=0$$
これにより文字数列を長く取ることにより、１つの送信信号に対し１つの受信信号を対応させることができる、つまり雑音による影響を限りなく小さくできることが分かります。
