シャノンの通信路定理とは

/情報・暗号

シャノンの定理とは

シャノンの定理とは、誤りの生じる(雑音のある)通話路であっても、誤りのない情報の伝送速度を、通話路容量に近づけられることを示した定理です。

通話路の容量を $C$ 、情報伝達速度を $R$ とすると、任意に小さい誤り確率 $\epsilon$ で送れる符号化が存在することを示しています。

$$R=C-\epsilon  ,  \epsilon\gt0$$

シャノンの定理を簡単に導く

通信路の入力側につながれた情報源の1秒当たりのエントロピーを $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}  -②$$

1つの受信信号に対する送信信号(文字数列)の候補の数は、情報のあいまい度 $H_Y(X)$ により $2^{H_Y(X)N}$ となります。この中に1つだけ①の確率で現れる文字数列があればよいので、そうでない(2つ以上現れる)確率 $P$ は②により以下で表されます。

$$P=(1-2^{-H_Y(X)N})^{2^{H_Y(X)N}-1}$$

この確率 $P$ は、2つの異なる送信信号に対して、同じ受信信号が発生してしまう確率になります。

ここで、が十分に長い文字数列($N\gg1$)を仮定とすると、$2^{-H_Y(X)N}\ll1$ より、テイラー展開することができて、

$$P\cong 1-2^{-H_Y(X)N}\cdot 2^{H_Y(X)N}=0$$

これにより文字数列を長く取ることにより、1つの送信信号に対し1つの受信信号を対応させることができる、つまり雑音による影響を限りなく小さくできることが分かります。

 

数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

 

タイトルとURLをコピーしました