通話路容量とは

/情報理論

通話路容量とは

通話路容量とは、通話路の能力を表す量で、1秒当たりのビット数で表されます。通話路容量は、通話路の情報伝達速度の最大値となります。

情報伝達速度 $R$(ビット/秒)は、情報量の平均($H$)を平均伝送時間($T$)で割って求められます。

$$R=\frac{H}{T}$$

ある通話路を信号{$A_1,A_2,\cdots,A_n$}が次々流れるとし、1つの信号 $A_i$ の発生確率を $p_i$、その信号を送るのに掛かる時間を $t_i$ 秒とします。このとき、1つの信号を送るのに掛かる時間の平均($T$)は以下で求められ、

$$T=\sum_ip_it_i  -①$$

1信号当たりの情報量($H$)は以下で求められます。

$$H=-\sum_ip_i\log_2{p_i}  -②$$

通話路容量を求める

通話路容量は、情報伝達速度の最大値であり、

$$C=\mathrm{max}\:R(\cdots p_i\cdots)=R(\cdots \hat{p}_i\cdots)$$

以下の方程式の正の根として求めることができます。

$$\sum_i2^{-Ct_i}=1  -③$$

また、信号が以下の確率で発生する場合、最大の速度で伝送することができます。

$$\hat{p}_i=2^{-Ct_i}$$

導出

これは以下の条件下で、

$$\sum_ip_i=1  -④$$

情報伝達速度 $R$ を最大にする確率 $\hat{p}_i$ を求める問題であるため、これをラグランジュ乗数法を使って解きます。以下の関数を定義して、

$$L\equiv R-\lambda\sum_ip_i$$

これが停留点をもつ条件を求めます。

$$\frac{\partial L}{\partial p_i}=0$$

これは、情報伝達速度の定義から以下のように書き換えられます。

$$\frac{1}{T}\frac{\partial H}{\partial p_i}-\frac{H}{T^2}\frac{\partial T}{\partial p_i}-\lambda=0$$$$\frac{1}{T}\Big(-\log_2{p_i}-\frac{1}{\ln{2}}\Big)-\frac{H}{T^2}t_i-\lambda=0  -⑤$$

ここで、$p_i$ を掛けて $i$ で和を取り、①②④を使うと以下になります。

$$-\frac{1}{T\ln{2}}-\lambda=0$$

これを⑤に代入すると、

$$\log_2{p_i}=-Rt_i$$

$\hat{p}_i$ で情報伝達速度 $R$ が最大(通話路容量:$C$)なるとすると、

$$\log_2{\hat{p}_i}=-Ct_i$$$$\hat{p}_i=2^{-Ct_i}$$

ここで④の条件を考えると、③が導かれます。

 

応用数学
情報理論、暗号理論、機械学習、金融工学、ゲーム理論
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

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