通話路容量とは - 理数の散策路

通話路容量
導出

通話路容量

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

$C = \max R (\dots p_{i} \dots) = R (\dots {\hat{p}}_{i} \dots)$

ある通話路を信号｛ $A_{1}, A_{2}, \dots, A_{n}$ ｝が次々流れるとし、１つの信号 $A_{i}$ の発生確率を $p_{i}$ 、その信号を送るのに掛かる時間を $t_{i}$ 秒とすると、通話路容量は以下の方程式の正の根として求めることができます。

$\sum_{i} 2^{- C t_{i}} = 1 - ①$

言い替えると、信号が以下の確率 ${\hat{p}}_{i}$ で発生する場合、最大の速度で伝送することができます。

${\hat{p}}_{i} = 2^{- C t_{i}} - ②$

また、通話路を通ることのできる信号系列のうちで、長さが $T$ 秒以内のものの総数を $N (T)$ とすると、通話路容量は以下で表すことができます。

$C = lim_{T \to \infty} \frac{\log_{2} N (T)}{T} - ③$

尚、雑音のない通話路の場合、情報伝達速度 $R$ （ビット/秒）は、１信号当たりの情報量 $H$ を、１信号を送るのに掛かる時間の平均 $T$ （平均伝送時間）で割って求められます。

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

$T = \sum_{i} p_{i} t_{i} - ④$ $H = - \sum_{i} p_{i} \log_{2} p_{i} - ⑤$

導出

①②を導く

これは以下の条件下で、

$\sum_{i} p_{i} = 1 - ⑥$

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

$L \equiv R - λ \sum_{i} p_{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}} - λ = 0$ $\frac{1}{T} (- \log_{2} p_{i} - \frac{1}{\ln 2}) - \frac{H}{T^{2}} t_{i} - λ = 0 - (1)$

ここで、 $p_{i}$ を掛けて $i$ で和を取り、④⑤⑥を使うと以下になります。

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

これを (1) に代入すると、

$\log_{2} p_{i} = - R t_{i}$

${\hat{p}}_{i}$ で情報伝達速度 $R$ が最大（通話路容量： $C$ ）なるとすると、②が導かれます。

$\log_{2} {\hat{p}}_{i} = - C t_{i}$ ${\hat{p}}_{i} = 2^{- C t_{i}} - ②$

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

$\sum_{i} 2^{- C t_{i}} = 1 - ①$

③を導く

長さが $T$ 秒以内の信号系列の最後の信号が $A_{i}$ とした場合、この $A_{i}$ を取り除いたときの信号系列の長さは $T - t_{i}$ 以内であり、その総数は $N (T - t_{i})$ であるとします。最後の信号の数を $m$ とすると、 $N (T)$ と $N (T - t_{i})$ の関係は以下で表されます。